Project Portfolio Selection
0-1 Knapsack · NP-Hard (weakly)
Construction firms reject 40–60% of bidding opportunities due to resource constraints, yet selecting the wrong project mix leaves €2–5M in annual margin on the table. Every fiscal quarter, a VP of Operations must decide which subset of candidate projects to pursue given limited capital, equipment, and skilled labor. This is the 0-1 Knapsack Problem — NP-hard but solvable in pseudo-polynomial time via dynamic programming.
The Problem
Maximizing portfolio value under capital constraints
A construction firm evaluates 12 candidate projects, each with an estimated net present value (NPV) ranging from €200K to €4M and a corresponding capital requirement. The total capital budget is constrained — the firm cannot pursue every opportunity. The objective is to select the subset of projects that maximizes total NPV without exceeding the available capital.
This maps directly to the 0-1 Knapsack Problem: each project is an item with a value (NPV) and a weight (capital cost), and the knapsack capacity is the firm’s budget. The binary decision variable for each project — pursue or reject — makes this a combinatorial optimization problem that is NP-hard but weakly NP-hard, admitting a pseudo-polynomial dynamic programming solution in O(nW) time.
subject to
Σi=1..n wi xi ≤ W // capital budget constraint
xi ∈ {0, 1} // select (1) or reject (0) each project
Where vi is the NPV of project i, wi is the capital cost, W is the total capital budget, and xi is the binary decision variable.
See full 0-1 Knapsack theory and all algorithmsTry It Yourself
Select construction projects to maximize portfolio NPV
Portfolio Optimizer
12 Projects · Budget €8MReady. Click “Solve & Compare All Algorithms” to run.
| Algorithm | NPV (€K) | Projects | Budget Used | Time |
|---|---|---|---|---|
| Click Solve & Compare All Algorithms | ||||
The Algorithms
Exact and heuristic approaches to the 0-1 Knapsack
Dynamic Programming
O(nW) | Pseudo-polynomialBuild a table of dimension n × W, where each cell stores the maximum value achievable using the first i items with capacity w. For each item, choose the better of excluding it (inherit the row above) or including it (add its value to the best solution at reduced capacity). Backtrack through the table to recover which items are selected. Guarantees an optimal solution but memory and time scale with the budget magnitude.
Greedy by NPV/Cost Ratio
O(n log n)Sort all projects by their value-to-weight ratio (NPV per euro of capital) in descending order. Greedily add projects to the portfolio as long as the budget is not exceeded. This combined greedy (best of density-first and max-value-first) guarantees at least 50% of OPT and runs in O(n log n) time. Often produces near-optimal solutions in practice.
Branch and Bound
O(2n) worst caseExplore the binary decision tree (include/exclude each project) using DFS. At each node, compute an upper bound via the LP relaxation (fractional knapsack) and prune branches whose bound cannot beat the current best known solution. Sorting items by value density before branching dramatically reduces the search space. For typical construction portfolios (n ≤ 30), B&B finds the optimum in milliseconds.
Real-World Complexity
Why construction portfolio selection goes beyond the classic knapsack
Beyond One Constraint
- Multiple resource types — Capital, skilled labor, and equipment are each constrained, creating a multi-dimensional knapsack
- Temporal dependencies — Some projects must start before others; precedence constraints introduce scheduling dimensions
- Cash flow timing — Capital is spread across quarters, requiring a time-phased budget model
- Risk correlation — Projects in the same region share risk factors; diversification objectives conflict with pure NPV maximization
- Synergies and conflicts — Some project pairs share mobilization costs; others compete for the same subcontractors
- Regulatory and capacity caps — Maximum concurrent projects by region, bonding limits, and insurance capacity constrain the feasible set
- Bid uncertainty — Stochastic knapsack variants model win probabilities alongside project values
Key References
Foundational works in knapsack optimization
- (1972). “Reducibility among combinatorial problems.” Complexity of Computer Computations, 85–103.
- (2004). “Knapsack Problems.” Springer.
- (1957). “Discrete-variable extremum problems.” Operations Research, 5(2), 266–288.
- (1974). “Computing partitions with applications to the knapsack problem.” JACM, 21(2), 277–292.
Need to optimize your project portfolio?
From capital allocation to resource scheduling and risk-adjusted selection, mathematical modeling can transform how construction firms choose projects. Let’s discuss how Operations Research can work for you.