• Otimização de números inteiros

Os problemas de otimização linear que exigem que algumas das variáveis sejam números inteiros são chamados de Programas de números inteiros mistos (MIPs, na sigla em inglês).

Essas variáveis podem surgir de duas maneiras:

  • Variáveis inteiras, que representam números de itens, como carros ou conjuntos de televisão, e o problema é decidir quantos itens de cada item são fabricados para maximizar o lucro.
    Normalmente, esses problemas podem ser definidos como problemas de otimização linear padrão, com o requisito extra de que as variáveis precisam ser números inteiros. A próxima seção mostra um exemplo desse tipo de problema.

  • Variáveis booleanas que representam decisões com valores de 0 a 1.
    Como exemplo, considere um problema que envolve a atribuição de workers a tarefas. Consulte Atribuição. Para configurar esse tipo de problema, defina variáveis booleanas xi,j que são iguais a 1 se o worker i estiver atribuído à tarefa j, e a 0 caso contrário.

Se quiser uma boa introdução sobre otimização de números inteiros, recomendamos o manual de modelagem Mosek (link em inglês).

Ferramentas

O Google oferece algumas maneiras de resolver problemas de MIP:

  • MPSolver: um wrapper para vários solucionadores de MIP de terceiros, que usam técnicas padrão de ramificação e vinculação.
  • Solucionador CP-SAT: um solucionador de programação de restrições que usa métodos de satisfação (SAT).
  • Solucionador de CP original: um solucionador de programação de restrições.

Qual solucionador devo usar?

Não há uma regra rígida para decidir entre usar um solucionador MIP ou o solucionador CP-SAT. Como guia básico:

  • Os solucionadores de MIP são mais adequados para problemas que podem ser configurados como uma LP padrão, mas com variáveis inteiras arbitrárias, como o primeiro exemplo acima.
  • O solucionador CP-SAT é mais adequado para problemas em que a maioria das variáveis é booleana, como o segundo exemplo acima.

Para MIPs típicos com variáveis booleanas e de números inteiros, muitas vezes não há uma diferença clara na velocidade entre os dois solucionadores, então sua escolha pode se restringir à preferência pessoal.

Para ver exemplos que usam os solucionadores MIP e CP-SAT, consulte Como resolver um problema de atribuição e as outras seções de atribuição.

Outra maneira de resolver problemas de programação com números inteiros é usando um solucionador de fluxo de rede.
Consulte Atribuição como um problema de fluxo de custo mínimo para ver um exemplo.
Para um problema que pode ser configurado como um fluxo de rede, o solucionador de fluxo de custo mínimo pode ser mais rápido do que os solucionadores MIP ou CP-SAT. No entanto, nem todos os MIPs podem ser configurados dessa maneira.