Skip to content
Voltar aos resultados

Programação Inteira Mista Robusta — Otimização com variáveis inteiras sob incerteza

Proposto por
Ben-Tal & Nemirovski; Bertsimas & Sim
Ano
1998–2004
Tipo
Deterministic robust reformulation of MIP under uncertainty
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?

A Programação Inteira Mista Robusta (RMIP) combina programação inteira mista com otimização robusta para encontrar soluções que permaneçam factíveis e quase ótimas apesar de parâmetros incertos.

Em vez de assumir dados fixos, ela protege decisões contra realizações adversariais ou de pior caso de entradas incertas, utilizando um conjunto de incerteza explícito para controlar o grau de conservadorismo, preservando a estrutura combinatória das decisões inteiras.

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

Programas inteiros mistos clássicos assumem que todos os dados são conhecidos com exatidão, mas na prática custos, demandas e tempos de processamento flutuam. A RMIP pergunta: quais decisões inteiras e contínuas são as melhores se os parâmetros incertos assumirem seus valores plausíveis de pior caso dentro de um intervalo definido? Ao incorporar a incerteza diretamente no modelo de otimização, a RMIP produz planos que são imunizados contra variações de dados sem recorrer a múltiplos cenários probabilísticos. A abordagem de orçamento de incerteza de Bertsimas-Sim permite que os praticantes ajustem o equilíbrio entre robustez total e eficiência de caso médio, tornando explícito o trade-off entre proteção e custo.

História

A otimização robusta como um paradigma tratável foi estabelecida por Ben-Tal e Nemirovski no final dos anos 1990 para problemas contínuos. Bertsimas e Sim (2004) a estenderam para programas lineares com um conjunto de orçamento de incerteza que preserva a tratabilidade linear. Trabalhos subsequentes integraram essa estrutura com programação inteira, resultando na RMIP, que foi amplamente adotada em pesquisa de cadeia de suprimentos, energia e transporte ao longo dos anos 2010.

Quando usar

Usar RMIP quando as decisões envolvem escolhas inteiras ou binárias (localização de instalações, dimensionamento de lotes, projeto de rede, escalonamento) e alguns parâmetros de entrada são incertos, mas as distribuições de probabilidade não estão disponíveis ou são não confiáveis. É apropriado quando violações de restrições são inaceitáveis (requisitos de factibilidade rígidos) e uma garantia determinística conservadora é preferida à otimização de valor esperado. NÃO usar quando as distribuições de incerteza são bem caracterizadas e a aproximação por média de amostra ou MIP estocástico é factível; quando todas as variáveis de decisão são contínuas (usar LP robusto em vez disso); ou quando o conjunto de incerteza é tão grande que o modelo se torna intratável sem estratégias de decomposição.

Limitações e considerações

  • Conservador por design — o objetivo de pior caso é tipicamente pior do que o objetivo de caso médio da programação estocástica.
  • A seleção de um conjunto de incerteza apropriado requer conhecimento do domínio; um conjunto mal escolhido leva a superproteção ou subproteção.
  • Reformulações robustas podem aumentar significativamente o tamanho do modelo (variáveis e restrições adicionais), elevando a carga computacional para instâncias grandes.
  • Não fornece declarações de probabilidade sobre o desempenho da solução; MIP estocástico é mais adequado quando medidas de risco probabilísticas são necessárias.

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

  • Fornece garantias determinísticas de factibilidade de pior caso sem exigir distribuições de probabilidade para parâmetros incertos.
  • O parâmetro de orçamento de incerteza (Gamma) fornece controle intuitivo e ajustável sobre o compromisso (trade-off) entre robustez e otimalidade.
  • A reformulação preserva a estrutura MIP, permitindo o uso de solucionadores comerciais maduros e tecnologia de branch-and-cut.
  • Aplicável a problemas combinatórios difíceis, como projeto de rede, localização de instalações e escalonamento de produção.
  • Computacionalmente mais tratável do que MIP estocástico completo com muitos cenários.

Aplicações

  • Projeto de rede de cadeia de suprimentos sob demanda e prazos de entrega incertos
  • Planejamento de expansão de capacidade de sistemas de energia com geração renovável incerta
  • Localização de instalações de saúde sob incerteza de demanda de pacientes
  • Escalonamento de tripulação de companhias aéreas com atrasos de voo incertos
  • Dimensionamento de lotes de fabricação sob custos e tempos de processamento incertos
  • Roteamento de rede de telecomunicações com volumes de tráfego incertos

Como funciona

Como funciona

1

