Gekko and Pulp results differs but both are valid, why?

user_19028753 0
Viewed 81

I have this simple product mix linear program, Pulp and Gekko results differs a lot but results are both valid.

I wonder why and how should I get exactly the same result using both solvers ?

There is a simple product mix example :
Let's say x1 is the amount of car toy 1, and x2 the amount of car toy 2 ( -> Decision variables).
Car toy 1 price is 2$, Car toy 2 price is 1 $ ( -> Objective function).
Constraint 1 is a worktime limit expressed in hours, Constraint 2 is a parts inventory limit expressed in units.

I want to know which cars to build to maximize my profit subject to both constraints.

# Import 
from gekko import GEKKO
# Local server used
m = GEKKO(remote=False) 
# Picking solver 1
m.options.SOLVER = 1

# Initialize variables
x1 = m.Var(value=1,lb=0,ub=1000,integer=True)
x2 = m.Var(value=1,lb=0,ub=1000,integer=True)

# Constraints 
m.Equation(2 * x1 + 3 * x2 <= 800)
m.Equation(2 * x1 + x2 <= 500)

# Objective
m.Maximize( 2 * x1 + 1 * x2) 

# Steady state optimization
m.options.IMODE = 3 

# Solve
m.solve(disp=False) 

# Display results
print('Results')
print('x1: ' + str(x1.value))
print('x2: ' + str(x2.value))
print('Objective: ' + str(m.options.objfcnval))

Results
x1: [184.0]
x2: [132.0]
Objective: -500.0

And, next, this is my Python Pulp code. You will notice that Python Pulp only picks the x1 variable, while Gekko seems to balance between the x1 and the x2 variables, or seems to optimize the decision variables allocation( Don't know if it's true or not); both results are valid, and constraints are not exceeded:

# Import 
import pulp 

# This is a maximization L.P 
model = pulp.LpProblem("Maximize", pulp.LpMaximize)

# Initialize variables  
x1 = pulp.LpVariable('x1', lowBound=0, cat='Integer')
x2 = pulp.LpVariable('x2', lowBound=0, cat='Integer')
  
# Objective
model +=  2 * x1 + 1 * x2, "Profit"

# Constraints 
model += 2 * x1 + 3 * x2 <= 800
model += 2 * x1 + x2 <= 500

# Solve
model.solve()

# Status
pulp.LpStatus[model.status]

# Display results
# Print our decision variable values
print ("x1 = {}".format(x1.varValue))
print ("x2 = {}".format(x2.varValue))
  
# Print our objective function value
print (pulp.value(model.objective))

Results
x1 = 250.0
x2 = 0.0
500.0

Gekko tells me to build 184 "car toy 1" and 132 "car toy 2" to maximize my profit , but Pulp tells me to only build 250 "car toy 1" , and to ignore "car toy 2" to maximize my profit.
In the second case, the factory could abandon the plan to build toy car 2 altogether and dismantle parts of the factory to save money ( So it's good), so the result has a lot of consequences.

Can somebody please tell me if that is a normal behavior, and how should I get the same behavior on both solvers ?

Is is due to a different simplex or interior point algorithm used by theses libraries?

( Secondary question : I don't know why the Gekko objective result is negative ... )

pulp solver gekko
1 Answers

There are multiple potential solutions because the profit objective and constraint 2 are co-linear and the objective contour is along constraint 2.

m.Equation(2*x1 + 1*x2 <= 500)
m.Maximize(2*x1 + 1*x2)

contour

This is apparent with a contour plot that shows the constraints (blue and red) and objective contours (green). The optimal solutions are along the blue line constraint (#2) until it intersects with the red line constraint (#1).

Generate a contour plot

import matplotlib
import numpy as np
import matplotlib.pyplot as plt

# Design variables at mesh points
x = np.arange(-1.0, 401, 5)
y = np.arange(-1.0, 501, 5)
x1, x2 = np.meshgrid(x,y)

# Equations and Constraints
profit = 2.0 * x1 + 1.0 * x2
c1 = 2.0 * x1 + 3.0 * x2
c2 = 2.0 * x1 + 1.0 * x2

# Create a contour plot
plt.figure()
# Profit contours
lines = np.linspace(100.0,800.0,4)
CS = plt.contour(x1,x2,profit,lines,colors='g')
plt.clabel(CS, inline=1, fontsize=10)
# Car 1 <= 800
CS = plt.contour(x1,x2,c1,[760.0, 780.0, 800.0],colors='r',linewidths=[0.5,0.5,4.0])
plt.clabel(CS, inline=1, fontsize=10)
# Car 2 < 500
CS = plt.contour(x1, x2,c2,[460.0,480.0,500.0],colors='b',linewidths=[0.5,0.5,4.0])
plt.clabel(CS, inline=1, fontsize=10)
# 0 <= Car 1 <= 1000
CS = plt.contour(x1, x2,x1 ,[0.0, 5.0, 10.0],colors='k',linewidths=[1.0,0.5,0.5])
plt.clabel(CS, inline=1, fontsize=10)
# 0 <= Car 2 <= 100
CS = plt.contour(x1, x2,x2 ,[0.0, 5.0, 10.0],colors='k',linewidths=[4.0,0.5,0.5])
plt.clabel(CS, inline=1, fontsize=10)
plt.xlabel('Car 1 Units'); plt.ylabel('Car 2 Units'); plt.show()

To make the solution unique, add a small penalty to one of the variables such as:

m.Minimize(1e-5*x2)

Here is the new Gekko script that returns the same solution as Pulp. Pulp is limited to Mixed Integer Linear Programming (MILP) problems while Gekko can solve Mixed Integer Nonlinear Programming (MINLP) problems with differential and algebraic constraints.

from gekko import GEKKO
m = GEKKO(remote=False) 
m.options.SOLVER = 1

# Initialize variables
x1 = m.Var(value=1,lb=0,ub=1000,integer=True)
x2 = m.Var(value=1,lb=0,ub=1000,integer=True)

# Equations
m.Equation(2 * x1 + 3 * x2 <= 800)
m.Equation(2 * x1 + x2 <= 500)

# Objective
m.Maximize( 2 * x1 + 1 * x2) 
m.Minimize(1e-5*x2)

# Steady state optimization
m.options.IMODE = 3 

# Solve
m.solve(disp=False) 

print('Results')
print('x1: ' + str(x1.value))
print('x2: ' + str(x2.value))
print('Objective: ' + str(-m.options.objfcnval))

Results
x1: [250.0]
x2: [0.0]
Objective: 500.0

Response to Secondary question: Gekko always converts to a minimization problem with -max(obj) = min(obj). Gekko is designed to potentially have multiple objectives so all are converted to minimization. An example is maximize profit, minimize costs, and minimize environmental damage. These may all be in a single optimization problem.

Additional information is in the ME575 (Design Optimization) course with the Design Optimization Online Textbook.

user_23669410
Related