Worst case scenario lemma for Γ-robust combinatorial optimization problems under max-min criterion

摘要

Robust optimization motivated by practical applications deals with optimization problems in which some input parameters are uncertain. In this paper, we consider Γ-robust combinatorial optimization problems under max-min criterion. For this type of problems, we propose and prove a general lemma that we call the worst case scenario lemma; it specifies a worst case scenario for a given solution. Based on the worst case scenario lemma, we propose an exact dynamic programming algorithm for the Γ-robust knapsack problem under max-min criterion.