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

[Sebastian Ruther]

Hello,

yes I've seen that part. That's why I'm using the lazy bounds.

What I probably should have added is: In iteration 10 the negative reduced cost are around -700 and in iteration 119 they are -72. So I don't think it has to do with tolerances. 

Cheers,
Sebastian
________________________________________
From: scip-bounces at zib.de [scip-bounces at zib.de] on behalf of Luigi Malagò [luigi.malago at gmail.com]
Sent: 23 August 2011 21:02
To: scip at zib.de
Subject: Re: [Scip] Regenerating column that is at it's upper bound

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<mailto: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<mailto:Scip at zib.de>
http://listserv.zib.de/mailman/listinfo/scip