HorusLP-Gurobi: Arquitectura de optimización de alto nivel para Gurobi

A medida que las tecnologías de optimización se vuelven más sofisticadas, los solucionadores comerciales han comenzado a desempeñar un papel cada vez más importante en la industria. En comparación con los solucionadores de código abierto, las soluciones comerciales tienden a tener más funciones para resolver modelos de optimización complejos, como la presolución avanzada, el arranque en caliente y la resolución distribuida.

Uno de los solucionadores comerciales más populares en el mercado es Gurobi, llamado así por los cofundadores Zonghao Gu, Edward Rothberg y Robert Bixby, cada uno de los cuales fue pionero en el espacio de los solucionadores comerciales. Gurobi ha impulsado muchos proyectos de optimización de alto perfil en la historia reciente, incluido el proyecto de asignación de ancho de banda de la FCC y el proyecto de reasignación de prisioneros de la prisión estatal de Pensilvania.

Hoy, veremos cómo HorusLP, un paquete de software que proporciona una interfaz declarativa de alto nivel para el modelado de optimización, se integra con la API de Gurobi para brindar una experiencia de modelado intuitiva a los usuarios mientras aprovecha las funciones más avanzadas de Gurobi.

Optimización: un repaso rápido

Para aquellos que no están familiarizados con la optimización o la investigación de operaciones, la optimización se refiere a una colección de técnicas matemáticas que encuentra los valores óptimos de las variables dentro de un sistema de ecuaciones sujeto a un sistema de restricciones. Si la oración anterior suena un poco seca, tal vez un ejemplo ayude a ilustrar.

Suponga que tiene una mochila con 15 libras de capacidad de carga. Tienes frente a ti algunos artículos, cada uno con un peso específico y un valor monetario:

1. Cámara: peso 2 libras, valor $5
2. Figurilla: peso 4 libras, valor $7
3. Sidra: peso 7 libras, valor $2
4. Cuerno: peso 10 libras, valor $10.

Desea elegir artículos para colocar en su mochila de modo que el peso total se mantenga por debajo de las 15 libras pero el valor se maximice. (Si necesita más contexto sobre por qué estamos metiendo artículos de alto valor en una mochila, le recomendamos que use su imaginación para una narrativa. Las buenas narrativas candidatas incluyen rescatar cosas de un incendio y subastas de bienes... o algunas actividades nefastas que Preferiría no mencionarlo.)

Podemos formular el problema como el siguiente problema de optimización:

 Let // Each variable stands for whether we put the item into the knapsack Camera = {0, 1} Figurine = {0, 1} Cider = {0, 1} Horn = {0, 1} // Maximize dollar value Maximize 5 * camera + 7 * figurine + 2 * cider + 10 * horn // Weight must stay below 15 pounds 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Una vez que hemos formulado este problema, podemos aplicar técnicas de optimización para encontrar los mejores elementos para colocar en nuestra mochila. Puede encontrar un ejemplo de la solución en mis artículos anteriores sobre cómo resolver problemas de optimización usando Python y cómo resolver problemas de optimización usando la API principal de HorusLP.

La técnica matemática subyacente es bastante fascinante, pero está fuera del alcance de este artículo. Si desea obtener más información, le recomiendo consultar aquí y aquí, ambos cortesía de Gurobi.

Gurobí

Mientras que los primeros problemas de optimización fueron resueltos por equipos de matemáticos que trabajaban con calculadoras, la mayoría de los problemas de optimización actuales se resuelven utilizando software especializado llamado solucionadores. Si bien la mayoría de los solucionadores generalmente pueden encontrar soluciones para la mayoría de los problemas de programación lineal y entera bien formulados, algunos solucionadores son mucho más capaces que otros. Pueden resolver clases de problemas que otros no pueden resolver, resolver problemas más rápidamente aplicando matemáticas de vanguardia o resolver problemas grandes y difíciles utilizando computadoras distribuidas. Las características más avanzadas generalmente se proporcionan en solucionadores comerciales desarrollados y mantenidos por compañías especializadas en construir los solucionadores más rápidos y sofisticados.

Gurobi es uno de los líderes en el mercado de solucionadores comerciales, utilizado por grandes segmentos de la comunidad de optimización, incluidos gobiernos, instituciones académicas y empresas que operan en industrias que van desde finanzas hasta logística. En términos de velocidad, gurobi supera constantemente en varios puntos de referencia utilizados para juzgar a los solucionadores comerciales y de código abierto.

