coin-or / coin-or/python-mip

LazyConstraint based MIP yields incorrect optimum

Aperta
#331 6 commenti 0 reazioni 0 assegnatari Vedi su GitHub
bug cbc
Lingua principale
Linear Programming
Stelle
600
Fork
108
Metriche di merge delle PR
Nessuna PR unita negli ultimi 30g

Descrizione

**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)

Guida per i contributori

Nessuna guida per i contributori indicizzata per questo repository

Direzione di ricerca

Inizia con il file allegato lazy-minimal-example.py.txt e confronta le sue esecuzioni complete-model, lazy-constraint e lazy-constraint-generator con il log di esecuzione. Traccia la gestione dei lazy constraints di Python-MIP con CBC; il lavoro è completato quando entrambe le varianti lazy producono lo stesso ottimo del complete model e lo riportano correttamente.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Valutazione

Stack tecnologico
python
Ambito
tooling
Tipo di issue
Bug
Difficoltà
4/5
Tempo stimato
3-5 giorni
Stato di attività
Ferma
Chiarezza
Abbastanza chiara
Idoneità per principianti
30/100

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.