CODEWITHSUNDEEP
pythonmathematical-optimizationpulp
xiaolingxiao
xiaolingxiao

Reputation: 4895

Integer linear programming program does not behave as expected

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)

Upvotes: 1

Views: 142

Answers (1)

sascha
sascha

Reputation: 33542

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

enter image description here

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.

Upvotes: 2

Related Questions