---
title: "Integer programming — 정수 계획법"
source: "https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95"
wiki: "systems-analysis.info/int"
article: "Integer_programming_—_정수_계획법"
language: "ko"
categories:
- "Category:Korean"
- "Category:Operations research"
revision_id: 3269
wiki_created_at: 2026-09-06T23:18:11Z
wiki_modified_at: 2026-09-06T23:18:11Z
downloaded_at: 2026-09-07T22:56:03Z
---
# Integer programming — 정수 계획법
**정수 계획법** (**정계법**; 영어 *integer programming, IP*) — 수리 최적화의 한 분야로, 일부 또는 모든 변수가 정수값만 취해야 하는 문제를 다룬다[\[1\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-ru-wiki-ip-1).
가장 널리 연구된 특수한 경우는 **정수 선형 계획법** (**정선계법**; 영어 *integer linear programming, ILP*)으로, 목적 함수와 제약 조건이 모두 선형인 경우이다. 변수가 임의의 실수값을 취할 수 있는 선형 계획법과 달리, 정수 조건의 요구는 정수 계획법 문제를 훨씬 더 풀기 어렵게 만든다[\[2\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-wolsey-book-2).
정수 계획법은 변수가 본질적으로 이산적인 경제학, 물류, 생산 계획 및 기타 분야에서 폭넓게 활용된다(예: 생산 단위 수량 또는 근로자 수)[\[3\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-pisaruk-book-3).
## 정의 및 용어
정수 선형 계획법의 일반적인 문제는 다음과 같이 기술할 수 있다:
벡터 $x$를 구하여:
$c^{T}x$를 최대화(또는 최소화)한다
다음 조건하에:
$Ax \leq b$
$x \geq 0$
$x \in {\mathbb{Z}}^{n}$ (벡터 $x$의 모든 성분은 정수)
여기서 $x$은 변수 벡터, $c$과 $b$는 벡터, $A$은 계수 행렬이다[\[4\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-conforti-book-4).
변수에 대한 요구 조건에 따라 다음과 같은 문제 유형으로 구분한다:
- **순수 정수 계획법**: 모든 변수가 정수여야 한다.
- **혼합 정수 계획법** (영어 *mixed-integer programming, MIP*): 일부 변수만 정수여야 한다.
- **이진(0-1) 계획법**: 변수가 0 또는 1의 값만 취하며, 이를 통해 "예/아니오" 유형의 논리적 결정을 모델링할 수 있다.
## 주요 특성 및 복잡도
### 계산 복잡도
정수 선형 계획법 문제는 일반적인 경우 NP-난해이다[\[5\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-karp-1972-5). 이는 임의의 정수 계획법 문제에 대해 다항 시간 내에 정확한 최적해를 구할 수 있는 알려진 알고리즘이 존재하지 않음을 의미한다. 이 복잡도는 문제의 조합론적 특성에서 비롯되며, 가능한 정수해의 수는 변수의 수가 증가함에 따라 지수적으로 증가할 수 있다.
### 선형 계획법과의 관계 (LP 완화)
임의의 정수 계획법 문제에 대해 **선형 완화** — 변수의 정수 조건을 제거한 선형 계획법(LP) 문제 — 를 수립할 수 있다. LP 완화의 해는 두 가지 중요한 특성을 가진다:
1. 훨씬 빠르게(다항 시간 내에) 구할 수 있다.
2. LP 완화의 최적 목적 함수값은 원래 정수 계획법 문제의 최적값에 대한 추정값(최대화 문제의 경우 상한, 최소화 문제의 경우 하한)을 제공한다[\[2\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-wolsey-book-2).
그러나 LP 완화의 분수 해를 단순히 가장 가까운 정수로 반올림하는 것은 일반적으로 정수 계획법 문제의 최적해 또는 실행 가능한 해로 이어지지 않는다[\[1\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-ru-wiki-ip-1).
### 완전 단모듈성 특성
LP 완화와 마찬가지로 쉽게 풀 수 있는 중요한 정수 선형 계획법 문제의 부류가 존재한다. 이는 제약 행렬 $A$이 **완전 단모듈(totally unimodular)**인 문제로(즉, 임의의 정방 부분행렬의 행렬식이 0, +1, 또는 −1인 경우), 행렬 $A$가 완전 단모듈이고 벡터 $b$가 정수이면 LP 완화의 실행 가능 영역의 모든 꼭짓점은 자동으로 정수가 된다. 따라서 단체법으로 구한 해는 정수해가 된다[\[4\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-conforti-book-4). 이러한 문제의 예로는 수송 문제와 할당 문제가 있다.
## 풀이 방법
완전 단모듈성을 갖지 않는 일반적인 정수 계획법 문제를 풀기 위해, 암묵적 열거의 아이디어에 기반한 정확한 방법들이 개발되었다.
- **분기 한정법** (영어 *Branch and Bound*) — 실행 가능 해의 집합을 부분 집합으로 체계적으로 분할(분기)하고, 최적해를 포함하지 않음이 명백한 부분 집합을 제거하는 기본 정확 방법이다. 부분 집합의 유망성을 평가하기 위해 LP 완화가 사용된다[\[6\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-en-wiki-ip-6).
- **절단면법** (고모리법; 영어 *Cutting Plane Method*) — 문제에 새로운 선형 제약 조건("절단면")을 순차적으로 추가하는 반복적 접근법이다. 이 절단면들은 LP 완화의 분수 해를 "잘라내면서" 실행 가능한 정수해는 하나도 제거하지 않으며, LP 완화의 실행 가능 영역을 점진적으로 정수해의 볼록 껍질에 근접시킨다[\[6\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-en-wiki-ip-6).
현대적인 솔버는 일반적으로 두 접근법의 장점을 결합한 **분기 절단법** (영어 *Branch and Cut*)과 같은 하이브리드 알고리즘을 사용한다.
## 예시 및 응용 분야
정수 계획법은 조합 최적화의 다양한 고전적 문제를 모델링할 수 있다.
- *배낭 문제*: 전체 무게 제한을 초과하지 않으면서 최대 총 가치를 가지는 물건의 집합을 선택해야 하는 고전적인 0-1 계획법 문제이다.
- *순회 판매원 문제*: 주어진 도시 집합을 모두 거치는 최단 경로를 찾는 문제이다. 변수가 최종 경로에 그래프의 간선 포함 여부를 나타내는 정수 계획법 문제로 수립할 수 있다.
그 유연성 덕분에 정수 계획법은 운용 과학에서 가장 널리 활용되는 도구 중 하나이며, 다음과 같은 분야에서 응용된다:
- **물류 및 공급망 관리**: 운송 경로 최적화, 창고 배치, 재고 관리.
- **생산 계획**: 생산 일정 수립, 자원 배분, 설비 가동률 관리.
- **금융 및 경제학**: 투자 포트폴리오 구성, 자본 지출 예산 책정.
- **통신 및 에너지**: 통신망 설계, 발전 설비 운용 계획.
## 같이 보기
- 선형 계획법
- 분기 한정법
## 주석
[\[1\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-ru-wiki-ip-1) [\[2\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-wolsey-book-2) [\[3\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-pisaruk-book-3) [\[4\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-conforti-book-4) [\[5\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-karp-1972-5) [\[6\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_note-en-wiki-ip-6) \
1. ↑ [1.0](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-ru-wiki-ip_1-0) [1.1](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-ru-wiki-ip_1-1) [1.2](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-ru-wiki-ip_1-2) "Целочисленное программирование". *Википедия*. [1]
2. ↑ [2.0](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-wolsey-book_2-0) [2.1](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-wolsey-book_2-1) [2.2](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-wolsey-book_2-2) Wolsey, Laurence A. (2020). *Integer Programming* (2nd ed.). John Wiley & Sons.
3. ↑ [3.0](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-pisaruk-book_3-0) [3.1](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-pisaruk-book_3-1) Писарук Н.Н. (2010). *Модели и методы смешанного целочисленного программирования*. Минск: БГУ.
4. ↑ [4.0](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-conforti-book_4-0) [4.1](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-conforti-book_4-1) [4.2](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-conforti-book_4-2) Conforti, M., Cornuéjols, G., & Zambelli, G. (2014). *Integer Programming*. Springer.
5. ↑ [5.0](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-karp-1972_5-0) [5.1](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-karp-1972_5-1) Karp, Richard M. (1972). "Reducibility among Combinatorial Problems". In: *Complexity of Computer Computations*. Springer.
6. ↑ [6.0](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-en-wiki-ip_6-0) [6.1](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-en-wiki-ip_6-1) [6.2](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%EC%A0%95%EC%88%98_%EA%B3%84%ED%9A%8D%EB%B2%95#cite_ref-en-wiki-ip_6-2) "Integer programming". *Wikipedia*. [2]