Implementation of exact solvers for the Unit-Profit Minimum Knapsack Problem with Compactness Constraints (UPM), comparing a Mixed-Integer Programming approach (Gurobi) with a Dynamic Programming algorithm.
Given n items with weights w₁, ..., wₙ, find the smallest subset whose total weight meets a minimum capacity c, subject to a compactness constraint: if two selected items are more than Δ positions apart, at least one item between them must also be selected.
This arises as a special case of the min-knapsack problem where all profits equal 1 (unit-profit), so minimizing profit is equivalent to minimizing the number of selected items.
| Method | Purpose | Complexity |
|---|---|---|
| MIP Solver (Gurobi) | Find provably optimal solutions via binary formulation | Exact, exponential worst-case |
| DP Decision Algorithm | Answer "can we solve it with ≤ t items?" | O(n · t · Δ) time, O(n · t) space |
- Instance generation: Multi-modal Gaussian weight distributions with random noise spikes, normalized to sum to 1
- Capacity as coverage: With normalized weights, c = 0.9 means "select items covering ≥ 90% of total weight"
- Validation: DP correctness verified against Gurobi optima on every instance — testing both feasibility (t = z*) and infeasibility (t = z* − 1)
- Generated and solved instances at three scales (n = 100, 200, 300)
- Explored the effect of the compactness parameter Δ on solution structure
- Validated DP correctness across all instances and parameter settings
- Benchmarked DP vs MIP solve times
pip install -r requirements.txt
jupyter notebook upm_dynamic_programming.ipynbNote: Requires a valid Gurobi license. Free academic licenses are available.
- Python 3.8+
- gurobipy
- numpy, pandas, matplotlib
- tabulate
Albert Lamb, Anabel Pichardo, Timothy Moynihan
Barcelona School of Economics — Deterministic Models and Optimization (Fall 2025)