Reducibility
Glossary Contents
← Ch I
Chapter II 0-1 Integer Programming
Ch III →
  1. 04 — Booleans in disguise
  2. 05 — Modeling in MiniZinc
  3. 06 — Capital budgeting
06

Capital budgeting

Every CFO who has ever picked which projects to fund has solved a 0-1 IP, with or without knowing it.

A pharmaceutical company has $400M (2026 USD) to allocate across twelve drug programs. Each program has an estimated NPV, a development cost, and shared resource demands (clinical-trial slots, regulatory bandwidth). You can fund a program or not — there is no half-trial. Maximize total NPV subject to budget and resource caps. That is a 0-1 integer program, and it is the bread and butter of strategic-finance teams at Pfizer, Boeing, and every utility deciding which transmission lines to build. Solvers like Gurobi will dispatch a twelve-binary problem in milliseconds and a thousand-binary capital plan in minutes — but the modeling effort is where consultancies bill the hours.

In plain terms

You have a fixed budget and a list of projects. Each project costs something and pays off something. You want to pick the combination that pays off most without going over budget. The "all-or-nothing" rule (you can't fund half a project) is what makes it a 0-1 problem rather than a smooth optimization.

Scan to come back to page 06

End of Chapter II
Chapter III Clique →
← 05 Modeling in MiniZinc
3/3 · 6/63
07 Friends of friends of friends →