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

La investigación de operaciones (OR) implica experimentos con modelos de optimización. El objetivo es encontrar el mejor diseño, plan o decisión para un sistema o un ser humano. En consecuencia, estos modelos constan de objetivos y limitaciones. Sin embargo, la mayoría de los paquetes o software disponibles para OR no son de código abierto. Así, se ha reducido el ritmo de transferencia de conocimiento o incluso la reproducibilidad de los resultados generados por los modelos de optimización. Además, los paquetes de optimización o software disponibles no proporcionan el mismo nivel de flexibilidad que conocemos, por ejemplo, de un lenguaje de programación como Python . Además, la mayoría de los programas o paquetes disponibles no son fáciles de usar.

En general, basarse en resultados anteriores en quirófano 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). En consecuencia, en este blog , estamos motivados para presentar y revisar interfaces populares de alto nivel para modelar problemas de optimización en Python. Como resultado, los analistas de SCM y OR pueden aprovechar herramientas mejores y más flexibles.

En particular, nos enfocamos en paquetes que pueden modelar y resolver programas lineales de enteros mixtos . Se utiliza un lenguaje de programación de alto nivel como Python para formular un problema. Luego, el problema se resuelve mediante optimizadores (solucionadores) escritos en lenguajes de bajo nivel.

Diferencia entre interfaces de modelado y solucionadores en Python

Al principio, se debe enfatizar y explicar la diferencia entre las interfaces de modelado (lenguajes de modelado) y los solucionadores 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 solucionadores al resolver un problema.
- Está disponible gratuitamente para cualquier lenguaje de programación.
- Proporciona herramientas de creación de modelos y estructuras de datos básicas.
- Establece los parámetros del solucionador.
Un solucionador :
- Puede ser comercial (es mejor) o de código abierto (puede ser inferior al resolver problemas de optimización a gran escala).
- Puede tener una interfaz específica para sí mismo.
- 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 (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 el 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=1X=1, y=1y=1 y el valor óptimo del objetivo es 7. Resolvemos 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 modelado para programación lineal y programación lineal de enteros mixtos en Python .
Solucionadores 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:

# Instalación (Descomente la línea de abajo) 
#! Pip install mip 

# Importar paquete 
import  mip  como  op 

# Definir entorno 
prob = op.Model ( "MyOptProblem" ) # Definir variables de decisión 
x = [prob.add_var (var_type = op.INTEGER) for i in range ( 1 )] 
y = [prob.add_var () for i in range ( 1 )] # Agregar función objetivo al entorno 
prob.objective = op.maximize ( 2 * x [ 0 ] + 5 * y [ 0 ])

  



# Agregar restricciones al entorno 
prob + = 5 * x [ 0 ] + 3 * y [ 0 ] <= 10 
prob + = 2 * x [ 0 ] + 7 * y [ 0 ] <= 9 

# El estado de la solución 
print (prob.optimize ()) # Para mostrar variables de decisión óptimas print ( 'x:' , x [ 0 ] .x)
 print ( 'y:' , y [ 0 ] .x) # Para mostrar el valor óptimo de la función objetivo print ( "El valor óptimo del objetivo es ="





, prob.objective_value)

2. Optimización con PuLP en Python

PuLP :

Lenguaje de modelado para programación lineal y programación lineal de enteros mixtos en Python .
Solucionadores 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:

# Instalación (descomente la línea de abajo) 
#! Pip

 install PuLP # Importar paquete 
import  PuLP  as  op 

# Definir entorno y dirección de optimización 
prob = op. LpProblem ( "MyOptProblem" , op.LpMaximize) # Definir variables de decisión 
x = op. LpVariable ( "x" , lowBound = 0 , upBound = None , cat = 'Continuous' ) 
y = op. LpVariable ( "y" , lowBound = 0 , upBound = None , cat = 'Integer' )



# Agregar función objetivo al 
problema ambiental + = 2 * x + 5 * y, "Objetivo" 

# Agregar restricciones al 
problema ambiental + = 5 * x + 3 * y <= 10 , "Restricción1" 
problema + = 2 * x + 7 * y <= 9 ,   "Constraint2" 

# Resuelve el problema (otros solucionadores: prob.solve (SOLVERNAME ())) 
prob.solve () # El estado de la solución print ( "Status:" , op. LpStatus [prob.status ]) # Para mostrar las variables de decisión óptimas para las variables en





prob.variables ():
     print (variables.name, "=" , variables.varValue) # Para mostrar el valor óptimo de la función objetivo print ( "El valor óptimo del objetivo es =" , op.value (prob.objective))

3. Optimización con Pyomo en Python

Pyomo :

Lenguaje de modelado 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.
Solucionadores compatibles: visite 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:

# Instalación (descomente la línea de abajo) 
#! Pip install pyomo 

# Importar paquete 
import  pyomo.environ  as  op 

# Definir entorno 
prob = op.ConcreteModel ( "MyOptProblem" ) # Definir variables de decisión 
prob.x = op.Var ([ 1 ] , domain = op.NonNegativeReals) 
prob.y = op.Var ([ 1 ], domain = op.PositiveIntegers) # Agregar función objetivo al entorno 
prob.OBJ = op.Objective (expr = 2 * prob.x [ 1 ] + 5 * prob.y [ 1 ]) # Agregar restricciones al entorno 
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 ) # Resuelva el 
solucionador de problemas = op.SolverFactory ( 'SOLVERNAME' ) 
results = solver.solve (prob) # Para mostrar los resultados imprimir (resultados)

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

