Bug: got Infeasible on obviously feasible problem

[etiennecallies]

Hi!

I think I discovered this bug on CBC using pulp: https://github.com/coin-or/pulp/issues/662

Here is my cbc version:

Version: 2.10.3
Build Date: Dec 15 2019

Here is the problem using Pulp framework:

    lp_problem = LpProblem('my_problem', LpMinimize)

    x_0 = LpVariable('x_0', lowBound=0, upBound=1, cat='Integer')
    x_1 = LpVariable('x_1', lowBound=0, upBound=1, cat='Integer')
    x_2 = LpVariable('x_2', lowBound=0, upBound=1, cat='Integer')
    c_0 = LpVariable('c_0', lowBound=0, upBound=1, cat='Integer')
    c_1 = LpVariable('c_1', lowBound=0, upBound=1, cat='Integer')

    # objective
    lp_problem += c_0 + c_1

    # constraints
    lp_problem += x_0 + c_1 == 1

    lp_problem += x_0 + c_0 >= 1
    lp_problem += x_1 + c_1 <= 1
    lp_problem += c_0 + c_1 <= 1

    lp_problem += x_2 == 1

    lp_problem += 9000 * x_1 + 7200 * x_2 + 10800 * c_1 >= 16200

    print(lp_problem)
    lp_problem.solve(PULP_CBC_CMD(msg=True))
    print(LpStatus[lp_problem.status])

It is indeed solvable if all x are 1 and c are 0. However I get Infeasible. As I said in the other issue, it is very weird since we just have to change a constraint to make it Optimal. For example with this little change:

# lp_problem += 9000 * x_1 + 7200 * x_2 + 10800 * c_1 >= 16200
lp_problem += 900 * x_1 + 720 * x_2 + 1080 * c_1 >= 1620

Here is the Pulp file:

\* my_problem *\
Minimize
OBJ: c_0 + c_1
Subject To
_C1: c_1 + x_0 = 1
_C2: c_0 + x_0 >= 1
_C3: c_1 + x_1 <= 1
_C4: c_0 + c_1 <= 1
_C5: 16200 c_1 + 7200 x_0 + 9000 x_1 >= 16200
Binaries
c_0
c_1
x_0
x_1
End

Here is the MPS file:

*SENSE:Minimize
NAME          my_problem
ROWS
 N  OBJ
 E  _C1
 G  _C2
 L  _C3
 L  _C4
 G  _C5
COLUMNS
    MARK      'MARKER'                 'INTORG'
    c_0       _C2        1.000000000000e+00
    c_0       _C4        1.000000000000e+00
    c_0       OBJ        1.000000000000e+00
    MARK      'MARKER'                 'INTEND'
    MARK      'MARKER'                 'INTORG'
    c_1       _C1        1.000000000000e+00
    c_1       _C3        1.000000000000e+00
    c_1       _C4        1.000000000000e+00
    c_1       _C5        1.620000000000e+04
    c_1       OBJ        1.000000000000e+00
    MARK      'MARKER'                 'INTEND'
    MARK      'MARKER'                 'INTORG'
    x_0       _C1        1.000000000000e+00
    x_0       _C2        1.000000000000e+00
    x_0       _C5        7.200000000000e+03
    MARK      'MARKER'                 'INTEND'
    MARK      'MARKER'                 'INTORG'
    x_1       _C3        1.000000000000e+00
    x_1       _C5        9.000000000000e+03
    MARK      'MARKER'                 'INTEND'
RHS
    RHS       _C1        1.000000000000e+00
    RHS       _C2        1.000000000000e+00
    RHS       _C3        1.000000000000e+00
    RHS       _C4        1.000000000000e+00
    RHS       _C5        1.620000000000e+04
BOUNDS
 BV BND       c_0     
 BV BND       c_1     
 BV BND       x_0     
 BV BND       x_1     
ENDATA

Here is the output:

At line 2 NAME          my_problem
At line 3 ROWS
At line 10 COLUMNS
At line 32 RHS
At line 38 BOUNDS
At line 43 ENDATA
Problem my_problem has 5 rows, 4 columns and 11 elements
Coin0008I my_problem read with 0 errors
Continuous objective value is 0 - 0.00 seconds
Cgl0000I Cut generators found to be infeasible! (or unbounded)
Pre-processing says infeasible or unbounded
Total time (CPU seconds):       0.00   (Wallclock seconds):       0.02

Thanks

[jjhforrest]

Odd. With my build of current stable there is no problem, but building release I get infeasible.

Will look into it

[jjhforrest]

It was lack of a tolerance in a test - which was stupid. Worked with some compiler options. Lower bound on an integer variable was computed to be 2.0210993372731735e-16 which is >0 so bound was set to 1! Should be fixed in stable.

[etiennecallies]

Thanks for your thorough examination @jjhforrest 👍🏻 I'll wait for the next release.