Mixed-Integer Linear Programming models often optimize the sum, or average, of different outcomes. In a deterministic setting, each outcome may be associated with an agent, for example a customer, an employee, or a time period. In a stochastic setting, each outcome may be associated with a discrete scenario. The average approach optimizes the overall efficiency of the solution, but neglects the possible unfair distribution of outcomes among agents or the risk of very bad scenarios. In this paper, we exploit the analogies of the two settings to derive a common optimization paradigm bridging the gap between k - sum optimization in the deterministic setting and Conditional Value-at-Risk optimization in the stochastic setting. We show that the proposed paradigm satisfies properties that make it an attractive criterion. To illustrate the proposed paradigm, we apply it to the multidimensional knapsack problem and the p - median/ p -center problem.

Bridging k-sum and CVaR optimization in MILP

Carlo Filippi
;
Włodzimierz Ogryczak;M. Grazia Speranza
2019-01-01

Abstract

Mixed-Integer Linear Programming models often optimize the sum, or average, of different outcomes. In a deterministic setting, each outcome may be associated with an agent, for example a customer, an employee, or a time period. In a stochastic setting, each outcome may be associated with a discrete scenario. The average approach optimizes the overall efficiency of the solution, but neglects the possible unfair distribution of outcomes among agents or the risk of very bad scenarios. In this paper, we exploit the analogies of the two settings to derive a common optimization paradigm bridging the gap between k - sum optimization in the deterministic setting and Conditional Value-at-Risk optimization in the stochastic setting. We show that the proposed paradigm satisfies properties that make it an attractive criterion. To illustrate the proposed paradigm, we apply it to the multidimensional knapsack problem and the p - median/ p -center problem.
File in questo prodotto:
File Dimensione Formato  
FilOgrSpe19_COR.pdf

accesso aperto

Descrizione: Articolo pubblicato
Tipologia: Full Text
Licenza: PUBBLICO - Creative Commons 4.0
Dimensione 699.42 kB
Formato Adobe PDF
699.42 kB Adobe PDF Visualizza/Apri
FilOgrSpe19_COR_Appendix.pdf

accesso aperto

Descrizione: Appendice: Materiale Supplementare
Tipologia: Altro materiale allegato
Licenza: PUBBLICO - Creative Commons 4.0
Dimensione 151.59 kB
Formato Adobe PDF
151.59 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/11379/514623
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 10
social impact