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
- 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())
¡Ingeniero industrial que se centra en aprovechar los métodos de optimización y las tecnologías de inteligencia artificial utilizando múltiples lenguajes de programación para capacitar a una empresa para que logre sus objetivos!
Leave a Reply