Integer Linear Programming

Formulating cutting & packing as a linear model over integer variables.

Also called: Integer Linear Programming · ILP · MILP · Mixed-Integer Linear Programming · 정수계획법

The modeling layer from which exact cutting & packing methods depart (classified as a method in v1). Writing placement, selection, and pattern decisions as integer variables with linear constraints (positional and pattern formulations) lets branch-and-bound or column-generation-based branch-and-price find optimal solutions. ILP models and exact methods for two-dimensional cutting & packing are surveyed by Lodi, Martello & Monaci (2002).

Claims & evidence

Every relationship is a claim with an evidence grade; applicable problem-to-problem relationships also carry an equivalence level. See the evidence policy.

A–X describes evidence reliability; E0–E4 describes mathematical similarity between problems. The two axes are independent.

Relationships from this entry 2

shares method with
Integer Linear Programming to Branch and Bound
Integer linear programs are solved exactly by branch-and-bound — ILP is the model that states the problem, branch-and-bound the method that solves it.
EvidenceA · Peer-reviewed / official
Equiv.E2 · shared methodology
Sources
- Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey
  Citation details
  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.
open-source implementation
Integer Linear Programming to Google OR-Tools
Google OR-Tools provides open-source MIP and CP-SAT solvers for integer linear programs.
EvidenceC · Vendor / case-reported
Sources
- Source grade: C — Vendor / case-reportedGoogle OR-Tools (Opens in a new tab)

Relationships from this entry
Relationship	Claim	Evidence	Equiv.	Sources
shares method with Integer Linear Programming to Branch and Bound	Integer linear programs are solved exactly by branch-and-bound — ILP is the model that states the problem, branch-and-bound the method that solves it.	A · Peer-reviewed / official	E2 · shared methodology	Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey Citation details 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.
open-source implementation Integer Linear Programming to Google OR-Tools	Google OR-Tools provides open-source MIP and CP-SAT solvers for integer linear programs.	C · Vendor / case-reported	—	Source grade: C — Vendor / case-reportedGoogle OR-Tools (Opens in a new tab)

Relationships to this entry 4

uses method
1D Cutting Stock to Integer Linear Programming
1D cutting stock is formulated as an integer linear program over pattern (cutting-pattern) variables — the Gilmore-Gomory pattern formulation is its basis.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialA Linear Programming Approach to the Cutting-Stock Problem
  Citation details
  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.
uses method
2D Bin Packing to Integer Linear Programming
2D bin packing is formulated as an integer linear program (ILP), the starting point for exact methods such as branch-and-bound and branch-and-price.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey
  Citation details
  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.
uses method
2D Strip Packing to Integer Linear Programming
2D strip packing is formulated as an integer linear program, the basis for exact methods.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey
  Citation details
  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.
uses method
0/1 Knapsack Problem to Integer Linear Programming
The 0/1 knapsack problem is directly formulated as a 0/1 integer linear program with binary variables and a single capacity constraint.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialKnapsack Problems
  Citation details
  Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.

Relationships to this entry
Relationship	Claim	Evidence	Equiv.	Sources
uses method 1D Cutting Stock to Integer Linear Programming	1D cutting stock is formulated as an integer linear program over pattern (cutting-pattern) variables — the Gilmore-Gomory pattern formulation is its basis.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialA Linear Programming Approach to the Cutting-Stock Problem Citation details 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.
uses method 2D Bin Packing to Integer Linear Programming	2D bin packing is formulated as an integer linear program (ILP), the starting point for exact methods such as branch-and-bound and branch-and-price.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey Citation details 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.
uses method 2D Strip Packing to Integer Linear Programming	2D strip packing is formulated as an integer linear program, the basis for exact methods.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey Citation details 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.
uses method 0/1 Knapsack Problem to Integer Linear Programming	The 0/1 knapsack problem is directly formulated as a 0/1 integer linear program with binary variables and a single capacity constraint.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialKnapsack Problems Citation details Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.