Modelamiento y resolución de problemas de optimización en Python

Published on by Keivan Tafakkori M.Sc.

La investigación de operaciones (OR) implica experimentos con modelos de optimización, cuyo objetivo es encontrar el diseño, plan o decisión óptimo para un sistema o un ser humano, en base a objetivos y restricciones. Sin embargo, la mayoría de los paquetes o software disponibles para OR no son de código abierto, reduciendo el ritmo de transferencia de conocimiento, e incluso la reproducibilidad de los resultados generados por los modelos de optimización. Además, los paquetes o software de optimización disponibles no son fáciles de usar, y no proporcionan el mismo nivel de flexibilidad que conocemos, por ejemplo, de un lenguaje de programación como Python.

Editado y traducido el 29 de junio del 2022 por Oswaldo Almonacid

En general, basarse en resultados anteriores en OR siempre ha sido difícil y ha llevado mucho tiempo, en comparación con otros campos de la informática, como el aprendizaje automático (ML) y la simulación (SM). Como resultado, en esta publicación presentaremos interfaces populares de alto nivel para modelar problemas de optimización en Python, y ayudar a analistas de Cadena de Suministro y OR a aprovechar herramientas mejores y más flexibles.

En particular, nos enfocamos en paquetes que pueden modelar y resolver programas lineales enteros mixtos, usando un lenguaje de programación de alto nivel como Python para formular el modelo matemático y resolver dicho modelo mediante optimizadores (solvers) escritos en lenguajes de bajo nivel.

Diferencias entre interfaces de modelamientos y solvers en Python

Primero, revisemos las diferencias entre las interfaces de modelado (lenguajes de modelado) y los solvers de problemas de optimización:

  • Una interfaz :
    • Entiende un lenguaje específico para comandos (sintaxis).
    • Depende del lenguaje de programación.
    • Devuelve un archivo intermedio que un solucionador lee como entrada (por ejemplo, en formatos .mps, .lp, .nl, .osil, .gms).
    • Puede seleccionar uno de varios solvers al resolver un problema.
    • Está disponible gratuitamente para un amplio rango de lenguajes de programación.
    • Proporciona herramientas de creación de modelos y estructuras de datos básicas.
    • Establece los parámetros del solucionador.
  • Un solver:
    • Puede ser comercial o de código abierto (puede ser inferior al resolver problemas de optimización a gran escala).
    • Puede tener una interfaz específica.
    • Proporciona bibliotecas que entienden los lenguajes de programación.
    • Realiza factorización, análisis de archivos, análisis de parámetros, resolución previa, matriz dispersa, almacenamiento de matrices, gestión de memoria y temporización.
    • Devuelve información que describe la solución y el estado del problema de optimización.

Un problema de prueba

Consideremos el siguiente modelo de optimización:

El espacio de solución o región factible (ya que x es una variable discreta e y es una variable de decisión continua) se puede derivar gráficamente de la siguiente manera:

Según la gradiente del objetivo (la flecha roja) y la dirección de la optimización (maximización), el punto verde es la solución óptima, en la que X=1, y=1, y el valor óptimo del objetivo es 7.

A continuación, presentamos la resolución de este modelo simple de programación lineal de enteros mixtos con siete paquetes de interfaz en Python, y analizamos su sintaxis y similitudes.

1. Optimización con MIP en Python

Python-MIP :

  • Lenguaje de modelamiento para programación lineal y programación lineal de enteros mixtos en Python .
  • Solvers compatibles: CLP, CBC, Gurobi.

El siguiente código comentado tiene como objetivo resolver el modelo de programación lineal de enteros mixtos propuesto con “mip” (el nombre del paquete) en Python:

# Installation (Uncomment the Line Below)
#!pip install mip

# Import package
import mip as op

# Define environment
prob = op.Model("MyOptProblem")

# Define decision variables
x = [prob.add_var(var_type=op.INTEGER) for i in range(1)]
y = [prob.add_var() for i in range(1)]

# Add objective function to the environment
prob.objective = op.maximize(2*x[0]+5*y[0])

# Add constraints to the environment
prob += 5*x[0]+3*y[0]<=10
prob += 2*x[0]+7*y[0]<=9

# The status of the solution
print(prob.optimize())

# To display optimal decision variables
print('x: ',  x[0].x)
print('y: ',  y[0].x)

# To display optimal value of objective function
print("Optimal Value of Objective Is = ",prob.objective_value)

2. Optimización con PuLP en Python

