Skip to content
Voltar aos resultados

Programação Inteira — IP e Programação Inteira Mista (MIP)

Proposto por
Ralph Gomory (cutting planes, 1958); land-and-doig branch-and-bound (1960)
Ano
1958
Tipo
Mathematical optimisation — exact combinatorial method

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 (IP), também chamada de programação inteira mista (MIP) quando apenas algumas variáveis são restritas a números inteiros, é um ramo da otimização matemática em que algumas ou todas as variáveis de decisão devem assumir valores inteiros ou binários.

Baseando-se na programação linear, foi formalizada através do método de planos de corte de Ralph Gomory (1958) e do algoritmo branch-and-bound de Land e Doig (1960), e desde então se tornou o quadro exato padrão para problemas de agendamento, alocação, roteamento e distribuição de recursos.

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

A programação linear comum encontra o melhor ponto em uma região factível contínua. Mas muitas decisões reais são discretas — você não pode ter 2,7 enfermeiras ou abrir meio armazém. A programação inteira adiciona a restrição de que algumas ou todas as variáveis devem ser números inteiros (ou escolhas binárias 0/1). O preço dessa restrição é computacional: o conjunto factível não é mais uma superfície suave, mas um conjunto disperso de pontos, e encontrar o melhor pode exigir a análise de um número enorme de soluções candidatas. Solucionadores gerenciam isso dividindo inteligentemente o problema em subproblemas menores (branching) e podando ramos que não podem superar a melhor solução encontrada até agora (bounding), ao mesmo tempo em que apertam a aproximação contínua através de desigualdades adicionadas (planos de corte).

História

A programação inteira surgiu no final da década de 1950, quando pesquisadores buscaram estender a programação linear para decisões discretas. Ralph Gomory introduziu o método sistemático de planos de corte em 1958, provando que qualquer programa inteiro poderia, em princípio, ser resolvido adicionando um número finito de cortes. Land e Doig (1960) formalizaram o branch-and-bound, que se tornou o algoritmo exato dominante. Wolsey (1998) e Nemhauser e Wolsey (1988) forneceram os tratamentos canônicos em livros didáticos nos quais o campo ainda se baseia. A revolução prática veio com o desenvolvimento de solucionadores branch-and-cut na década de 1990, combinando ambas as técnicas com heurísticas avançadas, e mais tarde com a explosão do desempenho de solucionadores comerciais e de código aberto que permitem aplicações em larga escala no mundo real hoje.

Quando usar

Use programação inteira quando as decisões são inerentemente discretas — escolhas binárias sim/não, quantidades inteiras ou restrições lógicas ligar/desligar — e quando você precisa de uma solução ótima exata ou quase exata com um limite de qualidade comprovável. É adequada para agendamento, alocação de tripulação e recursos, roteamento de veículos, localização de instalações, orçamento de capital e seleção de portfólio. Não há requisito de tamanho mínimo de amostra, pois IP é uma estrutura de otimização determinística, em vez de um procedimento de inferência estatística. Os tipos de variáveis podem ser binários, categóricos (codificados como binários) ou contínuos (no caso de inteiros mistos). O principal requisito prático é que o problema possa ser modelado com um objetivo linear e restrições lineares; se o objetivo ou as restrições forem não lineares, são necessárias extensões de programação não linear inteira mista (MINLP).

Limitações e considerações

  • A programação inteira é NP-difícil em geral; o tempo de solução pode crescer exponencialmente com o tamanho do problema e formulação ruim.
  • Uma relaxação LP fraca (grande lacuna de integridade) leva a árvores de busca profundas e caras e longos tempos de execução.
  • A expansão binária de variáveis categóricas de alta cardinalidade pode explodir o tamanho do modelo.
  • Para instâncias muito grandes, os solucionadores podem precisar ser terminados precocemente com uma tolerância de lacuna em vez de atingir lacuna zero.

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 ótimas exatas com uma lacuna de otimalidade certificada, ao contrário de heurísticas que não oferecem garantia de qualidade.
  • Manipula variáveis binárias e inteiras gerais nativamente, tornando-a a estrutura natural para decisões combinatórias.
  • Aplicável a uma ampla gama de problemas de domínio — agendamento, roteamento, alocação, mochila — com a mesma maquinaria matemática.
  • Solucionadores modernos de branch-and-cut podem resolver problemas com milhões de variáveis e restrições que teriam sido intratáveis décadas atrás.

Aplicações

  • Agendamento de pessoal e enfermeiros — alocação de turnos para atender aos requisitos de cobertura, respeitando as regulamentações de horas de trabalho.
  • Roteamento de veículos e logística — encontrar rotas de entrega de custo mínimo sob restrições de capacidade e janela de tempo.
  • Localização de instalações — decidir quais armazéns ou fábricas abrir para minimizar o custo total de distribuição.
  • Orçamento de capital — selecionar um portfólio de projetos de investimento dentro de um orçamento para maximizar o retorno total.
  • Planejamento de produção — determinar tamanhos de lote inteiros ao longo de períodos de tempo para equilibrar custos de setup e custos de manutenção.
  • Projeto de rede — escolher quais links instalar em uma rede de comunicação ou transporte.

