정수 선형 계획법 (Integer Linear Programming)

절단·적재 문제를 정수 변수의 선형 모델로 정식화하는 방법.

다른 이름: Integer Linear Programming · ILP · MILP · Mixed-Integer Linear Programming · 정수계획법

절단·적재의 정확 해법이 출발하는 모델링 계층(v1에서는 method로 분류). 배치·선택· 패턴 결정을 정수 변수와 선형 제약으로 적으면(위치 지정·패턴 정식화), 분기 한정이나 열 생성 기반 분기-가격으로 최적해를 구할 수 있다. 2차원 절단·적재의 ILP 모델과 정확 해법은 Lodi, Martello & Monaci(2002)의 서베이에 정리되어 있다.

주장 & 증거

모든 관계는 증거 등급을 가진 하나의 주장이고, 문제 간 관계에는 해당되는 경우 등가 수준도 표시합니다. 증거 정책을 참고하세요.

A–X는 근거의 신뢰도, E0–E4는 문제 사이의 수학적 유사도입니다. 두 축은 서로 독립적입니다.

이 항목에서 나가는 관계 2

방법 공유
정수 선형 계획법 (Integer Linear Programming)에서 분기 한정 (Branch and Bound)로
정수 선형 계획 모델은 분기 한정으로 정확히 풀린다 — ILP는 문제를 기술하는 모델이고, 분기 한정은 그 모델을 푸는 해법이다.
증거A · 동료심사 논문 / 공식 문서
등가E2 · 방법론 공유
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
  서지정보
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
오픈소스 구현
정수 선형 계획법 (Integer Linear Programming)에서 Google OR-Tools로
Google OR-Tools는 정수 선형 계획을 푸는 MIP·CP-SAT 솔버를 오픈소스로 제공한다.
증거C · 벤더 / 사례 보고
출처
- 출처 등급: C — 벤더 / 사례 보고Google OR-Tools (새 탭에서 열림)

이 항목에서 나가는 관계
관계	주장	증거	등가	출처
방법 공유 정수 선형 계획법 (Integer Linear Programming)에서 분기 한정 (Branch and Bound)로	정수 선형 계획 모델은 분기 한정으로 정확히 풀린다 — ILP는 문제를 기술하는 모델이고, 분기 한정은 그 모델을 푸는 해법이다.	A · 동료심사 논문 / 공식 문서	E2 · 방법론 공유	출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey 서지정보 Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
오픈소스 구현 정수 선형 계획법 (Integer Linear Programming)에서 Google OR-Tools로	Google OR-Tools는 정수 선형 계획을 푸는 MIP·CP-SAT 솔버를 오픈소스로 제공한다.	C · 벤더 / 사례 보고	—	출처 등급: C — 벤더 / 사례 보고Google OR-Tools (새 탭에서 열림)

이 항목으로 들어오는 관계 4

사용 방법
1D 절단 재고에서 정수 선형 계획법 (Integer Linear Programming)로
1D 절단 재고는 패턴(절단 방식) 변수를 갖는 정수 선형 계획으로 정식화된다 — Gilmore–Gomory의 패턴 정식화가 그 기반이다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서A Linear Programming Approach to the Cutting-Stock Problem
  서지정보
  Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
사용 방법
2D 빈 패킹에서 정수 선형 계획법 (Integer Linear Programming)로
2D 빈 패킹은 정수 선형 계획(ILP) 모델로 정식화되며, 이는 분기 한정·분기-가격 같은 정확 해법의 출발점이다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
  서지정보
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법
2D 스트립 패킹에서 정수 선형 계획법 (Integer Linear Programming)로
2D 스트립 패킹은 정수 선형 계획 모델로 정식화되어 정확 해법의 기반이 된다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
  서지정보
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법
0/1 배낭 문제에서 정수 선형 계획법 (Integer Linear Programming)로
0/1 배낭 문제는 이진 변수와 단일 용량 제약을 갖는 0/1 정수 선형 계획으로 직접 정식화된다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Knapsack Problems
  서지정보
  Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.

이 항목으로 들어오는 관계
관계	주장	증거	등가	출처
사용 방법 1D 절단 재고에서 정수 선형 계획법 (Integer Linear Programming)로	1D 절단 재고는 패턴(절단 방식) 변수를 갖는 정수 선형 계획으로 정식화된다 — Gilmore–Gomory의 패턴 정식화가 그 기반이다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서A Linear Programming Approach to the Cutting-Stock Problem 서지정보 Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
사용 방법 2D 빈 패킹에서 정수 선형 계획법 (Integer Linear Programming)로	2D 빈 패킹은 정수 선형 계획(ILP) 모델로 정식화되며, 이는 분기 한정·분기-가격 같은 정확 해법의 출발점이다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey 서지정보 Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법 2D 스트립 패킹에서 정수 선형 계획법 (Integer Linear Programming)로	2D 스트립 패킹은 정수 선형 계획 모델로 정식화되어 정확 해법의 기반이 된다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey 서지정보 Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법 0/1 배낭 문제에서 정수 선형 계획법 (Integer Linear Programming)로	0/1 배낭 문제는 이진 변수와 단일 용량 제약을 갖는 0/1 정수 선형 계획으로 직접 정식화된다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서Knapsack Problems 서지정보 Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.