Arquitetando algoritmos de otimização com HorusLP

Pesquisa operacional e otimização convexa é um campo da matemática aplicada que encontrou amplas aplicações comerciais ao longo dos anos. À medida que o poder de computação se tornou mais acessível e amplamente disponível, os pesquisadores começaram a construir algoritmos de otimização cada vez mais sofisticados para ajudá-los a tomar melhores decisões. Hoje, os aplicativos alimentados pela pesquisa operacional potencializam tudo, desde o roteamento na logística global até a suavização da produção de eletricidade no setor de energia.

À medida que a tecnologia subjacente cresceu em complexidade, um novo conjunto de ferramentas foi criado para ajudar pesquisadores e desenvolvedores a trabalhar de forma mais produtiva. Essas ferramentas, como AMPL, CVXPY e PuLP, permitem que os desenvolvedores definam, construam e executem rapidamente algoritmos de otimização e interface com uma ampla variedade de solucionadores.

No entanto, embora as tecnologias de otimização e as necessidades de negócios continuem a crescer em sofisticação, a maioria dessas ferramentas permaneceu mais ou menos a mesma e não evoluiu com rapidez suficiente para atender às necessidades do setor. Como resultado, desenvolver, gerenciar, depurar e ajustar esses algoritmos geralmente exige uma grande quantidade de sobrecarga cognitiva, especialmente em um ambiente de negócios em movimento rápido.

Hoje, gostaria de apresentar o HorusLP, uma biblioteca de otimização Python que ajuda na arquitetura de fluxos de trabalho de desenvolvimento de algoritmos. Falaremos sobre os problemas que a ferramenta foi projetada para resolver, depois forneceremos uma visão geral rápida da biblioteca Python e construiremos alguns algoritmos de otimização de exemplo.

Problemas enfrentados pelos desenvolvedores de algoritmos de otimização

Um dos problemas perenes enfrentados pela maioria dos desenvolvedores é o equilíbrio entre construir um software sustentável, eficiente e idiomático e entregar um produto dentro das restrições de tempo do projeto. Esteja você trabalhando em um aplicativo baseado em navegador, uma API da Web ou um microsserviço de autenticação de usuário, geralmente há uma troca entre a maneira “certa” e a maneira “rápida” de atingir seus objetivos. Essa compensação inerente torna-se mais saliente à medida que a complexidade do produto aumenta.

Na maioria das disciplinas, um desenvolvedor pode aliviar esse problema escolhendo uma estrutura ou biblioteca que ajude na arquitetura. No front-end voltado para a web, muitos desenvolvedores escolhem React ou Angular; no mundo do desenvolvimento de APIs, os engenheiros de software podem escolher entre Django, ASP.NET MVC ou Play, entre muitos outros. No entanto, quando se trata do humilde desenvolvedor de algoritmos de otimização, existem muito poucas ferramentas de arquitetura para ajudar a gerenciar a complexidade da arquitetura. O desenvolvedor é deixado para gerenciar variáveis, restrições e vários objetivos por conta própria. Além disso, os algoritmos de pesquisa operacional geralmente são difíceis de introspecção, exacerbando o problema.

O principal objetivo do HorusLP é fornecer uma estrutura de arquitetura para o desenvolvimento de algoritmos de otimização. Ao fornecer consistência estrutural, a estrutura facilita a organização e permite que os desenvolvedores se concentrem no que fazem melhor: construir algoritmos.

Desafios típicos do fluxo de trabalho de otimização

Existem várias fontes principais de complexidade ao desenvolver algoritmos OR:

Complexidade de variáveis

• Muitas vezes, as variáveis ​​precisam ser adicionadas para acomodar requisitos de negócios adicionais e não há uma maneira fácil de rastreá-las para uso em definições de modelos e relatórios posteriores.
• As variáveis ​​relacionadas precisam ser agrupadas e rastreadas, e não há uma maneira óbvia de gerenciá-las.

Complexidade das restrições

• Restrições precisam ser adicionadas e removidas para dar suporte a vários cenários e realizar depuração, mas não há um lugar óbvio para adicionar ou remover restrições.
• As restrições geralmente são relacionadas/dependentes umas das outras, e não há uma maneira natural de expressar seus relacionamentos.

