Arquitectura de algoritmos de optimización con HorusLP

La investigación de operaciones y la optimización convexa es un campo de las matemáticas aplicadas que ha encontrado una amplia gama de aplicaciones comerciales a lo largo de los años. A medida que el poder de cómputo se volvió más asequible y ampliamente disponible, los investigadores comenzaron a construir algoritmos de optimización cada vez más sofisticados para ayudarlos a tomar mejores decisiones. Hoy en día, las aplicaciones impulsadas por la investigación de operaciones impulsan todo, desde el enrutamiento en la logística global hasta el suavizado de la producción de electricidad en la industria energética.

A medida que la tecnología subyacente creció en complejidad, se creó un nuevo conjunto de herramientas para ayudar a los investigadores y desarrolladores a trabajar de manera más productiva. Estas herramientas, como AMPL, CVXPY y PuLP, permiten a los desarrolladores definir, crear y ejecutar rápidamente algoritmos de optimización e interactuar con una amplia variedad de solucionadores.

Sin embargo, mientras que las tecnologías de optimización y las necesidades comerciales continúan creciendo en sofisticación, la mayoría de estas herramientas se han mantenido más o menos igual y no evolucionaron lo suficientemente rápido para satisfacer las necesidades de la industria. Como resultado, desarrollar, administrar, depurar y ajustar estos algoritmos a menudo requiere una gran cantidad de sobrecarga cognitiva, especialmente en un entorno empresarial de rápido movimiento.

Hoy me gustaría presentar HorusLP, una biblioteca de optimización de Python que ayuda con la arquitectura de los flujos de trabajo de desarrollo de algoritmos. Hablaremos sobre los problemas que la herramienta está diseñada para resolver, luego brindaremos una descripción general rápida de la biblioteca de Python y crearemos algunos algoritmos de optimización de ejemplo.

Problemas que enfrentan los desarrolladores de algoritmos de optimización

Uno de los problemas perennes que enfrentan la mayoría de los desarrolladores es el equilibrio entre crear un software idiomático, eficiente y que se pueda mantener, y entregar un producto dentro de las limitaciones de tiempo del proyecto. Ya sea que esté trabajando en una aplicación basada en un navegador, una API web o un microservicio de autenticación de usuarios, a menudo existe una compensación entre la forma "correcta" y la forma "rápida" de lograr sus objetivos. Esta compensación inherente se vuelve más destacada a medida que aumenta la complejidad del producto.

En la mayoría de las disciplinas, un desarrollador puede aliviar este problema eligiendo un marco o biblioteca que ayude con la arquitectura. En el front-end orientado a la web, muchos desarrolladores eligen React o Angular; en el mundo del desarrollo de API, los ingenieros de software pueden elegir entre Django, ASP.NET MVC o Play, entre muchos otros. Sin embargo, cuando se trata del humilde desarrollador de algoritmos de optimización, existen muy pocas herramientas de arquitectura para ayudar a administrar la complejidad de la arquitectura. Se deja que el desarrollador maneje las variables, las restricciones y varios objetivos por su cuenta. Además, los algoritmos de investigación de operaciones generalmente son difíciles de introspeccionar, lo que exacerba el problema.

El objetivo principal de HorusLP es proporcionar un marco arquitectónico para desarrollar algoritmos de optimización. Al proporcionar coherencia estructural, el marco facilita la organización y permite a los desarrolladores centrarse en lo que mejor saben hacer: crear algoritmos.

Desafíos típicos del flujo de trabajo de optimización

Hay varias fuentes importantes de complejidad al desarrollar algoritmos OR:

Complejidad de las variables

• Con frecuencia, es necesario agregar variables para adaptarse a los requisitos comerciales adicionales y no existe una manera fácil de rastrearlas para usarlas en definiciones de modelos e informes más adelante.
• Las variables relacionadas deben agruparse y rastrearse, y no hay una forma obvia de administrarlas.

Complejidad de las restricciones

• Es necesario agregar y quitar restricciones para admitir varios escenarios y realizar la depuración, pero no hay un lugar obvio para agregar o quitar restricciones.
• Las restricciones a menudo están relacionadas o dependen unas de otras, y no existe una forma natural de expresar sus relaciones.

Complejidad de los objetivos

• Las expresiones objetivas pueden volverse difíciles de manejar si tienen varios componentes. Esto puede empeorar si se ponderan los diversos componentes y es necesario ajustar las ponderaciones en función de los requisitos comerciales.

Complejidad de la depuración

