Lifting of the Cover Inequalities for the Robust Knapsack Problem
Date:
Youngjoo Roh, Junyoung Kim, Kyungsik Lee* ; Seoul National University, Korea, Republic of.
More information here
In this study, we consider the robust knapsack problem introduced by Bertsimas and Sim [Operations Research 52(1) pp.35-53, 2004]. Robust cover inequalities are well-known valid inequalities for the robust knapsack problem. These inequalities can be strengthened using lifting methods that improve each coefficient of inequality by utilizing the optimal objective values of lifting problems. Since obtaining an optimal solution for every lifting problem can be time-consuming, we propose an efficient alternative lifting method using the upper bounds of the lifting problems. Through computational tests, we demonstrate that our lifting method outperforms existing methods in terms of computational efficiency, while the effectiveness of the resulting lifted robust cover inequalities remains competitive compared to those generated by existing lifting methods.