Complexidade dos objetivos

• Expressões objetivas podem se tornar difíceis se tiverem vários componentes. Isso pode ser agravado se os vários componentes forem ponderados e os pesos precisarem ser ajustados com base nos requisitos de negócios.

Complexidade da depuração

• Não há uma maneira fácil de ver os resultados do modelo durante o desenvolvimento. Um desenvolvedor precisa imprimir explicitamente novas variáveis ​​e valores de restrição para ver os resultados. Isso leva a código duplicado e desenvolvimento mais lento.
• Quando a adição de uma restrição faz com que o modelo se torne inviável, pode não ser óbvio por que a restrição fez com que o modelo se tornasse inviável. Normalmente, os desenvolvedores precisam eliminar várias restrições e procurar a incompatibilidade por tentativa e erro

A HorusLP espera tornar esses desafios mais gerenciáveis, fornecendo estrutura, ferramentas e práticas recomendadas para melhorar a produtividade do desenvolvedor e a manutenção do produto.

Tutorial HorusLP: algoritmo de otimização e visão geral da API

Sem mais delongas, vamos mergulhar e ver o que a biblioteca HorusLP pode fazer por você!

Como o HorusLP é baseado em Python e PuLP, vamos querer instalá-los usando pip. Execute o seguinte em sua linha de comando:

 Pip install horuslp pulp

Quando a instalação estiver concluída, vamos em frente e abrir um arquivo Python. Implementaremos o problema da mochila do meu artigo anterior sobre pesquisa operacional.

A biblioteca HorusLP tem uma API declarativa muito simples e muito pouco clichê. Vamos começar importando as classes e variáveis ​​necessárias:

 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

Depois de importar todas as variáveis, vamos definir as variáveis ​​que precisamos para este problema. Fazemos isso criando uma subclasse de gerenciador de variáveis ​​e preenchendo-a com as variáveis ​​binárias:

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

Agora que as variáveis ​​estão definidas, vamos definir as restrições. Criamos restrições subclassificando a classe de restrição principal e implementando sua função “define”.

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

Na função define, você pode solicitar as variáveis ​​necessárias pelo nome. O framework irá localizar a variável no gerenciador de variáveis ​​e passá-la para a função define.

Após a restrição ser implementada, podemos implementar o objetivo. Como é um objetivo simples, usaremos ObjectiveComponent :

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

A função define tem uma configuração muito semelhante à função define da classe de restrição. Em vez de retornar uma expressão de restrição, no entanto, retornamos uma expressão afim.

Agora que as variáveis, restrições e objetivos estão definidos, vamos definir o modelo:

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

Para construir o modelo, criamos uma classe que é uma subclasse da classe Problem e especificamos as variáveis, objetivos, restrições e o sentido. Com o problema especificado, podemos resolver o problema:

 prob = KnapsackProblem() prob.solve()

Após a resolução, podemos imprimir os resultados usando a função print_results da classe do problema. Também podemos acessar o valor de variáveis ​​específicas observando a classe result_variables .

 prob.print_results() print(prob.result_variables)

Execute o script e você deverá ver a seguinte saída:

 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}

Você deve ver o status do problema, o valor final das variáveis, o valor objetivo e o valor da expressão de restrição. Também vemos os valores resultantes das variáveis ​​como um dicionário.

E aí está, nosso primeiro problema HorusLP em cerca de 35 linhas!

Nos próximos exemplos, exploraremos alguns recursos mais sofisticados da biblioteca HorusLP.

Usando Grupos de Variáveis

Às vezes, as variáveis ​​estão relacionadas e pertencem a um grupo lógico. No caso do problema da mochila, todas as variáveis ​​podem ser colocadas em um grupo de objetos. Podemos refatorar o código para usar o grupo de variáveis. Certifique-se de salvar o código da seção anterior, pois iremos nos referir a ele em tutoriais subsequentes!

Altere as instruções de importação assim:

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

Agora também precisamos alterar as declarações da variável knapsack assim:

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

O primeiro argumento é o nome do grupo de variáveis, a segunda variável é uma lista de nomes para as variáveis ​​desse grupo.