Formular o MIP nominal: identificar variáveis de decisão (binárias ou inteiras y, contínuas x), função objetivo e restrições. Identificar quais parâmetros (coeficientes de custo, valores do lado direito, entradas da matriz tecnológica) são incertos e devem ser protegidos.

2

Definir um conjunto de incerteza U para os parâmetros incertos. Escolhas comuns são conjuntos caixa (intervalos para cada parâmetro), conjuntos elipsoidais (incerteza correlacionada) ou o conjunto de orçamento de Bertsimas-Sim (no máximo Gamma parâmetros desviam simultaneamente), onde Gamma controla o conservadorismo.

3

Substituir cada restrição incerta por sua contraparte robusta, que deve ser válida para todas as realizações em U. Para incerteza de orçamento, isso resulta em uma reformulação tratável: a restrição original é aumentada com um termo de penalidade que controla a soma de desvios de pior caso. O resultado é um modelo maior, mas ainda tratável por MIP.

4

Resolver o MIP robusto reformulado com um solver padrão de branch-and-bound ou branch-and-cut (por exemplo, CPLEX, Gurobi, SCIP). A reformulação preserva os requisitos de integridade em y. Para instâncias de larga escala, a decomposição de Benders ou métodos de plano de corte podem decompor o problema.

5

Avaliar a solução robusta por: (a) calcular seu valor objetivo sob parâmetros nominais e de pior caso, (b) comparar com a solução de programação estocástica usando cenários de Monte Carlo, e (c) reportar o preço da robustez — o custo extra pago pela proteção contra incerteza.

Erros comuns

  • Escolher Gamma=0 (nenhum orçamento de incerteza) reproduz o MIP nominal e não oferece proteção; Gamma muito grande leva a soluções excessivamente conservadoras e operacionalmente impraticáveis.
  • Tratar todos os parâmetros como incertos simultaneamente pode tornar a reformulação intratável — identificar os parâmetros incertos críticos para proteger seletivamente.
  • Ignorar a estrutura de correlação das incertezas pode resultar em um conjunto de incerteza excessivamente pessimista; conjuntos elipsoidais são preferíveis quando as correlações são conhecidas.
  • Relatar apenas o objetivo de pior caso sem compará-lo com benchmarks nominais ou estocásticos fornece uma imagem incompleta da qualidade da solução.

Perguntas frequentes

Como a RMIP difere da programação inteira mista estocástica?

MIP estocástico usa distribuições de probabilidade e otimiza o desempenho esperado em cenários amostrados, enquanto RMIP protege contra o pior caso dentro de um conjunto de incerteza sem exigir informações distribucionais. RMIP fornece uma única solução robusta determinística; MIP estocástico fornece uma política que é boa em média.

O que é o 'preço da robustez' e quão grande ele é tipicamente?

O preço da robustez é o aumento percentual no valor objetivo em comparação com o ótimo nominal (sem incerteza). Bertsimas e Sim mostram que ele cresce aproximadamente linearmente com Gamma, mas permanece modesto para valores típicos de orçamento, frequentemente 5–15% em aplicações práticas.

A RMIP pode lidar com valores de lado direito incertos, bem como com coeficientes de custo incertos?

Sim. Incerteza nos lados direitos das restrições leva a restrições de factibilidade robusta, enquanto incerteza nos coeficientes do objetivo afeta a otimalidade robusta. Ambas podem ser tratadas simultaneamente dentro do arcabouço de orçamento de incerteza, embora a estrutura de reformulação difira.

A RMIP é solúvel com solucionadores (solucionadores) MIP padrão?

Para o conjunto de orçamento de Bertsimas-Sim, a reformulação robusta permanece um MIP e pode ser resolvida diretamente com solucionadores como CPLEX ou Gurobi. Conjuntos de incerteza elipsoidais produzem programas de cone de segunda ordem inteiros mistos (MISOCP), que também são suportados por solucionadores modernos.

Quando devo preferir um conjunto de incerteza tipo caixa em vez do conjunto de orçamento de incerteza?

Um conjunto caixa protege contra todos os parâmetros desviando simultaneamente para seus extremos, o que é frequentemente excessivamente conservador. O conjunto de orçamento (Gamma) é preferido quando desvios de pior caso simultâneos de todos os parâmetros são improváveis, pois resulta em soluções menos conservadoras e mais econômicas.

Métodos relacionados

Fontes

  1. Bertsimas, D., Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53.

    Abrir referência DOI
    Copiado.
  2. Ben-Tal, A., El Ghaoui, L., Nemirovski, A. (2009). Robust Optimization. Princeton University Press, Princeton, NJ.

    ISBN: 9780691143682
    Copiado.