Wrong results
Nobody has claimed this yet.
Assessment
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Newbie friendliness
- 38/100
Research direction
Start by reproducing the result from the attached issue17b.lp.txt and issue17a.lp.txt files with Python-MIP 1.14.0, comparing the two variable orders. Inspect the model.write output and solver behavior around the reported integer solutions. Done means equivalent models return the correct optimum of 38122 consistently, regardless of variable order.
Written by the indexing model from the issue text.
Description
Describe the bug
I constructed an integer program modeling a number partitioning problem (partition a given set of numbers into two bins such that the largest bin sum is minimized), and the results are wrong.
To Reproduce
I attach the output of model.write in LP format:
issue17b.lp.txt
Minimize
OBJROW: 152 item00152_in_bin1 + 489 item00489_in_bin1 + 2178 item02178_in_bin1 + 2518 item02518_in_bin1 + 3212 item03212_in_bin1 + 3270 item03270_in_bin1 + 3410 item03410_in_bin1 + 4979 item04979_in_bin1 + 5984 item05984_in_bin1 + 7183 item07183_in_bin1
+ 7740 item07740_in_bin1 + 7862 item07862_in_bin1 + 8519 item08519_in_bin1 + 8798 item08798_in_bin1 + 9948 item09948_in_bin1
Subject To
constr(0): item00152_in_bin0 >= 0
constr(1): item00489_in_bin0 >= 0
constr(2): item02178_in_bin0 >= 0
constr(3): item02518_in_bin0 >= 0
constr(4): item03212_in_bin0 >= 0
constr(5): item03270_in_bin0 >= 0
constr(6): item03410_in_bin0 >= 0
constr(7): item04979_in_bin0 >= 0
constr(8): item05984_in_bin0 >= 0
constr(9): item07183_in_bin0 >= 0
constr(10): item07740_in_bin0 >= 0
constr(11): item07862_in_bin0 >= 0
constr(12): item08519_in_bin0 >= 0
constr(13): item08798_in_bin0 >= 0
constr(14): item09948_in_bin0 >= 0
constr(15): item00152_in_bin1 >= 0
constr(16): item00489_in_bin1 >= 0
constr(17): item02178_in_bin1 >= 0
constr(18): item02518_in_bin1 >= 0
constr(19): item03212_in_bin1 >= 0
constr(20): item03270_in_bin1 >= 0
constr(21): item03410_in_bin1 >= 0
constr(22): item04979_in_bin1 >= 0
constr(23): item05984_in_bin1 >= 0
constr(24): item07183_in_bin1 >= 0
constr(25): item07740_in_bin1 >= 0
constr(26): item07862_in_bin1 >= 0
constr(27): item08519_in_bin1 >= 0
constr(28): item08798_in_bin1 >= 0
constr(29): item09948_in_bin1 >= 0
constr(30): item00152_in_bin0 + item00152_in_bin1 = 1
constr(31): item00489_in_bin0 + item00489_in_bin1 = 1
constr(32): item02178_in_bin0 + item02178_in_bin1 = 1
constr(33): item02518_in_bin0 + item02518_in_bin1 = 1
constr(34): item03212_in_bin0 + item03212_in_bin1 = 1
constr(35): item03270_in_bin0 + item03270_in_bin1 = 1
constr(36): item03410_in_bin0 + item03410_in_bin1 = 1
constr(37): item04979_in_bin0 + item04979_in_bin1 = 1
constr(38): item05984_in_bin0 + item05984_in_bin1 = 1
constr(39): item07183_in_bin0 + item07183_in_bin1 = 1
constr(40): item07740_in_bin0 + item07740_in_bin1 = 1
constr(41): item07862_in_bin0 + item07862_in_bin1 = 1
constr(42): item08519_in_bin0 + item08519_in_bin1 = 1
constr(43): item08798_in_bin0 + item08798_in_bin1 = 1
constr(44): item09948_in_bin0 + item09948_in_bin1 = 1
constr(45): -152 item00152_in_bin0 + 152 item00152_in_bin1 -489 item00489_in_bin0 + 489 item00489_in_bin1 -2178 item02178_in_bin0 + 2178 item02178_in_bin1 -2518 item02518_in_bin0 + 2518 item02518_in_bin1 -3212 item03212_in_bin0 + 3212 item03212_in_bin1
-3270 item03270_in_bin0 + 3270 item03270_in_bin1 -3410 item03410_in_bin0 + 3410 item03410_in_bin1 -4979 item04979_in_bin0 + 4979 item04979_in_bin1 -5984 item05984_in_bin0 + 5984 item05984_in_bin1 -7183 item07183_in_bin0 + 7183 item07183_in_bin1
-7740 item07740_in_bin0 + 7740 item07740_in_bin1 -7862 item07862_in_bin0 + 7862 item07862_in_bin1 -8519 item08519_in_bin0 + 8519 item08519_in_bin1 -8798 item08798_in_bin0 + 8798 item08798_in_bin1 -9948 item09948_in_bin0 + 9948 item09948_in_bin1
>= -0
Bounds
Integers
item00152_in_bin0 item00152_in_bin1 item00489_in_bin0 item00489_in_bin1 item02178_in_bin0 item02178_in_bin1 item02518_in_bin0 item02518_in_bin1 item03212_in_bin0 item03212_in_bin1
item03270_in_bin0 item03270_in_bin1 item03410_in_bin0 item03410_in_bin1 item04979_in_bin0 item04979_in_bin1 item05984_in_bin0 item05984_in_bin1 item07183_in_bin0 item07183_in_bin1
item07740_in_bin0 item07740_in_bin1 item07862_in_bin0 item07862_in_bin1 item08519_in_bin0 item08519_in_bin1 item08798_in_bin0 item08798_in_bin1 item09948_in_bin0 item09948_in_bin1
End
Here is the solution I get, with value 38123:
item00152_in_bin0 = 0
item00489_in_bin0 = 0
item02178_in_bin0 = 0
item02518_in_bin0 = 1
item03212_in_bin0 = 0
item03270_in_bin0 = 0
item03410_in_bin0 = 1
item04979_in_bin0 = 0
item05984_in_bin0 = 1
item07183_in_bin0 = 0
item07740_in_bin0 = 1
item07862_in_bin0 = 0
item08519_in_bin0 = 1
item08798_in_bin0 = 0
item09948_in_bin0 = 1
item00152_in_bin1 = 1
item00489_in_bin1 = 1
item02178_in_bin1 = 1
item02518_in_bin1 = 0
item03212_in_bin1 = 1
item03270_in_bin1 = 1
item03410_in_bin1 = 0
item04979_in_bin1 = 1
item05984_in_bin1 = 0
item07183_in_bin1 = 1
item07740_in_bin1 = 0
item07862_in_bin1 = 1
item08519_in_bin1 = 0
item08798_in_bin1 = 1
item09948_in_bin1 = 0
Expected behavior
There is another solution, with value 38122:
item00152_in_bin0 = 1
item00489_in_bin0 = 1
item02178_in_bin0 = 0
item02518_in_bin0 = 0
item03212_in_bin0 = 0
item03270_in_bin0 = 0
item03410_in_bin0 = 1
item04979_in_bin0 = 0
item05984_in_bin0 = 0
item07183_in_bin0 = 0
item07740_in_bin0 = 1
item07862_in_bin0 = 1
item08519_in_bin0 = 1
item08798_in_bin0 = 0
item09948_in_bin0 = 1
item00152_in_bin1 = 0
item00489_in_bin1 = 0
item02178_in_bin1 = 1
item02518_in_bin1 = 1
item03212_in_bin1 = 1
item03270_in_bin1 = 1
item03410_in_bin1 = 0
item04979_in_bin1 = 1
item05984_in_bin1 = 1
item07183_in_bin1 = 1
item07740_in_bin1 = 0
item07862_in_bin1 = 0
item08519_in_bin1 = 0
item08798_in_bin1 = 1
item09948_in_bin1 = 0
Desktop (please complete the following information):
- Windows 11 22H2
- Python version: 3.10.2
- Python-MIP version (we recommend you to test with the latest version): 1.14.0
Additional context
Note that the alternative solution was derived by solving the same problem but with a different order of variables.
- Dominant language
- Linear Programming
- Stars
- 601
- Forks
- 108
- PR merge metrics
- No merged PRs in 30d
Getting set up
We have not checked this project's setup files yet. Start from its README, and see our first-contribution guide for the general steps.
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 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 ·
-
Difficulty 4/5 3-5 days Newbie friendliness 45/100
coin-or/python-mip#420 · 4 comments ·
All issues in coin-or/python-mip
Similar issues
-
Difficulty 2/5 Half a day Newbie friendliness 78/100
Maintainers usually reply within 1 day
-
needs-triage
Difficulty 1/5 Under an hour Newbie friendliness 90/100
JustJarethB/invoicer#54 ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
Maintainers usually reply within 1 day
-
good first issue
Difficulty 2/5 1-3 hours Newbie friendliness 88/100
Maintainers usually reply within 1 day
-
comp/tools P3 type/bug
Difficulty 2/5 1-3 hours Newbie friendliness 85/100
NousResearch/hermes-agent#126059 ·
Maintainers usually reply within 1 day