해결 기법 분지한정법, 절단평면법

분지한정법 (Branch and Bound)

분지한정법(Branch and Bound)은 정수계획법을 해결하는 대표적인 기법 중 하나로, 문제를 여러 개의 하위 문제로 분리한 후 그 하위 문제들을 해결하면서 불필요한 해를 가지는 영역을 배제하는 방식으로 진행된다. 이 과정은 탐색 트리 구조로 이루어지며, 트리의 각 노드는 특정 변수의 값을 정수로 고정하거나 연속적인 값을 가지게 하는 하위 문제로 정의된다.

분지(Branching)

분지 단계에서는 문제를 두 개 이상의 하위 문제로 나눈다. 예를 들어, 어떤 변수 $x_i$ 가 연속적인 값을 가진다면, 이를 정수로 고정시키기 위해 $x_i \leq k$ 와 $x_i \geq k+1$ 로 나누는 것이 대표적인 분지 방법이다. 이 과정을 반복함으로써 문제를 점점 더 작은 하위 문제로 나누게 된다.

예를 들어, $x_i = 1.5$ 일 때 이를 정수로 변환하려면 다음 두 가지 분기를 만들 수 있다:

$x_i \leq 1 \quad \text{또는} \quad x_i \geq 2$

한정(Bounding)

한정 단계에서는 각각의 하위 문제에 대해 상한 또는 하한을 계산한다. 상한 또는 하한은 최적화 문제의 목적 함수 값으로, 하위 문제에서 더 이상 고려할 필요가 없는 경우 이를 한정(bounding)하여 탐색 공간을 줄일 수 있다.

상한 또는 하한 계산은 보통 단체법(Simplex Method)을 사용하여 이루어지며, 정수해를 요구하지 않는 경우 연속적인 최적해를 계산할 수 있다.

한정에 대한 조건

한정 조건을 적용하는 경우는 다음과 같다: 1. 해를 찾은 경우: 하위 문제에서 최적해가 정수해를 가지면, 해당 해가 현재까지의 최적해인지 확인하고 다른 하위 문제들은 더 이상 고려하지 않는다. 2. 가능 영역이 없는 경우: 하위 문제에서 가능한 해가 없으면 더 이상 탐색하지 않는다. 3. 상한 또는 하한이 현재 최적해보다 나쁜 경우: 하위 문제에서 계산된 상한 또는 하한이 현재까지 구한 최적해보다 나쁜 경우 그 하위 문제는 더 이상 고려하지 않는다.

다이어그램을 통해 분지한정법의 프로세스를 간단히 나타낼 수 있다.

graph TD; A[최초 문제] --> B[분지 1]; A --> C[분지 2]; B --> D[하위 문제 1]; B --> E[하위 문제 2]; C --> F[하위 문제 3]; C --> G[하위 문제 4]; D --> H[정수해 여부]; E --> I[정수해 여부]; F --> J[정수해 여부]; G --> K[정수해 여부];

절단평면법 (Cutting Plane Method)

절단평면법(Cutting Plane Method)은 선형계획법의 해를 반복적으로 개선하여 정수해를 찾는 기법이다. 초기에는 연속적인 해를 찾고, 이 해가 정수해가 아닌 경우 정수해가 포함되지 않는 영역을 절단(cutting)하는 평면을 추가하여 해를 점진적으로 개선한다. 이 방법은 특히 혼합 정수계획법에서 많이 사용된다.

절단평면의 개념

절단평면은 가능 영역을 축소하는 평면이다. 이 평면은 원래의 선형계획 문제의 가능한 해들을 포함하는 반면, 정수해가 아닌 해들을 제거한다. 이를 통해 해를 정수해 쪽으로 유도할 수 있다.

예를 들어, $x_i = 1.5$ 라는 연속적인 해를 얻었을 때, 이 해를 제거하기 위해서는 $x_i \leq 1$ 또는 $x_i \geq 2$ 와 같은 절단평면을 도입할 수 있다.

$x_i \leq 1 \quad \text{또는} \quad x_i \geq 2$

절단평면 생성

절단평면은 정수해를 포함하지 않는 부분을 제거하기 위해 생성된다. 이때, 자주 사용되는 절단평면의 한 종류는 고모리 절단(Gomory Cut)이다. 이 절단은 단체법에서 얻은 연속적인 해의 분수를 기반으로 평면을 생성하는 방식이다.

