Packing & Cutting

Resource Allocation Under Capacity Constraints

Three foundational combinatorial optimization problems addressing how to best allocate items to limited-capacity containers. From the classical knapsack problem to industrial cutting stock optimization, this family covers exact dynamic programming, branch-and-bound methods, approximation algorithms with provable guarantees, and genetic algorithm metaheuristics.

Problems

389

Tests

Algorithms

Python Files

View Source Back to Portfolio

Quick Navigation

Knapsack Bin Packing Cutting Stock Variants Hierarchy Complexity References

0-1 Knapsack Problem

KP01 | max Σ v_ix_i s.t. Σ w_ix_i ≤ W, x_i ∈ {0,1}

NP-Hard (weakly) 37 Tests 5 Python Files 8 Test Classes

Capital Budgeting Resource Allocation Portfolio Selection Cargo Loading Ad-Budget Allocation

Given n items, each with a weight w_i and value v_i, and a knapsack with capacity W, select a subset of items to maximize total value without exceeding the weight limit. The binary constraint x_i ∈ {0,1} means each item is either fully included or excluded. Weakly NP-hard: it admits a pseudo-polynomial time DP algorithm in O(nW) but no known polynomial-time exact method.

maximize Σ i=1..n v i \cdot x i subject to Σ i=1..n w i \cdot x i \leq W // capacity constraint x i \in {0, 1} \forall i = 1, ..., n // binary selection // LP relaxation upper bound (Dantzig, 1957): // Sort items by v i /w i descending. Let S = set of fully packed items, // k = index of the first item that does not fit (the "break item"). UB = Σ i\inS v i + (W - Σ i\inS w i) \cdot (v k / w k)

Algorithms

Algorithm	Type	Complexity	Guarantee	Description
Dynamic Programming	Exact	O(n · W)	Optimal	Bellman (1957). Bottom-up tabulation. Pseudo-polynomial; practical for moderate W.
Branch & Bound	Exact	O(2ⁿ) worst-case	Optimal	Kolesar (1967). LP relaxation upper bound, greedy warm-start. Often much faster due to pruning.
FPTAS	Approx. Scheme	O(n / ε · min(n, 1/ε))	(1−ε)-approx	Ibarra & Kim (1975); Lawler (1979). Scales and rounds profits for (1−ε) guarantee in polynomial time. The canonical FPTAS result.
Greedy Value-Density	Heuristic	O(n log n)	—	Dantzig (1957). Sort items by v_i/w_i descending, pack greedily. No constant-factor guarantee alone.
Greedy Combined	Heuristic	O(n log n)	1/2-approx	Sahni (1975). Best of density-greedy solution and the single most valuable feasible item. Guarantees ≥ OPT/2.
Genetic Algorithm	Metaheuristic	O(G · P · n)	—	Binary encoding, uniform crossover, repair operator for infeasible solutions. Population-based search.

Benchmark Instances

small4

4 items
Optimal: 35
Small verification instance

medium8

8 items
Optimal: 300
Medium-scale validation

strongly_correlated_10

10 items, v_i = w_i + 10
Hardest for greedy methods
Tests algorithm robustness

Try It Yourself

Instance Parameters

Items: 8

Capacity: 60

Select Algorithms

DP (Exact)

B&B (Exact)

Greedy Density (H)

Greedy Max-Value (H)

Combined Greedy (H)

Visualization

Generate an instance and click Solve to begin.

Results

Algorithm	Value	Weight	Items	Time
No results yet

Interested in Knapsack Optimization?

Explore the full implementation with DP, Branch & Bound, greedy heuristics, and genetic algorithms — all with comprehensive test suites.

Contact LinkedIn Source Code

1D Bin Packing

BPP1D | min # bins s.t. Σ_{i∈B_j} s_i ≤ C ∀ j

NP-Hard (strongly) 29 Tests 3 Python Files 7 Test Classes

Container Loading Memory Allocation VM Provisioning Truck Loading Cloud VM Placement

Given n items with sizes s_i and identical bins of capacity C, pack all items into the minimum number of bins. Unlike knapsack, there is no selection: all items must be packed, and the objective is to minimize container usage. Strongly NP-hard, meaning no pseudo-polynomial algorithm exists unless P = NP. The problem admits excellent approximation algorithms, notably FFD with its (11/9)OPT + 6/9 guarantee.

