Skip to content
Torna ai risultati

Programmazione Intera Stocastica — Ottimizzazione di Decisioni Discrete Sotto Incertezza

Introdotto da
Dantzig, G. B.; Beale, E. M. L.
Anno
1955
Tipo
Optimization under uncertainty with discrete decisions
Famiglia
Simulation / optimization

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

La Programmazione Intera Stocastica (SIP) è un quadro di ottimizzazione che combina variabili decisionali intere (discrete) con la modellazione probabilistica esplicita dell'incertezza.

Cerca la migliore decisione immediata (here-and-now) che minimizzi il costo atteso (o massimizzi il beneficio atteso) su una distribuzione di scenari futuri, tenendo conto del fatto che alcune decisioni devono essere prese prima che l'incertezza sia risolta.

L’intuizione alla base del metodo

Molte decisioni reali sono sia discrete (costruire o meno una struttura; assegnare o meno un lavoratore) sia incerte (domanda, costi e vincoli non sono noti al momento della decisione). La SIP gestisce entrambe le sfide simultaneamente. Modella il futuro incerto come un insieme di scenari con probabilità associate, quindi trova la soluzione intera che si comporta meglio in media — o che si protegge contro gli esiti peggiori. A differenza della programmazione lineare stocastica, la struttura discreta rende il problema combinatoriamente più difficile, ma le decisioni prodotte sono direttamente implementabili senza arrotondamenti o approssimazioni.

Storia

La programmazione stocastica risale a Dantzig (1955) e Beale (1955), che proposero indipendentemente modelli di ricorso a due stadi per programmi lineari sotto incertezza. L'estensione intera emerse con la maturazione della programmazione intera negli anni '60-'80. Il libro di testo di Birge e Louveaux del 1997 codificò il campo, e Kleywegt et al. (2002) stabilirono la Sample Average Approximation come approccio computazionale standard per l'ottimizzazione discreta stocastica su larga scala.

Quando usarlo

Utilizzare la Programmazione Intera Stocastica quando le decisioni sono intrinsecamente discrete (scelte binarie, allocazioni di unità intere, assegnazioni di percorsi) e i parametri chiave sono incerti al momento della decisione. È ben adatta per la pianificazione della capacità, la progettazione di reti di supply chain, la pianificazione sotto incertezza della domanda, la spedizione di energia e l'allocazione di risorse con rese casuali. NON utilizzarla quando tutte le variabili sono continue (la programmazione lineare stocastica è sufficiente), quando l'incertezza è trascurabile o completamente osservabile prima di decidere, quando la scala del problema rende l'enumerazione degli scenari computazionalmente intrattabile senza decomposizione, o quando è rilevante solo uno scenario deterministico.

Limiti e considerazioni

  • La complessità computazionale cresce rapidamente con il numero di scenari e variabili intere; istanze di grandi dimensioni sono NP-hard.
  • La generazione di scenari richiede distribuzioni di probabilità credibili, che possono essere difficili da elicitare o stimare da dati limitati.
  • Le estensioni multi-stadio (più di due stadi) affrontano una crescita esponenziale degli alberi di scenario e sono raramente trattabili oltre i tre stadi.
  • È richiesta abilità di modellazione per specificare correttamente la fattibilità del ricorso, i vincoli di non-anticipatività e le strutture di penalità.

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Modella esplicitamente l'incertezza piuttosto che utilizzare stime puntuali, producendo soluzioni robuste agli scenari realizzati.
  • Gestisce nativamente decisioni discrete e binarie, quindi le soluzioni sono direttamente implementabili senza arrotondamenti post-hoc.
  • Il quadro a due stadi separa nettamente le decisioni strategiche del primo stadio dalle azioni operative di ricorso del secondo stadio.
  • Supporta ricche strutture di ricorso, inclusi approvvigionamento di risorse, costi di penalità e pianificazione correttiva.
  • I limiti di qualità statistica (tramite SAA) consentono ai professionisti di certificare la quasi-ottimalità con confidenza quantificata.

Applicazioni

  • Progettazione di reti di supply chain sotto domanda e tempi di consegna stocastici
  • Pianificazione dell'espansione della produzione di energia con output rinnovabile incerto
  • Pianificazione delle sale operatorie ospedaliere sotto durate variabili delle procedure
  • Pianificazione degli equipaggi delle compagnie aeree con ritardi di volo stocastici
  • Pre-posizionamento di beni di soccorso nella logistica umanitaria prima dei disastri
  • Ottimizzazione di portafoglio finanziario con selezione discreta di asset e rendimenti basati su scenari

Come funziona

Come funziona

1

Formulare il problema del primo stadio: scegliere variabili decisionali intere (o miste-intere) x prima che l'incertezza venga rivelata. Definire un obiettivo che includa sia il costo immediato sia il costo atteso di ricorso su tutti gli scenari. I vincoli che collegano x alle condizioni di fattibilità sono specificati qui.

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

