Issue regarding lazy constraints addition

[Shuvomoy]

The current version of GLPKMathProgInterface 0.1.11 might have an issue regarding problem modification. In a Benders decomposition problem using JuMP, after the callback function adds a lazy constraint, the modified master problem is not solved correctly, and in the subsequent iterations same sets of constraints are added repeatedly. In the GLPK code I have attached, only

t+[-1.0,-4.0]'x <=-7.666666666666667

t+[1.0,4.0]'x <=-0.0

are valid Benders lazy constraints. But after both of them are added to the master problem, GLPK keeps adding t+[2.5,-0.5]'x <=-3.0

(a valid cut) and t+[1.0,4.0]'x <=-0.0

repeatedly and keeps giving suboptimal solution every time with minuscule improvement. After 9 iterations, it finally reaches the optimal, (where only 2 is needed). Note that I made the upper bound for the variables to be 10. Initially the upper-bounds were 1e6 and GLPK kept adding same constraints again and again for a long time until I stopped it!

Both CPLEX and Gurobi work properly irrespective of the upper-bound. If heuristic and cut are not turned off, then Gurobi and CPLEX apply their heuristic and cuts besides the added lazy constraints. In Gurobi, Heuristic and Cut can be turned off for the master problem model to get the Benders lazy constraints only, in CPLEX I could not find the option to turn them off.

I have attached all the codes and associated outputs in https://groups.google.com/forum/#!topic/julia-opt/qeJ39VCyyc0

[mlubin]

I looked into this and I'm reasonably convinced that this is a bug or "feature" of GLPK and not the Julia interface. It's not guaranteed even by Gurobi or CPLEX that after a lazy constraint is added, it will be respected by all future solutions. This particular case is quite strange though.

If you add the following debugging code inside of the callback:

    internal = getInternalModel(masterProblemModel)
    @show MathProgBase.numconstr(internal)
    @show full(MathProgBase.getconstrmatrix(internal))
    @show full(MathProgBase.getconstrLB(internal))
    @show full(MathProgBase.getconstrUB(internal))

With the small fix I just pushed to GLPKMathProgInterface, you'll see that first GLPK reports 1 constraint, then 2 constraints, then the constraints added seem to disappear and reappear on future iterations. I think any further investigation into this will require digging into the GLPK source code.

Anyway as a workaround, I would suggest not using lazy constraints with GLPK and instead solving the master IP to optimality and then adding cuts in a loop. It's a bit inconvenient but still not too difficult to structure your cut generation code so that it can be used either within a callback or inside a loop.

Any ideas @carlobaldassi?

[Shuvomoy]

Hi Miles,

Thanks for your response. Yes, the issue might be with the GLPK source code itself; according to the discussion on the following link

http://lists.gnu.org/archive/html/help-glpk/2007-01/msg00010.html

, GLPK model object cannot store the lazy constraints. This explains why the same constraints were being added repeatedly.

For the benders decomposition in consideration, it is quite easy to add the cuts in a loop. I was more interested to see how the solvers compare when lazy constraints are concerned. It would have been wonderful, if GLPK worked :-(

Best Regards, Shuvo

[mlubin]

That response may be out of date, GLPK now does explicitly support lazy constraints. It's quite possible though that the feature is not widely used and therefore not well tested.