CODEWITHSUNDEEP
pythonlinear-programming
user7831701
user7831701

Reputation:

Pulp Python LP - Wrong Solution

When I run the following code: 

from pulp import * 

x = pulp.LpVariable("x", 0, None , LpContinuous) 
y = pulp.LpVariable("y", 0, None , LpContinuous)
problem = pulp.LpProblem("A simple max problem", pulp.LpMinimize) 
problem += x + y, "The objective function" 
problem += x + 2*y == 2, "1st constraint"
problem += 2*x + 3*y == 2, "2nd constraint"
problem += x >= 0, "3rd constraint"
problem += y >= 0, "4th constraint"
problem += x + y == 1, "5th constraint"

problem.writeLP("WhiskasModel.lp")
problem.solve()

for variable in problem.variables():
    print variable.name, "=", variable.varValue

print value(problem.objective)

I get as output:

x = 0.0
y = 1.0
1.0

which is clearly wrong, since 2nd constraint is not satisfied. Now the situation is that the above problem does not have a solution. So I would expect from pulp to notify me something relevant ("Infeasible problem") or something like that. Instead, I suspect that it arbitrarily drops some of the constraints and works with the rest of them. Similarly in the following case:

x = pulp.LpVariable("x", 0, None , LpContinuous) 
y = pulp.LpVariable("y", 0, None , LpContinuous)
problem = pulp.LpProblem("A simple max problem", pulp.LpMinimize) 
problem += x + y, "The objective function" 
problem += x + 2*y == 2, "1st constraint"
problem += 2*x + 3*y == 20, "2nd constraint"
problem += x >= 0, "3rd constraint"
problem += y >= 0, "4th constraint"
problem += x + y == 1, "5th constraint"

problem.writeLP("WhiskasModel.lp")
problem.solve()

for variable in problem.variables():
    print variable.name, "=", variable.varValue

print value(problem.objective)

the ouput is 

x = 34.0
y = -16.0
18.0

i.e. the 4th constraint is now "dropped".

Anyone having any idea as how to solve this?

Upvotes: 1

Views: 1684

Answers (2)

TCamara
TCamara

Reputation: 179

As you already said: the important thing is to check if the mathematical optimization problem is feasible or not. Pulp includes this feature.

Include:

if (problem.status == -1):
     print("Your problem is infeasible!")

in your code and you will see that.

Upvotes: 1

Uvar
Uvar

Reputation: 3462

Your program will just try to solve itself, starting from the first constraint down.

Think of it from a linear algebra perspective, the augmented matrix is:

[ 1 2 | 2
  2 3 | 20
  1 1 | 1 ]

with further constraints that both variables should be >=0. Directly subtracting twice the first row from the second you will end up with:

[ 1 2  | 2
  0 -1 | 16
  .........]

In other words, to satisfy your first constraint, you FORCE your y variable to become -16, only possible solution. The x variable becomes 34 as consequence to solve the first line. All further constraints and the objective function do not matter anymore. This was the only possible solution.

What you want is for the system to warn you if the problem does not have a solution which satisfies all constraints. Currently this is not implemented in the package and seeing the Git, they do not plan to change this behavior, so if you want to be warned about infeasible problems, change packages.

If you don't want to change packages, you can see your problem was infeasible from the solution violating your constraints. You can write a block of code to throw a warning/exception yourself.

Upvotes: 0

Related Questions