Agora precisamos alterar as definições de restrição e objetivo. Ao invés de pedir os nomes individuais, vamos pedir o grupo de variáveis, que será passado como um dicionário onde as chaves são os nomes e os valores são as variáveis. Altere as definições de restrição e objetivo da seguinte forma:

 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']

Agora podemos usar a mesma definição de problema e executar comandos:

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

Você deve ver isso em sua saída:

 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}}

Gerenciando várias restrições

Modelos com uma única restrição são relativamente raros. Ao trabalhar com várias restrições, é bom ter todas as restrições em um só lugar para que possam ser rastreadas e gerenciadas facilmente. HorusLP torna isso natural.

Suponha, por exemplo, que queiramos ver como os resultados mudariam se forçássemos o modelo a adicionar uma câmera à nossa mochila. Implementaríamos uma restrição adicional e a adicionaríamos à nossa definição de problema.

Volte para o modelo que implementamos no primeiro tutorial. Adicione a seguinte restrição:

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

Para adicionar a restrição ao modelo, basta adicioná-la à definição do problema da seguinte forma:

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

Execute o problema e você deverá ver a seguinte saída:

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

Você deve ver a nova restrição sendo impressa no stdout e os valores de variáveis ​​ideais alterados.

Gerenciando Restrições Dependentes e Grupos de Restrições

As restrições geralmente estão relacionadas umas às outras porque são dependentes umas das outras ou porque pertencem logicamente ao mesmo grupo.

Por exemplo, se você deseja definir uma restrição para limitar a soma do valor absoluto de um conjunto de variáveis, deve primeiro especificar as restrições para expressar as relações de valor absoluto entre as variáveis ​​pretendidas e, em seguida, especificar os limites de valor absoluto. Às vezes, você precisa aplicar restrições semelhantes a um grupo de variáveis ​​para expressar um relacionamento específico entre as variáveis.

Para expressar esses agrupamentos, podemos usar o recurso de restrições dependentes de nossas definições de restrições. Para ver como o recurso de restrição dependente pode ser usado, refatore o SizeConstraint do problema anterior assim:

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

E agora para testar se as restrições dependentes são implementadas automaticamente, vamos tirar o MustHaveItemConstraint da definição do problema:

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

E execute o código novamente, e você deverá ver o seguinte em stdout:

 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 o MustHaveItemConstraint foi implementado! Para obter um exemplo mais complexo de como a restrição dependente pode ser usada, consulte o exemplo de equipe no final do tutorial.

Gerenciando vários objetivos ponderados

Muitas vezes, durante o desenvolvimento de nossos algoritmos de otimização, encontraremos uma expressão objetiva composta por várias partes. Como parte de nossa experimentação, podemos alterar a ponderação de vários componentes objetivos para influenciar o algoritmo em direção ao resultado desejado. O CombinedObjective fornece uma maneira limpa e simples de expressar isso.

Suponha que queiramos influenciar o algoritmo para escolher a estatueta e a cidra. Vamos refatorar o código da seção anterior para usar CombinedObjective .

Primeiro, importe a classe CombinedObjective assim:

 from horuslp.core import CombinedObjective

Podemos implementar um componente objetivo independente assim:

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

Agora podemos combinar o objetivo de valor e o objetivo de cidra/estatueta implementando um CombinedObjective :

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

Agora vamos alterar a definição do problema assim:

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

Execute o problema e você deverá ver a seguinte saída:

 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

A saída irá delinear o valor objetivo combinado, o valor de cada um dos componentes objetivos, o peso e, claro, o valor de todas as restrições.

Encontrando restrições incompatíveis

Ao desenvolver algoritmos, muitas vezes nos deparamos com modelos inviáveis. Se o modelo for complexo, pode ser um desafio determinar por que o modelo é subitamente inviável. HorusLP tem uma ferramenta útil para ajudá-lo nesses casos.

Suponha que estivéssemos adicionando restrições e acabamos com o seguinte conjunto de restrições:

 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

