Abstract

Robust cover inequalities are well-known valid inequalities for the robust knapsack problem (RKP). To strengthen them, we use lifting, which involves solving lifting problems—special cases of the RKP. We propose a novel lifting method that leverages upper bounds for lifting problems. First, we introduce a strong, efficiently computable, and quality-guaranteed upper bound for the RKP based on the decomposition property of its solution set. We then devise an efficient lifting method by applying the proposed upper bound to lifting problems.