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

Wrong Answer #125

Closed vang1ong7ang closed 3 years ago

vang1ong7ang commented 4 years ago

Describe the bug

Querying optimization results shows the wrong answer.

To Reproduce

the lp file:

\Problem name: 

Minimize
OBJROW: - var(22)
Subject To
constr(0):  var(0) + var(1) = 1
constr(1):  - var(0) + var(2) + var(3) = -0
constr(2):  - var(1) + var(4) + var(5) = -0
constr(3):  -10000 var(2) + 9000 var(5) - var(6) = -0
constr(4):  var(2) - var(5) - var(7) = -0
constr(5):  var(8) + var(9) = 1
constr(6):  - var(8) + var(10) + var(11) = -0
constr(7):  - var(9) + var(12) + var(13) = -0
constr(8):  - var(10) + var(13) - var(14) = -0
constr(9):  12000 var(10) -11000 var(13) - var(15) = -0
constr(10):  var(16) = 1
constr(11):  - var(16) + var(17) + var(18) + var(19) = -0
constr(12):  16777216 var(18) - var(20) = -0
constr(13):  16777216 var(19) - var(21) = -0
constr(14):  16777216 var(18) + 16777216 var(19) - var(22) = -0
constr(15):  var(7) + var(14) - var(20) = -0
constr(16):  var(6) + var(15) - var(21) = -0
Bounds
 0 <= var(0) <= 1
 0 <= var(1) <= 1
 0 <= var(2) <= 1
 0 <= var(3) <= 1
 0 <= var(4) <= 1
 0 <= var(5) <= 1
 var(6) Free
 var(7) Free
 0 <= var(8) <= 1
 0 <= var(9) <= 1
 0 <= var(10) <= 1
 0 <= var(11) <= 1
 0 <= var(12) <= 1
 0 <= var(13) <= 1
 var(14) Free
 var(15) Free
 0 <= var(16) <= 1
 0 <= var(17) <= 1
 0 <= var(18) <= 1
 0 <= var(19) <= 1
 var(20) Free
 var(21) Free
 var(22) Free
Integers
var(0) var(1) var(8) var(9) var(16) 
End

the python code to reproduce:

from mip import Model

m = Model()
m.read('data.lp')
status = m.optimize()
print(status)
for v in m.vars:
    print(v, ':', v.x)

the output:

Welcome to the CBC MILP Solver 
Version: Trunk
Build Date: May 28 2020 

Starting solution of the Linear programming relaxation problem using Dual Simplex

Coin0506I Presolve 5 (-12) rows, 6 (-17) columns and 16 (-30) elements
Clp0000I Optimal - objective value -2000
Coin0511I After Postsolve, objective -2000, infeasibilities - dual 0 (0), primal 0 (0)
Clp0032I Optimal objective -2000 - 5 iterations time 0.002, Presolve 0.00