Temos algumas restrições sobre o tamanho total dos itens na mochila, uma restrição que exige que a cidra esteja na mochila e um conjunto incompatível de restrições que exigem que a câmera esteja e não na mochila. (É claro que, em um algoritmo do mundo real, as restrições geralmente não são tão óbvias e envolvem relacionamentos e restrições de variáveis ​​complexas.)

Suponha também que as restrições sejam agrupadas da seguinte maneira, talvez dificultando a detecção:

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

Aqui está a definição do problema:

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

Execute o problema e você deverá ver o seguinte resultado:

 KnapsackProblem: Infeasible

Ah não! O que nós fazemos? Se estivermos usando a maioria das ferramentas, devemos embarcar em uma sessão de depuração difícil, na qual reduzimos as restrições potencialmente conflitantes uma a uma. Felizmente, o HorusLP possui um recurso de pesquisa de incompatibilidade para ajudá-lo a restringir as restrições incompatíveis mais rapidamente. A maneira mais simples de usar o recurso de pesquisa de incompatibilidade é alterar a chamada print_results assim:

 prob.print_results(find_infeasible=True)

Simples assim! Execute o código e agora você deve ver o seguinte como saída:

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

Excelente! Agora, estabelecemos que MustHaveItemConstraint não é a causa da inviabilidade e que o problema é devido a CombinedConstraints1 e CombinedConstraints2 .

Isso nos dá algumas informações, mas entre as restrições combinadas existem quatro restrições dependentes. Podemos identificar quais das quatro restrições são incompatíveis? Bem, sim. Modifique sua chamada print_results assim:

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

Isso fará com que a pesquisa de inviabilidade expanda as restrições dependentes para que tenhamos uma imagem muito mais granular do que está causando a inviabilidade. Execute isso e você deverá ver a seguinte saída:

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

Embora seja tentador executar a pesquisa de inviabilidade profunda todas as vezes, para problemas realistas com um grande número de restrições totais, a pesquisa de inviabilidade profunda pode se tornar muito intensiva em recursos e demorada. Portanto, é melhor executar a pesquisa básica de inviabilidade para restringir a possibilidade e executar a pesquisa profunda de inviabilidade em um subconjunto menor depois de fazer alguma investigação manual.

Construindo Algoritmos a partir de Arquivos de Dados

Ao construir modelos, raramente temos o luxo de codificar todas as restrições e variáveis. Muitas vezes, nosso programa deve ser flexível o suficiente para alterar o modelo dependendo dos dados de entrada. Suponha que, em vez de uma entrada codificada, queiramos construir nosso problema da mochila a partir do seguinte 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 fazer isso contando com o suporte dos kwargs da função “define” que implementamos para restrições e objetivos.

