# 대규모 최적화 문제에서의 선형계획법

대규모 최적화 문제에서 선형계획법(Linear Programming, LP)을 적용하는 것은 많은 산업과 연구 분야에서 필수적이다. 특히, 변수와 제약 조건이 수천, 수백만 개에 달하는 문제는 매우 큰 계산량을 요구하며, 효율적인 방법론 없이는 실질적으로 해결이 불가능한다. 대규모 최적화 문제에서의 선형계획법은 이론적 기초뿐 아니라 실무 적용에서도 중요한 역할을 한다.

#### 1. 대규모 문제의 특성

대규모 선형계획 문제는 작은 문제와는 다른 특성을 가지고 있다. 주요 특징으로는 다음을 들 수 있다.

* **변수의 수가 많다**: 수천 개에서 수백만 개 이상의 결정 변수(Decision Variables)를 포함할 수 있다.
* **제약 조건의 수가 많다**: 일반적으로 대규모 문제는 복잡한 시스템을 모델링하기 때문에 제약 조건의 수 역시 많아진다.
* **데이터 크기**: 문제를 표현하는 데이터의 크기가 매우 커지며, 이로 인해 메모리와 계산 시간이 급격히 증가한다.
* **희소성**: 대부분의 대규모 문제는 희소행렬(Sparse Matrix) 형태로 나타나며, 이를 효과적으로 다루는 방법이 필요하다.

#### 2. 희소 행렬과 계산 효율성

대규모 선형계획 문제에서 중요한 개념 중 하나는 \*\*희소성(Sparsity)\*\*이다. 많은 실무 문제에서 각 변수와 제약 조건이 서로 독립적인 경우가 많아, 행렬의 대다수 원소가 0으로 채워져 있다. 이러한 행렬을 **희소 행렬**이라고 하며, 이를 효율적으로 처리하는 것이 대규모 문제 해결의 핵심이다.

희소 행렬을 처리하기 위해 다음과 같은 기법들이 사용된다:

* **압축 저장 방식**: 희소 행렬은 비제로(non-zero) 성분만을 저장하여 메모리 사용량을 줄이다. 대표적인 방식으로는 Compressed Row Storage (CRS)와 Compressed Column Storage (CCS)가 있다.

  예를 들어, 행렬 $\mathbf{A}$가 다음과 같이 주어졌다고 가정해봅시다:

$$
\mathbf{A} = \begin{bmatrix} 0 & 0 & 3 & 0 \ 0 & 5 & 0 & 0 \ 1 & 0 & 0 & 4 \ \end{bmatrix}
$$

이 행렬을 압축된 형태로 저장하는 방법은 비제로 성분과 그들의 위치만 기록하는 방식이다. 이 경우, 행렬 $\mathbf{A}$는 다음과 같이 저장될 수 있다:

* 값: $\[3, 5, 1, 4]$
* 열 인덱스: $\[2, 1, 0, 3]$
* 행 포인터: $\[0, 1, 3]$
* **희소 행렬 곱셈**: 희소 행렬 간의 곱셈을 수행할 때는, 0이 아닌 성분만을 곱하는 방식으로 계산량을 대폭 줄일 수 있다.

#### 3. 분해 기법

대규모 문제의 또 다른 해결 방법으로 \*\*분해 기법(Decomposition Techniques)\*\*이 자주 사용된다. 분해 기법은 큰 문제를 여러 개의 작은 하위 문제로 나누어 해결한 후, 이들을 다시 결합하는 방식이다. 이러한 접근 방식은 대규모 문제를 다루는 데 매우 유용하다.

대표적인 분해 기법으로는 다음이 있다:

**듀얼 분해법**

듀얼 분해법(Dual Decomposition)은 원래의 문제를 듀얼 문제로 변환하여 푸는 방법이다. 듀얼 문제를 풀 때, 각각의 제약 조건을 분리하여 독립적인 하위 문제로 처리할 수 있으며, 이는 병렬 계산이 가능하게 만든다.

다음과 같은 기본 선형계획 문제를 고려하자:

$$
\text{minimize } \mathbf{c}^\top \mathbf{x}
$$

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

듀얼 문제는 다음과 같이 작성된다:

$$
\text{maximize } \mathbf{b}^\top \mathbf{y}
$$

$$
\text{subject to } \mathbf{A}^\top \mathbf{y} \leq \mathbf{c}
$$

여기서, $\mathbf{y}$는 듀얼 변수이다. 듀얼 문제를 풀면, 원래 문제에 대한 최적 해를 유도할 수 있다. 이 과정에서 제약 조건을 분리하여 독립적인 문제로 나누어 해결하게 된다.

**분지 한정법**

분지 한정법(Branch and Bound)은 특히 정수계획법과 같은 문제에 유용한 방법이다. 이 방법은 가능한 해의 공간을 분할하여 하위 문제로 나눈 다음, 하위 문제를 순차적으로 해결해나가는 방식이다. 각 하위 문제는 특정한 변수의 값에 대한 제약을 적용하여 해결되며, 하위 문제에서 계산된 결과는 전체 문제의 해를 찾는 데 사용된다.

