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

[Gerald Gamrath]

Hi Sebastian,

could you check the solution status of the LP by calling P()? Probably, 
LP solving was stopped due to the objective limit, which gives you a 
dual feasible solution (which is sufficient for pricing), but the primal 
solution might be not feasible. That could be a reason for the different 
primal/dual LP solution values.

Can you confirm that the upper bound on the variables is really enforced 
by your constraints? Unfortunately, lazy bounds do not work if the bound 
is only enforced by constraints and objective function together, e.g. if 
you have set covering constraints and a minimzation problem like in 
coloring or bin packing. What happens with the regenerated column? Does 
it get a nonzero value in the next LP iteration?

Please check these things and tell me, then we can investigate some more 
things.

Best,
Gerald

Am 23.08.2011 15:22, schrieb 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
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip