Polyhedral aspects of a robust knapsack problem

Olivier Klopfenstein (olivier.klopfensteinfrancetelecom.com)
Dritan Nace (naceutc.fr)

Abstract: While dealing with uncertainty in linear programs, the robust optimization framework proposed by Bertsimas and Sim appears as relevant. In particular, it can readily be extended for integer linear programming. This paper outlines the polyhedral impacts of this robust model for the 0-1 knapsack problem. It shows especially how the classical cover cuts can be adapted to provide strong inequalities for the robust model.

Keywords: Robust optimization; Knapsack problem; Polyhedral analysis; Knapsack cover inequalities

Category 1: Robust Optimization

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Integer Programming (0-1 Programming )

Citation:

Download: [PDF]

Entry Submitted: 04/14/2006
Entry Accepted: 04/17/2006
Entry Last Modified: 09/19/2007

Modify/Update this entry