Polyhedral aspects of a robust knapsack problem

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.

Article

Download

View Polyhedral aspects of a robust knapsack problem