Skip to content
Voltar aos resultados

Programação Inteira Estocástica — Otimizando Decisões Discretas Sob Incerteza

Proposto por
Dantzig, G. B.; Beale, E. M. L.
Ano
1955
Tipo
Optimization under uncertainty with discrete decisions
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 Estocástica (SIP) é uma estrutura de otimização que combina variáveis de decisão inteiras (discretas) com modelagem probabilística explícita da incerteza.

Ela busca a melhor decisão "aqui e agora" que minimiza o custo esperado (ou maximiza o benefício esperado) em uma distribuição de cenários futuros, considerando o fato de que algumas decisões devem ser tomadas antes que a incerteza seja resolvida.

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

Muitas decisões reais são tanto discretas (construir uma instalação ou não; atribuir um trabalhador ou não) quanto incertas (demanda, custos e restrições não são conhecidos no momento da decisão). A SIP lida com ambos os desafios simultaneamente. Ela modela o futuro incerto como um conjunto de cenários com probabilidades associadas, então encontra a solução inteira que tem o melhor desempenho em média — ou que se protege contra os piores resultados. Ao contrário da programação linear estocástica, a estrutura discreta torna o problema combinatoriamente mais difícil, mas as decisões produzidas são diretamente implementáveis sem arredondamento ou aproximação.

História

A programação estocástica remonta a Dantzig (1955) e Beale (1955), que propuseram independentemente modelos de recurso de dois estágios para programas lineares sob incerteza. A extensão inteira surgiu à medida que a programação inteira amadureceu nas décadas de 1960-1980. O livro-texto de Birge e Louveaux de 1997 codificou o campo, e Kleywegt et al. (2002) estabeleceram a Aproximação da Média Amostral como a abordagem computacional padrão para otimização discreta estocástica em larga escala.

Quando usar

Use Programação Inteira Estocástica quando as decisões são inerentemente discretas (escolhas binárias, alocações de unidades inteiras, atribuições de roteamento) e os parâmetros-chave são incertos no momento da decisão. É bem adequada para planejamento de capacidade, projeto de redes de cadeia de suprimentos, agendamento sob incerteza de demanda, despacho de energia e alocação de recursos com rendimentos aleatórios. NÃO a use quando todas as variáveis são contínuas (programação linear estocástica é suficiente), quando a incerteza é desprezível ou totalmente observável antes de decidir, quando a escala do problema torna a enumeração de cenários computacionalmente intratável sem infraestrutura de decomposição, ou quando apenas um único cenário determinístico é relevante.

Limitações e considerações

  • A complexidade computacional cresce rapidamente com o número de cenários e variáveis inteiras; grandes instâncias são NP-difíceis.
  • A geração de cenários requer distribuições de probabilidade críveis, que podem ser difíceis de obter ou estimar a partir de dados limitados.
  • Extensões multiestágio (mais de dois estágios) enfrentam crescimento exponencial em árvores de cenários e raramente são tratáveis além de três estágios.
  • Habilidade de modelagem é necessária para especificar corretamente a viabilidade do recurso, as restrições de não-antecipação e as estruturas de penalidade.

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

  • Modela explicitamente a incerteza em vez de usar estimativas pontuais, produzindo soluções robustas para cenários realizados.
  • Lida com decisões discretas e binárias nativamente, então as soluções são diretamente implementáveis sem arredondamento post-hoc.
  • A estrutura de dois estágios separa claramente as decisões estratégicas de primeiro estágio das ações operacionais de recurso de segundo estágio.
  • Suporta estruturas de recurso ricas, incluindo aquisição de recursos, custos de penalidade e agendamento corretivo.
  • Limites de qualidade estatística (via SAA) permitem que os praticantes certifiquem a quase-otimalidade com confiança quantificada.

Aplicações

  • Projeto de rede de cadeia de suprimentos sob demanda estocástica e tempos de espera
  • Planejamento de expansão de geração de energia com produção renovável incerta
  • Agendamento de salas de cirurgia hospitalares sob durações de procedimento variáveis
  • Agendamento de tripulação de companhias aéreas com atrasos de voo estocásticos
  • Pré-posicionamento de suprimentos de ajuda humanitária antes de desastres
  • Otimização de portfólio financeiro com seleção discreta de ativos e retornos baseados em cenários

Como funciona

Como funciona

1

Formule o problema de primeiro estágio: escolha variáveis de decisão inteiras (ou mistas-inteiras) x antes que a incerteza seja revelada. Defina um objetivo que inclua tanto o custo imediato quanto o custo de recurso esperado em todos os cenários. As restrições que ligam x às condições de viabilidade são especificadas aqui.

Fórmula
\min_{x \in \mathbb{Z}^n} c^T x + \mathbb{E}_\xi[Q(x, \xi)]
2

Represente a incerteza através de um conjunto finito de cenários. Cada cenário atribui valores específicos a parâmetros aleatórios (níveis de demanda, custos, disponibilidade de recursos). Os cenários podem ser gerados por amostragem histórica, sorteios de Monte Carlo a partir de distribuições ajustadas, ou casos representativos definidos por especialistas. Cada cenário possui um peso de probabilidade que soma um.