PuLP :

  • Lenguaje de modelamiento para programación lineal y programación lineal de enteros mixtos en Python .
  • Solvers admitidos: GLPK, COIN-OR CLP / CBC, CPLEX, GUROBI, MOSEK, XPRESS, CHOCO, MIPCL, SCIP.

El siguiente código comentado tiene como objetivo resolver el modelo de programación lineal de enteros mixtos propuesto con ” PuLP ” (el nombre del paquete) en Python:

# Installation (uncomment the line below)
# !pip install PuLP

# Import package
import PuLP as op

# Define environment & direction of optimization
prob = op.LpProblem("MyOptProblem", op.LpMaximize)

# Define decision variables
x = op.LpVariable("x", lowBound = 0, upBound = None, cat='Continuous')
y = op.LpVariable("y", lowBound = 0, upBound = None, cat='Integer')

# Add objective function to the environment
prob += 2*x+5*y, "Objective"

# Add constraints to the environment
prob += 5*x+3*y<=10, "Constraint1"
prob += 2*x+7*y<=9,  "Constraint2"

# Solve the problem (other solvers: prob.solve(SOLVERNAME()))
prob.solve()

# The status of the solution
print("Status:", op.LpStatus[prob.status])

# To display optimal decision variables
for variables in prob.variables():
    print(variables.name, "=", variables.varValue)

# To display optimal value of objective function
print("Optimal Value of Objective Is = ", op.value(prob.objective))






3. Optimización con Pyomo en Python














Pyomo :





  • Lenguaje de modelamiento para programación lineal, programación cuadrática, programación no lineal, programación lineal de enteros mixtos, programación cuadrática de enteros mixtos, programación no lineal de enteros mixtos, programación estocástica, programación disyuntiva generalizada, ecuaciones algebraicas diferenciales, programación de dos niveles y programas matemáticos con restricciones de equilibrio en Python.
  • Solvers compatibles: visita este enlace.





El siguiente código comentado tiene como objetivo resolver el modelo de programación lineal de enteros mixtos propuesto con “pyomo” (el nombre del paquete) en Python:





# Installation (uncomment the line below)
# !pip install pyomo

# Import package
import pyomo.environ as op

# Define environment
prob = op.ConcreteModel("MyOptProblem")

# Define decision variables
prob.x = op.Var([1],domain=op.NonNegativeReals)
prob.y = op.Var([1],domain=op.PositiveIntegers)

# Add objective function to the environment
prob.OBJ = op.Objective(expr=2*prob.x[1]+5*prob.y[1])

# Add constraints to the environment
prob.Constraint1 = op.Constraint(expr=5*prob.x[1]+3*prob.y[1]<=10)
prob.Constraint2 = op.Constraint(expr=2*prob.x[1]+7*prob.y[1]<=9)

# Solve the problem
solver = op.SolverFactory('SOLVERNAME')
results = solver.solve(prob)

# To display results
print(results)






4. Optimización con Google OR-Tools en Python














OR-Tools de Google :





  • Lenguaje de modelado para programación de restricciones, programación lineal y programación lineal de enteros mixtos.
  • Solucionadores admitidos: Gurobi, CPLEX, SCIP, GLPK, GLOP , CP-SAT





El siguiente código comentado tiene como objetivo resolver el modelo de programación lineal de enteros mixtos propuesto con ” OR-Tools ” (el nombre del paquete) en Python:





# Installation (uncomment the line below)
# !pip install ortools

# Import package
from ortools.linear_solver import pywraplp

# Define environment
def prob():

#(Other solvers: pywraplp.Solver.CreateSolver('SOLVERNAME'))
    op = pywraplp.Solver.CreateSolver('SCIP')
 
# Define decision variables   
    x = op.NumVar(0.0, op.infinity(), 'x')
    y = op.IntVar(0.0, op.infinity(), 'y')

# Add objective function to the environment
    op.Maximize(2*x+5*y)

# Add constraints to the environment
    op.Add(5*x+3*y<=10)
    op.Add(2*x+7*y<=9)

# Solve the problem 
    status = op.Solve()

# The status of the solution
    if status == pywraplp.Solver.OPTIMAL:
        print('Solution:')
        print('Objective value =', op.Objective().Value())
        print('x =', x.solution_value())
        print('y =', y.solution_value())
    else:
        print('The problem does not have an optimal solution.')

if __name__ == '__main__':
    prob()






5. Optimización con Pymoo en Python














