정수계획법의 개요 - 실험 도서관

정수계획법(ILP, Integer Linear Programming)은 모든 의사결정 변수가 정수 값을 가져야 하는 선형계획법의 한 종류이다. 즉, 일반적인 선형계획법에서는 연속적인 값을 가질 수 있는 변수들이 정수로 제한된다는 점에서 차이가 있다. 이로 인해 문제의 복잡성이 커지지만, 현실 세계의 문제들 중 많은 부분에서 정수계획법이 필요하다.

정수계획법의 정의

정수계획법은 다음과 같이 정의된다.

주어진 목적 함수 $\mathbf{c}^\top \mathbf{x}$ 를 최대화 또는 최소화하는 것이 목표이며, 다음의 제약 조건들을 만족해야 한다.

$\mathbf{A} \mathbf{x} \leq \mathbf{b}$

$\mathbf{x} \in \mathbb{Z}^n$

여기서:

$\mathbf{A}$ 는 $m \times n$ 행렬이고, 각 원소는 실수이다.
$\mathbf{x}$ 는 $n$ 차원의 결정 변수 벡터이며, 각 원소는 정수이다.
$\mathbf{b}$ 는 $m$ 차원의 실수 벡터이다.
$\mathbf{c}$ 는 $n$ 차원의 실수 벡터로, 목적 함수의 계수를 나타낸다.
$\mathbb{Z}^n$ 은 모든 결정 변수가 정수임을 의미한다.

위 정의에서 볼 수 있듯이, 정수계획법은 일반적인 선형계획 문제와 구조적으로 유사하지만, 변수의 값이 정수로 제한된다는 점이 주요 차이점이다.

정수계획법의 응용

정수계획법은 다양한 응용 분야에서 사용된다. 그 중에서 대표적인 사례는 다음과 같다:

물류 최적화 문제: 제품을 여러 목적지로 운송하는 문제에서, 트럭이나 배와 같은 운송 수단은 일정한 수의 제품만을 실을 수 있으므로, 이러한 문제는 정수계획법으로 모델링될 수 있다.
네트워크 설계: 네트워크에서 연결의 유무를 나타내는 변수가 이진 변수(0 또는 1)인 경우, 정수계획법이 사용된다.
스케줄링 문제: 시간표나 작업 스케줄을 최적화하는 문제에서도 작업이 배정되는 시간이 정수 값으로 제한될 수 있다.

정수계획법의 종류

정수계획법은 그 특성에 따라 다양한 유형으로 나뉜다. 주요한 종류는 다음과 같다:

순수 정수계획법
순수 정수계획법(Pure Integer Linear Programming)은 모든 변수들이 정수 값만을 가질 때 적용된다. 즉, 문제에 포함된 모든 결정 변수 $\mathbf{x}_i$ 가 정수일 경우를 의미한다.

$\mathbf{x}_i \in \mathbb{Z} \quad \forall i$

이 방식은 예를 들어, 공장 생산에서 생산되는 제품의 개수가 정수로만 나올 수 있는 경우에 적합하다.

혼합 정수계획법
혼합 정수계획법(Mixed Integer Linear Programming, MILP)은 일부 결정 변수는 정수, 나머지 변수는 실수 값을 가질 수 있는 경우를 다룬다. 즉, 변수 벡터 $\mathbf{x}$ 가 두 부분으로 나뉘어, 일부는 정수로 제한되고 다른 일부는 연속적인 값을 가질 수 있다.

$\mathbf{x} = \left( \mathbf{x}_1, \mathbf{x}_2 \right)$

$\mathbf{x}_1 \in \mathbb{Z}^p, \quad \mathbf{x}_2 \in \mathbb{R}^{n-p}$

여기서 $\mathbf{x}_1$ 은 정수로 제한된 변수이고, $\mathbf{x}_2$ 는 연속적인 값을 가질 수 있는 변수이다. 이 모델은 실생활에서 매우 자주 사용되며, 다양한 공학 및 경제 문제를 모델링할 때 적합하다.

이진 정수계획법
이진 정수계획법(Binary Integer Linear Programming)은 변수들이 이진 값(0 또는 1)만 가질 수 있는 특별한 형태의 정수계획법이다. 이 유형은 선택 문제 또는 의사결정 문제에서 주로 사용되며, 예를 들어 특정 자원을 사용할지 말지를 결정하는 문제에 적합하다.

$\mathbf{x}_i \in \{0, 1\}$

이진 정수계획법은 여러 현실 문제에서 이진 선택을 필요로 하는 상황에서 매우 유용하게 사용된다.

정수계획법의 난이도

정수계획법은 일반적인 선형계획법에 비해 계산적으로 훨씬 어려운 문제로 간주된다. 선형계획법은 다항 시간 안에 해결할 수 있는 문제이지만, 정수계획법은 NP-난해 문제(NP-hard problem)로 분류된다. 이는 정수계획법을 해결하는 데 필요한 시간이 문제가 커짐에 따라 기하급수적으로 증가할 수 있음을 의미한다.

정수계획법에서 발생하는 어려움은 결정 변수들이 연속적인 값을 가지지 않고 정수로 제한됨에 따라, 탐색 공간이 비연속적이 되어 계산 과정에서 고려해야 할 가능성이 크게 늘어난다는 점에서 기인한다.

정수계획법의 해결 방법

정수계획법의 해법은 일반적인 선형계획법과는 다르며, 다음과 같은 기법들을 사용한다:

분지 한정법(Branch and Bound)
분지 한정법은 정수계획법에서 자주 사용되는 기법으로, 탐색 공간을 분할하여 가능한 해를 탐색하고, 특정 조건에서 탐색을 중단함으로써 효율적으로 해를 찾는다.
절단평면법(Cutting Plane Method)
절단평면법은 기존의 연속적인 해에서 출발하여, 정수해를 얻기 위한 추가적인 제약(절단평면)을 만들어 해를 구하는 방법이다. 이 방법은 선형계획법의 해를 기초로 정수해를 향해 접근해 가는 방식이다.
휴리스틱 알고리즘(Heuristic Algorithms)
복잡한 정수계획 문제의 경우, 완전한 최적해를 찾기보다는 근사적인 해를 빠르게 구하는 휴리스틱 방법이 많이 사용된다. 예를 들어 유전자 알고리즘(Genetic Algorithm), 시뮬레이티드 어닐링(Simulated Annealing) 등의 기법이 여기에 속한다.

정수계획법에서 최적화 문제를 풀 때 이러한 방법들이 적절히 조합되어 사용된다.