Knapsack Selection: Project Portfolio Optimization

You are a CTO with a $5M budget and 10 potential projects. Each project has costs, expected returns, and dependencies. How do you choose?

This is the knapsack selection problem - choosing the optimal combination under constraints.

Why Project Selection?

Every organization faces the same challenge: limited resources vs unlimited opportunities. Whether you are:

A startup choosing features to build
A corporation allocating budget across departments
A government selecting infrastructure projects
An investor building a portfolio

The question is always the same: which combination of options delivers the best outcome?

What Is Knapsack Selection?

Knapsack selection extends the classic knapsack with business constraints:

Standard knapsack: Maximize value, subject to weight <= capacity

Knapsack selection: Maximize business value, subject to:

Budget constraint
Dependency rules (project B requires project A)
Mutual exclusion (cannot do both project C and D)
Minimum selection (must pick at least 2 projects)
Cardinality constraints (at most 3 projects from category X)

Implementation with CP-SAT

from ortools.sat.python import cp_model

# Projects: (name, cost, value)
projects = [
    ("AI Customer Service", 150, 400),
    ("Data Platform", 200, 350),
    ("App Development", 180, 300),
    ("SEO Optimization", 50, 180),
    ("Performance System", 120, 250),
    ("Automated Testing", 80, 200),
    ("Security Audit", 60, 150),
    ("Internationalization", 100, 220),
    ("API Platform", 160, 280),
    ("BI Dashboard", 90, 190),
]

budget = 500  # $500K

model = cp_model.CpModel()
x = [model.NewBoolVar(f"x_{i}") for i in range(len(projects))]

# Budget constraint
model.Add(sum(projects[i][1] * x[i] for i in range(len(projects))) <= budget)

# Dependency: AI Customer Service requires Data Platform
model.Add(x[0] <= x[1])

# Mutual exclusion: App Development vs API Platform
model.Add(x[2] + x[8] <= 1)

# At least 3 projects must be selected
model.Add(sum(x) >= 3)

# At most 2 projects from "infrastructure" category (indices 1, 4, 5, 6, 9)
model.Add(x[1] + x[4] + x[5] + x[6] + x[9] <= 2)

# Objective: maximize value
model.Maximize(sum(projects[i][2] * x[i] for i in range(len(projects))))

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"=== Project Selection Result ===")
    print(f"Total value: {int(solver.ObjectiveValue())}K")
    
    total_cost = 0
    for i, (name, cost, value) in enumerate(projects):
        if solver.Value(x[i]):
            total_cost += cost
            print(f"  SELECTED: {name} - cost ${cost}K, value ${value}K")
    
    remaining = budget - total_cost
    print(f"\nTotal cost: ${total_cost}K / ${budget}K (${remaining}K remaining)")
else:
    print("No feasible solution found")

Real-World Business Constraints

| Constraint Type | CP-SAT Implementation | Business Example | |----------------|:---------------------:|------------------| | Dependency | x[A] <= x[B] | "Data platform required before AI" | | Mutual exclusion | x[A] + x[B] <= 1 | "React vs Vue - pick one framework" | | At least N | sum(x) >= N | "Must ship at least 3 features this quarter" | | At most N | sum(x) <= N | "At most 2 experimental projects" | | Conditional | x[A] + x[C] <= x[B] + 1 | "If we build iOS app, must also build Android" |

Investment Portfolio Selection

The same model works for stock portfolio optimization:

# Stocks: (name, price, expected_return, risk_level)
stocks = [
    ("AAPL", 180, 0.25, "low"),
    ("GOOGL", 140, 0.20, "low"),
    ("MSFT", 330, 0.22, "low"),
    ("AMZN", 150, 0.30, "medium"),
    ("TSLA", 250, 0.35, "high"),
    ("NVDA", 450, 0.40, "high"),
    ("META", 300, 0.28, "medium"),
]

max_investment = 1000  # $1M

model = cp_model.CpModel()
y = [model.NewBoolVar(f"y_{i}") for i in range(len(stocks))]

# Budget constraint
model.Add(sum(stocks[i][1] * y[i] for i in range(len(stocks))) <= max_investment)

# Diversification: select exactly 3 stocks
model.Add(sum(y) == 3)

# Risk limit: at most 1 high-risk stock
high_risk_indices = [i for i, s in enumerate(stocks) if s[3] == "high"]
model.Add(sum(y[i] for i in high_risk_indices) <= 1)

# Maximize expected return
model.Maximize(sum(stocks[i][2] * y[i] * 1000 for i in range(len(stocks))))

Application Scenarios

| Scenario | Decision Variables | Constraints | |----------|:-----------------:|-------------| | Hiring | Which candidates to hire | Budget, headcount, skill coverage | | Ad campaign | Which channels to use | Budget, reach, frequency | | Product features | What to build next | Engineering hours, dependencies | | Inventory | Which products to stock | Warehouse space, capital, turnover | | Research projects | Which RD projects fund | Budget, strategic alignment |

Comparison with Classic Knapsack

| Aspect | Classic Knapsack | Knapsack Selection | |--------|:----------------:|:------------------:| | Constraints | Single (weight) | Budget + dependencies + exclusions + cardinality | | Objective | Maximize value | Maximize business value | | Solver | DP: O(nW) | CP-SAT: handles all constraint types | | Real-world fit | Toy problems | Real business decisions |

The CP-SAT solver handles all these constraint types naturally, making it ideal for real business problems.

The Vibe Coding Approach

Describe your business problem:

"I am a CTO with $5M budget and 10 potential projects. Each project has cost and expected ROI. Some projects depend on others. I cannot do competing projects simultaneously. Help me select the optimal portfolio using OR-Tools CP-SAT."

The AI will generate the complete selection model with all business constraints.

Summary

Knapsack selection extends the classic knapsack to real business decisions with multiple constraint types. CP-SAT handles dependencies, exclusions, minimums, and maximums naturally.

Key takeaways:

Business project selection = knapsack with multiple constraint types
Dependencies: x[A] <= x[B]
Mutual exclusion: x[A] + x[B] <= 1
Cardinality: sum(x) >= N or <= N
CP-SAT handles all constraint types in one model
Same model works for hiring, investing, feature selection
Real business problems need more than classic knapsack

What's Next: Course Summary

This combinatorial optimization course covered: Bin Packing, Job Scheduling, Multi-Dimensional Knapsack, 2D Cutting Packing, and Knapsack Selection. You now have the tools to model and solve a wide range of resource allocation problems.

Advanced: Sensitivity Analysis

After finding the optimal portfolio, analyze sensitivity:

What if budget changes by 10%?

If budget increases 10% ($550K), which additional projects become viable?
If budget decreases 10% ($450K), which projects must be dropped?

Key Person Risk

If a critical team member leaves, which dependent projects are affected?
Have backup plans for projects with single points of failure

Time-to-Value Analysis

Some projects deliver value quickly (SEO, quick wins)
Others take longer but have higher returns (platform, AI)
Balance short-term wins with long-term strategic investments

The 80/20 Rule in Project Selection

Typically, 20% of projects deliver 80% of the value. Knapsack selection automatically finds this optimal 20%.

The optimizer naturally identifies high-value, low-cost projects.
These are the "low-hanging fruit" that deliver maximum ROI.

Course Summary

This combinatorial optimization course equipped you with: Bin Packing for logistics, Job Scheduling for timelines, Multi-Dimensional Knapsack for resource allocation, 2D Cutting for manufacturing, and Knapsack Selection for business decisions.

You can now model almost any resource allocation problem as a CP-SAT optimization.