Robust optimization has been successfully applied to optimization problems subject to data uncertainty over the last decade, due to its computational attractiveness as well as the modeling power. The aim of this thesis is to enhance the applicability of robust optimization methodology to a broad range of situations occuring in real world applications. Specifically, this research contributes to the field of robust optimization by:
1. Proposing a new uncertainty set model that has a more flexibility on describing uncertain data than is possible using the traditional interval uncertainty set model and showing its applicability to various kinds of optimization problems;
2. Presenting an efficient algorithm to solve the robust optimization problem that is a large-scale mixed-integer programming problem in practice;
3. Incorporating robust optimization into stochastic programming framework to deal with the situation arising when the insufficient information of probability distributions of uncertain data is available.
First, we present a robust optimization model with a generalized interval uncertainty set which enables practitioners to obtain a more elaborate description of uncertain data than is possible using the traditional interval uncertainty set of Bertsimas and Sim. In this uncertainty set, we allow for several choices of deviation for each coefficient, whereas the traditional uncertainty set allows only maximum deviation. We also show that in some cases the robust problem preserves the tractability of the original problem and present a cut generation approach for the other cases. Our robust optimization model is applied to the dynamic facility location problem under the condition of demand uncertainty. Computational results on randomly generated instances demonstrate that the proposed robust optimization approach can successfully handle the uncertainty of the data.
Next, we consider the bandwidth packing problem which selects calls from a given set and assigns single path to each selected call in a network subject to demand uncertainty. To obtain solutions that are insensitive to this uncertainty, we propose a robust optimization approach. In this approach, the robust problem formulation becomes a large-scale mixed integer programming problem which may not be solved directly. Therefore, we apply the Dantzig-Wolfe decomposition and propose the branch-and-price procedure to find optimal solution. Moreover, in order to solve the relatively large-sized problems in a reasonable time, we propose a column generation acceleration scheme which is based on aggregation of variables. Computational results on cases of randomly generated networks demonstrate that the robust solutions are attractive when the demands are uncertain and our branch-and-price algorithm significantly outperforms the general integer programming solver.
Further, we consider queueing delays in the network, which may cause in a deterioration in the quality of service to users if they exceed the acceptable limits. The integer programming formulation for the bandwidth packing problem with the queueing delay restriction contains a nonlinear constraint that is intrinsic to the model. We apply the Dantzig-Wolfe decomposition to this nonlinear constraint, and since the Dantzig-Wolfe decomposition has exponentially many variables, we propose the branch-and-price procedure to find optimal solutions. We also propose a generalized Dantzig-Wolfe reformulation based on the aggregation of variables, which makes our branch-and-price algorithm more competitive. Computational results on cases of randomly generated networks and some real-life telecommunication networks demonstrate that our algorithm performs well for large networks.
Next, we study a robust knapsack problem under the generalized interval uncertainty set. We show that this problem can be solved by solving several ordinary knapsack problems repeatedly, and therefore it enables us to solve the problem of practical size in almost real-time. We present two applications that can benefit from this property of fast computation. First, we show that our robust knapsack problem can quickly produce a good approximate solution for a certain class of chance-constrained knapsack problem. Second, we apply our robust knapsack problem to a column generation subproblem of the branch-and-price algorithm for solving the robust bandwidth packing problem and show that the fast algorithm for the robust knapsack problem makes the branch-and-price algorithm computationally attractive.
Lastly, we consider a vehicle routing problems on a network with stochastic travel times, where a penalty for each vehicle is incurred in excess of a given time limit. Traditional stochastic programming approach would require a precise knowledge of the underlying probability distributions of the random data. However, such precise knowledge is rarely available in practice, and a solution obtained from wrong inputs might show poor performance when implemented. In our approach, we assume that we have only rough information of future travel times; in particular, range forecasts of travel times and the probabilities of each range being realized are available in advance. In this setting, we replace point estimates of travel times on a scenario by range estimates of them. Then, for each scenario we find a robust route that protects the solution against the worst case within the given ranges, and finally we find the route that has minimum cost in a stochastic sense. Therefore our approach incorporates robust optimization technique into stochastic programming framework. We propose a branch-and-cut algorithm to solve the problem and report computational results on the well-known Solomon`s instances, which shows our approach is favorable when the exact information of probability distributions is not available.
강건 최적화는 데이터의 불확실성을 효과적으로 다루기 위한 방법으로, 계산적인 효율성과 모델링의 용이함으로 인해 최근 10여 년에 걸쳐 데이터의 불확실성이 존재하는 최적화 문제에 성공적으로 적용되어 왔다. 본 논문에서는 실제 최적화 문제에 대한 강건최적화 기법의 적용성을 향상시키는 것을 목표로 한다. 구체적으로 본 연구의 강건 최적화 분야에 대한 기여는 다음과 같다.
1. 전통적인 불확실성 집합에 비해 불확실한 데이터를 더 유연하게 묘사할 수 있는 새로운 불확실성 집합을 제시하고, 다양한 문제에 대한 적용성을 보임.
2. 강건 최적화 문제가 매우 큰 사이즈의 혼합 정수 계획법인 문제인 경우에 대한 효율적인 알고리즘을 제시함.
3. 불확실한 데이터의 확률분포에 대한 정보가 충분하지 않은 상황을 다루기 위해 강건 최적화 기법을 추계 계획법 프레임워크에 결합시키는 방법을 제시함.
먼저, Bertsimas와 Sim의 전통적인 구간 불확실성 집합을 일반화하여 불확실한 데이터에 대해 더 정교한 묘사를 가능하게 하는 일반화된 구간 불확실성 집합을 제시한다. 전통적인 불확실성 집합은 오직 하나의 최대 변화량을 허용하지만, 제시된 불확실성 집합은 각각의 불확실한 데이터가 여러 값으로 변화할 수 있게 한다. 또한 특정한 경우에 새로운 불확실성 집합을 이용하는 강건 최적화 문제가 원 문제의 계산 복잡도를 유지함을 보이고, 그 외의 경우에는 강건 최적화 문제를 풀기 위한 절단 평면 생성 기법을 제시한다. 그리고 제시된 불확실성 집합의 효용성을 조사하기 위해 강건 최적화 모델을 수요의 불확실성을 가진 입지 선정 문제에 적용한다. 계산 실험의 결과는 제시된 강건 최적화 모델이 데이터의 불확실성을 성공적으로 다룰 수 있음을 보여 준다.
다음으로 수요의 불확실성을 가지는 대역폭 할당 문제를 고려한다. 이 문제는 통신 네트워크에서 주어진 콜의 집합 중의 일부를 선택하고, 선택된 콜에 대해 하나의 경로를 할당하는 문제이다. 본 연구에서는 각 콜의 수요에 대한 불확실성에 민감하지 않은 해를 얻기 위해서 강건 최적화 기법을 적용한다. 하지만 이 때 강건 최적화 문제는 직접적으로 풀기에는 힘든 매우 큰 사이즈의 혼합 정수 계획법 문제가 되기 때문에, 최적해를 찾기 위해서 Dantzig-Wolfe 분해 기법을 적용하고 분지평가법에 기반한 알고리즘을 제시한다. 또한, 상대적으로 큰 사이즈의 문제를 적절한 시간 내에 풀기 위해서 변수들의 재정의에 기반을 둔 열 생성 가속화 기법을 제시한다. 계산 실험의 결과, 강건 최적화 기법을 이용해 얻어진 해는 수요가 불확실한 상황에서 매우 효과적임을 관찰할 수 있고, 분지평가법에 기반한 알고리즘이 일반적인 정수 계획법 소프트웨어에 비해 성능이 매우 우수함을 보여 준다.
이어서, 우리는 대역폭 할당 문제에 추가적으로 큐잉 지연을 고려한다. 큐잉 지연은 데이터 패킷이 이동하는 데 걸리는 시간으로 어느 한계를 넘을 경우에는 네트워크 사용자에 대한 서비스의 질을 저하시키게 된다. 큐잉 지연을 고려하는 대역폭 할당 문제에 대한 정수 계획법 모델은 비선형 제약식을 가지게 되어 일반적인 정수 계획법 소프트웨어로 풀 수가 없다. 우리는 이러한 비선형 제약식을 효과적으로 고려하기 위해서 Dantzig-Wolfe 분해기법을 적용하고 분지평가법에 기반한 알고리즘을 제시한다. 또한 제시된 알고리즘의 효율성을 높이기 위해 앞에서 제시한 열 생성 가속화 기법을 더 확장하여 일반화된 Dantzig-Wolfe 분해기법을 제시한다. 무작위로 생성된 네트워크와 현실의 통신 네트워크에 대한 실험 결과, 제시된 알고리즘이 큰 사이즈의 네트워크에 대해 좋은 성능을 보여 줌을 관찰할 수 있다.
다음으로, 우리는 일반화된 구간 불확실성 집합 하에서의 강건 배낭 문제를 연구한다. 본 연구에서는 이 문제의 해를 일반적인 배낭 문제를 여러 번 풀어서 구할 수 있음을 보인다. 그 결과 강건 배낭 문제의 해를 거의 실시간으로 구할 수 있게 된다. 그리고 이러한 빠른 계산적 특성으로 인해 이득을 얻을 수 있는 두 가지 응용 문제를 제시한다. 첫째로, 제시된 강건 배낭 문제가 특정한 클래스의 기회 제약 배낭 문제의 근사해를 매우 빨리 구할 수 있음을 보인다. 둘째로, 제시된 강건 배낭 문제가 수요의 불확실성을 가지는 대역폭 할당 문제에 대한 분지 평가 알고리즘의 열 생성 하부문제로 적용될 수 있음을 보이고, 계산 실험 결과를 통해 강건 배낭 문제의 빠른 알고리즘이 분지 평가 알고리즘의 성능을 매우 향상시킴을 보인다.
마지막으로, 우리는 확률적인 운행 시간을 가지는 네트워크에서의 차량 경로 문제를 다룬다. 이 때 각 차량에 대해 주어진 시간 제한을 초과하는 시간에 비례하는 페널티가 부과된다. 전통적인 추계 계획법은 임의의 데이터에 대한 확률 분포의 정확한 정보가 주어졌을 때를 가정한다. 하지만 그러한 정확한 정보는 실제로는 얻기 매우 어렵고 또한 잘못된 정보 하에서 얻어진 해는 실제로 적용되었을 때에 좋지 않는 성능을 보이기도 한다. 본 연구에서는, 미래의 운행 시간에 대해 정확한 확률분포 대신에 구간 추정과 각 구간이 실현될 확률을 얻을 수 있다고 가정한다. 이러한 가정 하에서 우리는 기존의 시나리오에 주어진 운행 시간에 대한 점 추정값을 구간 추정값으로 대체하고, 강건 최적화 기법을 이용하여 각 시나리오에 주어진 구간에 대해 강건한 경로를 구하고, 최종적으로는 확률적인 기대비용을 최소로 하는 경로를 선택한다. 따라서 제시된 방법은 강건 최적화 기법을 추계 계획법 프레임워크에 결합시키게 된다. 그리고 제시된 기법에 대한 해를 구하기 위해 분지 절단 알고리즘을 제시하며, 계산 실험 결과는 주어진 방법이 확률 분포에 대한 정보가 부족한 상황에서 효과적으로 적용됨을 보여 준다.