Starting MIP optimization
maxSavedSolutions was changed from 0 to 10
Continuous objective value is -2000 - 0.00 seconds
Cgl0004I processed model has 6 rows, 8 columns (2 integer (2 of which binary)) and 18 elements
Coin3009W Conflict graph built in 0.000 seconds, density: 1.471%
Cgl0015I Clique Strengthening extended 0 cliques, 0 were dominated
Cbc0038I Initial state - 0 integers unsatisfied sum - 2.22045e-16
Cbc0038I Solution found of -2000
Cbc0038I Relaxing continuous gives -2000
Cbc0038I Before mini branch and bound, 2 integers at bound fixed and 5 continuous
Cbc0038I Mini branch and bound did not improve solution (0.00 seconds)
Cbc0038I After 0.00 seconds - Feasibility pump exiting with objective of -2000 - took 0.00 seconds
Cbc0012I Integer solution of -2000 found by feasibility pump after 0 iterations and 0 nodes (0.00 seconds)
Cbc0001I Search completed - best objective -2000, took 0 iterations and 0 nodes (0.00 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Cuts at root node changed objective from -2000 to -2000
Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Gomory was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Knapsack was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Clique was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
OddWheel was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
FlowCover was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
ZeroHalf was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Cgl0013I Postprocessed model is infeasible - possible tolerance issue - try without preprocessing
3 relaxed row infeasibilities - summing to 9002

Result - Optimal solution found

Objective value:                -2000.00000000
Enumerated nodes:               0
Total iterations:               0
Time (CPU seconds):             0.00
Time (Wallclock seconds):       0.00

Total time (CPU seconds):       0.00   (Wallclock seconds):       0.00

OptimizationStatus.OPTIMAL
var(22) : 2999.999999999998
var(0) : 1.0
var(1) : 0.0
var(2) : 0.0
var(3) : 1.0
var(4) : 1.0000000000000004
var(5) : -1.0000000000000002
var(6) : -9000.000000000004
var(7) : 1.0000000000000002
var(8) : 1.0
var(9) : 0.0
var(10) : 1.0
var(11) : 0.0
var(12) : 0.0
var(13) : 0.0
var(14) : -1.0000000000000002
var(15) : 12000.000000000002
var(16) : 1.0
var(17) : 0.9998211860656738
var(18) : 0.0
var(19) : 0.00017881393432617177
var(20) : 0.0
var(21) : 2999.999999999998

Expected behavior

expected objective value should be 2000, but when I follow the doc to read the optimized objective value from model.vars, the value is 3000

actually, the bounds 0 <= var(5) <= 1 is ignored by python-mip.

Desktop (please complete the following information):

Additional context Add any other context about the problem here.

vang1ong7ang commented 4 years ago

another case here:

\Problem name: 

Minimize
OBJROW: - var(3) - var(8)
Subject To
constr(0):  var(0) = 1
constr(1):  - var(0) + var(1) + var(2) = -0
constr(2):  -256 var(1) + 256 var(2) - var(3) = -0
constr(3):  256 var(1) -256 var(2) - var(4) = -0
constr(4):  var(5) = 1
constr(5):  - var(5) + var(6) + var(7) = -0
constr(6):  -256 var(6) + 256 var(7) - var(8) = -0
constr(7):  256 var(6) -256 var(7) - var(9) = -0
constr(8):  var(10) = 1
constr(9):  - var(10) + var(11) + var(12) = -0
constr(10):  - var(11) - var(13) = -0
constr(11):  10 var(11) - var(14) = -0
constr(12):  var(4) + var(13) >= -0
constr(13):  var(9) + var(14) >= -0
constr(14):  var(3) + var(8) >= -0
constr(15):  var(4) + var(13) >= -10000
constr(16):  var(9) + var(14) >= -0
constr(17):  var(3) + var(8) >= -0
Bounds
 0 <= var(0) <= 1
 0 <= var(1) <= 1
 0 <= var(2) <= 1
 var(3) Free
 var(4) Free
 0 <= var(5) <= 1
 0 <= var(6) <= 1
 0 <= var(7) <= 1
 var(8) Free
 var(9) Free
 0 <= var(10) <= 1
 0 <= var(11) <= 1
 0 <= var(12) <= 1
 var(13) Free
 var(14) Free
Integers
var(0) var(5) var(10) 
End

the output is:

var(0) : 1.0
var(1) : 0.55
var(2) : 0.45000000000000007
var(3) : -25.599999999999994
var(4) : 25.6
var(5) : 1.0
var(6) : 0.0
var(7) : 1.0
var(8) : 256.0
var(9) : -256.0
var(10) : 1.0
var(11) : 25.6
var(12) : -24.6
var(13) : -25.6
var(14) : 256.0

where var(11) doesn't follows 0 <= var(11) <= 1

h-g-s commented 4 years ago

hi @vang1ong7ang , I just tested with python mip 1.10 and the result seems correct now, could you check ?

vang1ong7ang commented 4 years ago

@h-g-s

yep, it is now correct and runs well.

thank you a lot for fix this.