LazyConstraint based MIP yields incorrect optimum
Nobody has claimed this yet.
Assessment
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Newbie friendliness
- 30/100
Research direction
Start with the attached lazy-minimal-example.py.txt and compare its complete-model, lazy-constraint, and lazy-constraint-generator runs against the execution log. Trace the Python-MIP lazy-constraint handling with CBC; done means both lazy variants produce the same optimum as the complete model and report it correctly.
Written by the indexing model from the issue text.
Description
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):
- Operating System, version: macOS Monterey 12.4 (M1)
- Python version: 3.9.6
- Python-MIP version (we recommend you to test with the latest version): 1.14.2
- CBC built from coin-or/cbc/0713c30b8e5e2b2a8e1b804ee9d98087fc524530 (23.Nov 2022)
Example Program and Execution Log:
lazy-minimal-example.py.txt
lazy-minimal-example.log
- Dominant language
- Linear Programming
- Stars
- 601
- Forks
- 108
- PR merge metrics
- No merged PRs in 30d
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from coin-or/python-mip
-
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
coin-or/python-mip#428 · 2 comments ·
-
Difficulty 3/5 1-2 days Newbie friendliness 45/100
coin-or/python-mip#426 ·
-
Difficulty 4/5 3-5 days Newbie friendliness 45/100
coin-or/python-mip#425 · 1 comment ·
-
Difficulty 4/5 3-5 days Newbie friendliness 35/100
coin-or/python-mip#423 · 4 comments · 3 reactions ·
-
Difficulty 3/5 1-2 days Newbie friendliness 55/100
coin-or/python-mip#422 · 1 comment ·
All issues in coin-or/python-mip
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 75/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 75/100
nightscout/nocturne#1424 ·
-
A claim comment carrying the issue number is silently declined while the workflow reports success Openarea: repo bug perceived difficulty: 2
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 65/100
paritytech/zombienet-sdk#591 ·
-
bug
Difficulty 2/5 1-3 hours Newbie friendliness 75/100
mruangutai/harness#1897 ·