Skip to content
Voltar aos resultados

Programação Linear Robusta — Otimização Sob Incerteza

Proposto por
Ben-Tal, A. and Nemirovski, A.; further developed by Bertsimas, D. and Sim, M.
Ano
1999–2004
Tipo
Uncertainty-robust linear 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 Linear Robusta (RLP) estende a programação linear clássica para lidar com a incerteza nos dados do problema — coeficientes de custo, coeficientes de restrição ou lados direitos — exigindo que as soluções permaneçam factíveis e quase ótimas em todas as realizações dos parâmetros incertos dentro de um conjunto de incerteza definido.

Ela substitui suposições probabilísticas por garantias de pior caso, tornando-a prática quando o conhecimento distribucional é limitado.

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

A programação linear ordinária encontra a melhor solução assumindo que todos os dados são conhecidos com exatidão. Na prática, os coeficientes são estimados, previstos ou medidos com erro. A RLP pergunta: qual é a melhor decisão que permanece factível independentemente de como os parâmetros incertos variam dentro de uma faixa plausível? O analista especifica um conjunto de incerteza — um box, elipsoide ou região politópica — e o solver encontra o plano que é ótimo para o pior caso dentro desse conjunto. A formulação de orçamento de incerteza de Bertsimas e Sim permite ao analista ajustar o conservadorismo: um parâmetro Gamma controla quantos coeficientes podem desviar simultaneamente, interpolando entre o LP nominal e o pior caso totalmente conservador.

História

A otimização robusta foi firmemente estabelecida teoricamente por Ben-Tal e Nemirovski (1999), que mostraram que programas lineares incertos com conjuntos de incerteza elipsoidais resultam em programas de cone de segunda ordem tratáveis. Bertsimas e Sim (2004) introduziram o framework de orçamento de incerteza, que mantém a reformulação como um programa linear e torna a robustez ajustável através de um único parâmetro, expandindo grandemente a adoção prática em pesquisa operacional e engenharia.

Quando usar

Usar RLP quando a incerteza dos dados é real, mas as distribuições de probabilidade são desconhecidas ou não confiáveis, como no planejamento da cadeia de suprimentos com demanda incerta, despacho de energia com erros de previsão ou construção de portfólio financeiro sob retornos ambíguos. É apropriado quando a factibilidade das restrições sob todos os cenários é inegociável. Evitar RLP quando a incerteza é negligenciável em relação à escala do objetivo, quando as distribuições de probabilidade são bem caracterizadas (programação estocástica pode ser preferível), quando o número de parâmetros incertos é tão grande que a contraparte robusta se torna intratável, ou quando o cenário de pior caso é irrealisticamente pessimista para a aplicação.

Limitações e considerações

  • A orientação para o pior caso pode produzir soluções excessivamente conservadoras quando cenários extremos são altamente improváveis.
  • Conjuntos de incerteza elipsoidais produzem programas de cone de segunda ordem tratáveis, mas não mais LPs puros, aumentando os requisitos do solver.
  • Exige que o analista especifique um conjunto de incerteza, que é em si uma escolha de modelagem que afeta significativamente os resultados.
  • Não fornece diretamente declarações de probabilidade de violação; a programação estocástica é melhor se as probabilidades de cauda importam.
  • Degenera para o LP nominal quando Gamma = 0, não oferecendo proteção contra a incerteza.

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 de factibilidade de pior caso sem exigir suposições distribucionais.
  • A formulação de orçamento Bertsimas-Sim produz uma contraparte LP tratável, solúvel com solvers prontos para uso.
  • O orçamento de robustez Gamma dá ao analista um controle intuitivo para balancear a qualidade da solução contra o conservadorismo.
  • Computacionalmente eficiente — contrapartes robustas para conjuntos de orçamento têm complexidade similar à do LP original.
  • Particularmente bem adequada para problemas onde a violação de restrições é custosa ou insegura.

Aplicações

  • Projeto de rede da cadeia de suprimentos com custos de transporte e demanda incertos
  • Despacho de sistema de energia elétrica sob incerteza de previsão de energia renovável
  • Otimização de portfólio com faixas ambíguas de retorno de ativos
  • Planejamento de tratamento de radioterapia com incerteza de movimento do paciente
  • Agendamento de tripulação de companhia aérea sob atrasos de voo incertos
  • Alocação de recursos hídricos com precipitação e evaporação incertas

Como funciona

Como funciona

1

Formular o programa linear nominal: minimizar um objetivo linear c^T x sujeito a restrições de desigualdade linear Ax <= b e não-negatividade. Identificar quais coeficientes — tipicamente entradas da matriz de restrição a_ij — são incertos. Esta etapa espelha a modelagem LP padrão, mas sinaliza cada parâmetro incerto.

Fórmula
\min c^T x \text{ s.t. } Ax \leq b, \; x \geq 0
2

