[Scip] update constraint

Tobias Achterberg achterberg at zib.de
Thu Jul 22 12:00:01 MEST 2010


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


More information about the Scip mailing list