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
530 stars 92 forks source link

Solutions Are Incomplete, Nondeterministic #211

Closed coder0xff closed 2 years ago

coder0xff commented 2 years ago

Describe the bug The following model doesn't produce all optimal solutions.

\Problem name: 

Minimize
OBJROW: x7
Subject To
constr(0):  x0 + x1 - x2 -3 x3 + 2 x6 = 2
constr(1):  x1 + x2 + x3 + x5 + x6 = 1
constr(2):  -2 x1 -2 x2 + x4 -3 x6 = -2
constr(3):  x0 + x1 + x2 + x3 + x4 + x5 + x6 - x7 <= -0
constr(4):  x0 + x1 + x2 + x3 + x4 + x5 - x6 - x7 <= -0
constr(5):  x0 + x1 + x2 + x3 + x4 - x5 + x6 - x7 <= -0
constr(6):  x0 + x1 + x2 + x3 + x4 - x5 - x6 - x7 <= -0
constr(7):  x0 + x1 + x2 + x3 - x4 + x5 + x6 - x7 <= -0
constr(8):  x0 + x1 + x2 + x3 - x4 + x5 - x6 - x7 <= -0
constr(9):  x0 + x1 + x2 + x3 - x4 - x5 + x6 - x7 <= -0
constr(10):  x0 + x1 + x2 + x3 - x4 - x5 - x6 - x7 <= -0
constr(11):  x0 + x1 + x2 - x3 + x4 + x5 + x6 - x7 <= -0
constr(12):  x0 + x1 + x2 - x3 + x4 + x5 - x6 - x7 <= -0
constr(13):  x0 + x1 + x2 - x3 + x4 - x5 + x6 - x7 <= -0
constr(14):  x0 + x1 + x2 - x3 + x4 - x5 - x6 - x7 <= -0
constr(15):  x0 + x1 + x2 - x3 - x4 + x5 + x6 - x7 <= -0
constr(16):  x0 + x1 + x2 - x3 - x4 + x5 - x6 - x7 <= -0
constr(17):  x0 + x1 + x2 - x3 - x4 - x5 + x6 - x7 <= -0
constr(18):  x0 + x1 + x2 - x3 - x4 - x5 - x6 - x7 <= -0
constr(19):  x0 + x1 - x2 + x3 + x4 + x5 + x6 - x7 <= -0
constr(20):  x0 + x1 - x2 + x3 + x4 + x5 - x6 - x7 <= -0
constr(21):  x0 + x1 - x2 + x3 + x4 - x5 + x6 - x7 <= -0
constr(22):  x0 + x1 - x2 + x3 + x4 - x5 - x6 - x7 <= -0
constr(23):  x0 + x1 - x2 + x3 - x4 + x5 + x6 - x7 <= -0
constr(24):  x0 + x1 - x2 + x3 - x4 + x5 - x6 - x7 <= -0
constr(25):  x0 + x1 - x2 + x3 - x4 - x5 + x6 - x7 <= -0
constr(26):  x0 + x1 - x2 + x3 - x4 - x5 - x6 - x7 <= -0
constr(27):  x0 + x1 - x2 - x3 + x4 + x5 + x6 - x7 <= -0
constr(28):  x0 + x1 - x2 - x3 + x4 + x5 - x6 - x7 <= -0
constr(29):  x0 + x1 - x2 - x3 + x4 - x5 + x6 - x7 <= -0
constr(30):  x0 + x1 - x2 - x3 + x4 - x5 - x6 - x7 <= -0
constr(31):  x0 + x1 - x2 - x3 - x4 + x5 + x6 - x7 <= -0
constr(32):  x0 + x1 - x2 - x3 - x4 + x5 - x6 - x7 <= -0
constr(33):  x0 + x1 - x2 - x3 - x4 - x5 + x6 - x7 <= -0
constr(34):  x0 + x1 - x2 - x3 - x4 - x5 - x6 - x7 <= -0
constr(35):  x0 - x1 + x2 + x3 + x4 + x5 + x6 - x7 <= -0
constr(36):  x0 - x1 + x2 + x3 + x4 + x5 - x6 - x7 <= -0
constr(37):  x0 - x1 + x2 + x3 + x4 - x5 + x6 - x7 <= -0
constr(38):  x0 - x1 + x2 + x3 + x4 - x5 - x6 - x7 <= -0
constr(39):  x0 - x1 + x2 + x3 - x4 + x5 + x6 - x7 <= -0
constr(40):  x0 - x1 + x2 + x3 - x4 + x5 - x6 - x7 <= -0
constr(41):  x0 - x1 + x2 + x3 - x4 - x5 + x6 - x7 <= -0
constr(42):  x0 - x1 + x2 + x3 - x4 - x5 - x6 - x7 <= -0
constr(43):  x0 - x1 + x2 - x3 + x4 + x5 + x6 - x7 <= -0
constr(44):  x0 - x1 + x2 - x3 + x4 + x5 - x6 - x7 <= -0
constr(45):  x0 - x1 + x2 - x3 + x4 - x5 + x6 - x7 <= -0
constr(46):  x0 - x1 + x2 - x3 + x4 - x5 - x6 - x7 <= -0
constr(47):  x0 - x1 + x2 - x3 - x4 + x5 + x6 - x7 <= -0
constr(48):  x0 - x1 + x2 - x3 - x4 + x5 - x6 - x7 <= -0
constr(49):  x0 - x1 + x2 - x3 - x4 - x5 + x6 - x7 <= -0
constr(50):  x0 - x1 + x2 - x3 - x4 - x5 - x6 - x7 <= -0
constr(51):  x0 - x1 - x2 + x3 + x4 + x5 + x6 - x7 <= -0
constr(52):  x0 - x1 - x2 + x3 + x4 + x5 - x6 - x7 <= -0
constr(53):  x0 - x1 - x2 + x3 + x4 - x5 + x6 - x7 <= -0
constr(54):  x0 - x1 - x2 + x3 + x4 - x5 - x6 - x7 <= -0
constr(55):  x0 - x1 - x2 + x3 - x4 + x5 + x6 - x7 <= -0
constr(56):  x0 - x1 - x2 + x3 - x4 + x5 - x6 - x7 <= -0
constr(57):  x0 - x1 - x2 + x3 - x4 - x5 + x6 - x7 <= -0
constr(58):  x0 - x1 - x2 + x3 - x4 - x5 - x6 - x7 <= -0
constr(59):  x0 - x1 - x2 - x3 + x4 + x5 + x6 - x7 <= -0
constr(60):  x0 - x1 - x2 - x3 + x4 + x5 - x6 - x7 <= -0
constr(61):  x0 - x1 - x2 - x3 + x4 - x5 + x6 - x7 <= -0
constr(62):  x0 - x1 - x2 - x3 + x4 - x5 - x6 - x7 <= -0
constr(63):  x0 - x1 - x2 - x3 - x4 + x5 + x6 - x7 <= -0
constr(64):  x0 - x1 - x2 - x3 - x4 + x5 - x6 - x7 <= -0
constr(65):  x0 - x1 - x2 - x3 - x4 - x5 + x6 - x7 <= -0
constr(66):  x0 - x1 - x2 - x3 - x4 - x5 - x6 - x7 <= -0
constr(67):  - x0 + x1 + x2 + x3 + x4 + x5 + x6 - x7 <= -0
constr(68):  - x0 + x1 + x2 + x3 + x4 + x5 - x6 - x7 <= -0
constr(69):  - x0 + x1 + x2 + x3 + x4 - x5 + x6 - x7 <= -0
constr(70):  - x0 + x1 + x2 + x3 + x4 - x5 - x6 - x7 <= -0
constr(71):  - x0 + x1 + x2 + x3 - x4 + x5 + x6 - x7 <= -0
constr(72):  - x0 + x1 + x2 + x3 - x4 + x5 - x6 - x7 <= -0
constr(73):  - x0 + x1 + x2 + x3 - x4 - x5 + x6 - x7 <= -0
constr(74):  - x0 + x1 + x2 + x3 - x4 - x5 - x6 - x7 <= -0
constr(75):  - x0 + x1 + x2 - x3 + x4 + x5 + x6 - x7 <= -0
constr(76):  - x0 + x1 + x2 - x3 + x4 + x5 - x6 - x7 <= -0
constr(77):  - x0 + x1 + x2 - x3 + x4 - x5 + x6 - x7 <= -0
constr(78):  - x0 + x1 + x2 - x3 + x4 - x5 - x6 - x7 <= -0
constr(79):  - x0 + x1 + x2 - x3 - x4 + x5 + x6 - x7 <= -0
constr(80):  - x0 + x1 + x2 - x3 - x4 + x5 - x6 - x7 <= -0
constr(81):  - x0 + x1 + x2 - x3 - x4 - x5 + x6 - x7 <= -0
constr(82):  - x0 + x1 + x2 - x3 - x4 - x5 - x6 - x7 <= -0
constr(83):  - x0 + x1 - x2 + x3 + x4 + x5 + x6 - x7 <= -0
constr(84):  - x0 + x1 - x2 + x3 + x4 + x5 - x6 - x7 <= -0
constr(85):  - x0 + x1 - x2 + x3 + x4 - x5 + x6 - x7 <= -0
constr(86):  - x0 + x1 - x2 + x3 + x4 - x5 - x6 - x7 <= -0
constr(87):  - x0 + x1 - x2 + x3 - x4 + x5 + x6 - x7 <= -0
constr(88):  - x0 + x1 - x2 + x3 - x4 + x5 - x6 - x7 <= -0
constr(89):  - x0 + x1 - x2 + x3 - x4 - x5 + x6 - x7 <= -0
constr(90):  - x0 + x1 - x2 + x3 - x4 - x5 - x6 - x7 <= -0
constr(91):  - x0 + x1 - x2 - x3 + x4 + x5 + x6 - x7 <= -0
constr(92):  - x0 + x1 - x2 - x3 + x4 + x5 - x6 - x7 <= -0
constr(93):  - x0 + x1 - x2 - x3 + x4 - x5 + x6 - x7 <= -0
constr(94):  - x0 + x1 - x2 - x3 + x4 - x5 - x6 - x7 <= -0
constr(95):  - x0 + x1 - x2 - x3 - x4 + x5 + x6 - x7 <= -0
constr(96):  - x0 + x1 - x2 - x3 - x4 + x5 - x6 - x7 <= -0
constr(97):  - x0 + x1 - x2 - x3 - x4 - x5 + x6 - x7 <= -0
constr(98):  - x0 + x1 - x2 - x3 - x4 - x5 - x6 - x7 <= -0
constr(99):  - x0 - x1 + x2 + x3 + x4 + x5 + x6 - x7 <= -0
constr(100):  - x0 - x1 + x2 + x3 + x4 + x5 - x6 - x7 <= -0
constr(101):  - x0 - x1 + x2 + x3 + x4 - x5 + x6 - x7 <= -0
constr(102):  - x0 - x1 + x2 + x3 + x4 - x5 - x6 - x7 <= -0
constr(103):  - x0 - x1 + x2 + x3 - x4 + x5 + x6 - x7 <= -0
constr(104):  - x0 - x1 + x2 + x3 - x4 + x5 - x6 - x7 <= -0
constr(105):  - x0 - x1 + x2 + x3 - x4 - x5 + x6 - x7 <= -0
constr(106):  - x0 - x1 + x2 + x3 - x4 - x5 - x6 - x7 <= -0
constr(107):  - x0 - x1 + x2 - x3 + x4 + x5 + x6 - x7 <= -0
constr(108):  - x0 - x1 + x2 - x3 + x4 + x5 - x6 - x7 <= -0
constr(109):  - x0 - x1 + x2 - x3 + x4 - x5 + x6 - x7 <= -0
constr(110):  - x0 - x1 + x2 - x3 + x4 - x5 - x6 - x7 <= -0
constr(111):  - x0 - x1 + x2 - x3 - x4 + x5 + x6 - x7 <= -0
constr(112):  - x0 - x1 + x2 - x3 - x4 + x5 - x6 - x7 <= -0
constr(113):  - x0 - x1 + x2 - x3 - x4 - x5 + x6 - x7 <= -0
constr(114):  - x0 - x1 + x2 - x3 - x4 - x5 - x6 - x7 <= -0
constr(115):  - x0 - x1 - x2 + x3 + x4 + x5 + x6 - x7 <= -0
constr(116):  - x0 - x1 - x2 + x3 + x4 + x5 - x6 - x7 <= -0
constr(117):  - x0 - x1 - x2 + x3 + x4 - x5 + x6 - x7 <= -0
constr(118):  - x0 - x1 - x2 + x3 + x4 - x5 - x6 - x7 <= -0
constr(119):  - x0 - x1 - x2 + x3 - x4 + x5 + x6 - x7 <= -0
constr(120):  - x0 - x1 - x2 + x3 - x4 + x5 - x6 - x7 <= -0
constr(121):  - x0 - x1 - x2 + x3 - x4 - x5 + x6 - x7 <= -0
constr(122):  - x0 - x1 - x2 + x3 - x4 - x5 - x6 - x7 <= -0
constr(123):  - x0 - x1 - x2 - x3 + x4 + x5 + x6 - x7 <= -0
constr(124):  - x0 - x1 - x2 - x3 + x4 + x5 - x6 - x7 <= -0
constr(125):  - x0 - x1 - x2 - x3 + x4 - x5 + x6 - x7 <= -0
constr(126):  - x0 - x1 - x2 - x3 + x4 - x5 - x6 - x7 <= -0
constr(127):  - x0 - x1 - x2 - x3 - x4 + x5 + x6 - x7 <= -0
constr(128):  - x0 - x1 - x2 - x3 - x4 + x5 - x6 - x7 <= -0
constr(129):  - x0 - x1 - x2 - x3 - x4 - x5 + x6 - x7 <= -0
constr(130):  - x0 - x1 - x2 - x3 - x4 - x5 - x6 - x7 <= -0
Bounds
 x0 Free
 x1 Free
 x2 Free
 x3 Free
 x4 Free
 x5 Free
 x6 Free
Integers
x0 x1 x2 x3 x4 x5 x6 x7 
End

That solution that's produced is x4 = x6 = 1, and x0 = x1 = x2 = x3 = x5 = 0, resulting in x7 = 2 Another solution is x0 = x1 = 1, and x2 = x3 = x4 = x5 = x6 = 0, resulting in x7 = 2, but it does not appear in the solution pool

To Reproduce Load the above model and call optimize(). Check solution pool for both solutions given above. Only the first solution is seen.

Expected behavior Both solutions are seen.

Desktop (please complete the following information):

Additional context Add any other context about the problem here.

tuliotoffolo commented 2 years ago

There is a misunderstanding: Python-MIP will not return all optimal solutions.

Using default settings, both Gurobi and CBC will stop once a proven optimal solution is found. The solution pool will be formed by the solutions obtained during the search. Note that some of these solutions may be suboptimal.