Construir um conjunto de incerteza U que capture a faixa de valores plausíveis dos parâmetros sem exigir uma distribuição de probabilidade. Escolhas comuns são conjuntos de box (cada parâmetro varia independentemente dentro de [a_bar - a_hat, a_bar + a_hat]), conjuntos elipsoidais (Ben-Tal e Nemirovski, 1999) e conjuntos de orçamento (Bertsimas e Sim, 2004). O parâmetro de orçamento Gamma limita quantos parâmetros podem simultaneamente assumir seus valores de pior caso.

Fórmula
\mathcal{U} = \{ a_i : a_i = \bar{a}_i + \hat{a}_i \xi_i, \; \|\xi\|_\infty \leq 1 \}
3

Substituir cada restrição incerta por sua contraparte robusta: exigir factibilidade para cada realização em U. Isso transforma o problema original em um programa semi-infinito — infinitas restrições, uma por elemento de U.

Fórmula
\max_{a_i \in \mathcal{U}} a_i^T x \leq b_i \quad \forall i
4

Derivar um equivalente determinístico tratável. Para conjuntos de incerteza de orçamento, a contraparte robusta reformula-se como um LP padrão ou LP misto-inteiro de tamanho similar, solúvel com solvers convencionais. A reformulação chave introduz variáveis auxiliares que linearizam a maximização interna sobre o conjunto de incerteza.

Fórmula
\bar{a}_i^T x + \Gamma_i \max_{\{S: |S| \leq \Gamma_i\}} \sum_{j \in S} \hat{a}_{ij} |x_j| \leq b_i
5

Resolver o LP reformulado usando um solver padrão (simplex ou ponto interior). Avaliar a solução: verificar a violação da restrição de pior caso em todo o conjunto de incerteza, relatar o preço da robustez (o aumento do objetivo em relação ao LP nominal) e realizar análise de sensibilidade no orçamento de robustez Gamma.

Erros comuns

  • Definir Gamma muito alto faz com que todas as restrições sejam de pior caso simultaneamente, resultando em uma solução excessivamente conservadora e cara.
  • A especificação incorreta do conjunto de incerteza (por exemplo, ignorando a estrutura de correlação) pode levar a proteção excessiva ou insuficiente.
  • Confundir LP robusto com LP estocástico: RLP maximiza o desempenho de pior caso, não o desempenho esperado.
  • Ignorar o relatório do preço da robustez — sempre compare o objetivo robusto com o objetivo do LP nominal para quantificar o custo do conservadorismo.
  • Aplicar RLP a problemas com variáveis inteiras sem mudar para a formulação mista-inteira robusta, que requer reformulações diferentes.

Perguntas frequentes

Como a Programação Linear Robusta difere da Programação Linear Estocástica?

A Programação Linear Estocástica otimiza o desempenho esperado dada uma distribuição de probabilidade sobre cenários, exigindo conhecimento distribucional. A Programação Linear Robusta otimiza o desempenho de pior caso sobre um conjunto de incerteza, exigindo apenas limites — sem distribuição de probabilidade. A Programação Linear Robusta é preferível quando as distribuições são não confiáveis; a Programação Linear Estocástica é preferível quando são bem estimadas.

Qual é o preço da robustez?

O preço da robustez é o aumento no valor do objetivo (custo) da solução robusta em relação à solução do LP nominal. Bertsimas e Sim (2004) provaram que este preço cresce apenas como a raiz quadrada do número de parâmetros incertos para conjuntos de orçamento, tornando a robustez surpreendentemente acessível.

O que é o orçamento de robustez Gamma?

Gamma é um parâmetro no modelo Bertsimas-Sim que controla quantos coeficientes incertos podem simultaneamente assumir seus valores de pior caso. Gamma = 0 recupera o LP nominal; Gamma = n protege contra todos os n parâmetros desviando simultaneamente. Analistas tipicamente escolhem Gamma com base nos limites de probabilidade de violação aceitáveis.

A Programação Linear Robusta requer um solver especial?

Não. Para conjuntos de incerteza de box e orçamento, a contraparte robusta é em si um programa linear, solúvel com qualquer solver LP padrão (CPLEX, Gurobi, HiGHS, etc.). Conjuntos elipsoidais requerem um solver de programa de cone de segunda ordem, que também é amplamente suportado.

Quando devo usar Programação Mista-Inteira Robusta em vez disso?

Se as variáveis de decisão devem ser inteiras (por exemplo, decisões binárias sim/não, tamanhos de lote), a contraparte robusta contém variáveis inteiras e se torna um Programa Misto-Inteiro Robusto. A abordagem do conjunto de incerteza é a mesma, mas a reformulação e os requisitos do solver mudam de acordo.

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., Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations Research Letters, 25(1), 1–13.

    Abrir referência DOI
    Copiado.