// j = 1..n candidate bins (at most one item per bin gives trivial upper bound n) minimize Σ j=1..n y j // number of bins used subject to Σ i=1..n s i \cdot x ij \leq C \cdot y j \forall j // bin capacity Σ j=1..n x ij = 1 \forall i // each item packed once x ij, y j \in {0, 1} // binary assignment // Lower bounds: L1 = ⌈ Σ s i / C ⌉ // continuous relaxation L2 \geq L1 // Martello & Toth (1990) bound via item-pair matching

Algorithms

Algorithm	Type	Complexity	Guarantee	Description
Next Fit (NF)	Heuristic	O(n)	2 OPT	Johnson (1973). Online. Keep one open bin; if item doesn’t fit, close it and open a new one. Simplest online algorithm.
First Fit (FF)	Heuristic	O(n²) naive; O(n log n)	17/10 OPT + 7/10	Johnson (1973); Dósa & Sgall (2013). Online. Place each item in the first bin with sufficient capacity.
First Fit Decreasing (FFD)	Heuristic	O(n log n)	11/9 OPT + 6/9	Johnson (1973); Dósa (2007). Offline. Sort items descending, then apply FF. Classic offline heuristic baseline.
Best Fit Decreasing (BFD)	Heuristic	O(n log n)	11/9 OPT (asymptotic)	Johnson (1973). Offline. Sort descending, place in bin with tightest remaining capacity. Same asymptotic ratio as FFD.
Genetic Algorithm	Metaheuristic	O(G · P · n)	—	Falkenauer (1996). Permutation encoding with FF decoder. Evolves item orderings.

Benchmark Instances

easy6

6 items
Easy instance for validation
FF typically optimal

tight8

8 items
Tight capacity constraints
Tests packing efficiency

uniform10

10 items
Uniformly distributed sizes
Benchmark for scaling

Try It Yourself

Instance Parameters

Items: 8

Bin Capacity: 60

Select Algorithms

First Fit (H)

FFD (H)

BFD (H)

Visualization

Generate an instance and click Solve to begin.

Results

Algorithm	Bins Used	Lower Bound	Time

Need Custom Bin Packing Solutions?

From container loading to cloud VM provisioning — let’s discuss your optimization challenge.

Contact LinkedIn

1D Cutting Stock

CSP1D | min # rolls s.t. demand d_i satisfied ∀ i

NP-Hard 21 Tests 2 Python Files 6 Test Classes

Paper Industry Steel Cutting Textile Manufacturing Glass Cutting Cable Production

Given stock material of length L and m item types with lengths l_i and demands d_i, cut stock rolls to satisfy all demands using the minimum number of rolls. This generalizes Bin Packing: identical items are interchangeable, enabling cutting patterns where multiple copies of the same item type are cut from a single roll. The classical column generation approach (Gilmore-Gomory, 1961) solves the LP relaxation by generating patterns on-the-fly.

minimize Σ p=1..P y p // number of rolls used subject to Σ p=1..P a ip \cdot y p \geq d i \forall i // demand satisfaction y p \in ℤ \geq0 // integer roll count (0 = unused pattern) // a ip = number of type-i items cut in pattern p (given parameter) // Each pattern p must satisfy: Σ i l i \cdot a ip \leq L (knapsack subproblem) // P is exponential — solved via column generation (Gilmore-Gomory, 1961) // Reduces to Bin Packing when all d i = 1

Algorithms

Algorithm	Type	Complexity	Guarantee	Description
Gilmore-Gomory CG	Exact (LP)	Polynomial per iter	LP_OPT ≤ OPT	Gilmore & Gomory (1961). Column generation: solve LP master, generate patterns via knapsack pricing subproblem. LP solution typically within 1 of integer optimum (IRUP).
Greedy Largest-First	Heuristic	O(m · D)	—	Fill each roll by repeatedly selecting the largest item with remaining demand. D = Σd_i (total demand).
FFD-Based	Heuristic	O(D log D)	11/9 (inherited)	Expand demands to individual items, apply FFD, aggregate patterns. D = Σd_i. Inherits FFD’s asymptotic guarantee.

Benchmark Instances

simple3

3 item types
Stock length: L = 100
Basic validation instance

classic4

4 item types
Stock length: L = 10
Classic textbook instance

