반복영역 바로가기
주메뉴로 바로가기
좌측메뉴로 바로가기
본문으로 바로가기

Home News&ActivitySeminars

Seminars

프린트페이스북

Lifting and separation of robust cover inequalities

2017.11.24 17:38

<Speaker정슬기 박사과정, SOLAB>

 

Date & Time11 24 (), 2:00pm~

 

Title: Lifting and separation of robust cover inequalities

 

Abstract:

 

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 강의실

List