O que é Otimização Combinatória e como podemos modelar matematicamente um problema do mundo real?
A Otimização Combinatória é um ramo da ciência da computação e da matemática aplicada que trata de problemas de otimização. Existem diversas técnicas para resolver tais problemas. Quando queremos a melhor solução possível para um problema, utilizamos métodos exatos para resolvê-lo, como por exemplo, através de programação linear/inteira e programação por restrições. Métodos exatos podem se tornar inviáveis dependendo da natureza do problema. Para problemas muito complexos, exaurir todas as possíveis combinações de valores procurando por essa melhor solução, pode ser bastante custoso computacionalmente. Para tais casos, podemos utilizar algoritmos heurísticos e algoritmos aproximativos, que encontram boas soluções (não exatamente a melhor) em um tempo computacional viável. Neste artigo, iremos focar na resolução de modelos matemáticos através de programação linear/inteira.
A modelagem matemática pode ser vista como uma tentativa de representar matematicamente fenômenos do mundo real. Ao modelar um problema, precisamos identificar os dados de entrada necessários, um conjunto de variáveis de decisão, uma função objetivo e um conjunto de restrições. Os dados de entrada são as informações necessárias que precisam ser passadas como entrada para o modelo. As variáveis de decisão são responsáveis por formar uma solução para o problema. Para pensarmos em quais variáveis são necessárias para o nosso modelo, podemos tentar responder a seguinte pergunta: “o que o modelo precisa propor como solução”?.
Além disso, o modelo possui um conjunto de restrições (igualdades ou desigualdades) que irão limitar os valores possíveis das variáveis. Quando estamos modelando um problema, nós temos algumas regras de negócio que precisam ser respeitadas e essas regras podem ser modeladas através de restrições. Um conjunto de valores para as variáveis de decisão que respeite todas as restrições do modelo forma uma solução viável para o problema. Se tivermos uma valoração das variáveis que viole pelo menos uma restrição, então essa é uma solução inviável. Um problema de otimização pode ser de minimização ou de maximização. Um problema de minimização (maximização) busca encontrar a melhor solução viável, chamada de solução ótima, que minimize (maximize) o valor da sua função objetivo.
Um problema pode possuir uma ou mais soluções ótimas, isto é, valorações diferentes para as suas variáveis de decisão que levam a um mesmo valor ótimo de função objetivo. Se o problema não possuir nenhuma solução viável, então ele é um problema inviável. Mais ainda, se um modelo matemático não possuir restrições que limitem o valor da sua função objetivo, então este é um problema ilimitado. Neste caso, não existe uma solução ótima, visto que sempre é possível obter uma solução viável e de melhor valor objetivo.
Uma das áreas de otimização mais antiga e amplamente utilizada é a otimização linear (ou programação linear), na qual a função objetivo e as restrições podem ser escritas como expressões lineares. As variáveis de decisão de um problema linear podem ser contínuas ou inteiras, isto é, aceitar valores reais ou inteiros. Quando todas as variáveis de um problema são contínuas, este é chamado simplesmente de problema linear. Se todas as variáveis são inteiras, então temos um problema linear inteiro. Já quando um problema possui ambas as variáveis, este é um problema linear inteiro misto. A seguir, iremos apresentar um exemplo de problema linear inteiro.
Modelando um problema de otimização
Vamos considerar um problema bastante comum no mundo real e analisar como ficaria a sua modelagem matemática: o problema da formação de equipes de trabalho. Considere, por exemplo, um conjunto de pessoas de uma dada empresa. Cada uma dessas pessoas possui um conjunto de habilidades que está apta a desempenhar, não podendo ser alocada para desempenhar uma habilidade que não possui. O problema da formação de equipes consiste em agrupar essas pessoas em equipes de trabalho, em que essas equipes possuem certas demandas por habilidades que precisam ser atendidas. Além disso, imagine que existe um custo para alocar uma pessoa exercendo uma habilidade em uma equipe. Assim, o objetivo deste problema é formar equipes de trabalho, atendendo as demandas de habilidades de cada uma, com menor custo de alocação.
Existem várias variantes desse problema. Por exemplo, poderíamos considerar a possibilidade de uma pessoa ser alocada a mais de uma equipe, dividindo frações de seu tempo de trabalho. Também poderíamos considerar outras funções objetivos, como maximizar a afinidade entre pessoas alocadas a uma mesma equipe de trabalho.
Quando estamos modelando um problema real, são feitas entrevistas com as pessoas que entendem do negócio para que consigamos extrair as informações necessárias, entender o que elas querem como solução e quais regras de negócio precisamos atender com o nosso modelo matemático. Para esse exemplo, vamos supor que queremos alocar pessoas em equipes de trabalho, que cada pessoa deve estar alocada a no máximo uma equipe, que as demandas de habilidades de cada equipe devem ser atendidas e que o custo de alocação seja o mínimo possível.
Para exemplificar, vamos considerar que temos 7 pessoas e que queremos formar duas equipes de trabalho, e1 e e2. Cada pessoa possui o subconjunto de habilidades representado abaixo dela, na figura a seguir. Suponha que a equipe e1 precise de 1 pessoa com a habilidade h1, 2 com a habilidade h2 e 1 pessoa exercendo h3. Já a equipe e2 demanda por 2 pessoas com a habilidade h1 e 1 pessoa exercendo a habilidade h3.
Uma possível solução para esse problema é representada na figura abaixo. As 4 pessoas agrupadas no círculo azul estão alocadas na equipe e1 e as outras 3 pessoas, agrupadas no círculo vermelho, estão na equipe e2. A habilidade que cada pessoa está exercendo, dentre seu subconjunto de habilidades, está representada em negrito. Note que essa é uma solução viável para o nosso problema, uma vez que cada pessoa está alocada em no máximo 1 equipe e que a demanda de cada equipe está sendo atendida.
Para começarmos a modelagem, primeiro vamos pensar nos dados de entrada necessários para este problema. Olhando a descrição do mesmo, podemos perceber que existe um conjunto de pessoas, um conjunto de habilidades, um conjunto de equipes, que cada pessoa possui um certo subconjunto de habilidades, que cada equipe possui suas demandas e que existe um custo de alocação. Este são os nossos dados de entrada, que podem ser definidos matematicamente como:
Agora que temos os dados de entrada do nosso problema, podemos pensar quais são as variáveis de decisão necessárias. Lembre-se que as variáveis irão representar uma solução para o problema. Então, qual o objetivo desse problema? O que nosso modelo precisa decidir? Já que o intuito é formar equipes de trabalho, podemos pensar em uma variável que indique em qual equipe cada pessoa estará alocada e qual habilidade estará exercendo. Então vamos definir a seguinte variável binária (que só aceita 0 ou 1 como valor):
Perceba que definimos essas variáveis para cada pessoa p ∈ P e equipe e ∈ E, mas não precisamos definir para toda habilidade h ∈ H, visto que uma pessoa não poderá exercer uma habilidade que não possui. Assim, basta definirmos para cada h ∈ H(p).
Agora que já temos os dados de entrada e as variáveis definidos, já podemos modelar o nosso problema, através de uma função objetivo e um conjunto de restrições que expressem as regras de negócio existentes:
A função objetivo consiste em minimizar o custo de alocação. Para cada pessoa p ∈ P, equipe e ∈ E e habilidade h ∈ H(p) dessa pessoa, se p está alocada em e com a habilidade h, então x(p, e, h) = 1 e o custo c(p, e, h) dessa alocação será contabilizado no somatório. Já se x(p, e, h) = 0, então como p não está alocada a e com a habilidade h, este custo não será contabilizado.
O primeiro conjunto de restrições garante que cada pessoa p ∈ P estará alocada a no máximo uma equipe e ∈ E com uma habilidade h ∈ H(p). As demandas de habilidades das equipes são asseguradas pelo segundo conjunto de restrições. Note que, para cada equipe e ∈ E e habilidade h ∈ H, a restrição garante que serão alocadas exatamente r(e, h) pessoas, em que r(e, h) é o número de pessoas com a habilidade h que precisam ser alocadas a e. O último conjunto de restrições são simplesmente as restrições de integralidade das variáveis, indicando que a variável x é uma variável binária.
Implementando um problema de otimização em python
Para a implementação desse modelo em python, iremos utilizar o Google OR-Tools, um pacote de software gratuito e de código aberto desenvolvido pelo Google para resolver problemas de otimização. Também iremos utilizar o solver gratuito SCIP. Existem vários outros solvers para problemas de otimização, alguns deles são pagos, como o Gurobi e o CPLEX, e alguns são gratuitos, como o SCIP, o GLPK e o CBC.
O trecho de código a seguir importa as bibliotecas necessárias.
O seguinte código declara o solver SCIP.
O trecho de código abaixo cria os dados de entrada necessários para o problema. O array pessoa_habilidades representa o conjunto H(p), ∀p ∈ P. A matriz de demandas é representada pelo array demanda_habilidades e os custos de alocação são dados pelo dicionário custos.
As variáveis de decisão do problema são criadas no trecho de código a seguir.
O seguinte código cria as restrições do problema.
O trecho de código a seguir cria a função objetivo do nosso problema. Note que a função objetivo é de minimização do custo total de alocação.
O trecho de código abaixo invoca o solver, para a resolução do modelo criado.
A seguir, imprimimos a solução do problema para os dados de entrada que foram passados.
Segue a saída do programa:
A seguir, apresentamos o programa completo.
Conclusão
Neste artigo, vimos o conceito de otimização combinatória e algumas definições necessárias para entendimento, como de solução viável, inviável, ótima, dados de entrada, variáveis de decisão, função objetivo e restrições.
Vimos também que podemos resolver problemas de otimização tanto por abordagens exatas, que buscam a melhor solução viável possível (solução ótima), como por abordagens heurísticas e aproximativas, que encontram boas soluções, não necessariamente a ótima, em um tempo computacional viável. Neste artigo, focamos na resolução de um problema através de uma abordagem exata, a programação linear.
Apresentamos um problema bastante comum no mundo real: o problema de agrupar pessoas em equipes de trabalho, satisfazendo as demandas de habilidades de cada equipe e buscando o menor custo de alocação possível. Vimos a modelagem matemática desse problema, bem como uma implementação do mesmo na linguagem de programação python, usando o pacote de software Google OR-Tools e o solver SCIP, ambos gratuitos.