Standard benchmarks: CUTGEN (Gau & Wäscher, 1995) generates CSP instances by difficulty class. For knapsack, see Pisinger (2005) hard instance generator. For bin packing, see BPPLIB (Delorme et al., 2016) and Falkenauer/Schwerin benchmark sets.

Explore the Full Implementation

Greedy heuristics, FFD-based pattern aggregation, and comprehensive test suites for the 1D Cutting Stock Problem.

Source Code

Problem Variants

Extensions of the core packing and cutting problems implemented in this repository

Bounded / Unbounded Knapsack

Bounded: up to b_i copies of each item. Unbounded: unlimited copies. Both solvable by DP variants.

Multidimensional Knapsack

Multiple resource constraints (weight, volume, cost). No FPTAS unless P=NP. Core problem in capital budgeting.

Multiple Knapsack

Assign items to m knapsacks with different capacities. Bridges knapsack and bin packing.

2D Bin Packing

Pack rectangular items into bins with width and height. Adds rotation and orientation decisions.

Variable-Size Bin Packing

Bins with different capacities and costs. Minimise total cost instead of bin count.

2D Guillotine Cutting

Cut rectangular pieces from sheets using edge-to-edge (guillotine) cuts only. Core in glass and metal industries.

Problem Hierarchy

Complexity relationships between packing and cutting problems

Generalization Chain

0-1 Knapsack
Single container

Bin Packing
Multiple uniform bins, all items

Cutting Stock
Multiple rolls, item demands

Each problem generalizes the previous. Cutting Stock reduces to Bin Packing when all demands equal 1. Bin Packing extends the single-container selection problem to packing all items into the minimum number of bins.

Complexity Landscape

Why these three problems behave so differently

Weak vs Strong NP-Hardness

● 0-1 Knapsack is weakly NP-hard. It admits pseudo-polynomial DP in O(nW) and an FPTAS — for any ε > 0 you can get within (1−ε) of optimal in time polynomial in n and 1/ε.

● Bin Packing is strongly NP-hard. No pseudo-polynomial algorithm exists (unless P=NP). Best possible: asymptotic approximation schemes (APTAS). The 11/9 FFD bound is the practical workhorse.

● Cutting Stock is also strongly NP-hard, but the LP relaxation via column generation is remarkably tight — typically within 1 roll of optimal (the IRUP conjecture).

When to Use What

Knapsack: DP for moderate W; B&B for large sparse instances; FPTAS when provable near-optimality is needed; Greedy Combined for fast 1/2-approx.

Bin Packing: FFD as the go-to offline baseline; NF for streaming/online; branch-and-price for exact solutions on medium instances.

Cutting Stock: Gilmore-Gomory column generation for serious instances; greedy/FFD heuristics for quick estimates; branch-and-price for proven optima.

References

Knapsack

Bellman, R. (1957). Dynamic Programming. Princeton University Press.

Dantzig, G. (1957). Discrete-variable extremum problems. Operations Research, 5(2).

Sahni, S. (1975). Approximate algorithms for the 0/1 knapsack problem. JACM, 22(1).

Ibarra, O. & Kim, C. (1975). Fast approximation algorithms for the knapsack and sum of subset problems. JACM, 22(4).

Kolesar, P. (1967). A branch and bound algorithm for the knapsack problem. Management Science, 13(9).

Kellerer, H., Pferschy, U. & Pisinger, D. (2004). Knapsack Problems. Springer.

Pisinger, D. (2005). Where are the hard knapsack problems? Computers & OR, 32(9).

Bin Packing

Johnson, D. (1973). Near-Optimal Bin Packing Algorithms. Ph.D. thesis, MIT.

Dósa, G. (2007). The tight bound of FFD. ISCO 2007.

Dósa, G. & Sgall, J. (2013). First Fit bin packing: a tight analysis. STACS 2013.

Martello, S. & Toth, P. (1990). Lower bounds and reduction procedures for the bin packing problem. Discrete Applied Math, 28(1).

Falkenauer, E. (1996). A hybrid grouping genetic algorithm for bin packing. JORS, 47(11).

Cutting Stock

Gilmore, P. & Gomory, R. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6).

Gilmore, P. & Gomory, R. (1963). A linear programming approach to the cutting stock problem — Part II. Operations Research, 11(6).

Wäscher, G., Haußner, H. & Schumann, H. (2007). An improved typology of cutting and packing problems. European J. OR, 183(3).

Portfolio