Il existe plusieurs applications d'optimisation en Python qui peuvent gérer les problèmes de planification linéaire (LP).
Les applications sont généralement classées dans les deux types suivants.
--Solver; Une application qui inclut un algorithme pour résoudre un problème --Modèle; Une application qui facilite la programmation des problèmes d'optimisation. Pontage entre les utilisateurs et le solveur
Nous avons résumé les combinaisons de Solveur et de Modeleur disponibles et un exemple d'implémentation simple de 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
En supposant un environnement mac.
Non commercial
brew install glpk
pip install swiglpk
Licences commerciales et académiques disponibles.
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)
Résolvons les problèmes suivants en utilisant chaque modeleur.
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 #Fonction objective
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)
Vue des solveurs disponibles. (Référence; 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
Changé la formulation pour la forme suivante
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
Changé la formulation pour la forme suivante
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