방법
정수 선형 계획법 (Integer Linear Programming)
절단·적재 문제를 정수 변수의 선형 모델로 정식화하는 방법.
다른 이름: Integer Linear Programming · ILP · MILP · Mixed-Integer Linear Programming · 정수계획법
절단·적재의 정확 해법이 출발하는 모델링 계층(v1에서는 method로 분류). 배치·선택·
패턴 결정을 정수 변수와 선형 제약으로 적으면(위치 지정·패턴 정식화), 분기 한정이나
열 생성 기반 분기-가격으로 최적해를 구할 수 있다. 2차원
절단·적재의 ILP 모델과 정확 해법은 Lodi, Martello & Monaci(2002)의 서베이에 정리되어
있다.
주장 & 증거
모든 관계는 증거 등급을 가진 하나의 주장이고, 문제 간 관계에는 해당되는 경우 등가 수준도 표시합니다. 증거 정책을 참고하세요.
| 관계 | 주장 | 등가 | 증거 | 출처 |
|---|---|---|---|---|
| 방법 공유분기 한정 (Branch and Bound) | 정수 선형 계획 모델은 분기 한정으로 정확히 풀린다 — ILP는 문제를 기술하는 모델이고, 분기 한정은 그 모델을 푸는 해법이다. | E2 | A |
|
| 오픈소스 구현Google OR-Tools | Google OR-Tools는 정수 선형 계획을 푸는 MIP·CP-SAT 솔버를 오픈소스로 제공한다. | — | C |