[Scip] Regenerating column that is at it's upper bound

[Luigi Malagò]

hi sebastian,
i'm using SCIP for this first time, and i'm developing a column generation +
branch and cut,
similar to the binpacking example, so maybe i cant really help you...
i have to understand lazy bounds too.. have you seen this?

http://scip.zib.de/doc/html/FAQ.html

*What are the lazy bounds for variables in SCIP and what do I need them for?
*

In many Branch-and-Price applications, you have binary variables, but you do
not want to impose upper bounds on these variables in the LP relaxation,
because the upper bound is implicitly enforced by the problem contraints,
anyway. If the upper bounds are explicitly added to the LP, they lead to
further dual variables, which may be hard to take into account in the
pricing problem.

There are two possibilities how to solve this problem. First, you could
change the binary variables to general integer variables, if this does not
change the problem. However, if you use special linear constraints like set
partitioning/packing/covering, you can only add binary variables to these
constraints.

In order to still allow the usage of these types of constraints in a
branch-and-price approach, the concept of lazy bounds was introduced in SCIP
2.0. For each variable, you can define lazy upper and lower bounds, i.e.
bounds, that are implicitly enforced by constraints in the problem. SCIP
adds variable bounds to the LP only if the bound is tighter than the
corresponding lazy bound. In order to use lazy bounds, you have to make
sure, however, that each feasible LP solution respects these bounds (even
non-optimal LP solutions).

For instance, if you have set partioning constraints in your problem, you
can define variables contained in these constraints as binary and set the
lazy upper bound to 1, which allows you to use the better propagation
methods of the setppc constraint handler compared to the linear constraint
handler without taking care about upper bounds on variables in the master.


regards,
luigi



On Tue, Aug 23, 2011 at 9:24 AM, Sebastian Ruther <
Sebastian.Ruther at uon.edu.au> wrote:

>  Hello,
>
> my branch and price algorithm regenerates a column. I don't think I have
> a bug or at least it is not an obvious one because I manually checked
> that the dual values are handled correctly in the pricing problem and
> that the column gets added to the master problem correctly. When I add a
> column I generate a binary variable and call SCIPchgVarUbLazy(scip, var,
> 1.0).
>
> The original variable is generated in iteration 10, the new one in 119.
> When it regenerates, the original column is at value 1 in the lp
> solution. So the tasks the new column wants to do are covered (set
> partitioning constraints in the master problem).
>
> When I'm debugging this I calculate the dual objective function by
> simply summing the dual values of the constraints (set partitioning and
> set packing constriants) or multiplying them by SCIPgetRhsLinear if the
> constraint is linear. I compare that to SCIPgetLPObjval(scip). With this
> I want to check if the master problem LP was solved to optimality. The
> two values are the same for all iterations up to iteration number 118,
> in which
> PrimalLP = 21315.000000000000
> DualLP =  21369.999999999985
> then in iteration 119, when the column gets regenerated, I have
> PrimalLP = 21528.094557189928
> DualLP = 21600.875760878880
> Note also that this is a different node than iteration 118.
> However none of the branching decisions affect this pricing problem (I
> have multiple pricing problems). In fact nothing is fixed in this
> pricing problem.
>
> Why are the PrimalLP and DualLP values not the same?
> Any ideas why I regenerate the column? How do lazy bounds work in scip?
>
> Regards,
> Sebastian
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20110823/a8c89053/attachment.html