Lifting and separation of robust cover inequalities
<Speaker: 정슬기 박사과정, SOLAB>
Date & Time: 11월 24 일(금), 2:00pm~
Title: Lifting and separation of robust cover inequalities
Recently, a robust optimization approach for the optimization problems with uncertain data has been extensively studied and successfully applied to real world optimization problems. However, taking into account the uncertainty of data makes the problem more difficult than the deterministic problem. Therefore polyhedral studies on the robust optimization problems are important, since they can be applied to general robust optimization problems. We consider the cardinality constrained robust knapsack problem with Bertsimas and Sim model. Cover inequalities are well-known valid inequalities for the ordinary knapsack solution set, and successfully used. We generalize numerous studies for ordinary cover inequalities to robust cover inequalities. A polynomial time lifting algorithm and several separation algorithms for robust cover inequalities are proposed. In addition, an exact separation algorithm for extended robust cover inequalities is presented. The computational experiments exhibit the effect of proposed algorithms. The branch-and-cut algorithms with proposed lifting and separation algorithms are tested on the robust bandwidth packing problem.
Place : 2504, edu3.0 강의실