Multi-Dimensional Knapsack
Real-world resource allocation rarely has just one constraint. This chapter extends the knapsack problem to multiple dimensions.
Why Multi-Dimensional?
In the real world, every resource allocation has multiple constraints:
| Application | Constraint 1 | Constraint 2 | Constraint 3 | |-------------|:------------:|:------------:|:------------:| | Truck loading | Volume (m^3) | Weight (kg) | - | | Cloud server | CPU cores | RAM (GB) | Bandwidth (Gbps) | | Project portfolio | Budget ($) | Engineering hours | Strategic fit score | | Employee schedule | Headcount | Skill requirements | Shift availability |
Single-constraint knapsack cannot model these real-world problems.
What Is Multi-Dimensional Knapsack?
Multi-Dimensional Knapsack (MDKP) extends the classic knapsack by adding multiple resource constraints.
Mathematical formulation:
Maximize: sum(v_i * x_i) for i = 1..n [maximize total value]
Subject to:
sum(w_i1 * x_i) <= W1 [volume constraint]
sum(w_i2 * x_i) <= W2 [weight constraint]
...
sum(w_ik * x_i) <= Wk [k-th dimension constraint]
x_i in {0, 1} [each item pick or not]
How MDKP Differs from Classic Knapsack
| Aspect | Classic Knapsack | Multi-Dimensional | |--------|:----------------:|:-----------------:| | Constraints | 1 (weight) | 2+ (volume, weight, cost...) | | DP solution | O(nW) pseudo-polynomial | O(n x W1 x W2 x ...) - explodes | | Difficulty | NP-hard | Strongly NP-hard | | Real-world fit | Low (single constraint) | High (multiple constraints) |
Implementation with CP-SAT
from ortools.sat.python import cp_model
# Items: each has (volume, weight, value)
items = [
(10, 5, 100), # item 0
(15, 8, 150), # item 1
(8, 3, 80), # item 2
(20, 12, 200), # item 3
(12, 7, 120), # item 4
(6, 4, 60), # item 5
(18, 10, 180), # item 6
(14, 9, 140), # item 7
]
max_volume = 30
max_weight = 15
n = len(items)
model = cp_model.CpModel()
x = [model.NewBoolVar(f"x_{i}") for i in range(n)]
# Volume constraint
model.Add(sum(items[i][0] * x[i] for i in range(n)) <= max_volume)
# Weight constraint
model.Add(sum(items[i][1] * x[i] for i in range(n)) <= max_weight)
# Objective: maximize total value
model.Maximize(sum(items[i][2] * x[i] for i in range(n)))
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 10
status = solver.Solve(model)
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print(f"Optimal value: {int(solver.ObjectiveValue())}")
selected = [i for i in range(n) if solver.Value(x[i])]
print(f"Selected items: {selected}")
total_vol = sum(items[i][0] for i in selected)
total_wt = sum(items[i][1] for i in selected)
print(f"Total volume: {total_vol}/{max_volume}")
print(f"Total weight: {total_wt}/{max_weight}")
else:
print("No feasible solution")
Adding a Third Dimension: Cost
Extending to 3 dimensions is straightforward - just add another constraint:
# Items: (volume, weight, cost, value)
items_3d = [
(10, 5, 100, 100), # volume=10, weight=5, cost=100, value=100
(15, 8, 120, 150), # volume=15, weight=8, cost=120, value=150
(8, 3, 60, 80),
(20, 12, 180, 200),
]
max_vol, max_wt, max_cost = 30, 15, 300
model.Add(sum(items_3d[i][0] * x[i] for i in range(n)) <= max_vol)
model.Add(sum(items_3d[i][1] * x[i] for i in range(n)) <= max_wt)
model.Add(sum(items_3d[i][2] * x[i] for i in range(n)) <= max_cost)
CP-SAT handles any number of dimensions without changing the solver - just add more constraints.
Real-World Applications
1. Truck Loading
Maximize cargo value under both volume (container capacity) and weight (axle weight limits). This is the standard logistics optimization problem.
2. Cloud Resource Allocation
Deploy virtual machines across physical hosts constrained by CPU cores, RAM, and network bandwidth. Maximize the number of VMs deployed.
3. Investment Portfolio
Select stocks under capital (budget), risk (volatility), and liquidity (trading volume) constraints. Maximize expected return.
4. Project Portfolio
Select projects under budget, engineering hours, and strategic alignment constraints. Maximize business value.
Hardness and Practical Approaches
| Constraint Count | Problem Type | Practical Approach | |:----------------:|:------------:|:------------------:| | 1 dimension | Classic knapsack | DP: O(nW) | | 2 dimensions | 2D-KP | CP-SAT or branch-and-bound | | 3 dimensions | 3D-KP | CP-SAT (good for < 100 items) | | 4+ dimensions | High-dimensional KP | Heuristics (greedy, genetic algorithms) |
As dimensions increase, exact solutions become exponentially harder. For 4+ dimensions, heuristic approaches are recommended.
The Vibe Coding Approach
Describe your problem:
"I need to select cloud servers under CPU, RAM, and cost constraints. Each server has different specs and pricing. Use OR-Tools CP-SAT to find the optimal combination."
The AI will generate the complete model with appropriate constraints.
Summary
Multi-Dimensional Knapsack extends classic knapsack to real-world problems with multiple resource constraints. CP-SAT handles 2-3 dimensions well for moderate problem sizes.
Key takeaways:
- MDKP adds multiple resource constraints to classic knapsack
- Strongly NP-hard - no pseudo-polynomial DP solution
- CP-SAT works for 2-3 dimensions with up to ~100 items
- Additional dimensions are just extra constraints in CP-SAT
- Heuristic approaches needed for 4+ dimensions or very large instances
- Real applications: truck loading, cloud allocation, portfolios
What's Next: 2D Cutting & Packing
The next chapter extends MDKP to 2D geometry - placing rectangles on a sheet to minimize waste, with rotation support and NoOverlap2D constraints.
Practical Case Study: Cloud Server Selection
A startup needs to select cloud servers for their deployment. They have 3 resource constraints and 8 server types:
Constraints:
- Budget: $5,000/month
- Total vCPUs needed: at least 16
- Total RAM needed: at least 32 GB
Available server types: | Server | vCPUs | RAM (GB) | Cost ($/month) | Performance Score | |--------|:-----:|:--------:|:---------------:|:-----------------:| | t3.small | 2 | 2 | 20 | 30 | | t3.medium | 2 | 4 | 40 | 50 | | t3.large | 2 | 8 | 70 | 80 | | m5.large | 2 | 8 | 80 | 90 | | m5.xlarge | 4 | 16 | 160 | 170 | | m5.2xlarge | 8 | 32 | 320 | 330 | | c5.xlarge | 4 | 8 | 140 | 160 | | r5.xlarge | 4 | 32 | 200 | 190 |
CP-SAT Model:
servers = [
("t3.small", 2, 2, 20, 30),
("t3.medium", 2, 4, 40, 50),
("t3.large", 2, 8, 70, 80),
("m5.large", 2, 8, 80, 90),
("m5.xlarge", 4, 16, 160, 170),
("m5.2xlarge", 8, 32, 320, 330),
("c5.xlarge", 4, 8, 140, 160),
("r5.xlarge", 4, 32, 200, 190),
]
model = cp_model.CpModel()
x = [model.NewIntVar(0, 10, f"count_{i}") for i in range(len(servers))]
model.Add(sum(servers[i][3] * x[i] for i in range(len(servers))) <= 5000) # budget
model.Add(sum(servers[i][1] * x[i] for i in range(len(servers))) >= 16) # min vCPUs
model.Add(sum(servers[i][2] * x[i] for i in range(len(servers))) >= 32) # min RAM
model.Maximize(sum(servers[i][4] * x[i] for i in range(len(servers))))
This practical example shows how MDKP directly applies to real infrastructure decisions.
Additional Practical Tips
Tip 1: Scaling Issues
When constraints have different scales (e.g., budget in thousands vs count in single digits), CP-SAT handles this natively. No need to normalize.
Tip 2: Logical Constraints
CP-SAT supports logical relationships between items:
# If we pick item A, we must also pick item B
model.Add(x[1] >= x[0])
# Items A and B cannot both be selected
model.Add(x[0] + x[2] <= 1)
# At most 2 items from category C
model.Add(sum(x[i] for i in category_c) <= 2)
Tip 3: Warm Start
If you have a heuristic solution, provide it as a warm start to speed up the solver.
Summary
Multi-Dimensional Knapsack is the natural extension of knapsack problems to real-world scenarios with multiple resource constraints. CP-SAT handles MDKP effectively for 2-3 dimensions with moderate item counts.
What's Next: 2D Cutting & Packing
The next chapter moves from abstract dimensions to physical geometry - arranging rectangles on a 2D sheet to minimize waste, with rotation and no-overlap constraints.