We consider stochastic problems in which both the objective function and the feasible set are affected by uncertainty. We address these problems using a K-adaptability approach, in which K solutions for a given problem are computed before the uncertainty dissolves and afterwards the best of them can be chosen for the realized scenario. We analyze the complexity of the resulting problem from a theoretical viewpoint, showing that, even in case the deterministic problem can be solved in polynomial time, deciding if a feasible solution exists is NP-hard for discrete probability distributions. Besides that, we prove that an approximation factor for the underlying problem can be carried over to our problem. Finally, we present exact approaches including a branch-and-price algorithm. An extensive computational analysis compares the performances of the proposed algorithms on a large set of randomly generated instances.

Malaguti E., Monaci M., Pruente J. (2022). K-adaptability in stochastic optimization. MATHEMATICAL PROGRAMMING, 196, 567-595 [10.1007/s10107-021-01767-3].

K-adaptability in stochastic optimization

Malaguti E.;Monaci M.
;
2022

Abstract

We consider stochastic problems in which both the objective function and the feasible set are affected by uncertainty. We address these problems using a K-adaptability approach, in which K solutions for a given problem are computed before the uncertainty dissolves and afterwards the best of them can be chosen for the realized scenario. We analyze the complexity of the resulting problem from a theoretical viewpoint, showing that, even in case the deterministic problem can be solved in polynomial time, deciding if a feasible solution exists is NP-hard for discrete probability distributions. Besides that, we prove that an approximation factor for the underlying problem can be carried over to our problem. Finally, we present exact approaches including a branch-and-price algorithm. An extensive computational analysis compares the performances of the proposed algorithms on a large set of randomly generated instances.
2022
Malaguti E., Monaci M., Pruente J. (2022). K-adaptability in stochastic optimization. MATHEMATICAL PROGRAMMING, 196, 567-595 [10.1007/s10107-021-01767-3].
Malaguti E.; Monaci M.; Pruente J.
File in questo prodotto:
File Dimensione Formato  
K-adaptability_Malaguti_Monaci_Pruente-Journal.pdf

accesso aperto

Tipo: Versione (PDF) editoriale
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione 431.27 kB
Formato Adobe PDF
431.27 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/876118
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact