HorusLP-Gurobi: Arquitetura de Otimização de Alto Nível para Gurobi
Publicados: 2022-03-11À medida que as tecnologias de otimização se tornam mais sofisticadas, os solucionadores comerciais começaram a desempenhar um papel cada vez mais importante na indústria. Em comparação com solucionadores de código aberto, as soluções comerciais tendem a ter mais recursos para resolver modelos de otimização complexos, como pré-solução avançada, inicialização a quente e solução distribuída.
Um dos solucionadores comerciais mais populares do mercado é o Gurobi, em homenagem aos cofundadores Zonghao Gu, Edward Rothberg e Robert Bixby, cada um deles pioneiro no espaço dos solucionadores comerciais. Gurobi impulsionou muitos projetos de otimização de alto perfil na história recente, incluindo o projeto de alocação de largura de banda da FCC e o projeto de reatribuição de prisioneiros da Pensilvânia State Prison.
Hoje, veremos como o HorusLP, um pacote de software que fornece uma interface declarativa de alto nível para modelagem de otimização, se integra à API do Gurobi para trazer uma experiência de modelagem intuitiva aos usuários enquanto aproveita os recursos mais avançados do Gurobi.
Otimização: uma atualização rápida
Para aqueles que não estão familiarizados com otimização ou pesquisa operacional, otimização refere-se a uma coleção de técnicas matemáticas que encontram os valores ótimos de variáveis dentro de um sistema de equações sujeito a um sistema de restrições. Se a frase acima soar um pouco seca, talvez um exemplo ajude a ilustrar.
Suponha que você tenha uma mochila com 15 libras de capacidade de carga. Você tem à sua frente alguns itens, cada um com um peso e valor monetário específicos:
- Câmera: peso 2 libras, valor $ 5
- Estatueta: peso 4 libras, valor $ 7
- Cidra: peso 7 libras, valor $ 2
- Chifre: peso 10 libras, valor $ 10.
Você quer escolher itens para colocar em sua mochila de modo que o peso total fique abaixo de 15 libras, mas o valor seja maximizado. (Se você precisar de mais contexto sobre por que estamos colocando itens de alto valor em uma mochila, recomendamos que use sua imaginação para uma narrativa. Boas narrativas de candidatos incluem resgatar coisas de um incêndio e leilões de propriedades... ou algumas atividades nefastas que prefiro não mencionar.)
Podemos formular o problema como o seguinte problema de otimização:
Let // Each variable stands for whether we put the item into the knapsack Camera = {0, 1} Figurine = {0, 1} Cider = {0, 1} Horn = {0, 1} // Maximize dollar value Maximize 5 * camera + 7 * figurine + 2 * cider + 10 * horn // Weight must stay below 15 pounds 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15Uma vez formulado este problema, podemos aplicar técnicas de otimização para encontrar os melhores itens para colocar em nossa mochila. Você pode encontrar um exemplo da solução de meus artigos anteriores sobre como resolver problemas de otimização usando Python e resolver problemas de otimização usando a API principal do HorusLP.
A técnica matemática subjacente é bastante fascinante, mas está fora do escopo deste artigo. Se você quiser saber mais, recomendo olhar aqui e aqui, ambos cortesia de Gurobi.
Gurobi
Enquanto os primeiros problemas de otimização foram resolvidos por equipes de matemáticos trabalhando com calculadoras, a maioria dos problemas de otimização hoje são resolvidos usando software especializado chamado solvers. Enquanto a maioria dos solvers geralmente são capazes de encontrar soluções para a maioria dos problemas de programação linear e inteira bem formulados, alguns solvers são muito mais capazes do que outros. Eles podem resolver classes de problemas que outros não podem resolver, resolver problemas mais rapidamente aplicando matemática de ponta ou resolver problemas grandes e difíceis usando computadores distribuídos. Os recursos mais avançados geralmente são fornecidos em solucionadores comerciais desenvolvidos e mantidos por empresas especializadas em construir os solucionadores mais rápidos e sofisticados.
Gurobi é um dos líderes no mercado de solucionadores comerciais, usado por grandes segmentos da comunidade de otimização, incluindo governos, instituições acadêmicas e empresas que operam em setores que vão de finanças a logística. Em termos de velocidade, o gurobi supera consistentemente em vários benchmarks usados para julgar solucionadores comerciais e de código aberto.
O Gurobi também vem com uma poderosa API Python que permite construir modelos a partir do Python. Esse recurso dá aos modeladores acesso a todas as bibliotecas úteis de manipulação de dados do Python durante a construção do modelo, o que ajuda muito em seu processo. Como demonstração da API Python do gurobi, veja como você pode modelar o problema da mochila:
import gurobipy as gr m = gr.Model() camera = m.addVar(name='camera', vtype=gr.GRB.BINARY) figurine = m.addVar(name='figurine', vtype=gr.GRB.BINARY) cider = m.addVar(name='cider', vtype=gr.GRB.BINARY) horn = m.addVar(name='horn', vtype=gr.GRB.BINARY) m.addConstr(2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 , 'size constraint') m.setObjective(5 * camera + 7 * figurine + 2 * cider + 10 * horn, gr.GRB.MAXIMIZE) m.optimize() print(camera.x) print(figurine.x) print(horn.x) print(cider.x)A execução do exemplo fornecerá a seguinte saída:
Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% -0.0 1.0 1.0 -0.0HorusLP
HorusLP é uma biblioteca de modelagem de otimização que foi construída com base em experiências de desenvolvimento de algoritmos de otimização. As bibliotecas de modelagem atualmente disponíveis carecem de ferramentas necessárias para trabalhar com o tipo de problemas complexos e multifacetados que normalmente são encontrados por aplicações comerciais de pesquisa operacional.
Embora a maioria das bibliotecas de otimização ofereça uma interface imperativa de baixo nível, à medida que os modelos de otimização se tornam mais complexos, são necessárias melhores ferramentas para gerenciar a complexidade. HorusLP é uma biblioteca que fornece ferramentas de alto nível para gerenciar essas complexidades. O HorusLP também fornece ferramentas poderosas de depuração e relatórios que permitem desenvolvimento e iteração mais rápidos.
Em sua essência, HorusLP é uma biblioteca orientada a objetos que fornece uma arquitetura muito necessária em torno de modelos de otimização. Ao alavancar a sintaxe orientada a objetos do Python, a biblioteca HorusLP fornece uma estrutura em torno da qual os modelos de otimização podem ser otimizados. O resultado é uma base de código desacoplada, modular e fácil de ler.
Se você quiser uma introdução mais detalhada à biblioteca principal do HorusLP com exemplos de código, você pode encontrar um tutorial aqui.
Integração HorusLP-Gurobi
Embora a API principal do HorusLP forneça uma API conveniente e de alto nível para a construção de modelos de otimização, ela é construída no PuLP, que, embora seja capaz de usar o Gurobi como solucionador, não tem acesso a alguns dos recursos mais avançados do Gurobi.
HorusLP-Gurobi é uma versão da API HorusLP construída usando a API Python de Gurobi. Isso permite ao usuário acesso direto aos recursos avançados do Gurobi, mantendo a API do HorusLP consistente.
Uma das principais filosofias que orientam o desenvolvimento do HorusLP-Gurobi foi a consistência com a API principal do HorusLP. Ao manter a estrutura minimalista do HorusLP consistente, um usuário de um solucionador de código aberto pode facilmente fazer a transição para o uso do Gurobi instalando a API do Gurobi e alternando as instruções de importação.
Para modelos simples, os modelos baseados em HorusLP terão mais linhas de código do que simplesmente usar a API Python de forma imperativa. No entanto, à medida que o processo de desenvolvimento continua e os modelos se tornam mais complexos, os designs declarativos e orientados a objetos da API HorusLP facilitarão a depuração e o desenvolvimento. A orientação a objetos também tornará o modelo mais legível, pois a definição do modelo cria centraliza e delineia claramente os objetivos, restrições, variáveis, etc.
Sem mais delongas, vamos mergulhar em alguns exemplos de código!
Exemplos de código
API básica do HorusLP
Como o HorusLP-Gurobi mantém a API consistente, o código do tutorial principal do HorusLP pode ser portado com uma simples alteração nas importações. Para usar HoruLP-Gurobi, no entanto, você precisará certificar-se de ter instalado o otimizador Gurobi e a interface Python de Gurobi. Você pode obter Gurobi entrando em contato com eles aqui.
Depois de instalar o Gurobi, podemos começar a codificar com HorusLP-Gurobi! Vamos começar instalando o pacote de requisitos:
Pip install horuslp horuslp-gurobiAssim que a instalação estiver concluída, podemos começar a usar o HorusLP-Gurobi! Lembre-se do problema da mochila de exemplo anterior. Podemos usar HorusLP-Gurobi para modelar o problema da seguinte forma:
Primeiro, importe as bibliotecas relevantes.
from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZEDefina algumas variáveis.
class KnapsackVariables(VariableManager): # we define variables by declaring the “vars” class variable vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn')Agora, podemos definir as restrições usando a classe de restrições.
class SizeConstraint(Constraint): # implement the 'define' function, the variables will get passed in by name def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15Podemos então implementar o objetivo de maneira semelhante.
class ValueObjective(ObjectiveComponent): # implement the define function and return the objective expression def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * hornE, finalmente, podemos definir o problema.
class KnapsackProblem(Problem): # defining a problem using the Horus API is a matter of setting variables in the subclass variables = KnapsackVariables objective = ValueObjective # constraints is a list variable, since there can be multiple constraints,. constraints = [SizeConstraint] # make sure to set the sense! sense = MAXIMIZEE instanciamos o problema e chamamos a função solve. É aqui que a mágica acontece.
prob = KnapsackProblem() # instantiate prob.solve() # call the solve method prob.print_results() # optional: print the standard Horus debug report print(prob.result_variables) # optional: print the variable results as a listExecute o código e você deverá ver a seguinte saída:
Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% KnapsackProblem: Optimal camera -0.0 figurine 1.0 cider -0.0 horn 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'camera': -0.0, 'figurine': 1.0, 'cider': -0.0, 'horn': 1.0}A primeira parte é o solver Gurobi e a segunda parte é a saída do HorusLP. Como você pode ver, o algoritmo recomenda que peguemos a estatueta e o chifre, resultando em 14 quilos de itens com $ 17 de valor.
Um dos benefícios de usar HorusLP com Gurobi é que você obtém muitas informações “de graça”. Muitas das informações que normalmente se deseja examinar durante o desenvolvimento, como o valor de cada variável, o valor objetivo final e os valores de restrição, são calculados automaticamente e emitidos em um formato de fácil leitura.
Se você leu o artigo anterior sobre o núcleo do HorusLP, notará que esta é quase exatamente a mesma API. Para manter a API simples, as interfaces do núcleo HorusLP e HorsLP-Gurobi são idênticas, com diferenças entre os solucionadores abstraídos na implementação da superclasse.
Assim, deixaremos a introdução do HorusLP para este exemplo simples; exemplos mais complexos demonstrando recursos avançados do HorusLP podem ser encontrados no artigo anterior.
Recursos de Gurobi
Gurobi fornece muitos recursos avançados para resolver problemas complexos. A maioria dos recursos é acessível por meio do objeto Model. Para permitir total compatibilidade com a API do Gurobi, o objeto model é facilmente acessível a partir da classe do problema como model .
Por exemplo, se você quiser escrever o arquivo MPS do modelo da mochila, no Gurobi você pode escrever algo como m.write('knapsack.mps') . Ao usar HorusLP-Gurobi, você pode simplesmente:
# import the problem as usual from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE # define the constraint class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 # define the objectives as above class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn # define the variables used by the constraints and objectives class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') # define the problem as in the above example class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE # instantiate the problem. We don't need to call solve or print any reports. prob = KnapsackProblem() prob.model.write('knapsack.mps') # this is the only bit of new code!E você deve ver o arquivo MPS em seu diretório de trabalho.
Você pode usar essa interface para acessar recursos avançados do Gurobi, como calcular IIS, criar retornos de chamada ou fornecer dicas de variáveis.
Recursos avançados do Gurobi ao seu serviço
Hoje analisamos uma versão da biblioteca HorusLP construída sobre a API Gurobi Python. Além dos recursos de relatório e depuração do núcleo do HorusLP, agora você tem acesso a todos os recursos avançados do Gurobi, acessíveis perfeitamente por meio da integração com a API Python do Gurobi.
Se você é um usuário atual do Gurobi ou alguém interessado em usar a otimização do Gurobi, espero que experimente o HorusLP! Você pode encontrar código de exemplo, fazer sugestões ou contribuir para HorusLP-Gurobi no GitHub.