정수 계획법

3. NP-난해성 증명

정점 덮개에서 정수 계획법으로 환원하는 방법은 NP-난해성을 증명하는 데 사용된다.^[4]

무방향 그래프 $G\; =\; (V,E)$가 주어지면, 다음과 같은 선형 계획법을 정의할 수 있다.^[4]

:$\backslash begin\{align\}$

\min \sum_{v \in V} y_v \\

y_v + y_u & \ge 1 && \forall u,v \in E\\

y_v & \in \mathbb{Z^{+}} && \forall v \in V

\end{align}

$y\_v$는 0 또는 1로 제한되므로, 정수 계획법에서 실행 가능한 모든 해는 정점의 부분 집합을 나타낸다. 첫 번째 제약 조건은 모든 간선의 적어도 하나의 끝점이 이 부분 집합에 포함되어야 함을 의미하며, 이는 해가 정점 덮개를 나타낸다는 것을 뜻한다. 어떤 정점 덮개 C가 주어지면, $v\backslash in\; C$일 때 $y\_v$를 1로, $v\backslash not\backslash in\; C$일 때 0으로 설정하여 정수 계획법의 실행 가능한 해를 얻을 수 있다. 따라서 $y\_v$의 합을 최소화하면 최소 정점 덮개를 찾을 수 있다.^[4]

4. 변형 (Variants)

정수 계획법에는 여러 변형이 있다. 혼합 정수 선형 계획법(MILP)은 일부 변수만 정수로 제한하는 문제이고, 0-1 선형 계획법(또는 이진 정수 계획법)은 변수가 0 또는 1의 값만 가지도록 제한하는 문제이다.^[5]

4. 1. 혼합 정수 계획법 (Mixed Integer Linear Programming, MILP)

4. 2. 0-1 정수 계획법 (0-1 Integer Programming, Binary Integer Programming)

5. 응용 분야

정수 계획법은 현실의 다양한 문제에 적용될 수 있다. 정수 변수가 사용되는 주요 이유는 다음과 같다.

• 정수 표현: 3.7대의 자동차와 같이 정수만 가능한 수량을 나타낼 때 사용된다.
• 결정 표현: 그래프에 간선을 포함할지 여부와 같이 0 또는 1로 결정을 나타낼 때 사용된다.

• 생산 계획: 농업 생산 계획에서 자원 제약 하에 총 생산량을 최대화하는 데 사용된다.
• 스케줄링: 지하철과 같은 대중교통 시간표를 준수하고 운전자를 배정하는 문제를 해결하는 데 사용된다.
• 영토 분할: 정치, 학교, 의료 등 다양한 분야에서 특정 기준에 따라 지리적 구역을 나누는 문제에 적용된다.^[1]
• 통신망 설계: 통신 요구 사항을 충족하고 총비용을 최소화하는 네트워크 설계에 사용된다.^[6]
• 셀룰러 네트워크: GSM 이동 통신망에서 주파수 할당 문제를 해결하는 데 사용된다.^[7]

5. 1. 생산 계획 (Production Planning)

5. 2. 스케줄링 (Scheduling)

5. 3. 영토 분할 (Territorial Partitioning)

5. 4. 통신망 설계 (Telecommunications Networks)

5. 5. 셀룰러 네트워크 (Cellular Networks)

5. 6. 기타 응용 분야

• 현금 흐름 매칭
• 에너지 시스템 최적화^[8][9]
• 무인 항공기(UAV) 유도 시스템^[10][11]
• 대중교통 노선도 배치^[12]

6. 알고리즘

정수 계획법(ILP) 문제를 해결하기 위한 다양한 알고리즘이 개발되었다.

정수 계획법 문제를 푸는 간단한 방법은 정수 제약을 제거하고 선형 계획법(LP) 완화를 푼 다음, 그 해를 반올림하는 것이다. 그러나 이 방법은 최적해가 아니거나 실행 불가능할 수 있다.

절단 평면법은 선형 계획법 완화를 풀고 정수 해를 제외하지 않으면서 해를 정수로 만드는 선형 제약 조건을 추가한다. 분기 한정법과 절단 평면법을 결합한 분기 절단법도 사용된다.

NP-난해 문제의 특성상, 큰 문제에서는 최적해를 찾는 것이 현실적으로 어려울 수 있다. 타부 탐색^[24], 시뮬레이티드 어닐링, 유전 알고리즘 등 다양한 휴리스틱 기법을 사용하여 근사해를 찾는다. 하지만 이러한 방법은 해를 찾지 못할 경우 실행 가능한 해가 없는 것인지, 아니면 단순히 알고리즘이 해를 찾지 못한 것인지 판단하기 어렵고, 구한 해가 최적해에 얼마나 가까운지 정량화하기 어렵다는 단점이 있다.

6. 1. 전체 단일 모듈성 (Total Unimodularity) 활용

6. 2. 정확한 알고리즘 (Exact Algorithms)

6. 3. 변수 수가 적은 경우의 정확한 알고리즘

이러한 알고리즘은 일부 변수는 정수이고 일부 변수는 실수인 혼합 정수 선형 계획법(MILP)에도 사용할 수 있다.^[23]

6. 4. 휴리스틱 방법 (Heuristic Methods)

7. 희소 정수 계획법 (Sparse Integer Programming)