Rappresentare l'incertezza attraverso un insieme finito di scenari. Ogni scenario assegna valori specifici ai parametri casuali (livelli di domanda, costi, disponibilità di risorse). Gli scenari possono essere generati tramite campionamento storico, estrazioni Monte Carlo da distribuzioni adattate o casi rappresentativi definiti da esperti. Ogni scenario porta un peso di probabilità che somma a uno.

3

Nella formulazione standard a due stadi, dopo che x è fissato e lo scenario xi è realizzato, un problema di ricorso (secondo stadio) determina le azioni correttive y. Il problema di ricorso è spesso un programma lineare o intero. Il modello completo minimizza c^T x più il costo atteso di ricorso E[Q(x, xi)].

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

Risolvere i sotto-problemi degli scenari per valutare il costo di ricorso per ogni scenario dato x. Le tecniche includono branch-and-bound, decomposizione di Benders, rilassamento Lagrangiano e il metodo Sample Average Approximation (SAA). Per alberi di scenario di grandi dimensioni, gli algoritmi di decomposizione sfruttano la struttura a blocchi tra gli scenari.

5

Aggregare i risultati dei sotto-problemi per stimare il costo atteso di ricorso. In SAA, questo è la media su S scenari campionati. L'approssimazione risultante converge alla vera aspettativa all'aumentare di S. I limiti statistici sulla qualità della soluzione possono essere calcolati dalla varianza del campione.

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

Verificare l'ottimalità o la quasi-ottimalità tramite gap di ottimalità, criteri di convergenza o intervalli di confidenza statistici da SAA. Se il gap non è accettabile, affinare l'insieme degli scenari, aumentare la dimensione del campione o stringere i rilassamenti. Riportare la soluzione del primo stadio x* e il suo costo totale atteso.

Errori comuni

  • Usare troppo pochi scenari produce soluzioni troppo fiduciose; usarne troppi rende il problema computazionalmente infattibile — bilanciare tramite diagnostica di convergenza SAA.
  • Ignorare l'integralità nel secondo stadio quando è effettivamente richiesta porta a stime di costo ottimistiche e azioni di ricorso infattibili.
  • Assumere indipendenza degli scenari quando i parametri sono correlati (ad es., domanda e prezzo correlati) introduce un bias sistematico nella stima del costo atteso.
  • Dimenticare i vincoli di non-anticipatività nei problemi multi-stadio consente al modello di sfruttare informazioni future che non sarebbero disponibili in pratica.

Domande frequenti

In che modo la Programmazione Intera Stocastica differisce dall'ottimizzazione robusta?

La SIP minimizza il costo atteso su un insieme di scenari pesati per probabilità, accettando che alcuni scenari possano generare costi elevati se sono improbabili. L'ottimizzazione robusta minimizza il costo nel caso peggiore su un insieme di incertezza, senza fare assunzioni probabilistiche. La SIP richiede una distribuzione di probabilità; l'ottimizzazione robusta richiede solo un insieme di incertezza. La SIP è generalmente meno conservativa ma più esigente in termini di dati.

Quanti scenari sono necessari in pratica?

Dipende dalla dimensione del problema e dalla precisione desiderata. L'approccio Sample Average Approximation (SAA) fornisce intervalli di confidenza statistici sul gap di ottimalità. Studi applicati tipici utilizzano da decine a migliaia di scenari; i diagnostici di convergenza (varianza dello stimatore del limite) guidano la scelta. Per problemi strutturati, tecniche di riduzione degli scenari (ad es., Heitsch-Romisch) possono ridurre sostanzialmente il numero di scenari.

La Programmazione Intera Stocastica può gestire più di due stadi?

Sì, ma la SIP multi-stadio è significativamente più difficile. L'albero di scenario cresce esponenzialmente con gli stadi, e i vincoli di non-anticipatività devono essere applicati ad ogni nodo. In pratica, i modelli a tre stadi sono la norma per applicazioni trattabili; oltre questo limite, sono tipicamente necessarie approssimazioni come l'orizzonte mobile o la riduzione dell'albero di scenario.

Quale software può risolvere modelli di Programmazione Intera Stocastica?

I solver comuni includono CPLEX e Gurobi (tramite linguaggi di modellazione algebrica come AMPL, JuMP in Julia, o PuLP/Pyomo in Python), che supportano la decomposizione degli scenari. Framework specializzati per la programmazione stocastica includono PySP (Python), solver in formato SMPS e il pacchetto Julia StochasticPrograms.jl, che implementa SAA e progressive hedging.

La Programmazione Intera Stocastica è la stessa della Programmazione Mista Intera Stocastica?

La Programmazione Intera Stocastica è la classe più ampia; la Programmazione Mista Intera Stocastica (SMIP) si riferisce specificamente a modelli in cui alcune variabili sono continue e altre intere in uno o entrambi gli stadi. La SMIP è la forma più generale e più frequentemente incontrata in pratica.

Metodi correlati

Fonti

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

    ISBN: 978-1-4614-0237-4
    Copiato.
  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.

    Apri il riferimento DOI
    Copiato.