• No hay una manera fácil de ver los resultados del modelo durante el desarrollo. Un desarrollador tiene que imprimir explícitamente nuevas variables y valores de restricción para ver los resultados. Esto conduce a un código duplicado y un desarrollo más lento.
• Cuando agregar una restricción hace que el modelo se vuelva inviable, puede que no sea obvio por qué la restricción hizo que el modelo se volviera inviable. Por lo general, los desarrolladores tienen que eliminar varias restricciones y buscar la incompatibilidad a través de prueba y error.

HorusLP espera hacer que estos desafíos sean más manejables proporcionando estructura, herramientas y mejores prácticas para mejorar la productividad del desarrollador y la capacidad de mantenimiento del producto.

Tutorial de HorusLP: algoritmo de optimización y descripción general de la API

¡Sin más preámbulos, profundicemos y veamos qué puede hacer la biblioteca HorusLP por usted!

Dado que HorusLP se basa en Python y PuLP, querremos instalarlos usando pip. Ejecute lo siguiente en su línea de comando:

 Pip install horuslp pulp

Una vez que se complete la instalación, avancemos y abramos un archivo de Python. Implementaremos el problema de la mochila de mi artículo anterior sobre investigación de operaciones.

La biblioteca HorusLP tiene una API declarativa muy simple y muy poco repetitivo. Comencemos importando las clases y variables necesarias:

 from horuslp.core.Variables import BinaryVariable # we will be using binary variables, so we will import the BinaryVariable class from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent # We will also need to import the constraint class, variable manager class, the main problem class, and the objective class to define the objective. from horuslp.core.constants import MAXIMIZE # since we're maximizing the resulting value, we want to import this constant

Una vez que hayamos importado todas las variables, definamos las variables que necesitamos para este problema. Hacemos esto creando una subclase de administrador de variables y llenándola con las variables binarias:

 class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), # the first argument is the name of the variable BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') ]

Ahora que las variables están definidas, definamos las restricciones. Creamos restricciones subclasificando la clase de restricción principal e implementando su función "definir".

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

En la función de definición, puede solicitar las variables requeridas por nombre. El marco ubicará la variable en el administrador de variables y la pasará a la función de definición.

Después de implementar la restricción, podemos implementar el objetivo. Como es un objetivo simple, usaremos ObjectiveComponent :

 class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

La función de definición tiene una configuración muy similar a la función de definición de la clase de restricción. Sin embargo, en lugar de devolver una expresión de restricción, devolvemos una expresión afín.

Ahora que las variables, restricciones y objetivos están definidos, definamos el modelo:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE

Para construir el modelo, creamos una clase que es una subclase de la clase Problema y especificamos las variables, los objetivos, las restricciones y el sentido. Con el problema especificado, podemos resolver el problema:

 prob = KnapsackProblem() prob.solve()

Después de la resolución, podemos imprimir los resultados usando la función print_results de la clase del problema. También podemos acceder al valor de variables específicas mirando la clase result_variables .

 prob.print_results() print(prob.result_variables)

Ejecute el script y debería ver el siguiente resultado:

 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}

Debería ver el estado del problema, el valor final de las variables, el valor objetivo y el valor de la expresión de restricción. También vemos los valores resultantes de las variables como un diccionario.

Y ahí lo tenemos, ¡nuestro primer problema de HorusLP en unas 35 líneas!

En los próximos ejemplos, exploraremos algunas características más sofisticadas de la biblioteca HorusLP.

Uso de grupos de variables

A veces, las variables están relacionadas y pertenecen a un grupo lógico. En el caso del problema de la mochila, todas las variables se pueden colocar en un grupo de objetos. Podemos refactorizar el código para usar el grupo de variables. ¡Asegúrese de guardar el código de la sección anterior, ya que nos referiremos a él en tutoriales posteriores!

Cambie las declaraciones de importación así:

 from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp.core.constants import MAXIMIZE

Ahora también necesitamos cambiar las declaraciones de variables de la mochila de esta manera:

 class KnapsackVariables(VariableManager): vars = [ BinaryVariableGroup('objects', [ 'camera', 'figurine', 'cider', 'horn' ]) ]

El primer argumento es el nombre del grupo de variables, la segunda variable es una lista de nombres para las variables dentro de ese grupo.

Ahora necesitamos cambiar las definiciones de restricción y objetivo. En lugar de preguntar por los nombres individuales, lo haremos por el grupo de variables, que se pasará como un diccionario donde las claves son los nombres y los valores son las variables. Cambie las definiciones de restricciones y objetivos así:

 class SizeConstraint(Constraint): def define(self, objects): return 2 * objects['camera'] + 4 * objects['figurine'] + 7 * objects['cider'] + 10 * objects['horn'] <= 15 class ValueObjective(ObjectiveComponent): def define(self, objects): return 5 * objects['camera'] + 7 * objects['figurine'] + 2 * objects['cider'] + 10 * objects['horn']

