Selecting a subset from N candidate items, each with a value and a weight, so that total weight does not exceed a capacity (budget, labour, machine-hours) and total value is maximised. In the literature it is the Knapsack Problem — the ancestor of discrete-selection problems.
In plain words
Sound familiar?
- An annual investment committee with 50-200 candidate projects and a fixed 50-500M TRY total budget — project ranking is intuitive and political; an 'NPV/investment ratio' table is prepared but mathematical optimality is not guaranteed.
- For each candidate we have NPV estimate, required investment, required labour-hours, required machine-hours (three-dimensional constraints) — but we have never built a selection model that respects all of them simultaneously.
- Budget planning uses 'rank from top and pick' — but small but high-NPV/unit projects that fit the last 5-10% of budget routinely fail to make the cut.
- Digital marketing campaign selection: 30-80 campaign proposals, a fixed monthly or quarterly budget; which subset should be picked to maximise reach/conversion?
- Dependencies between candidates exist (project A reduces the cost of project B if chosen; project C and D are mutually exclusive) — the classical knapsack model does not capture this and additional constraints are required.
- On the logistics side: a capacity-bounded cargo plane or container load — each parcel has a value and a weight, maximise total value subject to capacity.
- Small-cap fund manager: a universe of 200-500 stocks, fixed fund size, each stock has an expected return and a minimum trade size; which subset should be chosen?
- Supplier contract decision: 100+ candidate suppliers, fixed annual procurement budget; each supplier has a minimum and maximum order; which subset should be picked to maximise total value?
Why it matters
How it's solved
Technical depth
How it's solved
Technical depthIn one sentence: Rank candidates by value per unit of weight as a greedy start; for an exact answer, run dynamic programming (capacity under 10K) or MIP (especially with multi-dimensional constraints or dependencies) — the best subset falls out in minutes.
In the Operations Research (the discipline that uses math and computers to solve business decisions) and computer-science literature this is the Knapsack Problem — N candidate items with value (vᵢ) and weight (wᵢ); capacity W; which subset maximises Σvᵢ subject to Σwᵢ ≤ W? A classical problem studied since the 1950s, with industry-standard solutions through dynamic programming, branch-and-bound and modern MIP solvers. Three stages:
1. Modelling — variant choice and data inputs. The problem family is broad; the application determines which variant applies:
- 0/1 Knapsack (Binary Knapsack): each item is either picked or not, no duplicates. Classical investment-project selection sits here. Decision variable xᵢ ∈ {0, 1}.
- Bounded Knapsack: each item has a bounded number of copies (xᵢ ∈ {0, 1, …, cᵢ}). Procurement contracts of the form ’take 1-5 lots from each supplier'.
- Unbounded Knapsack: each item can be taken any number of times (xᵢ ≥ 0 integer). Capacity-bounded production-line bin packing or integer share lots.
- Multi-Dimensional Knapsack (MKP): m constraints; each item has weight in m dimensions (budget + labour-hours + machine-hours + …). Σⱼwᵢⱼxᵢ ≤ Wⱼ for all j. Substantially harder.
- Quadratic Knapsack (QKP): quadratic objective — Σᵢvᵢxᵢ + ΣᵢΣⱼpᵢⱼxᵢxⱼ; interaction values between items (synergy). Procurement deals where ‘A and B together earn an extra discount’.
- Multiple-Choice Multi-Dimensional Knapsack: items are grouped; exactly one item must be picked from each group.
- Subset-Sum: target value equals weight; total weight as close to capacity as possible. Change-making, exact-budget consumption.
- Knapsack with Set-Up: picking an item incurs a fixed set-up cost (groups). Production lines, factory openings.
Inputs: candidate item list N, value and weight estimates (NPV and investment for capital budgeting; estimated conversion value and campaign cost for marketing), capacity W (annual budget, monthly budget, cargo plane payload), multi-dimensional constraints (labour-hours, machine-hours, category sub-budget), dependency structure (precedence, mutual exclusion, capacity discount).
2. Solution — algorithmic toolkit.
- Greedy + LP-relaxation: simplest approach — rank items by value/weight ratio and pick top until capacity. Does not guarantee optimality (classic counterexample: capacity 10, three items (v,w) = (6,5), (5,4), (4,3) — greedy yields 6+5=11 but 5+4+3=12 is optimum); LP-relaxation provides an upper bound used inside branch-and-bound. Useful as a one-shot quick check.
- Dynamic Programming (DP): the classical pseudo-polynomial algorithm (time depends on the numerical value of capacity W). State: dp[i][w] = the maximum value achievable using the first i items without exceeding weight w. Transition: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wᵢ] + vᵢ). Complexity O(N×W). N = 1000 items, W = 100,000 TRY units = 10⁸ operations, seconds on modern hardware. Practical reality: moderate scale (N ≤ 1000, W ≤ 10⁶) is solved to optimum in minutes by DP; the practitioner’s ‘NP-hard so unsolvable’ intuition is wrong.
- Branch-and-bound (tree search with cutting/pruning of unpromising branches): with LP-relaxation upper-bound pruning. A core-variable technique is practical state-of-the-art for million-item 0/1 knapsack.
- MIP (Mixed-Integer Linear Programming — optimisation with some 0/1 variables and some continuous): the natural tool for multi-dimensional (MKP) and dependency-rich instances. Open-source or commercial MIP solvers handle 100-1000-item MKPs to optimum (or with a small gap) in minutes to hours.
- FPTAS (Fully Polynomial-Time Approximation Scheme — for any ε > 0, returns a (1-ε)-approximation of the optimum in polynomial time): with ε = 0.01 it guarantees 99% of optimum and is practical for very large instances.
- Metaheuristics (genetic, tabu, simulated annealing): for very large multi-dimensional MKP or dependency-rich instances; no optimality guarantee but practical quality.
Investment-project selection (50-200 items, single budget or 2-4 constraints): MIP or 0/1 DP returns optimum in seconds. Very large multi-dimensional (500+ items, 5+ constraints): MIP near-optimum or FPTAS. In practice MIP is sufficient for most enterprise scenarios; a specialised knapsack algorithm is rarely required.
3. Field integration and sensitivity analysis. Output: the chosen subset, total value, per-constraint utilisation, LP-relaxation-based sensitivity (which project was picked by a hair, which one missed by a hair). Investment committee report: the selection proposal, alternative scenarios (which project differs if budget ±10%, which appears if labour constraint is relaxed), explicit reporting of dependency and political-strategy constraints. Quarterly re-planning: new project proposals are added, realised NPV is benchmarked against forecast, the model is re-solved.
Alternatives
Manual + spreadsheet ranking
FreeZero licence
Who it fits: Small scale, 10-30 candidate items, single budget, simple dependencies
- + Zero setup
- + Easy for political-strategic committee overrides
- + Sufficient for a quick top-N discussion
- − Rank-and-pick does not guarantee the best subset — 5-15% value loss is typical
- − Multi-dimensional constraints (labour + capacity) cannot be respected by hand
- − Dependency structure (precedent projects, mutually exclusive pairs) is crude
- − No sensitivity analysis (what if budget ±10%)
Open-source MIP solver + in-house model
Open SourceLicence free; in-house build 4-12 weeks or 200K-600K TRY consulting
Who it fits: Organisation with an OR or analytics team, 50M+ TRY annual budget
- + No licence fee
- + Project-selection models map well onto open-source solvers
- + Fast scenario analysis (budget, labour, capacity parameter changes)
- + In-house ownership — model transparent, assumptions auditable
- − Requires optimisation specialist and data engineer
- − Model maintenance rests with the operator
- − Return-estimate noise persists regardless of solver — input quality is decisive
Commercial MIP solver + in-house model
EnterpriseAnnual 200K-1.5M TRY licence (TR market observation); large enterprise 2-5M TRY
Who it fits: Large holding, 500M+ TRY annual budget, multi-dimensional constraints
- + Industry-grade optimum solving engine
- + High-performance parallel solving
- + Mature modelling interface (scripting plus modelling-language support)
- + Industrial support
- − High licence cost
- − Internal model development and maintenance still demands an optimisation specialist
- − Vendor lock-in risk — porting model to another solver costs 4-12 weeks
Enterprise project-portfolio management software
EnterpriseAnnual 500K-3M TRY licence (TR market observation), by organisation scale
Who it fits: Multi-portfolio, multi-category, multi-geography holding
- + Integrated flow from proposal to selection
- + Dependency structure (precedent projects, exclusion pairs, synergy discounts) modelled in the UI
- + Quarterly re-planning and realised-return comparison built in
- + Investment committee reports ready
- − High licence plus 6-12 month deployment
- − Built-in solver module is often limited — may be insufficient for large portfolios
- − Vendor lock-in
- − Sector-specific customisation extends the project
Recommendation
Ask in the meeting
- Which variants does the project-selection module support — 0/1 picks, bounded lot count, single-budget, multi-dimensional constraints, grouped selection, set-up cost?
- Which method drives the solver — solver with optimum guarantee, dynamic program, approximation, advanced search? What is the typical solve time for a 200-1000 project multi-constraint portfolio?
- Can the dependency structure (precedent projects, mutually exclusive pairs, synergy discount, set-up cost) be modelled in the UI, or must the rules be written by hand?
- Sensitivity analysis — for budget ±10% or labour-constraint ±20% scenarios, which projects change and is reporting automated?
- Can uncertainty in return inputs be modelled (selection under uncertainty), or only as point estimates?
- For multi-constraint solutions, is the percentage gap between achieved value and theoretical upper bound reported so the user knows whether the result is optimum or near-optimum?
- Does the solution output produce an investment-committee report directly — chosen subset, used budget percentage, hairline decisions?
- If the contract ends, in what standard format can candidate-project data, model inputs, solution history and sensitivity reports be exported?
Technical details
Editor’s note
In plain speech this problem is called “project selection”, “budget allocation” or “investment prioritisation”. In the literature its name is the Knapsack Problem — the name comes from the metaphor of packing the most valuable load into a capacity-bounded knapsack (Dantzig 1957). It is the ancestor of discrete-selection problems. It must not be confused with the portfolio-optimisation problem (#018 Markowitz mean-variance): Markowitz gives continuous weights (each asset gets some real-valued share of the portfolio between 0% and 100%) and models risk via variance and correlation; the knapsack is a discrete pick-or-not decision (xᵢ ∈ {0, 1}) and maximises value subject to budget and NPV. Most classical decision problems have a knapsack underneath — investment-project selection, campaign selection, cargo loading, supplier subset selection. Cutting stock (#005, multi-dimensional geometric cutting) and 3D bin packing (#015, volumetric packing) are close relatives but different problems: knapsack maximises value, cutting stock minimises the number of rolls, 3D bin packing fits parcels into bins. Assortment planning (#017, retail shelf selection) is a specialised knapsack variant — coupled with a product-level demand model.
Most overlooked point in the sector: the difference between pseudo-polynomial DP and the complexity-class label. The knapsack is NP-hard — no polynomial-time algorithm in the bit-length of the input is known. The practitioner reads this as “unsolvable” — wrong. Bellman’s DP runs in O(N×W) time where W is the capacity. In capital budgeting, W = 50M TRY but we typically model it in thousand-TRY units (W = 50,000); with N = 200 projects this is 10⁷ operations, seconds on modern hardware. Pseudo-polynomial: time is polynomial in the value of W (and exponential in the bit-length of W). Practical consequence: when W is kept moderate (thousands, tens of thousands) DP solves million-item-scale knapsack instances to optimum in minutes. The practitioner in the investment committee should not jump to “we cannot know the mathematical optimum, we just rely on intuition” — practical knapsack tools (MIP, DP) are within everyone’s reach.
Second overlooked point: the uncertainty in NPV/value inputs. The knapsack mathematics assumes inputs are deterministic. In reality NPV estimates rest on 5-year projections with ±20-40% deviation as the norm; especially for new-technology and digital-transformation projects, uncertainty is even larger. A classical knapsack solver absorbs that uncertainty and returns a single ‘optimum’ subset; under NPV ±20% the subset could change entirely. Remedies: stochastic knapsack (Bertsimas and Sim 2003 robust-optimisation approach, worst-case optimum across an NPV uncertainty set), chance-constrained knapsack (budget overrun probability at most 5%) or simply a sensitivity analysis (report the projects that remain selected across NPV ±20% scenarios). Third overlooked point: dependency structure. The classical knapsack assumes item independence — project A and project B’s values are simply summed. In practice synergistic (A + B together earn extra value), mutually exclusive (A xor B), precedence (A → B activation), capacity-discount (A makes B cheaper) structures exist. These are modelled as MIP constraints; one must move from the standard knapsack interface to a richer MIP.
Step by step — for the SMB
Stage 1 — Measure first, plan second. The last 3-5 years of candidate investment projects (accepted plus rejected): proposed NPV estimate, realised NPV (for the accepted), investment amount, labour-hours, machine-hours. NPV-estimate deviation statistics: by category (expansion, modernisation, digital, IT) and by size, forecast/realised ratio, ±% band. Document at which point in annual planning the budget and other constraints (labour, machine-hours, category sub-budget) are firmed up.
Stage 2 — Surface the knowledge capital. Typical dependency structures among candidates (precedence chains, mutually exclusive pairs, capacity-discount synergies). NPV reliability bands: small standard project ±10%, digital transformation ±30-40%, R&D ±50%. Political category sub-budget requirements (regional balance, sector diversification).
Stage 3 — Pilot. 6-10 weeks. In one annual investment-committee cycle, run an open-source MIP in parallel with the existing intuitive selection. Report both outputs side by side for the same candidate set; explain the differences (which project greedy picked, which MIP picked, why). The decision still rests with the committee; the MIP gives a recommendation. Success criterion set in advance: the MIP-recommended portfolio’s NPV is at least 5% higher than greedy.
Stage 4 — Rollout. 6-12 months to the full investment-committee process with MIP. Quarterly re-planning (new proposals added, cancelled projects removed). Annual sensitivity analysis (budget ±10% scenarios). Stochastic or robust knapsack only after the NPV-uncertainty foundation is laid. Quarterly investment committee: MIP recommendation vs approved portfolio, list of hairline decisions, NPV forecast-vs-realised calibration.
Risks — what can go wrong
- NPV / return estimation error. The knapsack solution is mathematically optimum to the given NPVs; if NPV ±20-40% then the optimum subset can change. Robust or stochastic knapsack extension or at least a sensitivity analysis (projects stable across NPV ±20% scenarios) is mandatory. For forecast calibration, track realised-NPV / forecast-NPV by category over time.
- Project-independence assumption. The classical knapsack assumes item values add up; in practice there is synergy (A + B together gain extra value), mutual exclusion (A xor B), precedence (A → B activation), capacity-discount (A makes B cheaper). These need MIP constraints; one has to move beyond the standard knapsack interface.
- Risk dispersion ignored. Pure knapsack maximises total value; it does not model portfolio risk (variance, covariance, tail risk). Picking five projects in the same sector can give a high total NPV but a risky portfolio in case of a sector shock. Sector / geography / category sub-budget constraints should be added, or knapsack selection should be paired with a CVaR-type risk measure (#063).
- Single-supplier investment-planning software lock-in. Without a contract clause for annual export of candidate-item data, model inputs, solution history and sensitivity reports in a standard format, swapping out the software means zeroing out the investment-planning institutional memory. Open-source MIP + in-house model gives supplier independence at moderate scale."
A technical look at the solution
| Approach | Typical scale | Solve time | Optimality guarantee? |
|---|---|---|---|
| Greedy (rank by NPV/investment) | Any | instant | No (85-95% optimum typical) |
| LP-relaxation upper bound | Any | instant | No (upper bound) |
| Dynamic Programming (Bellman 1957) | Moderate (N≤1000, W≤10⁶) | seconds-minutes | Yes |
| Branch-and-Bound (Martello-Toth 1990) | Mid-large 0/1 KP | minutes-hours | Yes |
| Pisinger expanding-core (1997) | Very large 0/1 KP | minutes | Yes |
| MIP (general solver) | General (MKP, QKP, set-up) | seconds-hours | Yes (within gap) |
| FPTAS (Ibarra-Kim 1975) | Very large, ε-approx OK | minutes | (1-ε) optimum |
| Metaheuristic (genetic, tabu, SA) | Very large MKP, dependency-rich | minutes-hours | No, good practical quality |
Knapsack variants comparison:
- 0/1 Knapsack: each item picked or not. Classical capital budgeting. xᵢ ∈ {0, 1}.
- Bounded Knapsack: bounded number of copies. Supplier lots. xᵢ ∈ {0, …, cᵢ}.
- Unbounded Knapsack: unlimited copies. Capacity-bounded production, integer share lots. xᵢ ≥ 0 integer.
- Multi-Dimensional Knapsack (MKP): m constraints — budget + labour + capacity + category. Substantially harder; moderate-scale MKP still goes to MIP optimum within hours.
- Quadratic Knapsack (QKP): pairwise synergy or interaction values. Procurement deals where ‘A + B together earn a discount’.
- Multiple-Choice MKP: items grouped, exactly one item per group. Modular selection (CPU + RAM + disk bundle).
- Subset-Sum: target equals weight; total as close to capacity as possible. Change-making, exact-budget consumption.
- Knapsack with Set-Up: fixed set-up cost to activate a group. Production lines, factory openings.
Objective-function choice:
- Objective 1 — Maximum total value (NPV, conversion value): classical.
- Objective 2 — Maximum budget-utilisation percentage (near subset-sum): exact-budget discipline.
- Objective 3 — Robust / worst-case value (across NPV uncertainty set): Bertsimas-Sim robust optimisation.
- Objective 4 — Maximum expected value minus variance penalty (stochastic): mean-variance knapsack, portfolio logic.
Dependency modelling (within MIP):
- Precedence (A → B): xB ≤ xA (B may only be chosen if A is chosen).
- Mutual exclusion (A xor B): xA + xB ≤ 1.
- Synergy discount: extra decision yA·B; A and B jointly trigger a cost discount.
- Set-up cost: extra decision yk per group; an item in the group requires the group’s set-up.
- Category sub-budget: Σᵢ∈Cwᵢxᵢ ≤ Wc for each category C.
Academic sources
Listed in the frontmatter under sources.
Sources
- Dantzig, G. B. (1957). Discrete-variable extremum problems. Operations Research, 5(2), 266-288. Foundational paper on the LP/IP framing of knapsack and discrete optimisation.
- Bellman, R. (1957). Dynamic Programming. Princeton University Press. The foundational book of dynamic programming; the knapsack is its canonical example.
- Martello, S. and Toth, P. (1990). Knapsack Problems: Algorithms and Computer Implementations. Wiley. The classical textbook; branch-and-bound algorithms, experimental comparisons.
- Kellerer, H., Pferschy, U. and Pisinger, D. (2004). Knapsack Problems. Springer. Modern comprehensive reference; all variants, FPTAS, MKP, QKP.
- Pisinger, D. (1997). A minimal algorithm for the 0-1 knapsack problem. Operations Research, 45(5), 758-767. Practical state-of-the-art expanding-core algorithm for 0/1 knapsack.
- Ibarra, O. H. and Kim, C. E. (1975). Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM, 22(4), 463-468. Foundational paper on the knapsack FPTAS.
- YÖK Thesis Center — keywords: ‘sırt çantası’, ‘knapsack’ or ‘proje seçimi’ — 25+ theses from TR academia. tez.yok.gov.tr
Glossary
- Knapsack Problem
- The foundational discrete-optimisation problem of selecting a subset from N items, each with a value and a weight, to maximise total value subject to a capacity constraint on total weight.
- Dynamic Programming
- The OR / computer-science technique for solving multi-stage decision problems by recursive decomposition into overlapping subproblems with stored intermediate results; introduced by Bellman (1957).
- MIP
- An optimization model where some decision variables are forced to be whole numbers (e.g. number of trucks, number of shifts).
Related problems
How Much Cash in Which ATM, How Often to Refill — Balancing Empty-ATM Complaints Against High Immobilisation Cost
If you are a mid-size commercial or participation bank running 50-500 ATMs, every morning you must answer three questions: how much cash should each ATM hold, how often should each one be replenished, and which route should the armoured vehicle take. The wrong extremes are expensive: too much cash sitting inside an ATM inflates the annual 5-15% interest-opportunity cost plus the insurance premium; too little cash empties the machine, customers cannot withdraw, complaints and brand damage follow. Because a shopping centre, a bus stop, a campus and an office district all have very different withdrawal patterns, an intuitive 'same amount everywhere' rule hurts both ends at once. This page is for bank operations teams who want to take all three decisions together, driven by data.
Multiple Inputs + Multiple Outputs — How Do I Measure the Relative Efficiency of My Branches or Units?
This page is for you if you run a bank with 100-500 branches, a multi-site hospital chain with 200-1,500 beds, an education directorate with hundreds of schools, or a public body comparing performance province by province. The core question: which of your branches/hospitals/schools is efficient and which is not — and for those that are not, which 'peer' unit should they learn from and by how much? Each unit consumes several inputs at once (headcount, floor space, budget) and produces several outputs at once (revenue, customers/patients/students, quality); a single-ratio metric like 'revenue per employee' does not capture that and can flag an efficient unit as weak, or vice versa. Done properly — because the peer benchmark gives a concrete improvement reference — acceptance of improvement plans for weak units rises by 40-70%, which is worth roughly 10-50 million TRY a year in operating margin on a mid-size branch network.