We consider discrete optimization problems under data uncertainty. Discrete optimization problems, including combinatorial optimization and integer programming problems, are utilized in various fields such as engineering, natural science, and operations research. In recent years, many researchers have attempted to formulate mathematical models using stochastic programming, robust optimization, and distributionally robust optimization, etc., to reflect data uncertainty in the real-world problems. However, not only are many discrete optimization problems difficult to solve themselves, but there are originally tractable ones that become difficult as well when data uncertainty is considered. We represent discrete optimization problems with some specific assumptions about data uncertainty as mixed-integer second-order cone programming problems and present several algorithms for these problems.
First, we propose some algorithms to solve a chance-constrained binary knapsack problem with weight uncertainty. The binary knapsack problem aims at efficient resource allocation with a capacity constraint and indivisible items. It can also be subroutines during the procedures of a branch-and-cut and a branch-and-price algorithm when a solution set of a mixed-integer programming problem includes capacity constraints. A chance constraint can replace the capacity constraint if the weights of items are random variables, and it can also be reformulated as the second-order cone constraint under some specific assumptions about the distributions of random weights. As a result, the problem becomes the second-order cone-constrained binary knapsack problem. We propose an algorithm to obtain the upper and lower bounds on its optimal value by approximating the second-order cone constraint through a robust optimization approach. Moreover, we present a pseudo-polynomial time algorithm by showing that the solution providing the upper bound can be an optimal one to the problem if the accuracy of the approximation reaches a theoretically certain level or more. Computational experiments on several types of randomly generated instances are presented to show the efficiency of the algorithms.
Next, we develop an exact algorithm for mean-standard deviation combinatorial optimization problems to consider combinatorial optimization problems in general, which have uncertainty in the objective cost coefficients. There are many combinatorial optimization problems that can be solved using polynomial or pseudo-polynomial time algorithms, such as the binary knapsack problem, the shortest path problem, the minimum cut problem, etc. They appear in many real-world problems and are also utilized as subproblems for large-sized optimization problems. We assume that the uncertain coefficients are independent random variables, and the mean and the standard deviation of each random variable are known. We can define $\rho$-quantile, also called value-at-risk(VaR) at level $1-\rho$, as a measure of the risk of loss for the objective function. Under some specific assumptions about the distributions of cost coefficients, the problem of minimizing the risk measure is equivalent to the mean-standard deviation combinatorial optimization problem with the deterministic second-order cone objective function. We propose a fully polynomial-time approximation scheme to derive an approximate solution whose objective function value is at most $(1 + \epsilon)$ times the optimal value of the problem. We also develop an iterative algorithm that solves a number of ordinary combinatorial optimization problems to obtain an optimal solution for the problem. The fitness of the algorithm is also proven. The exact algorithm was tested on the mean-standard deviation binary knapsack problem and the mean-standard deviation shortest path problem.
Lastly, we deal with a single-source capacitated facility location problem with demand uncertainty. Specific distributions or an ambiguity set of possible distributions can be designated to describe uncertain demands. The mathematical model can be reformulated as an allocation-based formulation by using Dantzig-Wolfe decomposition, and a branch-and-price algorithm is applied for the problem. We consider the structure of the master problem and the subproblem, the GRASP heuristic for initial columns, and several techniques to improve the performance of the algorithm. Computational experiments show that our branch-and-price algorithm outperforms CPLEX, which solves the quadratically constrained mixed-integer reformulation of the problem.
본 논문에서는 데이터 불확실성 하의 이산 최적화 문제를 다룬다. 이산 최적화에 속하는 조합 최적화 및 정수 계획법 문제는 공학, 자연과학, 경영과학 등의 다양한 분야에서 나타난다. 최근에는 현실의 데이터 불확실성을 반영하기 위하여 추계적 계획법, 강건 최적화, 분포 강건 최적화 등의 방법론을 적용하여 수리 모형을 설계하고 이러한 문제를 해결하는 연구가 활발히 이루어지고 있다. 그러나 이산 최적화 문제에는 일반적으로 해결이 어려운 문제가 많으며, 원래는 어렵지 않았던 문제라도 데이터 불확실성을 반영한 이후에는 어려운 문제가 될 수 있다. 본 논문은 데이터 불확실성 하의 이산 최적화 문제를 혼합 정수 2차 원뿔 계획법 문제로 나타내고, 이러한 문제를 해결할 수 있는 알고리즘을 제시한다.
우선, 각 아이템의 무게가 불확실한 경우의 이진 배낭 문제의 해결 방법을 제안한다. 이진 배낭 문제는 용량 제약 및 아이템의 분할 불가능 조건 하에서의 효율적인 자원 할당을 목적으로 한다. 또한, 이진 배낭 문제는 분지절단법, 분지평가법 등 해집합의 구성에 용량 제약 조건을 포함하는 혼합 정수 계획법 문제의 풀이 과정에서 해결해야 하는 부문제가 된다. 본 연구에서는 각 아이템의 무게가 서로 독립인 확률 변수라는 가정 하에 원래의 제약 조건을 위험도 제약 조건으로 재정의한다. 그리고 특수한 몇몇 조건 아래에서 이것이 2차 원뿔 제약 조건으로 표현 가능함을 설명하고 문제를 비선형 제약 조건을 지닌 이진 배낭 문제로 나타낸다. 우리는 이러한 제약 조건의 근사를 바탕으로 최적값의 상한 및 하한을 동시에 구할 수 있는 알고리즘을 제안한다. 또한, 제약 조건의 근사 정확도가 일정 수준 이상일 때, 최적값의 상한을 제시하는 해답이 또한 문제의 최적해가 된다는 것을 증명하고 이를 활용한 유사 다항 시간 알고리즘을 제시한다.
다음으로, 목적 함수의 계수가 불확실한 경우의 일반적인 조합 최적화 문제를 다루기 위하여 비선형 목적 함수를 지닌 평균-표준 편차 조합 최적화 문제의 정확한 최적 알고리즘을 개발한다. 조합 최적화에는 이진 배낭 문제, 최단 경로 문제, 최소 절단 문제 등 다항 시간이나 유사 다항 시간 내에 해결되는 문제들이 있으며, 현실의 문제 해결에 응용되거나 더 큰 규모의 최적화 문제 해결을 돕는 부문제로 사용된다. 본 연구에서는 목적 함수의 계수가 불확실한 상황에서 이를 서로 독립인 확률 변수로 정의하고, 최소화하고자 하는 위험도를 ρ-분위 내지는 value-at-risk(VaR)로 정의한다. 특수한 몇몇 조건 아래에서 이러한 위험도 목적 함수는 2차 원뿔식인 평균-표준 편차 목적 함수로 나타내어진다. 이로부터 해결법이 알려진 기초적인 조합 최적화 문제를 여러 번 풀어 원래 문제의 완전 다항 시간 근사 해법을 도출하는 한편, 정확한 최적해를 효율적으로 구하는 새로운 알고리즘을 개발한다.
마지막으로, 수요가 불확실한 상황에서 용량 제약 및 단일 할당 조건이 있는 설비 입지 선정 문제를 다룬다. 불확실한 개별 고객의 수요를 나타내기 위하여 기존 정보나 데이터를 바탕으로 이를 특정 확률 변수로 지정하거나 가능한 확률 변수의 모호성 집합을 정의하여 위험도 제약 조건을 포함하는 수리 모형을 설계할 수 있다. 우리는 이를 바탕으로 Dantzig-Wolfe 분해법을 적용하여 기존의 수리 모형을 할당 기반 수리 모형으로 재공식화하고, 이를 효율적으로 해결하는 분지평가법 알고리즘을 적용한다. 연구에서는 주문제 및 부문제의 구조와 해법, 초기 열 생성을 위한 휴리스틱, 그리고 알고리즘의 효율성 향상을 위한 여러 기법들을 다룬다.
