Integer linear programming program does not behave as expected

Question

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)

the way I saw it is that: d12 - (1-s12)*C < 0 implies either: d12 = 0 and s12 = 0, or d12 = 1 and s12 = 0. d12 = 0 implies x2 = x1, d12 = 1 implies x2 = 1. But neither case contradicts the other constraints. In fact the vacuous solutionm, we see x2 = 0 — xiaolingxiao
– xiaolingxiao, Commented Oct 20, 2016 at 0:48

sascha · Accepted Answer · 2016-10-20 14:01:08Z

2

I did not analyze your constraints but here is some comment on what kind of problem there might be.

You are using this to define a constraint:

d12 - (1 - s12)*C < 0

In Linear Programming, there are only inequalities of the form <= and >= (== may be constructed by these; ignoring numerical difficulties); everything else is just not natural (not much sense in regards to the math)
pulp-or only defines the mentioned operators above; but not < and > link; scroll to bottom; also see next image from the docs

Pulp is not that robust about wrong usage of the library and usually and silently overwrites the objective when some badly formed constraint is added (This might be the case here). Maybe you will find some experiences like that in pulp's issue-tracker

Consider using the Constraint-class and not using overloaded-operators.

edited Oct 20, 2016 at 14:01

answered Oct 20, 2016 at 13:55

sascha

33.7k6 gold badges80 silver badges117 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Integer linear programming program does not behave as expected

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related