The lexicographic α-robust knapsack problem

Rim Kalaï and Daniel Vanderpooten
Additional contact information
Rim Kalaï: LAMSADE - Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision - Université Paris Dauphine-PSL - PSL - Université Paris Sciences et Lettres - CNRS - Centre National de la Recherche Scientifique, Pôle Customer, Retail and Supply Chain - Rouen Business School - Rouen Business School
Daniel Vanderpooten: LAMSADE - Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision - Université Paris Dauphine-PSL - PSL - Université Paris Sciences et Lettres - CNRS - Centre National de la Recherche Scientifique

Post-Print from HAL

Abstract: The knapsack problem is a classical combinatorial optimization problem used to model many industrial situations. The robust version of this problem was studied in the literature using a max-min or min-max regret criterion. In this paper, we show the drawbacks of such criteria and propose a new robustness approach, called lexicographic α-robustness. We show that the complexity of the lexicographic α-robust problem does not increase compared with the max-min version and present a pseudo-polynomial algorithm in the case of a bounded number of scenarios.

Keywords: uncertainty; robustness; 0-1 knapsack problem; min-max (regret); complexity (search for similar items in EconPapers)
Date: 2011-01
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Published in International Transactions in Operational Research, 2011, Vol. 18 (n° 1), pp 103-113. ⟨10.1111/j.1475-3995.2010.00786.x⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-00820135

DOI: 10.1111/j.1475-3995.2010.00786.x

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().