There are several optimization applications in Python that can handle linear programming problems (LP).
Applications are broadly classified into the following two types.
--Solver; An application that includes an algorithm to solve a problem --Modeler; An application that makes it easier to program optimization problems. Bridging between users and Solver
We have summarized the available Solver and Modeler combinations and a simple implementation example of Modeler.
LP (Modeling & Solver summary)
LP Solver / Modeler | PuLP | Scipy | CVXOPT | PICOS | Pyomo |
---|---|---|---|---|---|
GLPK | ok | ok | ok | ok | |
CBC | ok | ok | |||
SCIP | ok? | ok | ok | ||
CPLEX | ok | ok | ok | ||
MOSEK | ok | ok | |||
GUROBI | ok | ok | ok | ||
CVXOPT | ok | ok | |||
SCIPY | ok |
Solver Install
Assuming a mac environment.
Non-commercial
brew install glpk
pip install swiglpk
Commercial and academic licenses available.
pip install mosek
and get academic license from https://www.mosek.com/products/academic-licenses/ if you can.
Modeler Install
pip install pulp scipy cvxopt picos pyomo
LP (Modeling)
Let's solve the following problems using each modeler.
min -x+4y
s.t. -3x + y ≤ 6
-x - 2y ≥ -4
y ≥ -3
PuLP
from pulp import LpVariable, LpProblem, value
x = LpVariable('x')
y = LpVariable('y', lowBound=-3) # y ≥ -3
prob = LpProblem()
prob += -x + 4*y #Objective function
prob += -3*x + y <= 6
prob += -x - 2*y >= -4
prob.solve()
print(value(prob.objective), value(x), value(y))
Available Solvers
CBC, CPLEX, GLPK, GUROBI, XPRESS, (CHOCO)
View of available solvers. (Reference; http://www.logopt.com/download/OptForPuzzle.pdf)
from pulp import LpSolver
def AvailableSolver(cls):
for c in cls.__subclasses__():
try:
AvailableSolver(c)
if c().available():
print(c)
except:
pass
AvailableSolver(LpSolver)
from pulp import PULP_CBC_CMD # GLPK, SCIP
solver = PULP_CBC_CMD() # solver=GLPK(), solver=SCIP()
prob.solve(solver=solver)
Scipy
min c^T x, s.t. Ax <= b
Changed the formulation to the following form
min -x+4y
s.t. -3x + y ≤ 6
x + 2y ≤ 4
-y ≤ 3
from scipy.optimize import linprog
c = [-1, 4]
A = [[-3, 1], [1, 2]]
b = [6, 4]
bounds =[
(None, None), # -∞ ≤ x ≤ ∞
(-3, None) # -s ≤ y ≤ ∞
]
res = linprog(c, A_ub=A, b_ub=b, bounds=bounds)
print(res)
CVXOPT
min c^T x s.t. Gx <= h, Ax = b
Changed the formulation to the following form
min -x+4y
s.t. -3x + y ≤ 6
x + 2y ≤ 4
0x + -y ≤ 3
from cvxopt import matrix, solvers
c = matrix([-1., 4.])
G = matrix([[-3., 1., 0.], [1., 2., -1.]])
h = matrix([6., 4., 3.])
sol = solvers.lp(c, G, h)
print(sol['primal objective'], sol['x'])
Available Solvers
conelp(CVXOPT), glpk, mosek
https://cvxopt.org/userguide/coneprog.html#s-lpsolver
sol = solvers.lp(c, G, h, solver='mosek') # solver='glpk'
print(sol['primal objective'], sol['x'])
CVXOPT (modeling)
from cvxopt import matrix
from cvxopt.modeling import variable, op
x = variable()
y = variable()
c1 = ( -3*x + y <= 6 )
c2 = ( -x - 2*y >= -4 )
c3 = ( y >= -3 )
lp = op(-x+4*y, [c1,c2,c3])
lp.solve()
print(lp.objective.value(), x.value, y.value)
Available Solvers
conelp(CVXOPT), glpk, mosek
sol = solvers.lp(c, G, h, solver='mosek') # solver='glpk'
print(sol['primal objective'], sol['x'])
PICOS (solver CVXOPT)
import picos as pic
prob = pic.Problem()
x = prob.add_variable('x')
y = prob.add_variable('y')
prob.set_objective('min', -x+4*y)
prob.add_constraint(-3*x + y <= 6)
prob.add_constraint(-x - 2*y >= -4)
prob.add_constraint(y >= -3)
sol = prob.solve()
print(sol.value, x.value, y.value)
/usr/local/lib/python3.7/site-packages/ipykernel_launcher.py:5: DeprecationWarning: Problem.add_variable is deprecated: Variables can now be created independent of problems, and do not need to be added to any problem explicitly.
"""
/usr/local/lib/python3.7/site-packages/ipykernel_launcher.py:6: DeprecationWarning: Problem.add_variable is deprecated: Variables can now be created independent of problems, and do not need to be added to any problem explicitly.
Available Solvers
https://picos-api.gitlab.io/picos/api/picos.modeling.options.html#option-solver
sol = prob.solve(solver='glpk')
print(sol.value, x.value, y.value)
Pyomo
import pyomo.environ as pyo
model = pyo.ConcreteModel()
model.x = pyo.Var()
model.y = pyo.Var()
model.OBJ = pyo.Objective(expr=-model.x + 4*model.y)
# add constraints
model.Constraint1 = pyo.Constraint(expr=-3*model.x+model.y <= 6)
model.Constraint2 = pyo.Constraint(expr=-model.x-2*model.y >= -4)
model.Constraint3 = pyo.Constraint(expr=model.y >= -3)
# add constraints
# def rule(model, i):
# A = [[-3, 1], [1, 2], [0, -1]]
# b = [6, 4, 3]
# return A[i][0]*model.x + A[i][1]*model.y <= b[i]
# model.const_set = pyo.Set(initialize=[0, 1, 2])
# model.CONSTRAINTS = pyo.Constraint(model.const_set, rule=rule)
opt = pyo.SolverFactory('glpk')
res = opt.solve(model)
print(model.OBJ(), model.x(), model.y())
Available Solvers
Serial Solver Interfaces
------------------------
The serial, pyro and phpyro solver managers support the following
solver interfaces:
asl + Interface for solvers using the AMPL Solver
Library
baron The BARON MINLP solver
bilevel_blp_global + Global solver for continuous bilevel linear
problems
bilevel_blp_local + Local solver for continuous bilevel linear
problems
bilevel_bqp + Global solver for bilevel quadratic
problems
bilevel_ld + Solver for bilevel problems using linear
duality
cbc The CBC LP/MIP solver
conopt The CONOPT NLP solver
contrib.gjh Interface to the AMPL GJH "solver"
cplex The CPLEX LP/MIP solver
cplex_direct Direct python interface to CPLEX
cplex_persistent Persistent python interface to CPLEX
gams The GAMS modeling language
gdpbb * Branch and Bound based GDP Solver
gdpopt * The GDPopt decomposition-based Generalized
Disjunctive Programming (GDP) solver
glpk * The GLPK LP/MIP solver
gurobi The GUROBI LP/MIP solver
gurobi_direct Direct python interface to Gurobi
gurobi_persistent Persistent python interface to Gurobi
ipopt The Ipopt NLP solver
mindtpy * MindtPy: Mixed-Integer Nonlinear
Decomposition Toolbox in Pyomo
mosek * Direct python interface to Mosek
mpec_minlp + MPEC solver transforms to a MINLP
mpec_nlp + MPEC solver that optimizes a nonlinear
transformation
multistart * MultiStart solver for NLPs
path Nonlinear MCP solver
pico The PICO LP/MIP solver
ps * Pyomo's simple pattern search optimizer
py + Direct python solver interfaces
scip The SCIP LP/MIP solver
trustregion * Trust region filter method for black
box/glass box optimization
xpress The XPRESS LP/MIP solver
https://pyomo.readthedocs.io/en/stable/solving_pyomo_models.html
Recommended Posts