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

I cannot attach the model as it exceeds the size limitation, but I will send it by email.

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

Note: See TracTickets for help on using tickets.