A pesquisa operacional e a otimização convexa é um campo da matemática aplicada que encontrou uma ampla gama de aplicações comerciais ao longo dos anos. À medida que o poder da 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 movidos pela pesquisa de operações impulsionam tudo, desde o roteamento na logística global até a suavização da produção de eletricidade no setor de energia.

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

No entanto, embora as tecnologias de otimização e as necessidades de negócios continuem crescendo em sofisticação, a maioria dessas ferramentas permaneceu mais ou menos a mesma e não evoluiu com rapidez suficiente para atender às necessidades da indústria. Como resultado, desenvolver, gerenciar, depurar e ajustar esses algoritmos geralmente requer uma grande sobrecarga cognitiva, especialmente em um ambiente de negócios em rápida evolução.

Hoje, eu gostaria de apresentar HorusLP , para Biblioteca de otimização Python que ajuda com a arquitetura de fluxos de trabalho de desenvolvimento de algoritmo. Falaremos sobre os problemas que a ferramenta foi projetada para resolver e, em seguida, 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 a construção de um software idiomático, eficiente e sustentável e a entrega de um produto dentro dos limites 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 se torna mais evidente à medida que a complexidade do produto aumenta.

Na maioria das disciplinas, um desenvolvedor pode aliviar esse problema escolhendo uma estrutura ou biblioteca que ajude com a arquitetura. No front-end voltado para a web, muitos desenvolvedores escolhem React ou Angular; no mundo do desenvolvimento de API, os engenheiros de software podem escolher 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 arquitetônica. O desenvolvedor é responsável por gerenciar variáveis, restrições e vários objetivos por conta própria. Além do mais, os algoritmos de pesquisa operacional são geralmente difíceis de introspectar, agravando o problema.

O principal objetivo do HorusLP é fornecer uma estrutura arquitetônica para o desenvolvimento de algoritmos de otimização. Ao fornecer consistência estrutural, a estrutura torna a organização mais fácil e permite que os desenvolvedores se concentrem no que fazem de 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á-los para uso em definições de modelo e relatórios posteriores.
• Variáveis ​​relacionadas precisam ser agrupadas e rastreadas, e não há uma maneira óbvia de gerenciá-las.

Complexidade de restrições

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

Complexidade dos objetivos

• Expressões objetivas podem se tornar difíceis de manejar se tiverem vários componentes. Isso pode ser exacerbado 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 deve imprimir explicitamente novas variáveis ​​e valores de restrição para ver os resultados. Isso leva a código duplicado e desenvolvimento mais lento.
• Ao adicionar 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 buscar a incompatibilidade por meio de tentativa e erro

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

HorusLP Tutorial: 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ê!

definição de princípio de design

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

Pip install horuslp pulp

Assim que a instalação for concluída, vamos prosseguir e abrir um arquivo Python. Vamos implementar o problema de mochila do meu artigo anterior sobre pesquisa operacional .

A biblioteca HorusLP possui 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 ​​de 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 criando uma subclasse da classe de restrição principal e implementando sua função “definir”.

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 por nome. O framework irá localizar a variável no gerenciador de variáveis ​​e passá-la para a função define.

Depois que a restrição é 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, entretanto, 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 classe do problema print_results função. Também podemos acessar o valor de variáveis ​​específicas observando result_variables classe.

prob.print_results() print(prob.result_variables)

Execute o script e você 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 VariableGroups

À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 como:

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 das variáveis ​​da mochila, como:

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 ​​dentro desse grupo.

Agora precisamos alterar as definições de restrição e objetivo. Em vez de pedir os nomes individuais, faremos o mesmo para 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 múltiplas 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 quiséssemos ver como os resultados mudariam se forçássemos o modelo a adicionar uma câmera à nossa mochila. Iríamos implementar uma restrição adicional e adicioná-la à 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, simplesmente precisamos 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ê verá o seguinte resultado:

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 variáveis ​​ideais alterados.

Gerenciando restrições dependentes e grupos de restrições

As restrições são frequentemente relacionadas umas às outras porque são dependentes umas das outras ou porque logicamente pertencem 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 uma relação específica entre as variáveis.

Para expressar esses agrupamentos, podemos usar o recurso de restrições dependentes de nossas definições de restrição. 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 pegar o MustHaveItemConstraint fora da definição do problema:

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

E execute o código novamente, e você 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 é implementado! Para um exemplo mais complexo de como a restrição dependente pode ser usada, consulte o exemplo de definição de equipe no final do tutorial.

Gerenciando múltiplos objetivos ponderados

Freqüentemente, durante o desenvolvimento de nossos algoritmos de otimização, encontramos uma expressão objetiva composta de 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 desejemos enviesar o algoritmo para escolher a estatueta e a sidra. Vamos refatorar o código da seção anterior para usar CombinedObjective.

Primeiro, importe CombinedObjective classe assim:

from horuslp.core import CombinedObjective

Podemos implementar um componente objetivo independente como:

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 mudar a definição do problema assim:

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

Execute o problema e você verá o seguinte 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

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

Encontrando Restrições Incompatíveis

Ao desenvolver algoritmos, frequentemente nos deparamos com modelos inviáveis. Se o modelo for complexo, pode ser desafiador determinar por que ele se tornou repentinamente inviável. O HorusLP possui uma ferramenta útil para ajudá-lo nesses casos.