Herramientas de quirófano 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 ” ortools ” (el nombre del paquete) en Python:

# Instalación (descomente la línea de abajo) 
#! Pip

 install ortools # Importar paquete 
desde  ortools .linear_solver  import pywraplp # Definir entorno def prob (): # (Otros solucionadores: pywraplp.Solver.CreateSolver ('SOLVERNAME')) 
    op = pywraplp. Solver.CreateSolver ( 'SCIP' ) # Definir variables de decisión    
    x = op.NumVar ( 0.0 , op.infinity (), 'x' ) 
    y = op.IntVar ( 0.0 , op.infinity (), 'y' ) # Agregar función objetivo al entorno 
    op.Maximizar ( 2 * x +


 


 


5 * y) # Agregar restricciones al entorno 
    op.Add ( 5 * x + 3 * y <= 10 ) 
    op.Add ( 2 * x + 7 * y <= 9 ) # Resolver el 
    estado del problema = op.Solve () # El estado de la solución si status == pywraplp.Solver.OPTIMAL:
         print ( 'Solución:' )
         print ( 'Valor objetivo =' , op.Objective (). Value ())
         print ( 'x =' , x.solution_value ())
         imprimir ( 'y ='






    , y.solution_value ())
     else :
         print ( 'El problema no tiene una solución óptima.' ) 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 restringidos y sin restricciones.
Solucionadores 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:

# Instalación (descomente la línea de abajo) 
#! Pip install pymoo 

# Importación de paquetes 
import  numpy  as  np 
from  pymoo.core.problem  import Problema
 de  pymoo.algorithms.moo.nsga2  import NSGA2
 from  pymoo.factory  import get_sampling, get_crossover, get_mutation
 from  pymoo .factory  import get_termination
 de  pymoo.optimize  import minimizar 

termination = get_termination ( "n_gen" , 40 ) # Solucionador del 
algoritmo del problema = NSGA2 (


    pop_size =  400, 
    n_offsprings = 10 , 
    muestreo = get_sampling ( "real_random" ), 
    crossover = get_crossover ( "real_sbx" , prob = 0.9 , eta = 15 ), 
    mutation = get_mutation ( "real_pm" , eta = 20 ), 
    eliminar_duplicates = True 
) # Definir clase de entorno MyOptProblem (Problema):
     def __init__ ( self ): # Definir variables de decisión 
        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): # Agregar función objetivo al entorno 
        f1 = - 2 * x [:, 0 ] + - 5 * np.round (x [:, 1 ]) 
        out [ "F" ] = np .column_stack ([f1]) # Agregar restricciones al entorno

     
        

        

        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 () # Resuelve el problema 
res = minimizar (prob, 
               algoritmo, 
               terminación, 
               semilla = 2 , 
               save_history = True , 
               verbose = False ) # Mostrar resultados imprimir




("El valor óptimo del objetivo es =" , -res.F [ 0 ])

6. Optimización con GEKKO en Python

GEKKO :

Lenguaje de modelado para programación de enteros mixtos, no lineales, cuadráticos y a gran escala.
Solucionadores 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:

# Instalación (descomente la línea a continuación) 
#! Pip install gekko 

# Importar paquetes 
desde  gekko  import GEKKO # Definir entorno 
prob = GEKKO (remoto = False ) # Definir variables de decisión 
x = prob.Var (lb = 0 , ub = None , integer = Verdadero ) 
y = prob.Var (lb = 0 , ub = None ) # Agregar función objetivo al entorno 
prob.Obj (- ( 2 * x + 5 * y)) # Objetivo # Agregar restricciones al entorno 
Prob.Ecation ( 5 * x + 3 * y <=







10 ) 
ecuación de prob. ( 2 * x + 7 * y <= 9 ) # Resuelve el problema (1: solucionador de MINLP, 2,3: otros solucionadores) 
opciones de prob . SOLVER = 1   
resolucion de prob (disp = False ) # Pantalla resultados print ( 'Resultados' )
 print ( 'x:' + str (x.value))
 print ( 'y:' + str (y.value))
 print ( 'El valor óptimo del objetivo es =' + str (-prob .options.objfcnval))

7. Optimización con PICOS en Python

PICOS :

Lenguaje de modelado para varios problemas de programación cónicos y enteros.
Solucionadores 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:

# Instalación (descomente la línea de abajo) 
#! Pip install picos 

# Importar paquete 
import  picos  como  op 

# Definir entorno 
prob = op.Problem ( "MyOptProblem" ) # Definir variables de decisión 
x = op.RealVariable ( "x" , lower = 0 ) 
y = op.IntegerVariable ( "y" , lower = 0 ) # Agregar función objetivo al entorno 
prob.set_objective ( 'max' , 2 * x + 5 * y) # Agregar restricciones al entorno 
prob + = 5 * x + 3 * y <=





10 
prob + = 2 * x + 7 * y <= 9 

# Resuelva el problema 
prob.solve (solver = 'glpk' ) # Para mostrar los resultados print ( 'x:' , x.value)
 print ( 'y:' , y .value)
 print ( "El valor óptimo del objetivo es =" , prob.obj_value ())

Keivan Tafakkori M.Sc.

¡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!