분해 방법 개요

대규모의 선형계획 문제는 변수의 수가 많고, 문제의 구조가 복잡하여 단순한 해법을 적용하기 어렵다. 이때 분해(decomposition) 기법을 사용하여 큰 문제를 여러 작은 부분 문제로 나누고 각각을 효율적으로 해결할 수 있다. 분해 방법의 기본 아이디어는 문제를 특정 구조에 따라 분리하여 병렬적으로 또는 단계적으로 해결하는 것이다.

분해 방법의 수학적 배경

분해 방법은 일반적으로 두 가지로 나뉜다: Dantzig-Wolfe 분해(Dantzig-Wolfe Decomposition)와 Benders 분해(Benders Decomposition). 이들은 각각 문제의 구조적 특성을 활용하여 문제를 해결한다.

Dantzig-Wolfe 분해

Dantzig-Wolfe 분해는 선형계획 문제의 제한된 자원(constraint)을 분리하여 부분 문제를 해결하는 방식이다. 이 방법은 주로 블록 구조(block structure)를 가진 문제에 적용된다.

먼저, 선형계획 문제의 일반적인 형태는 다음과 같다:

여기서, $\mathbf{A}$는 제약 조건 행렬, $\mathbf{b}$는 자원 벡터, $\mathbf{c}$는 비용 벡터, $\mathbf{x}$는 결정 변수 벡터이다.

Dantzig-Wolfe 분해에서는 문제를 두 부분으로 나눈다: 주 문제(master problem)와 여러 개의 부분 문제(subproblem). 주 문제는 전체 문제를 관리하는 역할을 하고, 부분 문제는 각 블록의 변수를 해결하는 역할을 한다.

주 문제의 형태는 다음과 같이 표현할 수 있다:

여기서, $\mathbf{z}_i$는 부분 문제에서의 변수, $\mathbf{B}_i$는 각 부분 문제의 제약 조건 행렬, $\pi_i$는 이중 변수(dual variable)를 의미한다.

부분 문제는 다음과 같은 형식으로 주어진다:

Benders 분해

Benders 분해는 주로 혼합 정수계획(Mixed Integer Programming, MIP) 문제에 적용된다. 이 방법은 주 문제와 부분 문제로 문제를 나누어 해결한다. Benders 분해는 주 문제에서 정수 변수(integer variables)를, 부분 문제에서 연속 변수(continuous variables)를 처리한다.

주 문제는 다음과 같은 형태로 표현된다:

여기서, $\mathbf{x}_I$는 정수 변수, $\theta$는 부분 문제의 목적 함수 값이다.

부분 문제는 주어진 $\mathbf{x}_I$에 따라 다음과 같이 정의된다:

여기서, $\mathbf{x}_C$는 연속 변수, $\mathbf{A}_C$는 부분 문제의 제약 조건 행렬이다.

Benders 분해는 부분 문제의 해석을 통해 주 문제의 $\theta$를 업데이트하며 최적 해를 찾아간다.

Dantzig-Wolfe 분해 과정

Dantzig-Wolfe 분해의 핵심은 주 문제와 부분 문제를 번갈아가며 해결하는 반복 과정이다. 이 과정은 다음과 같은 단계로 구성된다.

1. 초기 주 문제 설정

초기 주 문제는 문제의 큰 제약 조건을 해결한다. 초기에는 자원의 제한을 반영하지 않고 각 부분 문제의 최적화만을 수행하여 가능한 해를 찾는다.

주 문제의 초기 형태는 다음과 같다:

이때, $\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_k$는 부분 문제에서 구해진 해이다.

2. 부분 문제 해결

각 부분 문제는 주어진 $\mathbf{x}_i$에 대해 독립적으로 해결된다. 부분 문제의 일반적인 형태는 다음과 같다:

부분 문제에서 구해진 $\mathbf{z}_i$ 값은 주 문제의 해에 반영되며, 이를 통해 전체 자원의 제약 조건을 만족하는 방향으로 수렴해 나간다.

3. 이중 변수(dual variable) 갱신

각 부분 문제를 해결한 후, 주 문제는 이중 변수를 갱신한다. 이중 변수는 부분 문제와 주 문제 간의 연결을 관리하며, 최적화 과정에서 자원의 가격을 나타낸다.

주 문제에서의 이중 변수는 다음과 같이 표현된다:

여기서, $\lambda$는 주 문제의 라그랑지 승수(Lagrange multiplier)이다.

4. 반복 과정

이중 변수가 갱신된 후, 주 문제는 다시 한 번 최적화를 수행한다. 이때 각 부분 문제에서의 결과는 다음 반복에서 주 문제에 반영된다. 이 과정은 주 문제와 부분 문제의 수렴이 이루어질 때까지 반복된다.

Benders 분해 과정

Benders 분해는 주 문제와 부분 문제로 나누어 문제를 해결하는 또 다른 방식이다. Benders 분해는 주로 혼합 정수계획 문제에 적용되며, 다음과 같은 단계로 이루어진다.

1. 초기 주 문제 설정

Benders 분해에서는 먼저 정수 변수를 포함하는 주 문제를 정의한다. 주 문제는 다음과 같은 형태로 나타난다:

여기서, $\theta$는 부분 문제에서 계산된 목적 함수 값이며, 이는 이후 과정에서 반복적으로 갱신된다.

2. 부분 문제 해결

부분 문제는 주어진 정수 변수 $\mathbf{x}_I$를 이용하여 연속 변수 $\mathbf{x}_C$에 대한 최적 해를 구한다. 부분 문제는 다음과 같이 표현된다:

부분 문제에서 얻어진 해는 주 문제에 반영되며, 주 문제는 이를 바탕으로 $\theta$ 값을 업데이트한다.

3. 주 문제의 반복 갱신

주 문제는 부분 문제에서 얻은 결과를 바탕으로 정수 변수를 업데이트한다. 이 과정은 수렴할 때까지 반복되며, 최종적으로 최적 해에 도달하게 된다.

주 문제의 갱신된 형태는 다음과 같다:

Dantzig-Wolfe 분해와 Benders 분해의 차이점

Dantzig-Wolfe 분해는 블록 구조를 가진 선형계획 문제에 적합하며, Benders 분해는 혼합 정수계획 문제에서 사용된다. 두 방법 모두 문제를 분리하여 처리하지만, 그 방식과 적용 범위에 차이가 있다. Dantzig-Wolfe 분해는 주로 연속 변수에 초점을 맞추며, Benders 분해는 정수 변수와 연속 변수를 모두 고려하는 방식이다.