Skip to content
Voltar aos resultados

Programação Inteira Mista — Otimização exata sobre decisões contínuas e inteiras

Proposto por
Ralph Gomory (branch-and-bound cuts, 1958); Land & Doig (branch-and-bound, 1960)
Ano
1958–1960
Tipo
Mathematical optimization
Família
Simulation / optimization

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

Programação Inteira Mista (PIM) é uma estrutura de otimização matemática na qual algumas variáveis de decisão devem assumir valores inteiros enquanto outras podem ser contínuas.

Ela generaliza a programação linear e é amplamente utilizada em pesquisa operacional, logística, escalonamento, alocação de recursos e projeto de engenharia, onde restrições de indivisibilidade — como decisões sim/não ou quantidades de unidades inteiras — surgem naturalmente.

A intuição por trás do método

Muitos problemas de otimização reais envolvem decisões que não podem ser divididas — você abre uma instalação ou não, você atribui exatamente um trabalhador a um turno, você encomenda unidades inteiras. A programação linear contínua ignora essas realidades e pode produzir respostas fracionárias não implementáveis. A PIM impõe a integridade diretamente no modelo. O solver explora o espaço de soluções inteiras viáveis sistematicamente via branch-and-bound: ele resolve subproblemas contínuos relaxados para limitar a melhor solução possível em cada região, descarta regiões que não podem melhorar a melhor solução inteira encontrada até agora e adiciona planos de corte para apertar a busca. O resultado é um plano comprovadamente ótimo ou quase ótimo.

História

Os fundamentos da programação inteira foram lançados por Ralph Gomory, que introduziu o método de planos de corte em 1958, e por Land e Doig, que formalizaram o branch-and-bound em 1960. Décadas subsequentes viram o desenvolvimento da teoria de relaxação PL, combinatória poliédrica (Edmonds, Padberg, Grötschel) e, nos anos 1990, solvers comerciais tornaram a PIM em larga escala prática. O campo é tratado de forma abrangente em Nemhauser e Wolsey (1988) e Wolsey (1998).

Quando usar

Usar PIM quando seu problema tiver um objetivo e restrições lineares ou linearizáveis e incluir decisões que devem ser de valor inteiro (localização de instalações, escalonamento de tripulação, orçamento de capital, projeto de rede, problemas de corte de estoque). É o método de escolha quando você precisa de uma solução comprovadamente ótima ou com lacuna limitada e o tamanho do problema é tratável (milhares de variáveis com solvers modernos). NÃO usar PIM quando o objetivo ou as restrições forem altamente não lineares (usar programação não linear ou inteira mista não linear em vez disso), quando o problema for tão grande que métodos exatos sejam proibitivos (considerar heurísticas ou meta-heurísticas), ou quando aproximações contínuas forem suficientemente precisas (usar PL para velocidade).

Limitações e considerações

  • Complexidade no pior caso é NP-difícil; o tempo de solução pode crescer exponencialmente com o número de variáveis inteiras.
  • Requer uma formulação matemática precisa; modelos mal formulados podem ser intratáveis mesmo quando o problema subjacente é gerenciável.
  • Elementos não convexos ou não lineares exigem linearização adicional ou solvers especializados, aumentando a complexidade do modelo.
  • Custos de licenciamento de solvers podem ser significativos para ferramentas comerciais, embora existam alternativas de código aberto de alta qualidade.
  • Os resultados são tão bons quanto o modelo: a especificação incorreta de restrições leva a ótimos sem sentido.

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

  • Produz soluções comprovadamente ótimas com uma lacuna de otimalidade quantificável, permitindo justificativa rigorosa de decisões.
  • Lida nativamente com variáveis binárias e inteiras gerais, capturando indivisibilidade do mundo real e restrições lógicas.
  • Solvers modernos (Gurobi, CPLEX, SCIP) exploram branch-and-bound avançado, planos de corte e pré-processamento para lidar com instâncias grandes de forma eficiente.
  • A formulação transparente do modelo torna as suposições explícitas e auditáveis por especialistas do domínio.
  • Suporta análise de sensibilidade e estudos paramétricos para entender como as soluções mudam com os dados de entrada.
  • Amplamente suportado por linguagens de modelagem (AMPL, GAMS, Pyomo, JuMP), permitindo prototipagem rápida.

Aplicações

  • Cadeia de suprimentos e logística: roteamento de veículos, localização de instalações e otimização de estoque com quantidades inteiras de remessa.
  • Escalonamento de força de trabalho: escalonamento de enfermeiros, atribuição de tripulação e planejamento de turnos com variáveis de atribuição binárias.
  • Orçamento de capital: seleção de um portfólio de projetos de investimento indivisíveis sujeitos a restrições orçamentárias.
  • Telecomunicações e projeto de rede: expansão de capacidade e roteamento com decisões binárias de ativação de link.
  • Sistemas de energia: compromisso de unidades em redes de energia decidindo quais geradores ligar ou desligar a cada hora.
  • Manufatura: dimensionamento de lotes de produção, escalonamento de máquinas e problemas de corte de estoque com tamanhos de lote inteiros.

Como funciona

Como funciona

1

Definir o modelo de otimização: uma função objetivo (combinação linear de variáveis de decisão a minimizar ou maximizar), restrições lineares de desigualdade e igualdade, e requisitos de integridade. Variáveis contínuas tratam quantidades que podem ser fracionárias; variáveis binárias (0/1) ou inteiras gerais tratam decisões discretas.