pymoo :





  • Lenguaje de modelado para todo tipo de problemas de optimización de objetivo único y multiobjetivo con y sin restricciones.
  • Solvers admitidos: algoritmos metaheurísticos que se introducen en este enlace .





El siguiente código comentado tiene como objetivo resolver el modelo de programación lineal de enteros mixtos propuesto con “pymoo” (el nombre del paquete) en Python:





# Installation (uncomment the line below)
#!pip install pymoo

# Import packages
import numpy as np
from pymoo.core.problem import Problem
from pymoo.algorithms.moo.nsga2 import NSGA2
from pymoo.factory import get_sampling, get_crossover, get_mutation
from pymoo.factory import get_termination
from pymoo.optimize import minimize

termination = get_termination("n_gen", 40)

# Solver of the problem
algorithm = NSGA2(
    pop_size=400,
    n_offsprings=10,
    sampling=get_sampling("real_random"),
    crossover=get_crossover("real_sbx", prob=0.9, eta=15),
    mutation=get_mutation("real_pm", eta=20),
    eliminate_duplicates=True
)

# Define environment
class MyOptProblem(Problem):
    def __init__(self):

# Define decision variables
        largenumber = 10^10
        super().__init__(n_var=2,
                         n_obj=1,
                         n_constr=2,
                         xl=np.array([0,0]),
                         xu=np.array([largenumber,largenumber]))

    def _evaluate(self, x, out, *args, **kwargs):
        
# Add objective function to the environment
        f1 = -2*x[:,0] + -5*np.round(x[:,1])
        out["F"] = np.column_stack([f1])
        
# Add constraints to the environment
        g1 = 5*x[:,0] + 3*np.round(x[:,1]) - 10
        g2 = 2*x[:,0] + 7*np.round(x[:,1]) - 9
        out["G"] = np.column_stack([g1, g2])
       
prob = MyOptProblem()

# Solve the problem 
res = minimize(prob,
               algorithm,
               termination,
               seed=2,
               save_history=True,
               verbose=False)

# Display results
print("Optimal Value of Objective Is = ", -res.F[0])






6. Optimización con GEKKO en Python














GEKKO :





  • Lenguaje de modelamiento para programación de enteros mixtos, no lineales, cuadráticos y a gran escala.
  • Solvers compatibles: APOPT, BPOPT, IPOPT, SNOPT, MINOS.





El siguiente código comentado tiene como objetivo resolver el modelo de programación lineal de enteros mixtos propuesto con “gekko” (el nombre del paquete) en Python:





# Installation (uncomment the line below)
#!pip install gekko

# Import packages
from gekko import GEKKO

# Define environment
prob = GEKKO(remote=False)

# Define decision variables
x = prob.Var(lb=0,ub=None,integer=True)
y = prob.Var(lb=0,ub=None)

# Add objective function to the environment
prob.Obj(-(2*x+5*y)) # Objective

# Add constraints to the environment
prob.Equation(5*x+3*y<=10)
prob.Equation(2*x+7*y<=9)

# Solve the problem (1: MINLP solver, 2,3: Other Solvers)
prob.options.SOLVER=1  
prob.solve(disp=False) 

# Display results
print('Results')
print('x: ' + str(x.value))
print('y: ' + str(y.value))
print('Optimal Value of Objective Is = ' + str(-prob.options.objfcnval))






7. Optimización con PICOS en Python














PICOS :





  • Lenguaje de modelamiento para varios problemas de programación cónicos y enteros.
  • Solvers compatibles: visite este enlace .





El siguiente código comentado tiene como objetivo resolver el modelo de programación lineal de enteros mixtos propuesto con “picos” (el nombre del paquete) en Python:





# Installation (uncomment the line below)
# !pip install picos

# Import package
import picos as op

# Define environment
prob = op.Problem("MyOptProblem")

# Define decision variables
x = op.RealVariable("x", lower = 0)
y = op.IntegerVariable("y", lower = 0)

# Add objective function to the environment
prob.set_objective('max', 2*x+5*y)

# Add constraints to the environment
prob += 5*x+3*y<=10
prob += 2*x+7*y<=9

# Solve the problem
prob.solve(solver='glpk')

# To display results
print('x: ',  x.value)
print('y: ',  y.value)
print("Optimal Value of Objective Is = ", prob.obj_value())




    


	
Leave a Reply




		

		
Deja una respuesta 
Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *
 
 



 


 


	

	
Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.





		

	














    

        

            Close
        

        
        
Meta