퇴행과 비퇴행 문제 해결

퇴행(Degeneracy)

단체법을 수행하는 도중 퇴행(degeneracy)이 발생할 수 있다. 퇴행은 기본 해(basic solution)가 여러 개의 동일한 값에 대응하는 경우 발생한다. 퇴행이 발생하면, 기본 변수 중 하나가 0이 되며, 이로 인해 단체법의 성능이 저하되고 무한 루프에 빠질 가능성이 생깁니다.

퇴행의 정의

단체법에서 기본 변수 중 하나 이상이 0인 경우, 이를 퇴행이라고 부른다. 퇴행 상태에서는 피봇팅(pivoting)을 통해 더 이상 개선되지 않는 해가 계속해서 반복될 수 있으며, 이는 단체법의 수렴 속도를 저하시킬 수 있다.

수학적으로, 퇴행이 발생하는 경우는 다음과 같이 설명될 수 있다. 기본 해가 $\mathbf{x}$ 라면, $\mathbf{x}$ 의 구성 요소 중 최소 하나가 0인 상태에서 발생한다.

$\mathbf{x} = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} \quad \text{where} \quad x_i = 0 \quad \text{for some} \quad i$

이때 퇴행이 발생할 수 있다.

비퇴행(Non-Degeneracy) 문제 해결

