No dual bound when doing column generation

Question

I'm currently implementing column generation (variant of multi commodity flow). Note: i disabled presolving because i figured it would be easier for prototyping. In this scenario, the pricing works fine: the correct variables are added, constraints modified accordingly and so on - when no more variables are found during pricing, the primal bound given by SCIP prior to that round is the optimal objective value.

My problem is that the reported dual bound is "---" each iteration and SCIP doesn't recognise the solution as optimal.

I don't quite understand what happens internally, especially since the dual solutions SCIP is giving me during pricing (SCIPgetDualSolLinear()) are correct, one idea is that the objective function degenerates somehow.

The only relevant thing i could figure out is that it has something to do with presolving and marking constraints as modifiable.

If i don't mark constraints as modifiable, SCIP reports a proper dual bound, but pricing doesn't work because SCIPgetDualSolLinear() fails - My guess is that marking the constraint as modifiable kind of 'keeps it available for usage in pricing'? Anyway i wondered why the original constraint should be marked as modifiable, when variables are actually added to the constraints obtained from SCIPgetTransformedCons().

Whether presolving is on or off, not marking constraints as modifiable makes SCIP produce a dual bound but pricing fails as mentioned. The only exception to this: if i run the program with all variables already added and iff presolving is off, SCIPgetDualSolLinear() does not fail, even when the constraints are not marked as modifiable. In this case, a dual bound is also reported. I guess this supports the thought that the modifiable flag has something to do with 'preserving structure'.

I do hope this description was understandable and someone can point me in the right direction, i don't really have an idea on how to proceed.

Thanks

edit: i just tried setting the constraints obtained from SCIPgetTransformedCons() as modifiable, and not the original ones, but the results apparently stay the same.

edit2, additional info: I am reading in .lp files and use SCIPsetConsModifiable() during the call to activatePricerXyz(), but before calling activatePricer().

It sets it to SCIP_DIDNOTRUN at the start and to SCIP_SUCCESS if a variable was added, i just replicated what was done in the Binpacking example. — oldenj
– oldenj, Commented Feb 7, 2020 at 20:47
I looked into this more just now and changed it to always be SCIP_SUCCESS because the pricer can guarantee an optimal solution, now i am getting a dual bound after the last pricing run! Thank you for this hint ... i'll update this question if i have a definite solution. Also, i would greatly appreciate if you had time to elaborate what setting the constraint to modifiable actually does — oldenj
– oldenj, Commented Feb 7, 2020 at 21:04

oldenj · Accepted Answer · 2020-02-07 21:17:46Z

2

Well the solution, as most of the time, is reading the docs :)

In the usual case that the pricer either adds a new variable or ensures that there are no further variables with negative dual feasibility, the result pointer should be set to SCIP_SUCCESS. Only if the pricer aborts pricing without creating a new variable, but there might exist additional variables with negative dual feasibility, the result pointer should be set to SCIP_DIDNOTRUN. In this case, which sometimes is referred to as "early branching", the LP solution will not be used as a lower bound. The pricer can, however, store a valid lower bound in the lowerbound pointer.

In my case, the success pointer was set to SCIP_DIDNOTRUN even if the pricer could guarantee optimality.

answered Feb 7, 2020 at 21:17

oldenj

414 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

No dual bound when doing column generation

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related