Integer programming — 정수 계획법

From Systems analysis Wiki
Jump to navigation Jump to search

정수 계획법 (정계법; 영어 integer programming, IP) — 수리 최적화의 한 분야로, 일부 또는 모든 변수가 정수값만 취해야 하는 문제를 다룬다[1].

가장 널리 연구된 특수한 경우는 정수 선형 계획법 (정선계법; 영어 integer linear programming, ILP)으로, 목적 함수와 제약 조건이 모두 선형인 경우이다. 변수가 임의의 실수값을 취할 수 있는 선형 계획법과 달리, 정수 조건의 요구는 정수 계획법 문제를 훨씬 더 풀기 어렵게 만든다[2].

정수 계획법은 변수가 본질적으로 이산적인 경제학, 물류, 생산 계획 및 기타 분야에서 폭넓게 활용된다(예: 생산 단위 수량 또는 근로자 수)[3].

정의 및 용어

정수 선형 계획법의 일반적인 문제는 다음과 같이 기술할 수 있다:

벡터 x를 구하여:

cTx를 최대화(또는 최소화)한다

다음 조건하에:

Ax≤b
x≥0
x∈ℤn (벡터 x의 모든 성분은 정수)

여기서 x은 변수 벡터, c과 b는 벡터, A은 계수 행렬이다[4].

변수에 대한 요구 조건에 따라 다음과 같은 문제 유형으로 구분한다:

  • 순수 정수 계획법: 모든 변수가 정수여야 한다.
  • 혼합 정수 계획법 (영어 mixed-integer programming, MIP): 일부 변수만 정수여야 한다.
  • 이진(0-1) 계획법: 변수가 0 또는 1의 값만 취하며, 이를 통해 "예/아니오" 유형의 논리적 결정을 모델링할 수 있다.

주요 특성 및 복잡도

계산 복잡도

정수 선형 계획법 문제는 일반적인 경우 NP-난해이다[5]. 이는 임의의 정수 계획법 문제에 대해 다항 시간 내에 정확한 최적해를 구할 수 있는 알려진 알고리즘이 존재하지 않음을 의미한다. 이 복잡도는 문제의 조합론적 특성에서 비롯되며, 가능한 정수해의 수는 변수의 수가 증가함에 따라 지수적으로 증가할 수 있다.

선형 계획법과의 관계 (LP 완화)

임의의 정수 계획법 문제에 대해 선형 완화 — 변수의 정수 조건을 제거한 선형 계획법(LP) 문제 — 를 수립할 수 있다. LP 완화의 해는 두 가지 중요한 특성을 가진다:

  1. 훨씬 빠르게(다항 시간 내에) 구할 수 있다.
  2. LP 완화의 최적 목적 함수값은 원래 정수 계획법 문제의 최적값에 대한 추정값(최대화 문제의 경우 상한, 최소화 문제의 경우 하한)을 제공한다[2].

그러나 LP 완화의 분수 해를 단순히 가장 가까운 정수로 반올림하는 것은 일반적으로 정수 계획법 문제의 최적해 또는 실행 가능한 해로 이어지지 않는다[1].

완전 단모듈성 특성

LP 완화와 마찬가지로 쉽게 풀 수 있는 중요한 정수 선형 계획법 문제의 부류가 존재한다. 이는 제약 행렬 A이 완전 단모듈(totally unimodular)인 문제로(즉, 임의의 정방 부분행렬의 행렬식이 0, +1, 또는 −1인 경우), 행렬 A가 완전 단모듈이고 벡터 b가 정수이면 LP 완화의 실행 가능 영역의 모든 꼭짓점은 자동으로 정수가 된다. 따라서 단체법으로 구한 해는 정수해가 된다[4]. 이러한 문제의 예로는 수송 문제와 할당 문제가 있다.

풀이 방법

완전 단모듈성을 갖지 않는 일반적인 정수 계획법 문제를 풀기 위해, 암묵적 열거의 아이디어에 기반한 정확한 방법들이 개발되었다.

  • 분기 한정법 (영어 Branch and Bound) — 실행 가능 해의 집합을 부분 집합으로 체계적으로 분할(분기)하고, 최적해를 포함하지 않음이 명백한 부분 집합을 제거하는 기본 정확 방법이다. 부분 집합의 유망성을 평가하기 위해 LP 완화가 사용된다[6].
  • 절단면법 (고모리법; 영어 Cutting Plane Method) — 문제에 새로운 선형 제약 조건("절단면")을 순차적으로 추가하는 반복적 접근법이다. 이 절단면들은 LP 완화의 분수 해를 "잘라내면서" 실행 가능한 정수해는 하나도 제거하지 않으며, LP 완화의 실행 가능 영역을 점진적으로 정수해의 볼록 껍질에 근접시킨다[6].

현대적인 솔버는 일반적으로 두 접근법의 장점을 결합한 분기 절단법 (영어 Branch and Cut)과 같은 하이브리드 알고리즘을 사용한다.

예시 및 응용 분야

정수 계획법은 조합 최적화의 다양한 고전적 문제를 모델링할 수 있다.

  • 배낭 문제: 전체 무게 제한을 초과하지 않으면서 최대 총 가치를 가지는 물건의 집합을 선택해야 하는 고전적인 0-1 계획법 문제이다.
  • 순회 판매원 문제: 주어진 도시 집합을 모두 거치는 최단 경로를 찾는 문제이다. 변수가 최종 경로에 그래프의 간선 포함 여부를 나타내는 정수 계획법 문제로 수립할 수 있다.

그 유연성 덕분에 정수 계획법은 운용 과학에서 가장 널리 활용되는 도구 중 하나이며, 다음과 같은 분야에서 응용된다:

  • 물류 및 공급망 관리: 운송 경로 최적화, 창고 배치, 재고 관리.
  • 생산 계획: 생산 일정 수립, 자원 배분, 설비 가동률 관리.
  • 금융 및 경제학: 투자 포트폴리오 구성, 자본 지출 예산 책정.
  • 통신 및 에너지: 통신망 설계, 발전 설비 운용 계획.

같이 보기

  • 선형 계획법
  • 분기 한정법

주석

[1] [2] [3] [4] [5] [6] </references>

  1. ↑ 1.0 1.1 1.2 "Целочисленное программирование". Википедия. [1]
  2. ↑ 2.0 2.1 2.2 Wolsey, Laurence A. (2020). Integer Programming (2nd ed.). John Wiley & Sons.
  3. ↑ 3.0 3.1 Писарук Н.Н. (2010). Модели и методы смешанного целочисленного программирования. Минск: БГУ.
  4. ↑ 4.0 4.1 4.2 Conforti, M., Cornuéjols, G., & Zambelli, G. (2014). Integer Programming. Springer.
  5. ↑ 5.0 5.1 Karp, Richard M. (1972). "Reducibility among Combinatorial Problems". In: Complexity of Computer Computations. Springer.
  6. ↑ 6.0 6.1 6.2 "Integer programming". Wikipedia. [2]
Retrieved from "https://systems-analysis.info/int/index.php?title=Integer_programming_—_정수_계획법&oldid=3269"