coin-or / coin-or/python-mip

LazyConstraint based MIP yields incorrect optimum

Open
#331 6 comments 0 reactions 0 assignees View on GitHub
bug cbc
Dominant language
Linear Programming
Stars
600
Forks
108
PR merge metrics
No merged PRs in 30d

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](https://github.com/coin-or/python-mip/files/10377597/lazy-minimal-example.py.txt)
[lazy-minimal-example.log](https://github.com/coin-or/python-mip/files/10377600/lazy-minimal-example.log)

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.