조합 최적화

응용수학과 전산학에서 조합 최적화는 최적화 문제의 일종으로서, 운용 과학, 알고리즘 이론, 계산 복잡도 이론과 관련되어 있고, 인공지능, 수학, 소프트웨어 공학과 영역이 겹친다. 조합 최적화에서는 일반적으로 어렵다고 보는 문제를 풀려고 한다. 어려운 문제들은 보통 문제 공간이 크기 때문에 조합 최적화 알고리즘은 문제 공간을 좁히거나 탐색 효율을 높이는 데 중점을 둔다.

계산 복잡도 이론의 연구 결과가 조합 최적화에서 쓸모있는 경우가 많다. 조합 최적화 알고리즘은 보통 NP-완전인 문제를 다루는데, 일반적으로 NP-완전 문제는 쉽게 풀 수 없다고 보고 있다. 그러나 복잡도 이론의 여러 근사에 따르면 몇몇 특수한 경우에는 효율적으로 풀 수 있다. 조합 최적화에서는 바로 이러한 경우에 대해 관심을 갖는다. 이런 경우는 중요하고 실용적인 응용을 할 수 있을 때가 많다.

약식 정의

조합 최적화의 영역은 가능해가 이산 집합에 속하거나 이산적인 것으로 변환될 수 있고, 가장 좋은 해를 찾는 것이 목적인 최적화 문제이다.

엄밀한 정의

조합 최적화 문제의 인스턴스는 튜플 $(X,P,Y,f, extr)$ 로 쓸 수 있다. 여기서 각 기호는 아래와 같은 뜻이다.

X - 문제 공간 (이 공간상에서 f와 P가 정의된다)
P - 유효성을 나타내는 술어
Y - 가능해의 집합
f - 목적 함수
extr - 극단값 (보통 최솟값이나 최댓값)

대표적인 문제

차량 경로 문제
외판원 문제
최소 비용 걸침 나무 문제
선형계획법 (해의 공간이 어떤 변수를 기본 변수로 할 것인지 고르는 것과 같다면)
여덟 퀸 문제. (제약 만족 문제이다. 이러한 문제에 표준 조합 최적화 알고리즘을 적용할 때는 문제 전체가 만족되었는지 여부를 나타내는 불 변수 하나보다는 만족되지 않은 제약 조건의 수를 최적화하는 목적 함수를 주로 사용한다.)
배낭 문제

방법

아래 열거한 발견 탐색 방법(메타휴리스틱 알고리즘)은 조합 최적화 문제를 푸는 데 흔히 사용된다.

참고 문헌

William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver; Combinatorial Optimization; John Wiley & Sons; 1 edition (November 12, 1997); ISBN 0-471-55894-X.
Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger, A Compendium of NP Optimization Problems.
Christos H. Papadimitriou and Kenneth Steiglitz Combinatorial Optimization : Algorithms and Complexity; Dover Pubns; (paperback, Unabridged edition, July 1998) ISBN 0-486-40258-4.
Arnab Das and Bikas K. Chakrabarti (Eds.) Quantum Annealing and Related Optimization Methods, Lecture Note in Physics, Vol. 679, Springer, Heidelberg (2005)

학술지

Journal of Combinatorial Optimization Archived 2008년 11월 21일 - 웨이백 머신
Discrete Optimization

조합 최적화

목차

약식 정의

엄밀한 정의

대표적인 문제

방법

관련글

참고 문헌

학술지