Python integer linear programming program does not behave as expected

433 Views Asked by At

I have the following integer linear programming problem which assigns values as expected, but when I add certain constraints, the objective function seems to become vacuous. I am not sure what to make of it. I am using python to solve the problem.

Non Vacuous formulation

score12 = 1
score21 = -1
C       = 1000000

maximize  : (w12 - s12) * score12 + (w21 - s21) * score21

subject to:
            d12 = x2 - x1
            d21 = x1 - x2

            d12 - w12*C <= 0
            d21 - w21*C <= 0

            d12 + (1 - w12)*C > 0
            d21 + (1 - w21)*C > 0

            d12 + s12*C      >= 0
            d21 + s21*C      >= 0

            0 <= xi <= 1      , continuous
            0 <= wij, sij <= 1, integer

The objective function is as expected:

MAXIMIZE
-1*s_12 + 1*s_21 + 1*w_12 + -1*w_21 + 0

And the solution is as expected:

('d_12', '= ', 0.0)
('d_21', '= ', 0.0)
('s_12', '= ', 0.0)
('s_21', '= ', 1.0)
('w_12', '= ', 1.0)
('w_21', '= ', 0.0)
('x_1', '= ', 0.0)
('x_2', '= ', 0.0)

But when I add the following constraints, or just either one:

d12 - (1 - s12)*C < 0 
d21 - (1 - s21)*C < 0 

Python changes the objective function to:

MAXIMIZE
0*__dummy + False
SUBJECT TO
... omited

I'm not what to make of it, the solution becomes vacuous:

('__dummy', '= ', None)
('d_12', '= ', 0.0)
('d_21', '= ', 0.0)
('s_12', '= ', 1.0)
('s_21', '= ', 1.0)
('w_12', '= ', 1.0)
('w_21', '= ', 1.0)
('x_1', '= ', 0.0)
('x_2', '= ', 0.0)