3

Na formulação padrão de dois estágios, depois que x é fixado e o cenário xi é realizado, um problema de recurso (segundo estágio) determina as ações corretivas y. O problema de recurso é frequentemente um programa linear ou inteiro. O modelo completo minimiza c^T x mais o custo de recurso esperado E[Q(x, xi)].

Fórmula
Q(x, \xi) = \min_{y \geq 0} q(\xi)^T y \;\text{ s.t. } W(\xi)y = h(\xi) - T(\xi)x
4

Resolva os subproblemas de cenário para avaliar o custo de recurso para cada cenário dado x. As técnicas incluem branch-and-bound, decomposição de Benders, relaxamento lagrangiano e o método de Aproximação da Média Amostral (SAA). Para grandes árvores de cenários, algoritmos de decomposição exploram a estrutura em blocos entre os cenários.

5

Agregue os resultados dos subproblemas para estimar o custo de recurso esperado. No SAA, este é a média sobre S cenários amostrados. A aproximação resultante converge para a verdadeira expectativa à medida que S cresce. Limites estatísticos na qualidade da solução podem ser calculados a partir da variância da amostra.

Fórmula
\mathbb{E}_\xi[Q(x,\xi)] \approx \frac{1}{S} \sum_{s=1}^{S} Q(x, \xi_s)
6

Verifique a otimalidade ou quase-otimalidade através de gaps de otimalidade, critérios de convergência ou intervalos de confiança estatísticos do SAA. Se o gap não for aceitável, refine o conjunto de cenários, aumente o tamanho da amostra ou aperte os relaxamentos. Relate a solução de primeiro estágio x* e seu custo total esperado.

Erros comuns

  • Usar poucos cenários produz soluções excessivamente confiantes; usar muitos torna o problema computacionalmente inviável — equilibre via diagnósticos de convergência SAA.
  • Ignorar a integralidade no segundo estágio quando ela é realmente necessária leva a estimativas de custo otimistas e ações de recurso inviáveis.
  • Assumir independência de cenários quando os parâmetros são correlacionados (por exemplo, demanda e preço correlacionados) introduz viés sistemático na estimativa de custo esperado.
  • Esquecer as restrições de não-antecipação em problemas multiestágio permite que o modelo explore informações futuras que não estariam disponíveis na prática.

Perguntas frequentes

Como a Programação Inteira Estocástica difere da otimização robusta?

A SIP minimiza o custo esperado em um conjunto de cenários ponderados por probabilidade, aceitando que alguns cenários podem gerar alto custo se forem improváveis. A otimização robusta minimiza o custo do pior caso em um conjunto de incerteza, sem fazer suposições probabilísticas. A SIP requer uma distribuição de probabilidade; a otimização robusta requer apenas um conjunto de incerteza. A SIP é geralmente menos conservadora, mas exige mais dados.

Quantos cenários são necessários na prática?

Isso depende da dimensão do problema e da precisão desejada. A abordagem de Aproximação da Média Amostral (SAA) fornece intervalos de confiança estatísticos sobre o gap de otimalidade. Estudos aplicados típicos usam de dezenas a milhares de cenários; diagnósticos de convergência (variância do estimador do limite) guiam a escolha. Para problemas estruturados, técnicas de redução de cenários (por exemplo, Heitsch-Romisch) podem reduzir substancialmente a contagem de cenários.

A Programação Inteira Estocástica pode lidar com mais de dois estágios?

Sim, mas a SIP multiestágio é significativamente mais difícil. A árvore de cenários cresce exponencialmente com os estágios, e as restrições de não-antecipação devem ser impostas em cada nó. Na prática, modelos de três estágios são a norma para aplicações tratáveis; além disso, aproximações como horizonte rolante ou redução de árvore de cenários são tipicamente necessárias.

Qual software pode resolver modelos de Programação Inteira Estocástica?

Os resolvedores comuns incluem CPLEX e Gurobi (via linguagens de modelagem algébrica como AMPL, JuMP em Julia, ou PuLP/Pyomo em Python), que suportam decomposição de cenários. Estruturas especializadas de programação estocástica incluem PySP (Python), resolvedores de formato SMPS e o pacote Julia StochasticPrograms.jl, que implementa SAA e progressive hedging.

Programação Inteira Estocástica é o mesmo que Programação Mista-Inteira Estocástica?

Programação Inteira Estocástica é a classe mais ampla; Programação Mista-Inteira Estocástica (SMIP) refere-se especificamente a modelos onde algumas variáveis são contínuas e outras são inteiras em um ou ambos os estágios. SMIP é a forma mais geral e mais frequentemente encontrada na prática.

Métodos relacionados

Fontes

  1. Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.

    ISBN: 978-1-4614-0237-4
    Copiado.
  2. Kleywegt, A. J., Shapiro, A., & Homem-de-Mello, T. (2002). The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2), 479-502.

    Abrir referência DOI
    Copiado.