chibro2 - 8 months ago 32

Python 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)

Answer

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.

Source (Stackoverflow)