고모리 절단의 생성 방식은 다음과 같다. 먼저 단체법을 사용하여 다음과 같은 연속해를 얻었다고 가정한다:

$\mathbf{A} \mathbf{x} = \mathbf{b}, \quad x_i \notin \mathbb{Z}$

여기서 $x_i$ 가 정수가 아니므로, $x_i$ 가 정수가 되도록 절단평면을 추가해야 한다.

절단평면의 수학적 표현

절단평면의 수학적 표현은 다음과 같다. $x_i = 1.5$ 이라는 해가 나온 경우, 이 해를 제거하는 절단평면은 다음과 같은 부등식을 이용하여 도입될 수 있다:

$\mathbf{a}^T \mathbf{x} \leq \lfloor \mathbf{a}^T \mathbf{x} \rfloor$

이 절단은 가능 영역을 축소시키면서 정수해로 수렴하는 과정을 도와준다.

고모리 절단(Gomory Cut)

고모리 절단은 분수 값이 있는 선형계획법의 해를 정수해로 만드는 절단평면법 중 하나이다. 이 방법은 단체법으로 얻은 최적해가 정수해가 아닐 때 적용된다. 절단평면은 정수해를 제외하지 않으면서도 정수해가 아닌 해를 제거하는 평면이다.

고모리 절단의 과정

단체법으로 해 도출: 먼저 연속적인 선형계획 문제를 단체법을 통해 해결하여 최적해를 구한다. 만약 이 최적해가 정수해가 아니라면, 절단평면을 도입하여 정수해를 구하는 과정을 반복한다.
분수 부분 추출: 최적해에서 분수 값을 가지는 변수를 찾는다. 예를 들어, $x_i = 3.7$ 과 같이 분수 부분을 가진 경우, 이를 제거하기 위해 절단을 도입한다.
절단식 생성: 해당 분수 값을 기반으로 절단평면을 생성한다. 고모리 절단의 기본 원리는 다음과 같다. 단체법에서 얻은 해가 $\mathbf{A} \mathbf{x} = \mathbf{b}$ 를 만족한다고 가정하자. 이때, 모든 변수들이 정수가 아니므로 분수 부분을 가지는 $x_i$ 에 대해 절단식을 도입할 수 있다. 분수 부분이 $\mathbf{f}(x_i) = 0.7$ 라면, 새로운 제약식을 추가하여 해당 해를 제외한다:

$\mathbf{a}^T \mathbf{x} \leq \lfloor \mathbf{a}^T \mathbf{x} \rfloor$

여기서 $\mathbf{a}$ 는 새로운 절단을 나타내는 벡터이다.

고모리 절단 예시

고모리 절단의 구체적인 예시를 들어보자. 선형계획 문제에서 다음과 같은 제약식을 가지고 있다고 가정한다:

$3x_1 + 2x_2 = 5.7$

여기서 $x_1, x_2$ 는 정수여야 하므로, 고모리 절단을 적용할 수 있다. 우선 분수 부분을 분석하면, 해는 $5.7$ 로 분수 부분이 존재한다. 이를 해결하기 위해 새로운 절단을 다음과 같이 도입할 수 있다:

$3x_1 + 2x_2 \leq 5$

이 절단식을 통해 가능한 해의 영역을 좁히고, 정수해를 얻을 수 있다.

반복적인 절단

고모리 절단은 한 번의 절단으로 끝나는 것이 아니라, 정수해를 얻을 때까지 여러 번의 절단을 반복적으로 도입하여 최적해로 수렴한다. 각 단계에서 새로운 절단평면을 도입함으로써 최적화 문제를 해결해 나간다.

다이어그램으로 고모리 절단의 과정을 간략히 나타내면 다음과 같다:

graph TD; A[초기 해] --> B[분수 부분 분석]; B --> C[절단 평면 도입]; C --> D[새로운 해 계산]; D --> E[정수해 여부]; E --> F{정수해인가?}; F --> G[종료]; F --> B[분수 부분 재분석];

절단평면법의 수렴성