정수 계획법에서 행렬 $A$는 희소 행렬인 경우가 많다. 이는 특히 행렬이 여러 응용 분야에서 나타나는 블록 구조를 가질 때 발생한다. 행렬의 희소성은 다음과 같이 측정할 수 있다. $A$의 ''그래프''는 $A$의 열에 해당하는 꼭짓점을 가지며, 두 열이 모두 0이 아닌 항목을 가진 행을 $A$에서 공유하면 두 열은 가장자리를 형성한다. 이는 꼭짓점이 변수에 해당하고, 두 변수가 부등식을 공유하는 경우 가장자리를 형성하는 것과 같다. $A$의 ''희소성 측정'' $d$는 $A$ 그래프와 $A$의 전치 그래프의 트리-깊이 중 작은 값이다. $A$의 ''수치적 측정'' $a$는 $A$의 모든 항목의 절댓값 중 가장 큰 값으로 정의된다. 정수 계획법의 변수 개수를 $n$이라고 할 때, 2018년에 $a$와 $d$를 매개변수로 하는 강력하게 다항 시간 및 고정 매개변수 추적 가능 시간 안에 정수 계획법을 해결할 수 있다는 것이 밝혀졌다.^[25] 즉, 계산 가능한 함수 $f$와 상수 $k$에 대해 정수 계획법은 $f(a,d)n^k$ 시간에 해결될 수 있다. 특히, 이 시간은 우변 $b$ 및 목적 함수 $c$와는 독립적이다. 또한, 변수 개수 $n$이 매개변수인 렌스트라(Lenstra)의 고전적인 결과와는 달리, 이 경우 변수 개수 $n$은 입력의 가변적인 부분이다.

8. 정수 계획법으로 해결되는 문제의 예 (일본어 문서)

다음은 정수 계획법으로 해결할 수 있는 문제들이다.

• 최대 정점 덮개 문제
• 배낭 문제
• 해밀턴 회로 문제
• 외판원 문제
• 집합 커버 문제
• 시설 배치 문제
• 최대 독립 집합 문제
• 최소 극대 매칭 문제
• 최대 클릭 문제
• 지배 집합 문제
• 변 지배 집합 문제
• 빈 포장 문제
• 일반화 할당 문제

9. 참고 도서 (일본어 문서)

• 곤노 히로시, 《정수 계획법》, 산교도쇼, 1981.
• 곤노 히로시, 스즈키 히사토시 편저, 《정수 계획과 조합 최적화》, 닛카기렌, 1982.
• 쿠보 미키오, 타무라 아키히사, 마츠이 토모키 편, 《응용 수리 계획 핸드북》, 아사쿠라 서점, 2002.

참조

_[1] 서적 Complexity of Computer Computations New York: Plenum
_[2] 웹사이트 Mixed-Integer Linear Programming (MILP): Model Formulation http://macc.mcmaster[...] 2018-04-16
_[3] 서적 Combinatorial optimization: algorithms and complexity Dover
_[4] 웹사이트 Integer Programming Reduction https://courses.engr[...]
_[5] 서적 Logic and integer programming
_[6] 웹사이트 Designing telecommunication networks by integer programming http://www.zib.de/gr[...]
_[7] 웹사이트 Frequency Planning http://www.slideshar[...]
_[8] 간행물 Optimal scheduling of a renewable micro-grid in an isolated load area using mixed-integer linear programming http://www.sciencedi[...] 2010-01-01
_[9] 간행물 Distributed energy resource system optimisation using mixed integer linear programming http://www.sciencedi[...] 2013-10-01
_[10] 서적 2005 IEEE Aerospace Conference 2005
_[11] 간행물 Flight formation of UAVs in presence of moving obstacles using fast-dynamic mixed integer linear programming 2016-03-01
_[12] arXiv Efficient Generation of Geographically Accurate Transit Maps 2017-10-05
_[13] 간행물 Production Sets with Indivisibilities, Part I: Generalities https://www.jstor.or[...] 1981
_[14] 간행물 Integer Programming with a Fixed Number of Variables https://pubsonline.i[...] 1983-11-01
_[15] conference Proceedings of the AMS Special Session on Algebraic and Geometric Methods in Applied Discrete Mathematics held in San Antonio, TX, January 11, 2015 American Mathematical Society
_[16] 간행물 Minkowski's Convex Body Theorem and Integer Programming https://pubsonline.i[...] 1987-08-01
_[17] 간행물 Polynomiality for Bin Packing with a Constant Number of Item Types 2020-11-07
_[18] 간행물 An application of simultaneous diophantine approximation in combinatorial optimization https://doi.org/10.1[...] 1987-03-01
_[19] 간행물 Complexity of efficient and envy-free resource allocation: few agents, resources, or utility levels https://dl.acm.org/d[...] AAAI Press 2016-07-09
_[20] 서적 Proceedings of the 2019 ACM Conference on Economics and Computation Association for Computing Machinery 2019-06-17
_[21] 문서 Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation https://homepages.cw[...] 2012-06-14
_[22] 문서 The Subspace Flatness Conjecture and Faster Integer Programming https://arxiv.org/ab[...] 2023-03-26
_[23] 웹사이트 FPT algorithm for mixed integer program https://cstheory.sta[...] 2024-05-21
_[24] 간행물 Tabu search-Part II
_[25] conference 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9–13, 2018, Prague, Czech Republic Schloss Dagstuhl – Leibniz-Zentrum für Informatik