Programação Inteira

Programação Inteira (PI; em inglês: integer programming, IP) é um ramo da otimização matemática em que se investigam problemas nos quais algumas ou todas as variáveis devem assumir apenas valores inteiros.

O caso particular mais estudado é a programação linear inteira (PLI; em inglês: integer linear programming, ILP), onde a Função objetivo e as restrições são lineares. Diferentemente da programação linear, na qual as variáveis podem assumir quaisquer valores reais, a exigência de integralidade torna os problemas de PI significativamente mais difíceis de resolver.

A programação inteira tem ampla aplicação em economia, logística, planejamento de produção e outras áreas onde as variáveis são discretas por natureza (por exemplo, o número de unidades de um produto fabricadas ou o número de trabalhadores).

Definição e Terminologia

O problema geral de programação linear inteira pode ser formulado da seguinte maneira:

Encontrar um vetor $x$ que:

maximiza (ou minimiza) $c^{T}x$

sujeito a:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{\mathbb{Z}}}^n$ (todos os componentes do vetor $x$ são números inteiros)

onde $x$ é o vetor de variáveis, $c$ e $b$ são vetores, e $A$ é a matriz de coeficientes.

Dependendo das restrições sobre as variáveis, distinguem-se os seguintes tipos de problemas:

• Programação inteira pura: todas as variáveis devem ser inteiras.
• Programação inteira mista (em inglês: mixed-integer programming, MIP): apenas uma parte das variáveis precisa ser inteira.
• Programação binária (0-1): as variáveis podem assumir apenas os valores 0 ou 1, o que permite modelar decisões lógicas do tipo "sim/não".

Propriedades Chave e Complexidade

Complexidade Computacional

O problema de programação linear inteira, no caso geral, é NP-difícil. Isso significa que não existe um algoritmo conhecido capaz de encontrar a solução ótima exata para um problema de PI arbitrário em tempo polinomial. A complexidade decorre da natureza combinatória do problema, pois o número de soluções inteiras possíveis pode crescer exponencialmente com o aumento do número de variáveis.

Relação com a Programação Linear (Relaxação LP)

Para qualquer problema de PI, é possível formular sua relaxação linear — um problema de programação linear (PL), no qual a exigência de integralidade das variáveis é removida. A solução da relaxação LP possui duas propriedades importantes:

1. Ela pode ser encontrada de forma significativamente mais rápida (em tempo polinomial).
2. O valor ótimo da função objetivo da relaxação LP fornece um limite (limite superior para problemas de maximização e limite inferior para minimização) para o valor ótimo do problema inteiro original.

No entanto, o simples arredondamento da solução fracionária da relaxação LP para os inteiros mais próximos geralmente não leva a uma solução ótima, ou mesmo viável, para o problema inteiro.

Propriedade de Unimodularidade Total

Existe uma classe importante de problemas de PLI que são resolvidos com a mesma facilidade que suas relaxações LP. São os problemas em que a matriz de restrições $A$ é totalmente unimodular (ou seja, o determinante de qualquer uma de suas submatrizes quadradas é igual a 0, +1 ou −1). Se a matriz $A$ é totalmente unimodular e o vetor $b$ é inteiro, então todos os vértices do poliedro de soluções viáveis da relaxação LP serão automaticamente inteiros. Consequentemente, a solução encontrada pelo método simplex será inteira. Exemplos desses problemas incluem o problema do transporte e o problema da designação.

Métodos de Solução

Para resolver problemas gerais de PI que não possuem a propriedade de unimodularidade total, foram desenvolvidos métodos exatos baseados em ideias de enumeração implícita.

• Método Branch-and-Bound (em inglês: Branch and Bound) — o principal método exato, baseado na divisão sistemática do conjunto de soluções viáveis em subconjuntos (ramificação) e na eliminação (poda) dos subconjuntos que comprovadamente não contêm a solução ótima. A relaxação LP é usada para avaliar o potencial dos subconjuntos.

• Método dos Planos de Corte (método de Gomory; em inglês: Cutting Plane Method) — uma abordagem iterativa que adiciona sequencialmente novas restrições lineares ("cortes") ao problema. Esses cortes "cortam" soluções fracionárias da relaxação LP sem remover nenhuma solução inteira viável, aproximando gradualmente a região viável da relaxação LP ao fecho convexo das soluções inteiras.

Solucionadores modernos (solvers) geralmente usam algoritmos híbridos, como o método Branch-and-Cut (em inglês: Branch and Cut), que combina as vantagens de ambas as abordagens.

Exemplos e Áreas de Aplicação

A programação inteira permite modelar uma variedade de problemas clássicos de otimização combinatória.

• Problema da Mochila: um problema clássico de programação 0-1, no qual se deve selecionar um conjunto de itens com o maior valor total possível, sem exceder uma restrição de peso total.
• Problema do Caixeiro-Viajante: o problema de encontrar a rota mais curta que passa por um conjunto de cidades. Pode ser formulado como um problema de programação inteira, onde as variáveis representam a inclusão de arestas de um grafo na rota final.

Graças à sua flexibilidade, a PI é uma das ferramentas mais requisitadas em pesquisa operacional e encontra aplicação em áreas como:

• Logística e gerenciamento da cadeia de suprimentos: otimização de rotas de transporte, localização de armazéns, gestão de estoques.
• Planejamento da produção: elaboração de cronogramas de produção, alocação de recursos, carregamento de equipamentos.
• Finanças e economia: formação de carteiras de investimento, orçamento de capital.
• Telecomunicações e energia: projeto de redes de comunicação, planejamento da operação de unidades de energia.

Ver também

• Programação linear
• Método Branch-and-Bound