Como funciona

Como funciona

1

O problema é formulado como um programa matemático: defina variáveis de decisão (que devem ser declaradas como inteiras ou binárias onde o problema exigir), escreva uma função objetivo linear para minimizar ou maximizar e liste todas as restrições lineares. Uma formulação apertada — aquela cuja relaxação contínua (LP) está o mais próxima possível do ótimo inteiro verdadeiro — reduz dramaticamente o tempo de solução.

2

As restrições de integridade são temporariamente descartadas para obter a relaxação LP. Resolver essa relaxação é rápido e fornece um limite: seu valor ótimo é sempre pelo menos tão bom quanto o ótimo inteiro verdadeiro (um limite inferior para minimização). Se a solução da relaxação por acaso for totalmente inteira, o problema está resolvido. Caso contrário, a lacuna entre a relaxação e a integridade guia a busca.

3

Uma variável fracionária na solução de relaxação é selecionada e o problema é dividido em dois subproblemas — um exigindo que a variável seja arredondada para baixo, outro para cima. Cada subproblema é relaxado e resolvido, criando uma árvore de busca. Ramos cujo limite de relaxação é pior do que a melhor solução inteira encontrada até agora são podados sem exploração adicional.

4

Planos de corte são desigualdades lineares válidas que cortam parte da região factível da relaxação LP sem remover nenhum ponto inteiro factível. Adicionar cortes fortes (cortes de Gomory, desigualdades de cobertura, cortes de clique) aperta o limite LP e reduz o número de nós que o solucionador deve explorar.

5

A melhor solução inteira factível encontrada em todos os nós explorados é retornada como o ótimo. A lacuna de otimalidade — a diferença percentual entre a melhor solução inteira e o melhor limite restante — é relatada; uma lacuna de zero certifica a otimalidade global. Para instâncias NP-difíceis grandes, o solucionador pode terminar precocemente com uma tolerância de lacuna especificada pelo usuário, retornando uma solução quase ótima com um limite comprovável.

Erros comuns

  • Declarar variáveis como contínuas quando deveriam ser inteiras — ou vice-versa — produz silenciosamente soluções incorretas; sempre verifique se os tipos de variáveis correspondem à realidade física do problema.
  • Uma formulação solta com uma grande lacuna de relaxação LP causa ramificação excessiva; invista tempo no aperto da formulação (desigualdades fortes, quebra de simetria) antes de resolver.
  • Ignorar a lacuna de integridade na saída do solucionador: um valor objetivo relatado é apenas a melhor solução inteira encontrada, não necessariamente o ótimo global, a menos que a lacuna seja zero.
  • Aplicar IP a problemas cujos objetivo ou restrições são não lineares sem o tratamento MINLP apropriado resultará em modelos incorretos.
  • Para problemas de agendamento ou roteamento, deixar de adicionar desigualdades válidas (como cortes de clique ou de cobertura) deixa ganhos de desempenho substanciais na mesa.

Perguntas frequentes

Qual é a diferença entre IP e MIP?

Na programação inteira pura (IP), toda variável de decisão deve ser um inteiro. Na programação inteira mista (MIP), algumas variáveis são inteiras ou binárias, enquanto outras podem ser contínuas. MIP é a estrutura mais geral e mais comumente usada na prática, pois a maioria dos problemas reais mistura escolhas discretas com quantidades contínuas.

Por que a programação inteira é NP-difícil se a programação linear é polinomial?

A programação linear otimiza sobre um politopo convexo e pode ser resolvida em tempo polinomial pelos métodos simplex ou de ponto interior. Adicionar restrições de integridade destrói essa convexidade: o conjunto factível se torna um conjunto finito, mas potencialmente astronomicamente grande, de pontos inteiros, e nenhum algoritmo de tempo polinomial é conhecido para encontrar o melhor em geral. A relaxação LP fornece um limite, mas não uma solução direta.

Como sei se minha solução é ótima?

O solucionador relata uma lacuna de otimalidade — a diferença percentual entre a melhor solução inteira encontrada e o melhor limite inferior restante. Uma lacuna de 0% certifica a otimalidade global. Para problemas grandes, você pode definir uma tolerância de lacuna (por exemplo, 1%) e aceitar uma solução quase ótima; o limite ainda garante que o ótimo verdadeiro não pode ser mais do que essa porcentagem melhor.

O que torna uma formulação 'apertada' e por que isso importa?

Uma formulação apertada é aquela cuja relaxação LP fornece um limite próximo ao ótimo inteiro, deixando uma pequena lacuna de integridade. Quando a lacuna é pequena, o branch-and-bound precisa explorar menos nós e termina mais rápido. Adicionar desigualdades válidas, como cortes de Gomory, desigualdades de cobertura ou cortes de clique, aperta a formulação e é frequentemente a maneira mais impactante de acelerar um solucionador.

Métodos relacionados

Fontes

  1. Wolsey, L.A. (1998). Integer Programming. Wiley.

    ISBN: 9780471283669
    Copiado.
  2. Nemhauser, G.L. & Wolsey, L.A. (1988). Integer and Combinatorial Optimization. Wiley.

    ISBN: 9780471359432
    Copiado.