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

Wrong results #337

Open erelsgl opened 1 year ago

erelsgl commented 1 year ago

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

Additional context Note that the alternative solution was derived by solving the same problem but with a different order of variables.

issue17a.lp.txt