Gurobi también viene con una potente API de Python que le permite crear modelos a partir de Python. Esta función brinda a los modeladores acceso a todas las bibliotecas de manipulación de datos útiles de Python durante la construcción del modelo, lo que ayuda enormemente en su proceso. Como demostración de la API de gurobi Python, así es como podría modelar el problema de la mochila:

 import gurobipy as gr m = gr.Model() camera = m.addVar(name='camera', vtype=gr.GRB.BINARY) figurine = m.addVar(name='figurine', vtype=gr.GRB.BINARY) cider = m.addVar(name='cider', vtype=gr.GRB.BINARY) horn = m.addVar(name='horn', vtype=gr.GRB.BINARY) m.addConstr(2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 , 'size constraint') m.setObjective(5 * camera + 7 * figurine + 2 * cider + 10 * horn, gr.GRB.MAXIMIZE) m.optimize() print(camera.x) print(figurine.x) print(horn.x) print(cider.x)

Ejecutar el ejemplo le dará el siguiente resultado:

 Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% -0.0 1.0 1.0 -0.0

HorusLP

HorusLP es una biblioteca de modelado de optimización que se creó a partir de experiencias en el desarrollo de algoritmos de optimización. Las bibliotecas de modelado actualmente disponibles carecen de las herramientas necesarias para trabajar con el tipo de problemas complejos y multifacéticos que normalmente se encuentran en las aplicaciones comerciales de la investigación de operaciones.

Si bien la mayoría de las bibliotecas de optimización ofrecen una interfaz imperativa de bajo nivel, a medida que los modelos de optimización se vuelven más complejos, se necesitan mejores herramientas para administrar la complejidad. HorusLP es una biblioteca que proporciona herramientas de alto nivel para gestionar estas complejidades. HorusLP también proporciona potentes herramientas de depuración y generación de informes que permiten un desarrollo y una iteración más rápidos.

En esencia, HorusLP es una biblioteca orientada a objetos que proporciona una arquitectura muy necesaria en torno a los modelos de optimización. Al aprovechar la sintaxis orientada a objetos de Python, la biblioteca HorusLP proporciona una estructura alrededor de la cual se pueden optimizar los modelos de optimización. El resultado es una base de código desacoplada, modular y fácil de leer.

Si desea una introducción más detallada a la biblioteca principal de HorusLP con ejemplos de código, puede encontrar un tutorial aquí.

Integración HorusLP-Gurobi

Si bien la API central de HorusLP proporciona una API conveniente y de alto nivel para crear modelos de optimización, se basa en PuLP, que, si bien es capaz de utilizar Gurobi como solucionador, no tiene acceso a algunas de las capacidades más avanzadas de Gurobi.

HorusLP-Gurobi es una versión de la API de HorusLP creada con la API de Python de Gurobi. Esto le permite al usuario acceder directamente a funciones avanzadas de Gurobi, mientras mantiene la API de HorusLP consistente.

Una de las filosofías clave que guiaron el desarrollo de HorusLP-Gurobi fue la coherencia con la API central de HorusLP. Al mantener constante la estructura minimalista de HorusLP, un usuario de un solucionador de código abierto puede pasar fácilmente al uso de Gurobi instalando la API de Gurobi y cambiando las declaraciones de importación.

Para modelos simples, los modelos basados ​​en HorusLP requerirán más líneas de código que simplemente usar la API de Python de forma imperativa. Sin embargo, a medida que el proceso de desarrollo continúa y los modelos se vuelven más complejos, los diseños declarativos y orientados a objetos de la API de HorusLP facilitarán la depuración y el desarrollo. La orientación a objetos también hará que el modelo sea más legible, ya que la definición del modelo crea, centraliza y delinea claramente los objetivos, restricciones y variables, etc.

Sin más preámbulos, ¡vamos a sumergirnos en algunos ejemplos de código!

Ejemplos de código

API básica de HorusLP

Debido a que HorusLP-Gurobi mantiene la API consistente, el código del tutorial central de HorusLP se puede transferir con un simple cambio en las importaciones. Sin embargo, para usar HoruLP-Gurobi, deberá asegurarse de tener instalado el optimizador Gurobi y la interfaz Python de Gurobi. Puede obtener Gurobi poniéndose en contacto con ellos aquí.