Ahora podemos usar la misma definición de problema y ejecutar comandos:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results() print(prob.result_variables)

Deberías ver esto en tu salida:

 KnapsackProblem: Optimal objects[camera] 0.0 objects[figurine] 1.0 objects[cider] 0.0 objects[horn] 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'objects': {'camera': 0.0, 'figuring': 1.0, 'cider': 0.0, 'horn': 1.0}}

Gestión de múltiples restricciones

Los modelos con una sola restricción son relativamente raros. Cuando se trabaja con múltiples restricciones, es bueno tener todas las restricciones en un solo lugar para que puedan ser rastreadas y administradas fácilmente. HorusLP lo hace natural.

Supongamos, por ejemplo, que quisiéramos ver cómo cambiarían los resultados si forzáramos al modelo a agregar una cámara a nuestra mochila. Implementaríamos una restricción adicional y la agregaríamos a nuestra definición de problema.

Regrese al modelo que implementamos en el primer tutorial. Agregue la siguiente restricción:

 class MustHaveItemConstraint(Constraint): def define(self, camera): return camera >= 1

Para agregar la restricción al modelo, simplemente necesitamos agregarla a la definición del problema de la siguiente manera:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, MustHaveItemConstraint # just add this line :) ] sense = MAXIMIZE

Ejecute el problema y debería ver el siguiente resultado:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

Debería ver la nueva restricción que se imprime en la salida estándar y los valores variables óptimos modificados.

Gestión de restricciones dependientes y grupos de restricciones

Las restricciones suelen estar relacionadas entre sí porque dependen unas de otras o porque pertenecen lógicamente al mismo grupo.

Por ejemplo, si desea establecer una restricción para limitar la suma del valor absoluto de un conjunto de variables, primero debe especificar restricciones para expresar las relaciones de valor absoluto entre las variables deseadas y luego especificar los límites de valor absoluto. A veces, necesita aplicar restricciones similares a un grupo de variables para expresar una relación específica entre variables.

Para expresar estas agrupaciones, podemos usar la función de restricciones dependientes de nuestras definiciones de restricciones. Para ver cómo se puede usar la función de restricción dependiente, refactorice SizeConstraint del problema anterior de la siguiente manera:

 class SizeConstraint(Constraint): dependent_constraints = [MustHaveItemConstraint] def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Y ahora, para probar que las restricciones dependientes se implementan automáticamente, MustHaveItemConstraint de la definición del problema:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, ] sense = MAXIMIZE

Y ejecute el código nuevamente, y debería ver lo siguiente en la salida estándar:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

¡Parece que MustHaveItemConstraint está implementado! Para ver un ejemplo más complejo de cómo se puede usar la restricción dependiente, consulte el ejemplo de asignación de personal al final del tutorial.

Gestión de múltiples objetivos ponderados

A menudo, durante el desarrollo de nuestros algoritmos de optimización, encontraremos una expresión objetiva compuesta de múltiples partes. Como parte de nuestra experimentación, podemos cambiar la ponderación de varios componentes objetivos para sesgar el algoritmo hacia el resultado deseado. CombinedObjective proporciona una forma clara y sencilla de expresar esto.

Supongamos que quisiéramos sesgar el algoritmo para elegir la figurilla y la sidra. Refactoricemos el código de la sección anterior para usar CombinedObjective .

Primero, importe la clase CombinedObjective así:

 from horuslp.core import CombinedObjective

Podemos implementar un componente objetivo independiente así:

 class ILoveCiderFigurineObjectiveComponent(ObjectiveComponent): def define(self, figurine, cider): return figurine + cider