절단평면법은 이론적으로는 무한히 많은 절단평면을 도입해야 할 수도 있지만, 실제 문제에서는 유한한 단계에서 정수해를 얻는 경우가 많다. 절단평면법의 효과는 문제의 구조에 따라 달라지며, 고모리 절단 외에도 다양한 절단 기법들이 존재한다.

절단평면의 종류

고모리 절단 외에도 여러 가지 절단평면이 존재하며, 다음과 같은 절단 방법들이 자주 사용된다:

Chvátal-Gomory 절단: 고모리 절단의 확장으로, 선형계획 문제의 해를 정수해로 변환하는 일반적인 방법이다.
커버 절단(Cover Cut): 정수계획법에서 커버 조건을 만족하지 않는 해를 제거하기 위해 도입된다.
혼합 정수 절단(Mixed Integer Cut): 혼합 정수계획법에서 연속 변수와 정수 변수가 함께 존재하는 경우, 절단을 도입하여 정수해를 얻는 방법이다.

절단평면법의 응용

절단평면법은 다양한 실제 문제에 적용될 수 있으며, 특히 혼합 정수계획법(Mixed Integer Programming, MIP) 문제에서 많이 활용된다. 혼합 정수계획법은 연속 변수와 정수 변수를 함께 다루는 문제로, 절단평면법을 통해 연속 변수와 정수 변수를 구분하여 처리할 수 있다.

혼합 정수계획 문제에서의 절단평면

혼합 정수계획 문제는 일반적으로 다음과 같은 형태를 띤다:

$\min \mathbf{c}^T \mathbf{x}$

$\text{subject to } \mathbf{A} \mathbf{x} \leq \mathbf{b}, \quad x_i \in \mathbb{Z}, \, x_j \in \mathbb{R}$

여기서 $\mathbf{x} = (x_1, x_2, \dots, x_n)$ 은 정수 변수와 연속 변수의 혼합으로 이루어진 벡터이다. 이 문제를 해결하기 위해 절단평면법을 사용하면, 먼저 연속 변수에 대한 최적해를 찾고, 이를 바탕으로 정수해로 수렴하는 과정을 진행한다.

절단평면법의 절차

연속 최적해 계산: 초기 단계에서는 연속 변수를 포함한 문제를 해결하여 최적해를 계산한다. 이때, 정수 제약 조건은 무시된다.
정수 여부 확인: 최적해의 변수들이 모두 정수값을 가지는지 확인한다. 만약 모든 변수가 정수값을 가진다면, 이 해는 최종 해가 된다.
절단평면 도입: 최적해가 정수값을 가지지 않는 경우, 절단평면을 도입하여 연속 해를 제외하고 정수해로 수렴하도록 유도한다. 이 과정은 필요한 만큼 반복된다.

절단평면법의 수렴 조건

절단평면법은 일반적으로 유한한 단계에서 수렴한다. 문제의 구조에 따라 절단평면이 더 많이 필요할 수도 있지만, 혼합 정수계획 문제는 절단평면법을 통해 비교적 효율적으로 해결될 수 있다. 특히 고모리 절단과 같은 특정 절단 방법을 사용하는 경우, 더 빠른 수렴을 기대할 수 있다.

절단평면법의 실용적인 응용 사례

물류 최적화: 절단평면법은 물류 시스템에서 경로 최적화, 창고 관리 등의 문제에서 정수해를 요구하는 문제를 해결하는 데 효과적으로 사용된다.
스케줄링 문제: 절단평면법은 인력 스케줄링, 기계 스케줄링과 같은 문제에서도 적용될 수 있다. 특히 작업 시간과 관련된 제약이 정수해를 요구하는 경우 절단평면법이 유용하다.
네트워크 설계: 통신 네트워크에서 비용을 최소화하면서 정수 조건을 만족하는 최적의 네트워크를 설계할 때 절단평면법이 사용된다.

절단평면법의 장점과 한계

절단평면법은 정수계획 문제와 혼합 정수계획 문제에서 강력한 도구로 사용될 수 있지만, 몇 가지 한계도 존재한다. 절단평면을 도입할 때 계산 복잡도가 증가할 수 있으며, 문제의 구조에 따라 수렴 속도가 느려질 수 있다. 그러나 적절한 절단 방법을 선택하면 이러한 문제를 완화할 수 있다.