search

coin-or / python-mip

Python-MIP: collection of Python tools for the modeling and solution of Mixed-Integer Linear programs
Eclipse Public License 2.0
513 stars 88 forks source link

LazyConstraint based MIP yields incorrect optimum #331

Open ciderale opened 1 year ago

ciderale commented 1 year ago

Describe the bug Solving a MIP with lazy constraints yields a sub optimal solution. Yet, the solver reports the solution to be optimal.

My assumption is that adding all constraints (a) up-front, (b) as lazy constraints, or (c) using a lazy constraint generator should not affect the optimal of the solution. Is this assumption incorrect?

To Reproduce A minimal example with 1 continuous variable (the objective), 4 integer variables, and 2 constraint is provided. The problem is solved three times: (a) complete model, (b) lazy constraints, (c) using lazy constraint generator.

Solving the complete model yields the true optimal solution. Both lazy variants provide a sub-optimal solution. Variant (c) shows that both constraints are generated and added to the model in the first call to the lazy constraint generator.

Expected behavior Using (generated) lazy constraints should yield the same optimum as solving the complete model with all constraint provided up front.

Desktop (please complete the following information):

Example Program and Execution Log: lazy-minimal-example.py.txt lazy-minimal-example.log

sebheger commented 1 year ago

Most likely to be duplicate to #36

sebheger commented 1 year ago

@ciderale Thanks for reporting the issue. It is at the moment unlikely, that this bug will be fixed on cbc side soon.

ciderale commented 1 year ago

@sebheger Thank you for your quick response. Do you have an idea what the root cause could be?

Since #36 is already closed, do you think it is a duplicate of the example mentioned towards the last comments (after the issue was closed)? A comment in #274 mentions that some lazy constraint seem to be ignored, but a minimalistic examples was missing. That sounds related to this problem and I hoped that the above example is minimal enough to help finding the problem. Is there something more I could do?

sebheger commented 1 year ago

@ciderale Many thanks for the minimalistic example. I guess that will help also for future development/testing

aBBDnGus commented 1 year ago

Any updates on this bug?

tkralphs commented 1 year ago

It is at the moment unlikely, that this bug will be fixed on cbc side soon.

36 was addressed on the Cbc side because @h-g-s, who is a Cbc developer, got involved. If there are still issues, this needs to get reported to Cbc or it certainly won't be addressed. The Cbc developers are not generally monitoring python-mip for bug reports (although I try my best). If the python-mip team could refer these kind of issues to Cbc, that would be helpful.