비퇴행 문제는 퇴행을 방지하기 위한 여러 방법을 통해 해결할 수 있다. 그 중 대표적인 방법은 블랜트의 규칙(Bland's Rule)이다.

블랜트의 규칙(Bland's Rule)

블랜트의 규칙은 피봇 선택 규칙 중 하나로, 퇴행 상태에서 무한 루프를 방지하기 위한 방법이다. 블랜트의 규칙은 들어오는 변수와 나가는 변수를 선택할 때 가장 작은 인덱스를 가진 변수를 선택하도록 강제한다.

이 규칙의 핵심은 피봇팅 과정에서 사이클링(cycling)을 방지하는 것이다. 즉, 같은 해로 계속해서 돌아오는 무한 루프를 방지하여 단체법이 수렴하도록 한다.

수학적으로 블랜트의 규칙은 다음과 같이 표현된다:

가장 작은 지수를 가진 음의 값을 가지는 $\mathbf{c}$ 벡터의 요소를 선택하여 들어오는 변수를 결정한다.

$\min \{ j : c_j < 0 \}$

나가는 변수는 가장 작은 인덱스를 가지는 변수를 선택하여 결정한다.

$\min \{ i : \frac{b_i}{a_{ij}} > 0 \}$

이 규칙은 무한 루프를 방지하며, 퇴행 상태에서의 문제 해결을 보장한다.

퇴행을 방지하기 위한 추가 방법들

작은 상수 추가법 (Perturbation Method)

퇴행을 방지하기 위한 또 다른 방법으로, 작은 상수를 추가하여 문제를 수정하는 작은 상수 추가법이 있다. 이 방법은 기본 해를 변경하지 않으면서 퇴행 상태를 해소할 수 있도록 도와준다.

이 방법의 주요 아이디어는 선형계획 문제의 제약 조건에 아주 작은 값을 추가함으로써 퇴행이 발생하지 않도록 하는 것이다. 수식적으로 다음과 같이 표현할 수 있다.

$\mathbf{A} \mathbf{x} = \mathbf{b} \quad \Rightarrow \quad \mathbf{A} \mathbf{x} = \mathbf{b} + \epsilon$

여기서 $\epsilon$ 은 매우 작은 양수이다. 이 상수를 추가함으로써, 퇴행 상태에서 벗어나 새로운 해를 찾을 수 있다. 이 방법은 퇴행 상태에서 무한 루프에 빠지지 않도록 하며, 문제의 수정이 직관적으로 이루어진다.

정수형 선형계획법(Integer Linear Programming)을 이용한 해결

퇴행이 발생하는 문제를 해결하기 위해 정수형 선형계획법을 적용할 수 있다. 정수형 선형계획법은 해가 정수로 제한되기 때문에, 퇴행 문제를 어느 정도 방지할 수 있는 장점이 있다. 특히, 퇴행이 발생하는 경우 기본 해가 여러 개 존재할 수 있는데, 이때 정수형 제약을 통해 해를 단일화할 수 있다.

정수형 선형계획법은 다음과 같은 형태로 정의된다:

$\max \mathbf{c}^\top \mathbf{x} \quad \text{subject to} \quad \mathbf{A} \mathbf{x} = \mathbf{b}, \quad \mathbf{x} \in \mathbb{Z}^n$

다단계 접근법 (Multi-Phase Method)

다단계 접근법은 퇴행 문제를 해결하기 위해 두 단계로 나누어 문제를 푸는 방법이다. 이 방법은 주어진 선형계획 문제를 해결하기 전, 첫 번째 단계에서 문제의 기본 해가 퇴행 상태인지 확인하고, 퇴행이 발생하는 경우 별도의 방법을 적용하여 비퇴행 상태로 전환한다.

1단계: 인공 변수를 도입하여 퇴행 상태를 벗어나게 한다.
2단계: 퇴행이 발생하지 않는 상태에서 원래의 문제를 풀어 최적 해를 찾는다.

이 과정에서 사용되는 수식은 다음과 같다:

$\mathbf{A} \mathbf{x} = \mathbf{b}, \quad \mathbf{x} \geq 0$

회전법(Anti-Cycling Rule)

퇴행 문제를 해결하기 위한 또 다른 방법은 회전법(Anti-Cycling Rule)이다. 이 방법은 단체법에서 발생할 수 있는 사이클링(cycling)을 방지하기 위해 고안되었다. 회전법은 다양한 규칙을 적용하여 퇴행 상태에서도 무한 루프에 빠지지 않도록 한다.

회전법의 주요 규칙

레진-리조스 규칙(Lexicographic Rule): 이 규칙은 퇴행이 발생했을 때, 각 기본 해를 사전순으로 정렬하여 비교하는 방법이다. 새로운 해를 구할 때 사전순으로 더 나은 해를 선택함으로써 퇴행을 방지한다. 이 방법은 해의 순서가 항상 정의되어 있으므로, 사이클링이 발생하지 않도록 보장된다.

레진-리조스 규칙을 적용하는 과정은 다음과 같다: 1. 각 기본 해를 벡터로 나타낸다. 2. 기본 해가 0인 변수가 있을 경우, 가장 작은 지수부터 비교한다. 3. 사전순으로 더 나은 해를 선택하여 퇴행을 방지한다.

무작위 피봇팅(Randomized Pivoting): 퇴행 상태에서 무작위로 피봇팅을 선택하는 방법이다. 이 규칙은 피봇 선택 시, 일정한 규칙을 따르지 않고 무작위로 변수를 선택함으로써 사이클링을 방지한다.

레진-리조스 규칙 수식

레진-리조스 규칙을 수식으로 설명하면, 각 기본 해를 사전순으로 비교하는 과정을 통해 퇴행을 방지한다. 기본 해 $\mathbf{x}$ 는 다음과 같이 사전순으로 비교될 수 있다:

$\mathbf{x}_1 = \begin{bmatrix} x_{11} \\ x_{12} \\ \vdots \\ x_{1n} \end{bmatrix}, \quad \mathbf{x}_2 = \begin{bmatrix} x_{21} \\ x_{22} \\ \vdots \\ x_{2n} \end{bmatrix}$

사전순 비교를 통해 $\mathbf{x}_1$ 과 $\mathbf{x}_2$ 중 작은 값을 선택한다:

$\mathbf{x}_1 \prec \mathbf{x}_2 \quad \text{if} \quad x_{1i} < x_{2i} \quad \text{for the smallest} \quad i \quad \text{where} \quad x_{1i} \neq x_{2i}$

이 규칙을 통해 퇴행을 방지하며, 피봇 선택을 보다 체계적으로 수행할 수 있다.