Vamos modificar o código do problema simples da mochila (o problema que implementamos na seção 1 do tutorial). Primeiro, vamos colocar a string JSON no arquivo. É claro que normalmente o leríamos de uma fonte externa, mas para simplificar vamos manter tudo em um arquivo. Adicione o seguinte ao seu 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 } '''

Vamos também garantir que nosso programa seja capaz de analisá-lo. Adicione o seguinte às suas instruções de importação:

 Import json

Agora, vamos modificar nosso código de configuração de variável assim:

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

Isso definirá uma variável para cada um dos itens no JSON e a nomeará apropriadamente.

Vamos alterar as definições de restrição e objetivo assim:

 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)

Ao pedir **kwargs em vez de variáveis ​​específicas, a função define obtém um dicionário contendo todas as variáveis ​​por nome. A função de definição de restrição pode acessar as variáveis ​​do dicionário.

Nota: Para grupos de variáveis, será um dicionário aninhado onde o primeiro nível é o nome do grupo e o segundo nível é o nome da variável.

O resto é bem simples:

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

Execute este programa e você deverá ver a seguinte saída:

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

Definindo Métricas Personalizadas no HorusLP

Às vezes, para fins de depuração e relatórios, criamos métricas personalizadas que não são expressas diretamente no objetivo ou como uma restrição. HorusLP tem um recurso para tornar simples a especificação de métricas personalizadas.

Suponha que quiséssemos acompanhar quantas frutas o modelo da nossa seção anterior estava colocando na mochila. Para acompanhar isso, podemos definir uma métrica personalizada. Vamos começar importando a classe base Metrics:

 From horuslp.core import Metric

Agora vamos definir a métrica personalizada:

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

Como você pode ver, a interface definida se parece muito com as da classe de componente de restrição e objetivo. Se você seguiu o tutorial até agora, isso deve ser bastante familiar para você.

Agora precisamos adicionar a métrica à definição do problema. A interface aqui novamente é muito semelhante à definição de restrição:

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

Execute isso e você deverá ver a seguinte saída:

 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

Você pode ver o número de frutas impresso na parte inferior.

Resolvendo um problema mais complexo: duas mochilas

Vamos trabalhar com um exemplo um pouco mais complexo. Suponha que, em vez de uma única mochila, tenhamos uma bolsa e uma mala. Também temos duas classes de objetos, duráveis ​​e frágeis. A mala, por ser mais protetora, pode conter tanto bens frágeis quanto duráveis. A bolsa, por outro lado, só pode conter bens duráveis. Suponha também que os dados dos itens sejam fornecidos no seguinte 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 }

Vamos ver como isso muda o modelo. Vamos começar com uma lousa em branco, pois o modelo será bem diferente. Comece com a configuração do 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)

Agora vamos configurar as variáveis. Vamos configurar uma variável binária para cada combinação possível de item/contêiner.

 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']]) ]

Agora queremos implementar restrições de peso tanto para a mala quanto para a bolsa.

 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']

Agora precisamos implementar uma restrição um pouco mais complexa - a restrição que garante que um item não entre na mala e na bolsa - ou seja, se a variável "na mala" for 1, então a variável "na mala" variável precisa ser zero e vice-versa. É claro que queremos ter certeza de permitir instâncias em que o item também não termine em nenhum dos contêineres.

Para adicionar essa restrição, precisamos iterar sobre todos os itens duráveis, encontrar a variável “na mala” e a variável “na mala” e afirmar que a soma dessas variáveis ​​é menor que 1.

Podemos definir restrições dependentes dinamicamente com bastante facilidade no 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

Agora que as restrições estão definidas, vamos construir o objetivo. O objetivo é simples a soma de todos os valores que obtemos de todos os itens que estão nos containers. Portanto:

 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

Vamos também definir algumas métricas personalizadas para que possamos ver rapidamente quanto peso foi colocado na bolsa e na mala, bem como quanto do peso da mala veio de bens duráveis ​​e frágeis:

 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']])

Agora que temos todas as peças finalizadas, vamos instanciar o problema e executar o 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()

Execute isso e você deverá ver a seguinte saída em seu stdout:

 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

Assim, a câmera, os óculos, a maçã e a banana vão para a mala com um total de 15 unidades de peso, a estatueta, o chifre e o homem de couro vão para a mala com um total de 17 unidades de peso. O valor total das mercadorias chega a 32 unidades de valor. Curiosamente, nenhum dos bens duráveis ​​acabou na mala, muito provavelmente porque a mala tinha capacidade suficiente para conter todos os bens duráveis.

Um cenário maior e mais realista: o problema do pessoal

Se você chegou até aqui em nosso tutorial HorusLP, parabéns! Agora você tem uma boa ideia de como usar o HorusLP.

No entanto, todos os exemplos em que trabalhamos até agora foram permutações do problema da mochila, e alguns dos requisitos e parâmetros são um pouco irreais. Vamos resolver mais um problema juntos para ver como o HorusLP pode resolver um problema mais realista. Vamos trabalhar com o problema de pessoal descrito na segunda metade do meu artigo anterior da Toptal.

Por questão de tempo, iremos direto para a versão final do modelo (com conflitos pessoais, regulamentos trabalhistas e subsídios para trabalhadores temporários), mas a implementação do modelo inicial mais simples também está disponível no GitHub.

Então vamos começar configurando o 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

Agora vamos definir as variáveis, que neste caso seriam variáveis ​​binárias determinando se um trabalhador deve trabalhar em seu turno, e variáveis ​​inteiras determinando quantos 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))

Agora vamos implementar a restrição que exige que tenhamos pessoal suficiente 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

Agora, precisamos implementar as restrições que impedem que pessoas específicas trabalhem umas com as outras:

 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.

Empacotando

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!