[Scip] update constraint

[Mattia Barbieri]

On 22 July 2010 12:00, Tobias Achterberg <achterberg at zib.de> wrote:

> Mattia Barbieri wrote:
>
>>    Please wait a second before you implement those hacks. There must be
>>    some conceptually clean solution, and this is what you should
>> implement.
>>
>>    Could you please explain a bit more in detail what you want to do?
>>    For example, what is the penalty function that should be used at the
>>    root node of the solving process, and how is this penalty function
>>    updated in local nodes?
>>
>> My problem is basically the same as the following "/Stabilized column
>> generation for highly degenerate multiple-depot vehicle scheduling
>> problems/ - Oukil, Amor, Desrosiers, Gueddari, 2006", except that in my
>> case the maximum number of vehicle leaving each depot is 1. No better
>> way to explain the problem of generate an update the penalty function
>> that read pages 824-828 of this article (I can send you the PDF, if you
>> ask me).
>>
>>
>>    The only thing that you can do when going to a more local node is to
>>    *restrict* the feasibile region of your problem. Everything else
>>    will result either in an error or a wrong answer to your problem. In
>>    particular, you cannot modify the objective function.
>>
>> I understood that I can't modify the objective function, so I tried to
>> create a dummy variable, linked with a constraint expressing the penalty
>> function. Adding such columns on the master problem will limit the
>> region of the dual, because they translate into more constraints in the
>> dual. Is this right?
>>
>
> Yes. But please note that you cannot use this trick to create arbitrary
> modifications in the objective function. You need to be sure that if the new
> variable had already been available at the root node, then it would not have
> changed the root LP solution.
>
> In other words: you always need to pretend that all variables of your
> problem already exist at the start of the solving process, even if they are
> not yet actually created. The only trick of branch-and-price is that you do
> not need to actually create a variable when you know that it will be zero in
> the optimal LP solution to the current node. If you later add a variable to
> the problem formulation and it turns out that by using this variable one
> could have improved (decreased for minimization problems) the objective
> value of an LP relaxation of a ancestor node, then you screwed up because
> the LP dual bounds of the ancestor nodes would not be valid.
>
> To say it again differently: you can only restrict primal feasible region
> of the LP relaxation and you must not extend it. Adding a column means to
> potentially extend the feasible region and is therefore, in principle, not
> allowed. The only reason why it can be allowed is because you know that this
> new variable would have been zero in the optimal solutions to the ancestor
> relaxations anyway and thus you can pretend that this variable was already
> available at the start of the optimization.
>
>
> So, please verify that this fundamental property is satisfied in your
> approach. If it is true, then we can discuss how to implement this in SCIP.
>
>
> Tobias
>

Ok, I think I understand the underlying theory, and not, in my approach the
feasible region of the LP might change, extending itself (due to the penalty
terms, which can change the direction of the objective function), so it is
not possible to work as I hoped. Or is SCIP able to handle this problem and
manage a region that might extend in time? So the questions are:

  1.- is there any way built-in in SCIP to easily manage the degenerancy of
a column-generation approach? In other words, is there a predefined way to
stabilize a generic CG problem?

  2.- if not, a possible solultion should be this: implement myself a
relaxator, which is called at each CG iteration. At this point, if dual
values provided by the LP relaxation at the current iteration are outside
the trust region, penalty will be applied, so the relaxator construct a
quite NEW problem and find a new bound. Otherwise if dual values are inside
the trust region, no penalty will be applied. Another probleme arises: we
have to guess the trust region at the beginning. It may happen that no new
variables (columns) are found by the slave problem (min path) because we are
too far from the trust region, and thus penalty terms are very high for the
dual variables provided at the current iteration. In this case, the
relaxator have to notice that no new columns have been found, but the trust
region is moving (hopefully towards the right position), and thus optimize.
It must not close the node because no new columns have been found. It close
the node only if no new columns have been found and the trust region has not
changed since last iteration (with an epsilon tolerance). How to do this in
a clean and hopefully efficient way?

    Thanks in advance

-- 
Mattia Barbieri
barbieri.mattia at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20100726/f3040caa/attachment.html