When I run this program in PuLP that is supposed to minimize the unconstrained gamma variable, I get infeasible. Notice the constraint signs are mixed ≤ and ≥. The gamma variable in the dictionaries represents a weight placed on the importance of that goal. But when I negate the constraints to make them all ≤, which should be the same thing, I get a solution. What am I missing here about how PuLP works?
My question is based on the fact that the goal 1, 2, 4, and 5 constraint inequalities should be mathematically the identical but the program solutions are different.
For example, goal 1 is initially written as x3 + x6 +16/6 gamma ≥ 1.
Then I negate it to be -x3 - x6 - 16/6 gamma ≤ -1 which is the same. Why does Pulp give two different solution?
import pulp as lp
# Define the problem
prob = lp.LpProblem("Annual_usage", lp.LpMinimize)
# Decision variables
# x_i is the project type
x = {
'X1': lp.LpVariable('x_1', lowBound=0, cat='Binary'),
'X2': lp.LpVariable('x_2', lowBound=0, cat='Binary'),
'X3': lp.LpVariable('x_3', lowBound=0, cat='Binary'),
'X4': lp.LpVariable('x_4', lowBound=0, cat='Binary'),
'X5': lp.LpVariable('x_5', lowBound=0, cat='Binary'),
'X6': lp.LpVariable('x_6', lowBound=0, cat='Binary'),
'X7': lp.LpVariable('x_7', lowBound=0, cat='Binary'),
'X8': lp.LpVariable('x_8', lowBound=0, cat='Binary'),
'gamma': lp.LpVariable('gamma', lowBound=None, cat='Continuous')
}
# Usage
usage = {
'X1': 4.7, 'X2': 12.5, 'X3': 3.2, 'X4': 7.5, 'X5': 41, 'X6': 47, 'X7': 23, 'X8': 16,
'gamma': 0
}
# Costs
cost = {
'X1': 75, 'X2': 180, 'X3': 350, 'X4': 45, 'X5': 120, 'X6': 80, 'X7': 115, 'X8': 210,
'gamma': 0
}
# Acreage
acreage = {
'X1': 7, 'X2': 12, 'X3': 20, 'X4': 6, 'X5': 3, 'X6': 25, 'X7': 5, 'X8': 8,
'gamma': 0
}
goal1 = { # at least 1 of X3 and X6
'X1': 0, 'X2': 0, 'X3': 1, 'X4': 0, 'X5': 0, 'X6': 1, 'X7': 0, 'X8': 0,
'gamma': 16/6
}
goal2 = { # at least 130
'X1': 4.7, 'X2': 12.5, 'X3': 3.2, 'X4': 7.5, 'X5': 41, 'X6': 47, 'X7': 23, 'X8': 16,
'gamma': 16/3
}
goal3 = { #sum is at most 7
'X1': 3, 'X2': 2, 'X3': 1, 'X4': 3, 'X5': 2, 'X6': 1, 'X7': 2, 'X8': 3,
'gamma': 16/2
}
goal4 = { #at least 495)
'X1': 75, 'X2': 180, 'X3': 350, 'X4': 45, 'X5': 120, 'X6': 80, 'X7': 115, 'X8': 210,
'gamma': 16
}
goal5 = { # sum is at least 5
'X1': 1, 'X2': 1, 'X3': 1, 'X4': 1, 'X5': 1, 'X6': 1, 'X7': 1, 'X8': 1,
'gamma': 4
}
gamma_objective = {
'X1': 0, 'X2': 0, 'X3': 0, 'X4': 0, 'X5': 0, 'X6': 0, 'X7': 0, 'X8': 0,
'gamma': 1
}
# Objective function
prob += lp.lpSum(gamma_objective[i] * x[i] for i in x)
# Constraints
prob += lp.lpSum(x[i] * goal1[i] for i in x) >= 1, "goal 1"
prob += lp.lpSum(x[i] * goal2[i] for i in x) >= 130, "goal 2"
prob += lp.lpSum(x[i] * goal3[i] for i in x) <= 7, "goal 3"
prob += lp.lpSum(x[i] * goal4[i] for i in x) >= 495, "goal 4"
prob += lp.lpSum(x[i] * goal5[i] for i in x) >= 5, "goal 5"
prob += lp.lpSum(x[i] * cost[i] for i in x) <=550, "# cost constraint"
prob += lp.lpSum(x[i] * acreage[i] for i in x) <=50, "# acreage constraint"
# Solve the problem
prob.solve()
# Print the solution
for v in prob.variables():
print(v.name, "=", v.varValue)
print("Total Cost =", lp.value(prob.objective))
status = prob.status
print("Status:", lp.LpStatus[status])
This is the code that gives me a solution when I negative the 1st, 2nd, 4th, and 5th goal constraints.
import pulp as lp
# Define the problem
prob = lp.LpProblem("Annual_usage", lp.LpMinimize)
# Decision variables
# x_i is the project type
x = {
'X1': lp.LpVariable('x_1', lowBound=0, cat='Binary'),
'X2': lp.LpVariable('x_2', lowBound=0, cat='Binary'),
'X3': lp.LpVariable('x_3', lowBound=0, cat='Binary'),
'X4': lp.LpVariable('x_4', lowBound=0, cat='Binary'),
'X5': lp.LpVariable('x_5', lowBound=0, cat='Binary'),
'X6': lp.LpVariable('x_6', lowBound=0, cat='Binary'),
'X7': lp.LpVariable('x_7', lowBound=0, cat='Binary'),
'X8': lp.LpVariable('x_8', lowBound=0, cat='Binary'),
'gamma': lp.LpVariable('gamma', lowBound=None, cat='Continuous')
}
# Usage
usage = {
'X1': 4.7, 'X2': 12.5, 'X3': 3.2, 'X4': 7.5, 'X5': 41, 'X6': 47, 'X7': 23, 'X8': 16,
'gamma': 0
}
# Costs
cost = {
'X1': 75, 'X2': 180, 'X3': 350, 'X4': 45, 'X5': 120, 'X6': 80, 'X7': 115, 'X8': 210,
'gamma': 0
}
# Acreage
acreage = {
'X1': 7, 'X2': 12, 'X3': 20, 'X4': 6, 'X5': 3, 'X6': 25, 'X7': 5, 'X8': 8,
'gamma': 0
}
goal1 = { # at least X3 and X6
'X1': 0, 'X2': 0, 'X3': -1, 'X4': 0, 'X5': 0, 'X6': -1, 'X7': 0, 'X8': 0,
'gamma': -16/6
}
goal2 = { # at least 130
'X1': -4.7, 'X2': -12.5, 'X3': -3.2, 'X4': -7.5, 'X5': -41, 'X6': -47, 'X7': -23, 'X8': -16,
'gamma': -16/3
}
goal3 = { #sum is at most 7
'X1': -3, 'X2': -2, 'X3': -1, 'X4': -3, 'X5': -2, 'X6': -1, 'X7': -2, 'X8':-3,
'gamma': -16/2
}
goal4 = { # At least 495k
'X1': -75, 'X2': -180, 'X3': -350, 'X4': -45, 'X5': -120, 'X6': -80, 'X7': -115, 'X8': -210,
'gamma': -16
}
goal5 = { # sum is at least 5
'X1': -1, 'X2': -1, 'X3': -1, 'X4': -1, 'X5': -1, 'X6': -1, 'X7': -1, 'X8': -1,
'gamma': -4
}
gamma_objective = {
'X1': 0, 'X2': 0, 'X3': 0, 'X4': 0, 'X5': 0, 'X6': 0, 'X7': 0, 'X8': 0,
'gamma': 1
}
# Objective function
prob += lp.lpSum(gamma_objective[i] * x[i] for i in x)
# Constraints
prob += lp.lpSum(x[i] * goal1[i] for i in x) <= -1, "goal 1"
prob += lp.lpSum(x[i] * goal2[i] for i in x) <= -130, "goal 2"
prob += lp.lpSum(x[i] * goal3[i] for i in x) <= 7, "goal 3"
prob += lp.lpSum(x[i] * goal4[i] for i in x) <= -495, "goal 4"
prob += lp.lpSum(x[i] * goal5[i] for i in x) <= -5, "goal 5"
prob += lp.lpSum(x[i] * cost[i] for i in x) <=550, "# cost constraint"
prob += lp.lpSum(x[i] * acreage[i] for i in x) <=50, "# acreage constraint"
# Solve the problem
prob.solve()
# Print the solution
for v in prob.variables():
print(v.name, "=", v.varValue)
print("Total Cost =", lp.value(prob.objective))
status = prob.status
print("Status:", lp.LpStatus[status])
So you've broken equivalence, but not addressed the root problem of infeasibility. Don't bother tinkering with different representations; use only the most obvious and easy-to-debug formulation from a business perspective. As is often the case, you've over-used dictionaries when you should be using matrices, sums and dot products. Goal 3 is too aggressive. You need to relax it (or your other constraints) to make the problem feasible:
import pulp
x1, x2, x3, x4, x5, x6, x7, x8 = project_types = pulp.LpVariable.matrix(
name='x', cat=pulp.LpBinary, indices=range(1, 9))
gamma = pulp.LpVariable(
name='gamma', cat=pulp.LpContinuous)
prob = pulp.LpProblem(name='Annual_usage', sense=pulp.LpMinimize)
usage = pulp.lpDot(project_types, (4.7, 12.5, 3.2, 7.5, 41, 47, 23, 16))
cost = pulp.lpDot(project_types, (75, 180, 350, 45, 120, 80, 115, 210))
acreage = pulp.lpDot(project_types, (7, 12, 20, 6, 3, 25, 5, 8))
prob.addConstraint(
name='goal1',
constraint=x3 + x6 + 16/6*gamma >= 1,
)
prob.addConstraint(
name='goal2',
constraint=usage + 16/3*gamma >= 130,
)
goal3 = pulp.lpDot(
project_types,
(3, 2, 1, 3, 2, 1, 2, 3),
) + 16/2*gamma
prob.addConstraint(
name='goal3',
constraint=goal3 <= 13, # 7
)
prob.addConstraint(
name='goal4',
constraint=cost + 16*gamma >= 495,
)
prob.addConstraint(
name='goal5',
constraint=pulp.lpSum(project_types) + 4*gamma >= 5,
)
prob.addConstraint(
name='cost',
constraint=cost <= 550,
)
prob.addConstraint(
name='acreage',
constraint=acreage <= 50,
)
prob.setObjective(gamma)
print(prob)
prob.solve()
assert prob.status == pulp.LpStatusOptimal
for v in prob.variables():
print(v.name, '=', v.value())
print('usage =', usage.value())
print('cost =', cost.value())
print('acreage =', acreage.value())
print('goal3 only reduced to', goal3.value())
Annual_usage:
MINIMIZE
1*gamma + 0.0
SUBJECT TO
goal1: 2.66666666667 gamma + x_3 + x_6 >= 1
goal2: 5.33333333333 gamma + 4.7 x_1 + 12.5 x_2 + 3.2 x_3 + 7.5 x_4 + 41 x_5
+ 47 x_6 + 23 x_7 + 16 x_8 >= 130
goal3: 8 gamma + 3 x_1 + 2 x_2 + x_3 + 3 x_4 + 2 x_5 + x_6 + 2 x_7 + 3 x_8
<= 13
goal4: 16 gamma + 75 x_1 + 180 x_2 + 350 x_3 + 45 x_4 + 120 x_5 + 80 x_6
+ 115 x_7 + 210 x_8 >= 495
goal5: 4 gamma + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 >= 5
cost: 75 x_1 + 180 x_2 + 350 x_3 + 45 x_4 + 120 x_5 + 80 x_6 + 115 x_7
+ 210 x_8 <= 550
acreage: 7 x_1 + 12 x_2 + 20 x_3 + 6 x_4 + 3 x_5 + 25 x_6 + 5 x_7 + 8 x_8
<= 50
VARIABLES
gamma free Continuous
0 <= x_1 <= 1 Integer
0 <= x_2 <= 1 Integer
0 <= x_3 <= 1 Integer
0 <= x_4 <= 1 Integer
0 <= x_5 <= 1 Integer
0 <= x_6 <= 1 Integer
0 <= x_7 <= 1 Integer
0 <= x_8 <= 1 Integer
...
Result - Optimal solution found
Objective value: 0.56250000
Enumerated nodes: 0
Total iterations: 4
Time (CPU seconds): 0.00
Time (Wallclock seconds): 0.00
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.00 (Wallclock seconds): 0.00
gamma = 0.5625
x_1 = 0.0
x_2 = 0.0
x_3 = 0.0
x_4 = 0.0
x_5 = 1.0
x_6 = 1.0
x_7 = 1.0
x_8 = 1.0
usage = 127.0
cost = 525.0
acreage = 41.0
goal3 only reduced to 12.5