Ahora podemos combinar el objetivo de valor y el objetivo de sidra/figurilla implementando un CombinedObjective :

 class Combined(CombinedObjective): objectives = [ (ILoveCiderFigurineObjectiveComponent, 2), # first argument is the objective, second argument is the weight (ValueObjectiveComponent, 1) ]

Ahora cambiemos la definición del problema así:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = Combined constraints = [SizeConstraint] sense = MAXIMIZE

Ejecute el problema y debería ver el siguiente resultado:

 KnapsackProblem: Optimal camera 1.0 figurine 1.0 cider 1.0 horn 0.0 Combined: 18.00 ILoveCiderFigurineObjectiveComponent: 2.00 * 2 ValueObjectiveComponent: 14.00 * 1 SizeConstraint: 13.00 MustHaveItemConstraint: 1.00

La salida describirá el valor objetivo combinado, el valor de cada uno de los componentes objetivos, el peso y, por supuesto, el valor de todas las restricciones.

Encontrar restricciones incompatibles

Al desarrollar algoritmos, a menudo nos encontramos con modelos inviables. Si el modelo es complejo, puede ser un desafío determinar por qué el modelo es repentinamente inviable. HorusLP tiene una herramienta útil para ayudarte en esos casos.

Supongamos que estamos agregando restricciones y terminamos con el siguiente conjunto de restricciones:

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 class SizeConstraint2(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 20 class MustHaveItemConstraint(Constraint): def define(self, cider): return cider >= 1 class IncompatibleConstraint1(Constraint): def define(self, camera): return camera >= 1 class IncompatibleConstraint2(Constraint): def define(self, camera): return camera <= 0

Tenemos un par de restricciones en el tamaño total de los artículos en la mochila, una restricción que requiere que la sidra esté en la mochila y un conjunto incompatible de restricciones que requieren que la cámara esté dentro y fuera de la mochila. (Por supuesto, en un algoritmo del mundo real, las restricciones generalmente no son tan obvias e involucran relaciones y restricciones de variables complejas).

Supongamos también que las restricciones se agrupan de la siguiente manera, lo que quizás dificulte la detección:

 class CombinedConstraints1(Constraint): dependent_constraints = [SizeConstraint2, IncompatibleConstraint1] class CombinedConstraints2(Constraint): dependent_constraints = [SizeConstraint, IncompatibleConstraint2] # MustHaveItemConstraint will be included in the problem definition independently

Aquí está la definición del problema:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [CombinedConstraints1, CombinedConstraints2, MustHaveItemConstraint] sense = MAXIMIZE

Ejecute el problema y debería ver el siguiente resultado:

 KnapsackProblem: Infeasible

¡Oh, no! qué hacemos? Si estamos utilizando la mayoría de las herramientas, debemos embarcarnos en una sesión de depuración difícil en la que reducimos las restricciones potencialmente conflictivas una por una. Afortunadamente, HorusLP tiene una función de búsqueda de incompatibilidad para ayudarlo a reducir las restricciones incompatibles más rápido. La forma más sencilla de usar la función de búsqueda de incompatibilidad es cambiar la llamada print_results de la siguiente manera:

 prob.print_results(find_infeasible=True)

¡Simple como eso! Ejecute el código, y ahora debería ver lo siguiente como resultado:

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('CombinedConstraints1', 'CombinedConstraints2')

¡Genial! Ahora hemos establecido que MustHaveItemConstraint no es la causa de la inviabilidad y que el problema se debe a CombinedConstraints1 y CombinedConstraints2 .

Eso nos da alguna información, pero entre las restricciones combinadas hay cuatro restricciones dependientes. ¿Podemos identificar cuáles de las cuatro restricciones son incompatibles? Bueno, sí. Modifique su llamada print_results esta manera:

 prob.print_results(find_infeasible=True, deep_infeasibility_search=True)

Esto hará que la búsqueda de inviabilidad amplíe las restricciones dependientes para que obtengamos una imagen mucho más granular de lo que está causando la inviabilidad. Ejecute esto y debería ver el siguiente resultado:

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('IncompatibleConstraint1', 'IncompatibleConstraint2')

Si bien es tentador ejecutar una búsqueda de inviabilidad profunda cada vez, para problemas realistas con una gran cantidad de restricciones totales, la búsqueda de inviabilidad profunda puede requerir muchos recursos y consumir mucho tiempo. Por lo tanto, es mejor ejecutar la búsqueda de inviabilidad básica para reducir la posibilidad y ejecutar la búsqueda de inviabilidad profunda en un subconjunto más pequeño después de realizar una investigación manual.

Creación de algoritmos a partir de archivos de datos

Al construir modelos, rara vez tenemos el lujo de codificar cada restricción y variable. A menudo, nuestro programa debe ser lo suficientemente flexible para cambiar el modelo en función de los datos de entrada. Supongamos que, en lugar de una entrada codificada, queremos construir nuestro problema de mochila a partir del siguiente JSON:

 { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 }

Podemos hacer esto confiando en el apoyo de los kwargs de la función "definir" que implementamos para restricciones y objetivos.

Modifiquemos el código del problema de la mochila simple (el problema que implementamos en la sección 1 del tutorial). Primero, coloquemos la cadena JSON en el archivo. Por supuesto, normalmente lo leeríamos de una fuente externa, pero por simplicidad, guardemos todo en un archivo. Agregue lo siguiente a su código:

 JSON = ''' { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 } '''

También asegurémonos de que nuestro programa pueda analizarlo. Agregue lo siguiente a sus declaraciones de importación:

 Import json

Ahora, modifiquemos nuestro código de configuración variable de la siguiente manera:

 mip_cfg = json.loads(JSON) class KnapsackVariables(VariableManager): vars = [ BinaryVariable(i['name']) for i in mip_cfg['items'] ]

Esto definirá una variable para cada uno de los elementos en el JSON y le dará el nombre apropiado.

Cambiemos las definiciones de restricción y objetivo así:

 class CapacityConstraint(Constraint): def define(self, **kwargs): item_dict = {i['name']: i['weight'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs) <= mip_cfg['capacity'] class ValueObjective(ObjectiveComponent): def define(self, **kwargs): item_dict = {i['name']: i['value'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs)

Al solicitar **kwargs en lugar de variables específicas, la función define obtiene un diccionario que contiene todas las variables por nombre. La función de definición de restricciones puede entonces acceder a las variables del diccionario.

Nota: Para grupos de variables, será un diccionario anidado donde el primer nivel es el nombre del grupo y el segundo nivel es el nombre de la variable.

El resto es bastante sencillo:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

Ejecute este programa y debería ver el siguiente resultado:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00

Definición de métricas personalizadas en HorusLP

A veces, tanto con fines de depuración como de generación de informes, crearemos métricas personalizadas que no se expresan directamente en el objetivo o como una restricción. HorusLP tiene una función para simplificar la especificación de métricas personalizadas.

Supongamos que quisiéramos hacer un seguimiento de cuántas frutas estaba poniendo en la mochila el modelo de nuestra sección anterior. Para realizar un seguimiento de esto, podemos definir una métrica personalizada. Comencemos importando la clase base Metrics:

 From horuslp.core import Metric

Ahora definamos la métrica personalizada:

 class NumFruits(Metric): name = "Number of Fruits" def define(self, apple, banana): return apple + banana

Como puede ver, la interfaz definida se parece mucho a las de la clase de componente de restricción y objetivo. Si ha seguido el tutorial hasta ahora, esto debería ser bastante familiar para usted.

Ahora necesitamos agregar la métrica a la definición del problema. La interfaz aquí nuevamente es muy similar a la definición de restricción:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective metrics = [NumFruits] sense = MAXIMIZE

Ejecute esto y debería ver el siguiente resultado:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00 Number of Fruits: 1.00

Puede ver la cantidad de frutas impresas en la parte inferior.

Resolver un problema más complejo: dos mochilas

Analicemos un ejemplo un poco más complejo. Supongamos que en lugar de una sola mochila, tenemos un bolso y una maleta. También tenemos dos clases de objetos, duraderos y frágiles. La maleta, al ser más protectora, puede contener tanto mercancías frágiles como duraderas. La bolsa, por otro lado, solo puede contener bienes duraderos. Supongamos también que los datos de los elementos se proporcionan en el siguiente JSON:

 { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 }

Veamos cómo cambia esto el modelo. Comencemos con una pizarra en blanco ya que el modelo será bastante diferente. Comience con la configuración del problema:

 import json from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, Metric, ObjectiveComponent from horuslp.core.constants import MAXIMIZE JSON = ''' { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 } ''' mip_cfg = json.loads(JSON)

Ahora configuremos las variables. Configuraremos una variable binaria para cada combinación posible de artículo/contenedor.

 class KnapsackVariables(VariableManager): vars = [ # suitcase can hold both fragile and durable goods BinaryVariableGroup('suitcase_f', [i['name'] for i in mip_cfg['fragile']]), BinaryVariableGroup('suitcase_d', [i['name'] for i in mip_cfg['durable']]), # bag can only hold durable goods. BinaryVariableGroup('bag_d', [i['name'] for i in mip_cfg['durable']]) ]

Ahora queremos implementar restricciones de peso tanto para la maleta como para el bolso.

 class SuitcaseCapacityConstraint(Constraint): def define(self, suitcase_d, suitcase_f): fragile_weight = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_weight = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_weight + durable_weight <= mip_cfg['suitcase_capacity'] class BagCapacityConstraint(Constraint): def define(self, bag_d): durable_weight = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return durable_weight <= mip_cfg['bag_capacity']

Ahora necesitamos implementar una restricción un poco más compleja, la restricción que asegura que un artículo no entre tanto en la maleta como en la bolsa, es decir, si la variable "en la maleta" es 1, entonces "en la bolsa" variable debe ser cero y viceversa. Por supuesto, queremos asegurarnos de permitir instancias en las que el artículo no termine en ningún contenedor.

Para agregar esta restricción, debemos iterar sobre todos los artículos duraderos, encontrar la variable "en la maleta" y la variable "en la bolsa" y afirmar que la suma de estas variables es menor que 1.

Podemos definir dinámicamente las restricciones dependientes con bastante facilidad en HorusLP:

 class UniquenessConstraints(Constraint): def __init__(self): super(UniquenessConstraints, self).__init__() # call the dependent constraint builder function for every durable item, and push them into dependent constraints. dependent_constraints = [self.define_uniqueness_constraint(item) for item in mip_cfg['durable']] self.dependent_constraints = dependent_constraints def define_uniqueness_constraint(self, item): # classes are first-class objects in python, so we can define a class within this function and return it class UQConstraint(Constraint): # we name the constraint based on the item this is for, so that debugging is easier. name = "Uniqueness_%s" % item['name'] def define(self, suitcase_d, bag_d): # the define function can access the variables much in the same way as other functions return suitcase_d[item['name']] + bag_d[item['name']] <= 1 return UQConstraint

Ahora que las restricciones están definidas, construyamos el objetivo. El objetivo es simple la suma de todos los valores que obtenemos de todos los artículos que están en los contenedores. Por lo tanto:

 class TotalValueObjective(ObjectiveComponent): def define(self, suitcase_f, suitcase_d, bag_d): fragile_value = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_value_s = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) durable_value_d = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_value + durable_value_s + durable_value_d

También definamos algunas métricas personalizadas para que podamos ver de un vistazo cuánto peso se puso en la bolsa y la maleta, así como qué parte del peso de la maleta provino de bienes duraderos y frágiles:

 class SuitcaseFragileWeightMetric(Metric): def define(self, suitcase_f): return sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) class SuitcaseDurableWeightMetric(Metric): def define(self, suitcase_d): return sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) class BagWeightMetric(Metric): def define(self, bag_d): return sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']])

Ahora que tenemos todas las piezas terminadas, instanciamos el problema y ejecutamos el modelo:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [SuitcaseCapacityConstraint, BagCapacityConstraint, UniquenessConstraints] objective = TotalValueObjective metrics = [SuitcaseDurableValueMetric, SuitcaseFragileValueMetric, BagValueMetric] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

Ejecute esto, y debería ver el siguiente resultado en su salida estándar:

 KnapsackProblem: Optimal suitcase_f[camera] 1.0 suitcase_f[glasses] 1.0 suitcase_f[apple] 1.0 suitcase_f[pear] 0.0 suitcase_f[banana] 1.0 suitcase_d[figurine] 0.0 suitcase_d[horn] 0.0 suitcase_d[leatherman] 0.0 bag_d[figurine] 1.0 bag_d[horn] 1.0 bag_d[leatherman] 1.0 TotalValueObjective: 32.00 SuitcaseCapacityConstraint: 15.00 BagCapacityConstraint: 17.00 Uniqueness_figurine: 1.00 Uniqueness_horn: 1.00 Uniqueness_leatherman: 1.00 SuitcaseDurableWeightMetric: 0.00 SuitcaseFragileWeightMetric: 15.00 BagWeightMetric: 17.00

Entonces, la cámara, los anteojos, la manzana y el plátano van a la maleta por un total de 15 unidades de peso, la figurilla, el cuerno y el hombre de cuero van a la bolsa por un total de 17 unidades de peso. El valor total de los bienes sale a 32 unidades de valor. Curiosamente, ninguno de los bienes duraderos terminó en la maleta, probablemente porque la bolsa tenía suficiente capacidad para contener todos los bienes duraderos.

Un escenario más amplio y realista: el problema de la dotación de personal

Si has llegado hasta aquí en nuestro tutorial de HorusLP, ¡felicidades! Ahora tiene una buena idea de cómo usar HorusLP.

Sin embargo, todos los ejemplos en los que hemos estado trabajando hasta ahora han sido permutaciones del problema de la mochila, y algunos de los requisitos y parámetros son poco realistas. Trabajemos juntos en un problema más para ver cómo HorusLP puede resolver un problema más realista. Trabajaremos en el problema de personal descrito en la segunda mitad de mi artículo anterior de Toptal.

En aras del tiempo, iremos directamente a la versión final del modelo (con conflictos personales, regulaciones laborales y asignaciones para trabajadores temporales), pero la implementación del modelo inicial más simple también está disponible en GitHub.

Entonces, comencemos por configurar el problema:

 from horuslp.core.Variables import BinaryVariableGroup, IntegerVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent, CombinedObjective from horuslp.core.constants import MINIMIZE shift_requirements = [1, 4, 3, 5, 2] # the number of workers we need to staff for each shift # the availability and pay rates of each of the employees workers = { "Melisandre": { "availability": [0, 1, 4], "cost": 20 }, "Bran": { "availability": [1, 2, 3, 4], "cost": 15 }, "Cersei": { "availability": [2, 3], "cost": 35 }, "Daenerys": { "availability": [3, 4], "cost": 35 }, "Theon": { "availability": [1, 3, 4], "cost": 10 }, "Jon": { "availability": [0, 2, 4], "cost": 25 }, "Tyrion": { "availability": [1, 3, 4], "cost": 30 }, "Jaime": { "availability": [1, 2, 4], "cost": 20 }, "Arya": { "availability": [0, 1, 3], "cost": 20 } } # the following people can't work together, sadly. ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } # Dothraki Staffing Corp will provide us with expensive temp workers DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

Ahora definamos las variables, que en este caso serían variables binarias que determinan si un trabajador debe trabajar su turno, y variables enteras que determinan cuántos dothrakis contratamos para cada turno:

 class StaffingVariables(VariableManager): vars = [] def __init__(self): # like dependent constraints, we can dynamically define variables in the init function super(StaffingVariables, self).__init__() # regular workers varkeys = [] for employee, availability_info in workers.items(): for shift in availability_info['availability']: varkeys.append((employee, shift)) self.vars.append(BinaryVariableGroup('employee_shifts', varkeys)) # dothrakis dothraki_keys = [i for i in range(len(shift_requirements))] self.vars.append(IntegerVariableGroup('dothraki_workers', dothraki_keys, 0, DOTHRAKI_COST))

Ahora implementemos la restricción que requiere que tengamos suficiente personal para cada turno:

 class SufficientStaffingConstraint(Constraint): # we need to staff people sufficiently dependent_constraints = [] def __init__(self): super(SufficientStaffingConstraint, self).__init__() for shift_num, shift_req in enumerate(shift_requirements): self.dependent_constraints.append(self.build_shift_constraint(shift_num, shift_req)) def build_shift_constraint(self, sn, sr): class ShiftConstraint(Constraint): name = "shift_requirement_%d" % sn def define(self, employee_shifts, dothraki_workers): variables = [val for key, val in employee_shifts.items() if key[1] == sn] variables.append(dothraki_workers[sn]) return sum(variables) >= sr return ShiftConstraint

Ahora, necesitamos implementar las restricciones que impiden que personas específicas trabajen entre sí:

 class PersonalConflictsConstraint(Constraint): # some people can't work together dependent_constraints = [] def __init__(self): super(PersonalConflictsConstraint, self).__init__() for person_1, person_2 in ban_list: for shift in range(len(shift_requirements)): self.dependent_constraints.append(self.build_conflict_constraint(person_1, person_2, shift)) def build_conflict_constraint(self, p1, p2, s): class ConflictConstraint(Constraint): name = "Conflict_%s_%s_%d" % (p1, p2, s) def define(self, employee_shifts): if (p1, s) in employee_shifts and (p2, s) in employee_shifts: return employee_shifts[p1, s] + employee_shifts[p2, s] <= 1 return True # returning true will make the constraint do nothing return ConflictConstraint

And finally the labor standards constraint. We'll implement this one slightly differently for demonstrative purposes:

 class LaborStandardsConstraint(Constraint): # we can make someone work more than two shifts a day. dependent_constraints = [] def __init__(self): super(LaborStandardsConstraint, self).__init__() for worker in workers.keys(): # we don't need a constraint builder function, but in those circumstances # we need to set the needed values as class variables and refer to them # via the self keyword due to how python's closure system works class LaborConstraint(Constraint): # we can't use worker directly! wk = worker name = "labor_standard_%s" % worker def define(self, employee_shifts): # we need to access the worker using self. Change self.wk to worker to see # why we need to do this worker_vars = [var for key, var in employee_shifts.items() if key[0] == self.wk] return sum(worker_vars) <= 2 self.dependent_constraints.append(LaborConstraint)

And now let's set up the objectives. The dothraki cost and regular employee costs are calculated very differently, so we'll put them in separate objective components:

 class CostObjective(ObjectiveComponent): # this is the cost function for all the named workers def define(self, employee_shifts, dothraki_workers): costs = [ workers[key[0]]['cost'] * var for key, var in employee_shifts.items() ] return sum(costs) class DothrakiCostObjective(ObjectiveComponent): # don't forget the Dothrakis def define(self, dothraki_workers): dothraki_costs = [ dothraki_workers[sn] * DOTHRAKI_COST for sn in dothraki_workers ] return sum(dothraki_costs) class TotalCostObjective(CombinedObjective): objectives = [ (CostObjective, 1), (DothrakiCostObjective, 1) ]

And now we can define and run the problem:

 class StaffingProblem(Problem): variables = StaffingVariables objective = TotalCostObjective constraints = [SufficientStaffingConstraint, PersonalConflictsConstraint, LaborStandardsConstraint] sense = MINIMIZE # we're minimizing this time, not maximizing. if __name__ == '__main__': prob = StaffingProblem() prob.solve() prob.print_results()

Run the script and you should see the following:

 StaffingProblem: Optimal employee_shifts[('Melisandre', 0)] 0.0 employee_shifts[('Melisandre', 1)] 1.0 employee_shifts[('Melisandre', 4)] 1.0 employee_shifts[('Bran', 1)] 0.0 employee_shifts[('Bran', 2)] 1.0 employee_shifts[('Bran', 3)] 1.0 employee_shifts[('Bran', 4)] 0.0 employee_shifts[('Cersei', 2)] 0.0 employee_shifts[('Cersei', 3)] 0.0 employee_shifts[('Daenerys', 3)] 1.0 employee_shifts[('Daenerys', 4)] 0.0 employee_shifts[('Theon', 1)] 1.0 employee_shifts[('Theon', 3)] 1.0 employee_shifts[('Theon', 4)] 0.0 employee_shifts[('Jon', 0)] 0.0 employee_shifts[('Jon', 2)] 1.0 employee_shifts[('Jon', 4)] 0.0 employee_shifts[('Tyrion', 1)] 1.0 employee_shifts[('Tyrion', 3)] 1.0 employee_shifts[('Tyrion', 4)] 0.0 employee_shifts[('Jaime', 1)] 1.0 employee_shifts[('Jaime', 2)] 0.0 employee_shifts[('Jaime', 4)] 1.0 employee_shifts[('Arya', 0)] 1.0 employee_shifts[('Arya', 1)] 0.0 employee_shifts[('Arya', 3)] 1.0 dothraki_workers[0] 0.0 dothraki_workers[1] 0.0 dothraki_workers[2] 1.0 dothraki_workers[3] 0.0 dothraki_workers[4] 0.0 TotalCostObjective: 335.00 CostObjective: 290.00 * 1 DothrakiCostObjective: 45.00 * 1 shift_requirement_0: 1.00 shift_requirement_1: 4.00 shift_requirement_2: 3.00 shift_requirement_3: 5.00 shift_requirement_4: 2.00 Conflict_Jon_Cersei_2: 1.00 Conflict_Jon_Jaime_2: 1.00 Conflict_Jon_Jaime_4: 1.00 Conflict_Daenerys_Cersei_3: 1.00 Conflict_Daenerys_Jaime_4: 1.00 Conflict_Arya_Jaime_1: 1.00 Conflict_Arya_Cersei_3: 1.00 Conflict_Arya_Melisandre_0: 1.00 Conflict_Arya_Melisandre_1: 1.00 Conflict_Jaime_Cersei_2: 0.00 labor_standard_Melisandre: 2.00 labor_standard_Bran: 2.00 labor_standard_Cersei: 0.00 labor_standard_Daenerys: 1.00 labor_standard_Theon: 2.00 labor_standard_Jon: 1.00 labor_standard_Tyrion: 2.00 labor_standard_Jaime: 2.00 labor_standard_Arya: 2.00

If you compare this with the problem we implemented in the previous tutorial, you should see that the results match.

Terminando

Congratulations for making it through our first HorusLP tutorial! You're now a competent practitioner of HorusLP.

I hope that this article convinced you of the benefits of architecting your MIP models, and that you will make use of HorusLP in your coming projects. You can find the HorusLP source code, as well as the code for all the tutorials, on GitHub. Additional HorusLP documentation and a tutorial page will be added to GitHub very soon.

As HorusLP is a fairly new project, we would love to hear from you and incorporate your input. If you have any questions, comments, or suggestions, please drop me a line either through Toptal or using the contact information you can find on GitHub. I hope to hear from you soon!