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. In this thesis, we study valid inequalities for robust MIP problems.
First, 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.
Second, we consider a chance-constrained knapsack problem where weights of items are independent and normally distributed. Probabilistic cover inequalities can be defined for the chance-constrained knapsack problem. The lifting problem for probabilistic cover inequalities is NP-hard. We propose a polynomial time approximate lifting method for probabilistic cover inequalities based on the robust optimization approach. We present computational experiments on multidimensional chance-constrained knapsack problems. The results show that our lifting method reduces the computation time substantially.
Third, we study the robust continuous knapsack problem with a single unbounded continuous variable. Using submodularity of the cardinality constrained robust knapsack set function, we define submodular inequalities. Proposed valid inequalities for the robust continuous knapsack problem can be applied to general robust mixed 0-1 programming problems. A polynomial time separation algorithm for the most violated submodular inequality is proposed. We prove that the convex hull of the robust continuous knapsack polyhedron can be described completely by submodular inequalities and bound inequalities. In addition, we propose a polynomial time algorithm for the robust continuous knapsack problem. The computational results on the robust knapsack problem and the robust mixed 0-1 knapsack problem show the effect of submodular inequalities.
최근, 데이터의 불확실성을 고려한 강건 최적화 방법론은 광범위하게 연구되어왔고 실제 최적화 문제에 성공적으로 적용되고 있다. 하지만 데이터의 불확실성을 고려한 강건 최적화 문제는 기존의 문제보다 더 해결하기 어렵다. 따라서 일반적인 강건 최적화 문제에 적용될 수 있는 이의 해집합에 대한 연구는 중요한 역할을 한다. 본 논문에서는 강건 혼합 정수 계획법 문제의 유효 부등식에 대해 연구한다.
첫 번째로, Bertsimas와 Sim의 모델로 정의된 강건 배낭 문제의 해집합을 다룬다. 덮개 부등식은 일반적인 배낭 문제의 해집합에서 정의되는 대표적인 유효 부등식으로 성공적으로 사용되어 왔다. 본 연구에서는 일반적인 덮개 부등식에 대한 다양한 연구를 강건 덮개 부등식으로 확장시킨다. 강건 덮개 부등식의 다항 시간 올림 알고리즘과 다양한 분리 알고리즘을 제안한다. 또한 확장 강건 덮개 부등식의 분리 알고리즘을 제안한다. 제안된 다양한 올림, 분리 알고리즘을 통신 문제 중 하나인 강건 대역폭 할당 문제에 적용하여 그 효과를 확인하였다.
두 번째로, 각 아이템의 무게가 정규분포를 따르는 위험도 제약 배낭 문제의 해집합에 대해 연구한다. 확률 덮개 부등식이 위험도 제약 배낭문제에 정의될 수 있고 이의 올림 부문제는 NP hard 문제이다. 본 연구에서는 강건 최적화 접근 방법을 기반으로 한 확률 덮개 부등식의 근사 다항 시간 알고리즘을 제안한다. 제안된 방법을 다차원 위험도 제약 배낭문제에 적용하여 그 효과를 확인하였다.
마지막으로, 실수 변수 하나를 포함하고 있는 강건 배낭 문제의 해집합에 대해 연구한다. 강건 배낭 집합 함수가 부분 보형 함수임을 이용하여, 부분 보형 부등식을 정의한다. 부분 보형 부등식은 다항 시간 내에 분리가 가능하고, 이는 일반적인 강건 혼합 이진 문제에 적용이 가능하다. 실수 변수를 포함한 강건 배낭 문제의 해집합의 볼록 껍질은 부분 보형 부등식으로 완벽히 표현될 수 있다. 또한 실수 변수를 포함한 강건 배낭 문제를 푸는 다항 시간 알고리즘을 제안한다. 마지막으로 실험적으로 부분 보형 부등식의 효과를 확인하였다.
