Programação Inteira Estocástica — Otimização Sob Incerteza com Decisões Discretas e Contínuas
- Proposto por
- Birge, J. R.; Louveaux, F.; Sen, S.
- Ano
- 1990s–2000s
- Tipo
- Stochastic optimization model
- 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 Estocástica (PIE) é um arcabouço de otimização que encontra a melhor combinação de decisões binárias, inteiras e contínuas quando parâmetros chave — custos, demandas, capacidades — são incertos e modelados como distribuições de probabilidade sobre um conjunto de cenários.
Estende a Programação Inteira Clássica (PIC) incorporando árvores de cenários ou objetivos de valor esperado que se protegem contra a incerteza, ao mesmo tempo que respeitam restrições combinatórias.
A intuição por trás do método
Muitos problemas reais de planejamento forçam escolhas sim/não ou de número inteiro — construir uma instalação ou não, atribuir um número inteiro de veículos — mas o futuro é incerto. A PIE formaliza isso considerando uma coleção de cenários futuros plausíveis e escolhendo compromissos de primeira etapa (antes que a incerteza seja revelada) que minimizam o custo esperado ou maximizam o benefício esperado em todos os cenários. As restrições inteiras tornam o problema combinatoriamente difícil, mas algoritmos de decomposição exploram a estrutura de cenários para tornar instâncias grandes tratáveis.
História
A programação estocástica originou-se com Dantzig (1955) e Beale (1955) como LP de dois estágios. A extensão inteira mista emergiu proeminentemente nos anos 1990 com as adaptações do método L-shaped para recurso inteiro por Laporte e Louveaux (1993) e o tratamento abrangente no livro de Birge e Louveaux (1997). O algoritmo C3/D2 de Sen e Higle (2005) avançou solucionadores escaláveis de PIE, estabelecendo o campo como uma disciplina madura dentro da pesquisa operacional.
Quando usar
Usar PIE quando as decisões envolvem escolhas discretas ou binárias (investir/não investir, número de unidades a abrir) e os parâmetros de entrada chave são genuinamente incertos com distribuições de probabilidade quantificáveis. Ideal para projeto de rede de cadeia de suprimentos sob incerteza de demanda, expansão de capacidade energética, planejamento de instalações de saúde e pré-posicionamento de resposta a desastres. Não usar quando todas as decisões são contínuas (usar LP estocástico em vez disso), quando a incerteza não pode ser significativamente quantificada como distribuições, quando o número de cenários necessários para representar a incerteza leva a tamanhos de modelo intratáveis e a decomposição não está disponível, ou quando uma heurística baseada em simulação é suficiente para a qualidade de decisão exigida.
Limitações e considerações
- A complexidade computacional cresce combinatoriamente com o número de cenários e variáveis inteiras; instâncias grandes podem ser intratáveis sem decomposição eficaz.
- Requer distribuições de probabilidade explícitas ou conjuntos de cenários — modelos de incerteza mal especificados levam a soluções que têm desempenho ruim fora da amostra.
- Formulações de dois estágios podem simplificar demais decisões multiperíodo; PIE multi-estágio é significativamente mais difícil.
- O recurso inteiro no segundo estágio destrói a convexidade explorada pelos cortes de Benders padrão, exigindo cortes L-shaped inteiros especializados.
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
- Lida com decisões discretas combinatórias sob incerteza em um único modelo de otimização coerente.
- Produz planos de primeira etapa protegidos que equilibram o desempenho esperado em todos os cenários.
- As métricas VSE e VEIP fornecem justificativa transparente para o valor da modelagem estocástica.
- Algoritmos de decomposição (L-shaped, progressive hedging) escalam para grandes conjuntos de cenários.
- Amplamente suportado em solucionadores comerciais (CPLEX, Gurobi) e linguagens de modelagem (AMPL, Pyomo).
Aplicações
- Projeto de rede de cadeia de suprimentos com demandas de clientes incertas e decisões binárias de localização de instalações.
- Planejamento de expansão de capacidade de energia elétrica sob geração renovável incerta e crescimento da carga.
- Alocação de recursos do sistema de saúde (equipe inteira, abertura binária de clínicas) sob incerteza epidemiológica.
- Pré-posicionamento de logística humanitária de suprimentos discretos antes de cenários de desastre.
- Otimização de portfólio financeiro com custos de transação e restrições de lote inteiro sob incerteza de mercado.
- Agendamento de tripulação de companhias aéreas sob atrasos de voo incertos com variáveis binárias de atribuição.
Como funciona
Como funciona
Identificar variáveis de decisão: decisões de primeira etapa x tomadas antes que a incerteza seja revelada (inteiras e/ou binárias entre elas), e variáveis de recurso de segunda etapa y(xi) tomadas após o cenário xi se materializar. Especificar coeficientes do objetivo, matrizes de restrição e a distribuição de probabilidade ou conjunto discreto de cenários para parâmetros incertos.
Construir um conjunto finito de cenários {xi_1, ..., xi_S} com probabilidades associadas {p_1, ..., p_S} aproximando a distribuição subjacente. Cenários podem ser derivados de dados históricos, elicitação de especialistas, amostragem por hipercubo latino ou métodos de correspondência de momentos. A qualidade do cenário afeta diretamente a qualidade da solução.
Formular o equivalente determinístico: minimizar c'x + sum_s p_s Q(x, xi_s) sujeito a restrições de primeira etapa e integridade. Q(x, xi_s) é a função de valor de segunda etapa — o custo ótimo das ações de recurso dadas x e o cenário xi_s. O programa combinado é uma grande PIC cujo tamanho cresce com o número de cenários.
Fórmula
\min_{x \in X} c^T x + \mathbb{E}_\xi[Q(x,\xi)] \quad \text{s.t. } Ax = b,\; x \in \mathbb{Z}^p \times \mathbb{R}^{n-p}Resolver usando algoritmos de decomposição — método L-shaped (decomposição de Benders) para segundos estágios convexos, branch-and-cut com subproblemas de cenário, ou progressive hedging para decomposição paralela de cenários. A integridade no segundo estágio requer cortes adicionais (cortes L-shaped inteiros, lift-and-project). Solucionadores modernos (CPLEX, Gurobi com callbacks, ou bibliotecas específicas de PIE) implementam essas rotinas.
Avaliar a solução via Valor da Solução Estocástica (VSE = CVM - CP) e o Valor Esperado da Informação Perfeita (VEIP = CP - VSA), onde CP é o valor ótimo do problema de recurso, CVM é o custo esperado de usar a solução determinística de valor médio, e VSA é o valor de esperar para ver. Essas métricas quantificam o benefício de modelar explicitamente a incerteza.
Erros comuns
- Usar poucos cenários sub-representa a incerteza, gerando soluções excessivamente confiantes; muitos cenários tornam o modelo computacionalmente infactível.
- Confundir os papéis das variáveis de primeira e segunda etapa leva a formulações que não respeitam a temporalidade da revelação da informação.
- Confiar na solução de valor esperado (ignorando a estocasticidade) pode ser significativamente subótimo — sempre calcular o VSE para justificar o esforço da PIE.
- Negligenciar a integridade no estágio de recurso quando ela está realmente presente resulta em uma relaxação cuja solução pode ser infactível na prática.
- Configurações padrão do solucionador para MIP frequentemente precisam de ajuste (prioridades de ramificação, estratégias de corte) em frameworks de decomposição de PIE.
Perguntas frequentes
Como a PIE difere da Programação Inteira regular?
A PIC otimiza sob parâmetros fixos e conhecidos. A PIE modela explicitamente parâmetros incertos como um conjunto de cenários com probabilidades, otimizando o desempenho esperado em todos os cenários, garantindo que as decisões de primeira etapa sejam tomadas antes que a incerteza seja revelada.
Quantos cenários eu preciso?
Não há regra universal. Apenas 10–50 cenários podem ser suficientes para decisões estáveis de primeira etapa em alguns problemas; outros requerem milhares. Técnicas de redução de cenário e testes de estabilidade (verificando que a solução ótima não muda à medida que você adiciona mais cenários) ajudam a determinar a adequação.
O que é o método L-shaped?
O método L-shaped é uma decomposição de Benders adaptada para programas estocásticos. Ele resolve iterativamente um MIP mestre sobre variáveis de primeira etapa e subproblemas de cenário, adicionando cortes de otimalidade e factibilidade ao mestre até a convergência. Para recurso inteiro, cortes L-shaped inteiros substituem os cortes de Benders padrão.
Quando devo usar progressive hedging em vez de L-shaped?
Progressive hedging decompõe por cenário em vez de por estrutura de subproblema, tornando-o adequado para computação paralela. É preferível quando os cenários são muitos e os subproblemas são grandes, e quando o algoritmo pode ser executado em um cluster. O L-shaped é geralmente preferido para cenários menos numerosos e bem estruturados.
A PIE pode lidar com mais de dois estágios?
Sim, mas a PIE multi-estágio requer uma árvore de cenários que cresce exponencialmente no número de estágios, e a decomposição torna-se substancialmente mais complexa. Na prática, a maioria dos modelos de PIE aplicados usa dois estágios, aproximando dinâmicas multiperíodo por horizonte rolante ou agregação.
Métodos relacionados
Fontes
Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer Series in Operations Research. New York: Springer.
ISBN: 9780387982175Copiado.Sen, S., & Higle, J. L. (2005). The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: Set convexification. Mathematical Programming, 104(1), 1–20.
Abrir referência DOICopiado.