Programação Inteira Determinística — Otimização Exata com Variáveis de Decisão Inteiras
- Proposto por
- Ralph E. Gomory
- Ano
- 1958
- Tipo
- Exact combinatorial optimization
- Família
- Simulation / optimization
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
Programação Inteira Determinística (PID) é uma abordagem de otimização matemática que encontra a melhor solução para problemas onde algumas ou todas as variáveis de decisão devem assumir valores inteiros, dados dados de objetivo e restrição totalmente conhecidos (determinísticos).
É a forma clássica e não estocástica de programação inteira, fundamental para pesquisa operacional e otimização combinatória desde o final da década de 1950.
A intuição por trás do método
Muitas decisões do mundo real são inerentemente discretas: abre-se uma instalação ou não; atribui-se um trabalhador a um turno ou não. Métodos de otimização contínua não conseguem impor esses requisitos de número inteiro. A Programação Inteira Determinística lida com isso restringindo variáveis a inteiros, enquanto todos os parâmetros do problema — custos, capacidades, demandas — são conhecidos com certeza. O resultado é uma solução exata e comprovadamente ótima sob essa suposição de certeza, tornando-a a formulação de referência contra a qual variantes estocásticas e robustas são comparadas.
História
A programação inteira emergiu da programação linear no final da década de 1950. O algoritmo de plano de corte de Ralph Gomory em 1958 foi o primeiro método exato sistemático. Concomitante com a ramificação e limite (Land e Doig, 1960), essas abordagens definiram o campo. O adjetivo 'determinístico' distingue a formulação clássica da programação inteira estocástica (Birge e Louveaux, 1997) e tornou-se terminologia padrão à medida que variantes conscientes da incerteza proliferavam.
Quando usar
Usar Programação Inteira Determinística quando: (1) as variáveis de decisão são inerentemente discretas (atribuição, escalonamento, localização de instalações, empacotamento de caixas, projeto de rede); (2) todos os parâmetros do problema são conhecidos com certeza ou podem ser estimados de forma confiável como valores pontuais; (3) uma solução ótima exata é necessária em vez de uma aproximação heurística. NÃO usar quando: os parâmetros são incertos ou dependentes de cenário (usar programação inteira estocástica ou robusta em vez disso); a escala do problema é tão grande que a ramificação e limite é computacionalmente intratável e heurísticas são aceitáveis; as variáveis são verdadeiramente contínuas (usar PL); ou múltiplos objetivos conflitantes precisam ser balanceados simultaneamente (usar programação inteira multiobjetivo).
Limitações e considerações
- Assume que todos os parâmetros do problema são conhecidos exatamente — a incerteza do mundo real é ignorada por design.
- NP-difícil em geral; o tempo de solução no pior caso cresce exponencialmente com o tamanho do problema.
- Problemas combinatórios grandes podem exigir horas ou dias de computação, mesmo com solucionadores modernos.
- A qualidade da formulação do modelo (aperto das restrições, quebra de simetria) afeta fortemente o tempo de solução.
As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.
Pontos fortes
- Garante uma solução comprovadamente ótima dentro das suposições do modelo determinístico.
- Lida naturalmente com estruturas de decisão discretas e combinatórias que métodos contínuos não conseguem.
- Suportado por solucionadores comerciais e de código aberto maduros e altamente eficientes (CPLEX, Gurobi, SCIP).
- Fornece um certificado de lacuna de otimalidade, permitindo terminação antecipada baseada em princípios para instâncias grandes.
- Serve como formulação de referência padrão ouro para comparar variantes heurísticas e estocásticas.
Aplicações
- Planejamento e escalonamento de produção com recursos discretos de máquinas ou mão de obra
- Localização de instalações: decidir quais armazéns ou fábricas abrir
- Roteamento de veículos e escalonamento de tripulação em transporte e logística
- Orçamento de capital: seleção de um portfólio de projetos de investimento indivisíveis
- Projeto de rede de telecomunicações com custos fixos de estabelecimento de links
- Escalonamento de escalas de pessoal de saúde e de salas de cirurgia
Como funciona
Como funciona
Definir o modelo de otimização: uma função objetivo a ser minimizada (ou maximizada) como uma combinação linear de variáveis de decisão inteiras, sujeita a um conjunto de restrições lineares de desigualdade ou igualdade. Todos os coeficientes (c, A, b) são fixos e conhecidos — é isso que torna a formulação determinística. Variáveis binárias (0/1) são um caso especial para decisões sim/não.
Fórmula
\min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0,\; x \in \mathbb{Z}^nResolver o relaxamento PL (Programação Linear), que temporariamente permite que as variáveis assumam valores contínuos. Isso fornece um limite inferior para o objetivo inteiro ótimo. Se a solução do relaxamento PL já for de valor inteiro, ela é ótima para o PI (Programação Inteira); caso contrário, inicia-se o ramificação (branching).
Fórmula
\text{Solve LP relaxation: } \min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0Selecionar uma variável fracionária da solução do relaxamento PL e dividir a região factível adicionando uma restrição de piso (x_j <= valor_inteiro) em um ramo e uma restrição de teto (x_j >= valor_inteiro) no outro, gerando dois subproblemas a serem resolvidos recursivamente.
Fórmula
\text{Select fractional variable } x_j^*. \text{ Create two subproblems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceilResolver o relaxamento PL de cada subproblema para obter um limite. Se o limite de um nó for pior que a melhor solução inteira conhecida (incumbente), podá-lo. Se o subproblema gerar uma solução inteira factível melhor que a incumbente, atualizar a incumbente. O processo forma uma árvore de busca ramificada e limitada (branch-and-bound).
Fórmula
\text{Compute bounds; prune nodes where LP bound} \geq \text{incumbent. Update best integer solution.}Métodos de plano de corte (cutting-plane methods) — notavelmente os cortes de Gomory — derivam desigualdades lineares adicionais do tableau PL que são satisfeitas por todas as soluções inteiras, mas violadas pela solução PL fracionária atual. Adicionar esses cortes aperta o relaxamento PL e reduz a ramificação. Solucionadores modernos combinam ramificação e limite com cortes em uma estrutura de ramificação e corte (branch-and-cut).
Fórmula
\text{Optionally add Gomory cuts or problem-specific valid inequalities to tighten LP relaxation.}O algoritmo termina quando todos os nós abertos são podados ou geram soluções inteiras. A incumbente na terminação é a solução inteira comprovadamente ótima. Solucionadores também relatam uma lacuna (gap) entre o melhor limite e a incumbente, que pode ser usada como critério de parada para problemas grandes.
Fórmula
\text{Return optimal integer solution } x^* \text{ with objective value } z^* = c^\top x^*Erros comuns
- Tratar parâmetros incertos como estimativas pontuais determinísticas pode gerar soluções que têm desempenho ruim na prática — valide essa suposição antes de aplicar PID.
- Relaxamentos PL fracos (grandes lacunas de integridade) levam a árvores de ramificação e limite enormes; invista em desigualdades válidas e reformulação antes de escalar.
- A explosão de variáveis binárias de formulações big-M pode desestabilizar numericamente o relaxamento PL; prefira reformulações de restrição mais apertadas.
- Confundir factibilidade com otimalidade ao usar uma tolerância de lacuna não nula — sempre relate a lacuna junto com o valor do objetivo.
- Ignorar simetria em modelos (por exemplo, máquinas ou trabalhadores idênticos) causa ramificação redundante; adicione restrições de quebra de simetria.
Perguntas frequentes
O que distingue a programação inteira determinística da programação inteira estocástica?
Na PI determinística, todos os parâmetros de objetivo e restrição são fixos e conhecidos. A PI estocástica modela explicitamente parâmetros incertos via distribuições de probabilidade ou cenários, produzindo soluções que são robustas ou ótimas em expectativa nesses cenários. A PI determinística é mais simples e rápida de resolver, mas ignora a incerteza.
A programação binária é um caso especial de programação inteira?
Sim. A programação binária (0-1) restringe cada variável de decisão a {0, 1}. É o caso especial mais comum, usado para decisões sim/não, como se abrir uma instalação, selecionar um projeto ou atribuir um trabalhador. A programação inteira geral permite qualquer valor inteiro não negativo.
Quando devo mudar da PI determinística para um método heurístico?
Quando a árvore de ramificação e limite é muito grande para ser explorada dentro de um limite de tempo aceitável e a lacuna de otimalidade de uma boa heurística (algoritmo genético, recozimento simulado, busca em vizinhança grande) é tolerável para a aplicação. Relate e justifique a lacuna ao se desviar da otimização exata.
A PI determinística pode lidar com objetivos ou restrições não lineares?
A PI determinística clássica assume linearidade (programação linear inteira). A programação inteira não linear existe, mas é substancialmente mais difícil; muitas formas não lineares podem ser linearizadas através de variáveis binárias auxiliares e reformulações big-M. A programação quadrática inteira (PQI) é suportada diretamente por alguns solucionadores modernos.
Qual solucionador devo usar para PI determinística na prática?
Comerciais: Gurobi ou IBM CPLEX para melhor desempenho. Acadêmicos/código aberto: SCIP, CBC (via COIN-OR) ou HiGHS. Todos implementam ramificação e corte com pré-processamento automático. Para usuários de Python, PuLP, Pyomo ou scipy.optimize.milp fornecem interfaces de modelagem convenientes.
Métodos relacionados
Fontes
Gomory, R. E. (1958). Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5), 275-278.
Abrir referência DOICopiado.Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.
ISBN: 9780471283669Copiado.