Lifting Heuristic for Robust Cover Inequalities for Robust Knapsack Problem
Date:
Youngjoo Roh, Junyoung Kim, Kyungsik Lee* ; Seoul National University, Korea, Republic of.
Robust cover inequalities are well-known valid inequalities for the robust knapsack problem (RKP) introduced in Bertsimas and Sim [Operations Research 52(1) pp.35-53, 2004]. These inequalities can be strengthened using lifting methods that utilize the optimal objective values of lifting problems, which are special cases of the RKP. In this study, we propose an alternative lifting method, which we call the lifting heuristic, exploiting the upper bounds of the lifting problems.