Fórmula
\min_{x,y}\; c^\top x + d^\top y \quad \text{s.t.}\; Ax + By \leq b,\; x \geq 0,\; y \in \mathbb{Z}^p
2

Resolver a relaxação PL (Programação Linear) descartando temporariamente as restrições de integridade. Isso fornece um limite inferior (para minimização) no objetivo ótimo da PIM e uma solução candidata que pode ser fracionária.

Fórmula
\text{LP relaxation: replace } y \in \mathbb{Z}^p \text{ with } y \geq 0
3

Selecionar uma variável inteira fracionária da solução da relaxação PL. Criar dois subproblemas filhos adicionando uma restrição de piso em um e uma restrição de teto no outro, particionando o espaço viável sem perder nenhum ponto viável inteiro.

Fórmula
\text{Select fractional } y_j^*; \text{ create subproblems: } y_j \leq \lfloor y_j^* \rfloor \text{ and } y_j \geq \lceil y_j^* \rceil
4

Resolver a relaxação PL de cada subproblema. Se o limite for pior que a melhor solução inteira encontrada até agora (o incumbente), podar esse ramo. Se a solução PL por acaso for viável inteira, atualizar o incumbente se ele melhorar o objetivo.

Fórmula
\text{Prune node if LP bound} \geq \text{incumbent; update incumbent when integer-feasible solution found}
5

Opcionalmente, adicionar planos de corte — desigualdades válidas que cortam a solução PL fracionária sem remover nenhum ponto viável inteiro. Cortes de Gomory são a abordagem clássica; cortes específicos do problema (por exemplo, cortes de clique, cortes de fluxo) podem reduzir dramaticamente o tamanho da árvore.

Fórmula
\text{Add Gomory or problem-specific cutting planes to tighten LP relaxation before branching}
6

Parar quando a árvore branch-and-bound for totalmente explorada ou quando a lacuna entre a melhor solução inteira e o limite inferior global cair dentro de uma tolerância especificada pelo usuário (por exemplo, 0,01%). Retornar a solução incumbente com seu certificado de otimalidade.

Fórmula
\text{Stop when all nodes pruned; return incumbent } x^*, y^* \text{ with optimality gap} \leq \epsilon

Erros comuns

  • Escolher uma tolerância de lacuna de otimalidade muito apertada pode fazer o solver rodar indefinidamente; sempre defina uma lacuna prática (por exemplo, 1%) para instâncias grandes.
  • A simetria no modelo (por exemplo, instalações intercambiáveis) cria ramos redundantes e infla a árvore de busca — use restrições de quebra de simetria.
  • Relaxações PL fracas (grande lacuna de integridade) levam a árvores branch-and-bound muito grandes; invista tempo adicionando desigualdades válidas ou apertando a formulação.
  • Tratar todas as variáveis como inteiras quando apenas algumas precisam ser é desnecessariamente custoso; use variáveis binárias apenas onde restrições lógicas as exigem.
  • Ignorar o warm-starting com uma boa solução viável inicial desperdiça tempo do solver na busca do primeiro incumbente.

Perguntas frequentes

Como a PIM difere da programação linear (PL)?

A PL exige que todas as variáveis de decisão sejam contínuas (valor real), o que pode gerar soluções fracionárias fisicamente inviáveis (por exemplo, 2,7 caminhões). A PIM adiciona restrições de integridade em algumas ou todas as variáveis, forçando soluções de número inteiro ou binárias ao custo de maior complexidade computacional.

Quando devo usar uma heurística em vez de PIM?

Quando o problema tem milhões de variáveis, estrutura altamente não linear, ou requer uma solução quase em tempo real, a PIM exata pode ser muito lenta. Meta-heurísticas (algoritmos genéticos, recozimento simulado) podem produzir boas soluções rapidamente, mas sem garantias de otimalidade. A PIM é preferível quando a certificação da qualidade da solução é importante.

O que é a lacuna de otimalidade e quão pequena ela deve ser?

A lacuna é (objetivo incumbente - limite PL) / limite PL, expressa como porcentagem. Ela certifica o quão longe a melhor solução inteira conhecida pode estar do ótimo verdadeiro. Para a maioria das aplicações práticas, uma lacuna de 0,1–1% é suficiente; lacunas mais apertadas exigem exponencialmente mais tempo do solver.

A PIM pode lidar com objetivos ou restrições não lineares?

A PIM padrão assume linearidade. Relações não lineares devem ser linearizadas (por exemplo, aproximação linear por partes, expansão binária de produtos) ou tratadas por solvers de programação não linear inteira mista (MINLP), que são significativamente mais difíceis de resolver.

Quais solvers são recomendados para PIM?

Comerciais: Gurobi e CPLEX são os benchmarks da indústria. Código aberto: SCIP, CBC (via COIN-OR) e HiGHS são competitivos para problemas de tamanho moderado. Todos suportam interfaces de modelagem padrão como AMPL, Pyomo e JuMP.

Métodos relacionados

Fontes

  1. Nemhauser, G. L., Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience, New York.

    ISBN: 9780471359432
    Copiado.
  2. Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.

    ISBN: 9780471283669
    Copiado.