Opened 11 years ago
Closed 10 years ago
#58 closed defect (fixed)
Cbc 2.2 reports model integer-infeasible, actually feasible
Reported by: | nowozin | Owned by: | somebody |
---|---|---|---|
Priority: | major | Component: | component1 |
Version: | Keywords: | ||
Cc: |
Description
Cbc 2.2 reports the attached model (submitted to the lp-solve mailing list for examination) as integer feasible:
Coin Cbc and Clp Solver version 2.20.00, build Sep 20 2008 command line - /opt/coin-cbc-2.2.0/bin/cbc out.mps At line 8 NAME At line 9 ROWS At line 2700 COLUMNS At line 137775 RHS At line 138113 BOUNDS At line 141138 ENDATA Problem no_name has 2689 rows, 4032 columns and 268128 elements Coin0008I no_name read with 0 errors Continuous objective value is 145980 - 0.15 seconds Perturbing problem by 0.001 % of 478.647 - largest nonzero change 0.00146329 (% 0.000305713) - largest zero change 0.000244159 0 Obj 145980 Primal inf 3349.78 (576) Primal infeasible - objective value 153640 Cgl0000I Cut generators found to be infeasible! Pre-processing says infeasible or unbounded Total time 0.73
I personally verified Cplex 9.1 also reports the model infeasible, whereas people report later versions of Cplex, Xpress MP and SCIP producing integer-feasible solutions.
Change History (6)
comment:1 Changed 11 years ago by nowozin
comment:2 Changed 11 years ago by nowozin
There may be a conversion issue (the original model was a lp-solve LP file, which I converted to MPS). I will look into that as soon as possible and clarify it here.
comment:3 Changed 11 years ago by nowozin
This is most likely a bug in Cbc 2.2 or Cgl.
The MPS file available at http://www.nowozin.net/test.zip produces a integer-feasible solution after 25,000 nodes with GLPK 4.27:
glpsol --mps test.mps lpx_read_mps: reading problem data from `test.mps'... lpx_read_mps: problem name not specified lpx_read_mps: 2690 rows, 4032 columns, 270144 non-zeros lpx_read_mps: 4032 integer columns, 2016 of which are binary lpx_read_mps: 141138 cards were read glp_simplex: original LP has 2690 rows, 4032 columns, 270144 non-zeros glp_simplex: presolved LP has 1681 rows, 3024 columns, 135072 non-zeros lpx_adv_basis: size of triangular part = 1681 0: objval = 0.000000000e+00 infeas = 1.000000000e+00 (0) 200: objval = 0.000000000e+00 infeas = 1.000000000e+00 (0) 400: objval = 4.968000000e+04 infeas = 4.858684576e-01 (0) 600: objval = 6.461333333e+04 infeas = 3.389731870e-01 (0) 800: objval = 8.531630966e+04 infeas = 1.502789781e-01 (0) 1000: objval = 9.835184102e+04 infeas = 6.772932409e-02 (0) 1200: objval = 1.007848246e+05 infeas = 4.777066272e-02 (0) 1400: objval = 1.036354949e+05 infeas = 3.453695403e-02 (0) 1600: objval = 1.058332710e+05 infeas = 1.789188085e-02 (0) 1800: objval = 1.050143791e+05 infeas = 9.124520507e-03 (0) 2000: objval = 1.053971785e+05 infeas = 4.370541393e-03 (0) 2200: objval = 1.060234909e+05 infeas = 2.644864612e-03 (0) 2400: objval = 1.061356559e+05 infeas = 5.741590605e-04 (0) 2551: objval = 1.059470340e+05 infeas = 2.332458220e-18 (0) * 2551: objval = 1.059470340e+05 infeas = 2.000479442e-13 (0) * 2600: objval = 1.051352657e+05 infeas = 2.574980160e-18 (0) * 2800: objval = 1.025373690e+05 infeas = 4.529709940e-16 (0) * 3000: objval = 1.006550013e+05 infeas = 1.366278924e-15 (0) * 3200: objval = 9.961699583e+04 infeas = 3.252606517e-19 (0) * 3400: objval = 9.933354845e+04 infeas = 5.684402872e-14 (0) * 3600: objval = 9.920301384e+04 infeas = 5.487061903e-18 (0) * 3800: objval = 9.912210407e+04 infeas = 4.380854403e-18 (0) * 3937: objval = 9.910482706e+04 infeas = 4.619415961e-12 (0) OPTIMAL SOLUTION FOUND Integer optimization begins... + 3937: mip = not found yet >= -inf (1; 0) + 3942: mip = not found yet >= 9.910482706e+04 (4; 0) + 3945: mip = not found yet >= 9.910482706e+04 (7; 0) + 3947: mip = not found yet >= 9.910482706e+04 (9; 0) ... + 25400: mip = not found yet >= 9.910482706e+04 (801; 0) + 25466: mip = not found yet >= 9.910482706e+04 (821; 0) + 25498: >>>>> 1.202200000e+05 >= 9.910482706e+04 17.6% (834; 0) + 25676: mip = 1.202200000e+05 >= 9.910482706e+04 17.6% (828; 17)
Whereas Cbc 2.2 run on the same file produces:
Coin Cbc and Clp Solver version 2.20.00, build Sep 20 2008 command line - /opt/coin-cbc-2.2.0/bin/cbc test.mps At line 8 NAME At line 9 ROWS At line 2700 COLUMNS At line 137775 RHS At line 138113 BOUNDS At line 141138 ENDATA Problem no_name has 2689 rows, 4032 columns and 268128 elements Coin0008I no_name read with 0 errors Continuous objective value is 145980 - 0.14 seconds Perturbing problem by 0.001 % of 478.647 - largest nonzero change 0.00146329 (% 0.000305713) - largest zero change 0.000244159 0 Obj 145980 Primal inf 3349.78 (576) Primal infeasible - objective value 153640 Cgl0000I Cut generators found to be infeasible! Pre-processing says infeasible or unbounded Total time 0.70
comment:4 Changed 11 years ago by asm4
both clp-1.06.00 and cplex-10.2 lp solver declare the LP relaxation infeasible. so its more likely an issue with lp tolerances
comment:5 Changed 11 years ago by nowozin
Andrew Makhorin pointed out on coin-discuss:
In your mps file some integer columns are not listed in the BOUNDS section. Glpk sets default lower and upper bounds of such columns to 0 and +inf, resp. However, the IBM OSL documentation says: "For non-integer variables, the default bounds on columns are 0 and +inf. For integer variables, the default bounds on columns are 0 and 1." AFAIK, Cbc uses the latter convention that explains why the results are different.
So solvers do interpret the MPS standard wrongly. Cbc and Cplex follow the standard strictly by interpreting non-bounded integer columns as being bounded [0;1] by default. Xpress MP, GLPK, and lp_solve assume default bounds of [0;inf] for integer columns.
I believe a proper workaround would be to add explicit bounds upon conversion of other formats to MPS, in GLPK and lp_solve. The necessary overhead would be quite small.
comment:6 Changed 10 years ago by forrest
- Resolution set to fixed
- Status changed from new to closed
Closing as explanation seems satisfactory
I cannot attach the model as it exceeds the size limitation, but I will send it by email.