Una vez que instale Gurobi, ¡podemos comenzar con la codificación con HorusLP-Gurobi! Comencemos instalando el paquete requerido:

 Pip install horuslp horuslp-gurobi

Una vez que se completa la instalación, ¡podemos comenzar a usar HorusLP-Gurobi! Recuerde el ejemplo anterior del problema de la mochila. Podemos usar HorusLP-Gurobi para modelar el problema de la siguiente manera:

Primero, importe las bibliotecas relevantes.

 from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE

Defina algunas variables.

 class KnapsackVariables(VariableManager): # we define variables by declaring the “vars” class variable vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn')

Ahora, podemos definir las restricciones usando la clase de restricciones.

 class SizeConstraint(Constraint): # implement the 'define' function, the variables will get passed in by name def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Entonces podemos implementar el objetivo de una manera similar.

 class ValueObjective(ObjectiveComponent): # implement the define function and return the objective expression def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

Y finalmente, podemos definir el problema.

 class KnapsackProblem(Problem): # defining a problem using the Horus API is a matter of setting variables in the subclass variables = KnapsackVariables objective = ValueObjective # constraints is a list variable, since there can be multiple constraints,. constraints = [SizeConstraint] # make sure to set the sense! sense = MAXIMIZE

E instanciamos el problema y llamamos a la función solve. Aquí es donde ocurre la magia.

 prob = KnapsackProblem() # instantiate prob.solve() # call the solve method prob.print_results() # optional: print the standard Horus debug report print(prob.result_variables) # optional: print the variable results as a list

Ejecute el código y debería ver el siguiente resultado:

 Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% KnapsackProblem: Optimal camera -0.0 figurine 1.0 cider -0.0 horn 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'camera': -0.0, 'figurine': 1.0, 'cider': -0.0, 'horn': 1.0}

La primera parte es el solucionador de Gurobi y la segunda parte es la salida de HorusLP. Como puede ver, el algoritmo recomienda que tomemos la estatuilla y el cuerno, lo que da como resultado 14 libras de artículos con un valor de $17.

Uno de los beneficios de usar HorusLP con Gurobi es que obtienes mucha información “gratis”. Gran parte de la información que uno normalmente querría ver durante el desarrollo, como el valor de cada variable, el valor del objetivo final y los valores de las restricciones, se calcula automáticamente y se genera en un formato fácil de leer.

Si ha leído el artículo anterior sobre el núcleo de HorusLP, notará que esta es casi exactamente la misma API. Para mantener la API simple, las interfaces de HorusLP core y HorsLP-Gurobi son idénticas, con diferencias entre los solucionadores abstraídas en la implementación de la superclase.

Por lo tanto, dejaremos la introducción de HorusLP a este simple ejemplo; En el artículo anterior se pueden encontrar ejemplos más complejos que demuestran las características avanzadas de HorusLP.

Características de Gurobi

Gurobi proporciona muchas funciones avanzadas para resolver problemas complejos. Se puede acceder a la mayoría de las características a través del objeto Modelo. Para permitir una compatibilidad total con la API de Gurobi, se puede acceder fácilmente al objeto modelo desde la clase de problema como model .

Por ejemplo, si desea escribir el archivo MPS del modelo de mochila, en Gurobi puede escribir algo como m.write('knapsack.mps') . Mientras usa HorusLP-Gurobi, simplemente puede:

 # import the problem as usual from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE # define the constraint class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 # define the objectives as above class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn # define the variables used by the constraints and objectives class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') # define the problem as in the above example class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE # instantiate the problem. We don't need to call solve or print any reports. prob = KnapsackProblem() prob.model.write('knapsack.mps') # this is the only bit of new code!

Y debería ver el archivo MPS en su directorio de trabajo.

Puede usar esta interfaz para acceder a funciones avanzadas de Gurobi, como calcular IIS, crear devoluciones de llamada o dar sugerencias variables.

Características avanzadas de Gurobi a su servicio

Hoy vimos una versión de la biblioteca HorusLP construida sobre la API Gurobi Python. Además de las funciones de informes y depuración del núcleo de HorusLP, ahora tiene acceso a todas las funciones avanzadas de Gurobi accesibles sin problemas a través de la integración con la API de Python de Gurobi.

Si es un usuario actual de Gurobi o alguien interesado en usar la optimización de Gurobi, ¡espero que pruebe HorusLP! Puede encontrar código de ejemplo, hacer sugerencias o contribuir a HorusLP-Gurobi en GitHub.