[Cbc-tickets] [COIN-OR Branch-and-Cut MIP Solver] #58: Cbc 2.2 reports model integer-infeasible, actually feasible

[COIN-OR Branch-and-Cut MIP Solver]

#58: Cbc 2.2 reports model integer-infeasible, actually feasible
-------------------------+--------------------------------------------------
  Reporter:  nowozin     |       Owner:  somebody
      Type:  defect      |      Status:  new     
  Priority:  major       |   Milestone:          
 Component:  component1  |     Version:          
Resolution:              |    Keywords:          
-------------------------+--------------------------------------------------
Comment (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
 }}}

-- 
Ticket URL: <https://projects.coin-or.org/Cbc/ticket/58#comment:3>
COIN-OR Branch-and-Cut MIP Solver <http://projects.coin-or.org/Cbc>
An LP-based branch-and-cut MIP solver.