Suponha que estivéssemos adicionando restrições e terminássemos 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 = 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 quanto ao 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 exige que a câmera esteja dentro e não na mochila. (Claro, 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 tornando a detecção mais difícil:

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ê 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 difícil sessão de depuração, onde reduzimos as restrições potencialmente conflitantes uma por uma. Felizmente, o HorusLP possui um recurso de pesquisa de incompatibilidade para ajudá-lo a diminuir as restrições incompatíveis mais rapidamente. A maneira mais simples de usar o recurso de pesquisa de incompatibilidade é alterar o parâmetro print_results chame assim:

prob.print_results(find_infeasible=True)

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

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

Ótimo! Agora estabelecemos que MustHaveItemConstraint não é a causa da inviabilidade e que o problema se deve 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 o seu print_results chame 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ê verá a seguinte saída:

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

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

Construindo Algoritmos de Arquivos de Dados

Ao construir modelos, raramente temos o luxo de codificar permanentemente todas as restrições e variáveis. Freqüentemente, nosso programa deve ser flexível o suficiente para alterar o modelo dependendo dos dados de entrada. Suponha que, em vez de uma entrada embutida em código, quiséssemos construir nosso problema de 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 'definir' que implementamos para restrições e objetivos.

Vamos modificar o código do problema da mochila simples (o problema que implementamos na seção 1 do tutorial). Primeiro, vamos colocar a string JSON no arquivo. Claro, normalmente o leríamos de uma fonte externa, mas por uma questão de simplicidade, 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 } '''

Também vamos nos certificar de que nosso programa seja capaz de analisá-lo. Adicione o seguinte às suas declaraçõ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 o nomeará apropriadamente.

Vamos mudar as definições de restrição e objetivo da seguinte forma:

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, o define função obtém um dicionário contendo todas as variáveis ​​por nome. A função de definição de restrição pode então 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 é bastante simples:

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

Execute este programa e você 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ório, construiremos métricas personalizadas que não são expressas diretamente no objetivo ou como uma restrição. O HorusLP tem um recurso que simplifica a especificação de métricas personalizadas.

Suponha que você queira controlar quantas frutas o modelo da seção anterior colocou 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 é muito semelhante àquelas 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ê 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.

Trabalhando em 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, sendo mais protetora, pode conter bens frágeis e duráveis. A sacola, por outro lado, só pode conter bens duráveis. Suponha também que os dados dos itens são 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 um quadro 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 / recipiente.

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 sacola.

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 vá para a mala e a bolsa - isto é, se a variável 'na mala' for 1, então o 'na mala' a variável precisa ser zero e vice-versa. Claro, queremos ter certeza de permitir instâncias em que o item acabe em nenhum contêiner também.

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

Podemos definir dinamicamente as restrições dependentes 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 em recipientes. 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 terminamos todas as peças, 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ê 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 para um total de 15 unidades de peso, a estatueta, o chifre e o homem-couro vão para a bolsa para 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, provavelmente porque a bolsa tinha capacidade suficiente para conter todos os bens duráveis.

Um cenário maior e mais realista: o problema de 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 estivemos trabalhando até agora foram permutações do problema da mochila e alguns dos requisitos e parâmetros são um pouco irrealistas. Vamos trabalhar mais um problema juntos para ver como o HorusLP pode resolver um problema mais realista. Vamos resolver o problema de pessoal descrito na segunda metade do meu artigo anterior do ApeeScape .

No interesse do 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 definindo 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 deveria 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 uma equipe 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

E, finalmente, a restrição dos padrões de trabalho. Vamos implementar este um pouco diferente para fins demonstrativos:

diferença entre as empresas s e c

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)

E agora vamos definir os objetivos. O custo dothraki e os custos regulares de funcionários são calculados de forma muito diferente, então vamos colocá-los em componentes objetivos separados:

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

E agora podemos definir e executar o problema:

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()

Execute o script e você verá o seguinte:

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

Se você comparar isso com o problema que implementamos no tutorial anterior, verá que os resultados correspondem.

Empacotando

Parabéns por passar por nosso primeiro tutorial HorusLP! Você agora é um praticante competente do HorusLP.

Espero que este artigo tenha convencido você dos benefícios de arquitetar seu Modelos MIP , e que você fará uso do HorusLP em seus próximos projetos. Você pode encontrar o código-fonte HorusLP, bem como o código de todos os tutoriais, em GitHub . Documentação HorusLP adicional e uma página de tutorial serão adicionadas ao GitHub em breve.

Como HorusLP é um projeto relativamente novo, adoraríamos ouvir de você e incorporar sua opinião. Se você tiver dúvidas, comentários ou sugestões, escreva para mim através do ApeeScape ou usando as informações de contato que você pode encontrar no GitHub. Espero ouvir de você em breve!

Compreender o básico

O que é HorusLP?

HorusLP é uma biblioteca de otimização Python projetada para ajudá-lo a arquitetar fluxos de trabalho de desenvolvimento de algoritmos. Possui uma API simples e declarativa e muito pouco clichê.

Qual é o problema da mochila?

O problema da Knapsnack é um problema de otimização centrado na otimização combinatória. Quando apresentado a um conjunto de itens com pesos e valores diferentes, o objetivo é “encaixar” o maior número deles em uma mochila restrita e não sujeita a alterações.