분지 한정법의 작동 원리를 시각적으로 mermaid를 이용하여 표현하면 다음과 같다:

{% @mermaid/diagram content="graph TD
Start\[문제 시작] --> Branch1\[분할 1]
Start --> Branch2\[분할 2]
Branch1 --> SubProblem1\[하위 문제 1]
Branch1 --> SubProblem2\[하위 문제 2]
Branch2 --> SubProblem3\[하위 문제 3]
Branch2 --> SubProblem4\[하위 문제 4]" %}

이와 같은 방식으로 큰 문제를 분할하여 해결해 나가면, 각 하위 문제를 병렬적으로 처리할 수 있어 계산 효율성이 높아진다.

#### 4. 병렬 계산의 활용

대규모 선형계획 문제를 해결할 때는 **병렬 계산(Parallel Computing)** 기법이 매우 유용하게 사용된다. 병렬 계산은 여러 개의 프로세서나 컴퓨터 노드에서 동시에 작업을 수행함으로써 계산 속도를 높이고, 대규모 문제를 실시간에 가깝게 해결할 수 있는 방법이다.

**병렬 단체법**

병렬 계산을 선형계획법에 적용하는 대표적인 방법 중 하나는 \*\*병렬 단체법(Parallel Simplex Method)\*\*이다. 단체법은 각 반복에서 변수와 제약 조건을 업데이트하는 방식으로 작동하는데, 대규모 문제에서는 이러한 업데이트를 병렬로 수행할 수 있는 기회가 많다. 병렬 단체법의 주요 특징은 다음과 같다:

* **기저 행렬(Basis Matrix)의 병렬 업데이트**: 단체법에서 기저 행렬은 반복마다 계산되며, 이를 여러 스레드에서 병렬로 처리할 수 있다. 특히, 희소 행렬의 경우 각 열을 독립적으로 업데이트할 수 있기 때문에 병렬 계산의 장점을 극대화할 수 있다.
* **다중 단계의 병렬화**: 단체법의 각 단계(기저 선택, 기저 업데이트, 최적화 값 계산 등)를 병렬로 수행함으로써 전체 알고리즘의 속도를 높일 수 있다.

**병렬 내부점 방법**

내부점 방법(Interior-Point Method) 또한 병렬 계산과 잘 맞습니다. 내부점 방법은 반복적으로 중심 경로를 따라 최적 해를 찾는 방식으로, 큰 행렬을 반복적으로 계산하는 과정을 포함한다. 이 과정에서 각 반복 단계에서의 계산을 병렬화할 수 있다. 내부점 방법에서 병렬화가 이루어지는 부분은 주로 **행렬의 곱셈과 분해** 단계이다.

병렬 내부점 방법의 작동 과정은 다음과 같다:

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

위 제약 조건을 만족하는 해를 찾기 위해 내부점 방법은 다음과 같은 반복적인 계산을 병렬로 수행할 수 있다:

* 행렬 곱셈: $\mathbf{A} \mathbf{x}$와 같은 연산은 각 행과 열에 대해 병렬로 수행될 수 있다.
* 뉴턴 단계: 내부점 방법에서 사용하는 뉴턴 방법(Newton's Method)은 주어진 해를 향해 수렴하는 과정을 병렬화할 수 있다.

**분산 계산**

\*\*분산 계산(Distributed Computing)\*\*은 병렬 계산보다 더 확장된 개념으로, 여러 대의 컴퓨터나 서버에 문제를 나누어 계산하는 방식이다. 이는 대규모 문제에서 매우 유용하며, 특히 클라우드 컴퓨팅 환경에서는 매우 효과적이다.

대표적인 분산 계산 방법으로는 \*\*MPI(Message Passing Interface)\*\*와 같은 기술을 사용할 수 있다. 이 방식은 다음과 같은 단계로 이루어진다:

1. 문제를 여러 개의 작은 하위 문제로 분할
2. 각 하위 문제를 별도의 노드에서 계산
3. 계산된 결과를 통합하여 최종 해 도출

예를 들어, 대규모 네트워크 흐름 문제를 해결하는 과정에서 분산 계산을 적용할 수 있다. 각 노드에서 독립적으로 작은 부분 문제를 해결하고, 최종적으로 중앙 서버에서 그 결과를 취합하여 전체 네트워크의 흐름을 최적화할 수 있다.

**GPU 가속**

또한, **GPU 가속**을 통해 대규모 선형계획 문제를 빠르게 해결할 수 있다. GPU는 다수의 연산을 병렬로 처리하는 데 최적화되어 있어, 특히 희소 행렬 연산과 같은 병렬화가 잘 되는 문제에서 매우 유용하다.

#### 5. 대규모 선형계획법의 분해 기법: Dantzig-Wolfe 분해법

**Dantzig-Wolfe 분해법**은 대규모 선형계획 문제를 해결할 때 자주 사용되는 방법 중 하나이다. 특히, 특정 구조를 가진 문제를 효율적으로 해결할 수 있는 방법이다. 이 기법은 문제를 여러 하위 문제로 분리한 후, 각 하위 문제를 독립적으로 해결하고, 그 결과를 결합하여 전체 문제를 해결한다.

**문제 구조**

Dantzig-Wolfe 분해법은 **계획 문제의 블록 구조**를 가지고 있는 경우 유리한다. 문제는 다음과 같은 형식으로 주어진다.

$$
\text{minimize } \mathbf{c}^\top \mathbf{x}
$$

$$
\text{subject to } \mathbf{A}\_1 \mathbf{x}\_1 + \mathbf{A}\_2 \mathbf{x}\_2 + \cdots + \mathbf{A}\_n \mathbf{x}\_n = \mathbf{b}, \quad \mathbf{x}\_i \geq 0 \quad (i = 1, 2, \dots, n)
$$

여기서 각 $\mathbf{x}\_i$는 독립적인 하위 문제로 나눌 수 있으며, 이는 각 블록 $\mathbf{A}\_i$의 특성에 따라 처리된다.

**Dantzig-Wolfe 분해 절차**

Dantzig-Wolfe 분해법은 다음과 같은 절차로 이루어진다:

1. **마스터 문제(Master Problem)**: 먼저, 전체 문제의 일부인 마스터 문제를 정의한다. 이 문제는 전체 문제의 목표 함수를 기반으로 하며, 각 하위 문제의 해를 포함한다.
2. **하위 문제(Subproblem)**: 각 하위 문제는 고정된 제약 조건 하에서 독립적으로 해결된다. 각 하위 문제에서 얻은 해는 마스터 문제에 피드백된다.
3. **재결합**: 하위 문제에서 얻은 해를 바탕으로 마스터 문제를 갱신하며, 이 과정을 반복하여 전체 문제의 최적 해를 구한다.

이 과정을 시각적으로 표현하면, 다음과 같은 다이어그램으로 나타낼 수 있다:

{% @mermaid/diagram content="graph TD
Master\[마스터 문제] --> SubProblem1\[하위 문제 1]
Master --> SubProblem2\[하위 문제 2]
Master --> SubProblem3\[하위 문제 3]
SubProblem1 --> Result1\[결과 1]
SubProblem2 --> Result2\[결과 2]
SubProblem3 --> Result3\[결과 3]
Result1 --> Master
Result2 --> Master
Result3 --> Master" %}

이러한 방식으로 마스터 문제와 하위 문제 간의 반복적인 상호작용을 통해 최적 해에 도달한다.

**Dantzig-Wolfe 분해의 수식적 표현**

마스터 문제와 하위 문제를 수식으로 표현하면 다음과 같다.

* **마스터 문제**:

$$
\min \mathbf{c}^\top \mathbf{x} + \sum\_{i=1}^{n} \lambda\_i \mathbf{d}\_i
$$

여기서 $\lambda\_i$는 하위 문제에서 도출된 변수이다.

* **하위 문제**:

  각 하위 문제는 다음과 같이 나타낼 수 있다:

$$
\min \mathbf{c}\_i^\top \mathbf{x}\_i \quad \text{subject to } \mathbf{A}\_i \mathbf{x}\_i = \mathbf{b}\_i, \quad \mathbf{x}\_i \geq 0
$$

각 하위 문제에서 얻은 해는 마스터 문제로 전달되어 전체 문제의 해를 업데이트한다.

#### 6. Benders 분해법

**Benders 분해법**은 또 다른 중요한 분해 기법으로, 대규모 혼합 정수 선형계획(Mixed Integer Linear Programming, MILP) 문제에 주로 사용된다. Benders 분해법은 문제를 두 개의 하위 문제로 나누어 해결하며, 하나는 **마스터 문제**이고, 다른 하나는 **서브 문제**이다.

**Benders 분해의 절차**

Benders 분해법은 다음과 같은 절차로 이루어진다:

1. **초기화**: 먼저, 마스터 문제에서 초기 해를 구한다.
2. **서브 문제 생성**: 마스터 문제의 해를 사용하여 서브 문제를 생성한다.
3. **서브 문제 해결**: 서브 문제를 해결하여, 그 결과를 바탕으로 마스터 문제를 업데이트한다.
4. **반복**: 서브 문제와 마스터 문제 간의 반복적인 피드백을 통해 최적 해에 도달한다.

**Benders 분해법의 수식**

* **마스터 문제**:

$$
\min \mathbf{c}^\top \mathbf{x} + \sum\_{j=1}^{m} \theta\_j
$$

여기서 $\theta\_j$는 서브 문제에서 도출된 변수이다.

* **서브 문제**:

  서브 문제는 다음과 같이 나타난다:

$$
\min \mathbf{d}\_j^\top \mathbf{y}\_j \quad \text{subject to } \mathbf{A}\_j \mathbf{y}\_j = \mathbf{b}\_j, \quad \mathbf{y}\_j \geq 0
$$

이 과정에서 얻어진 $\mathbf{y}\_j$ 값은 마스터 문제로 다시 전달되어 전체 해를 갱신한다.