A strong compact formulation for the robust knapsack problem with its application to a lifting heuristic for robust cover inequalities
Date:
Youngjoo Roh, Junyoung Kim, Kyungsik Lee* ; Seoul National University, Korea, Republic of.
More information here 1 More information here 2
In this study, we consider the robust knapsack problem introduced by Bertsimas and Sim [Operations Research 52(1) pp.35-53, 2004]. Based on the decomposition property of the feasible solution set, we present a compact formulation using the disjunctive programming approach for the problem. Through theoretical analyses, we show the proposed formulation provides tighter linear programming (LP) relaxation bounds compared with existing formulations. Then, we propose a heuristic procedure for lifting valid inequalities for the robust knapsack problem.