Key takeaways
– Zero-one integer programming (also written 0-1 integer programming) models decisions that are binary: choose (1) or do not choose (0).
– It is widely used in capital budgeting, project selection, scheduling, facility location, and many combinatorial optimization problems.
– Formulate the problem with binary decision variables, a linear objective, and linear constraints; solve using integer programming methods (branch-and-bound, cutting planes) or commercial/free solvers.
– For real problems, follow a structured modeling and validation workflow, use solver capabilities, and apply preprocessing or heuristics when scale becomes an issue.
What is zero-one integer programming?
Zero-one integer programming is a class of integer linear programming in which variables are constrained to take only the values 0 or 1. Each binary variable typically encodes a yes/no, on/off, or select/don’t-select decision. The objective function and constraints are linear expressions in these variables. Because many decision problems can be expressed as selecting a subset of items subject to constraints, 0-1 formulations are especially natural and powerful.
Core mathematical form
Maximize (or minimize)
c1 x1 + c2 x2 + … + cn xn
subject to
a11 x1 + a12 x2 + … + a1n xn ≤ b1
…
am1 x1 + am2 x2 + … + amn xn ≤ bm
xi ∈ {0, 1} for i = 1..n
Here xi are binary decision variables, ci are coefficients in the objective (e.g., profit, cost saving), aij and bj are coefficients describing constraints (e.g., budgets, resource capacities).
Why use 0-1 integer programming?
– Natural modeling: Many practical decisions (accept/reject a project, open/close a facility, assign/do not assign a worker to a shift) are binary.
– Guarantees feasibility: Constraints capture capacity and logic; integer restriction enforces discrete choices.
– Optimization under constraints: Helps maximize returns, minimize cost, or meet service levels while obeying limits.
– Integrates logical relationships: Mutually exclusive choices, implication constraints, and “at most/at least k selected” rules are easy to model.
Common applications
– Capital budgeting / project selection (capital rationing)
– Knapsack and resource allocation problems
– Facility location and network design
– Crew scheduling and rostering
– Production planning with discrete choices (produce product or not)
– Portfolio selection with buy/sell decision flags or minimum lot sizes
– Advertising placement / media mix with discrete slots
Basic solution approaches
– Exact methods
• Branch-and-bound / branch-and-cut: standard in modern solvers (CPLEX, Gurobi, SCIP).
• Cutting plane methods: add linear constraints to tighten LP relaxation.
– Relaxation and rounding
• Solve LP relaxation (allow xi ∈ [0,1]) for bounds or starting solution; apply heuristics to produce a feasible integer solution.
– Heuristics and metaheuristics
• Greedy methods, local search, simulated annealing, genetic algorithms for very large or hard instances.
– Specialized algorithms
• Dynamic programming for knapsack-like subproblems, Benders decomposition for structured models.
Practical modeling patterns (useful constraints)
– Cardinality constraint: sum xi ≤ K (select at most K items).
– Mutual exclusivity: xi + xj ≤ 1 (cannot select both i and j).
– Implication: xi ≤ xj (if i selected then j must be selected).
– Fixed choice: xi = 0 or xi = 1 (force decision).
– Linking discrete and continuous: yi ≤ M xi (activate continuous variable yi only if xi = 1).
Step-by-step practical workflow
1. Define the decision and objective
• Precisely state what is being decided (which projects to fund, which facilities to open).
• Choose the objective: maximize profit, minimize cost, minimize time, etc.
2. Identify binary variables
• Create one binary variable per choice that is inherently yes/no.
• Name variables clearly (x_projectA = 1 if project A is selected).
3. Build linear constraints
• Translate capacities, budgets, and logical rules into linear inequalities/equalities.
• Check units and scale (all costs in same currency, time units consistent).
4. Validate small/edge cases
• Work out simple instances by hand to verify the model produces expected decisions.
• Check feasibility: are there scenarios with no feasible solution?
5. Choose a solver and implement
• For prototyping: open-source solvers like CBC, GLPK, or OR-Tools.
• For large or performance-critical problems: commercial solvers like Gurobi or CPLEX.
• Use modeling APIs: Python’s PuLP, Pyomo, OR-Tools, JuMP (Julia).
6. Solve and inspect results
• Review selected variables and verify constraints satisfied.
• Examine solver log and solution gaps (optimality gap, runtime).
7. Sensitivity and scenario analysis
• Change budgets, costs, or returns to test robustness.
• Consider multi-period extensions or stochastic variants if parameters uncertain.
8. Scale and refine
• Use preprocessing (remove dominated options), variable fixing, symmetry breaking.
• If too slow, try heuristics, cutting planes, or decomposition techniques.
Illustrative (small) capital-rationing example
Problem: A company has 5 possible projects. Each project i has cost ci and expected return ri. A budget limit is B = 10. Choose which projects to fund to maximize total return.
Data
– Project 1: cost 6, return 10
– Project 2: cost 4, return 7
– Project 3: cost 3, return 4
– Project 4: cost 5, return 6
– Project 5: cost 2, return 3
Decision variables
xi = 1 if project i is selected, 0 otherwise.
Model
Maximize 10 x1 + 7 x2 + 4 x3 + 6 x4 + 3 x5
subject to 6 x1 + 4 x2 + 3 x3 + 5 x4 + 2 x5 ≤ 10
xi ∈ {0, 1} for i = 1..5
Solution (small enumerative reasoning)
– Check feasible combinations with budget ≤ 10. The combination x1 = 1, x2 = 1 (projects 1 and 2) uses budget 10 and yields return 17, which is the best among feasible subsets. So the optimal solution is choose projects 1 and 2.
This toy example demonstrates the structure and interpretation; in practice a solver would find the same answer quickly.
Implementation tips (example tools)
– Python + PuLP (open-source) — easy for small/medium models.
– Python + OR-Tools — good performance and free.
– Gurobi / CPLEX — excellent performance for large industrial models (commercial).
– Modeling packages (PuLP, Pyomo, JuMP) provide readable model specification and interfaces to multiple solvers.
Simple PuLP-style pseudocode
– Define binary variables xi
– Add budget constraint: sum(cost[i]*x[i]) ≤ B
– Set objective: maximize sum(return[i]*x[i])
– Solve with chosen solver
– Extract x[i] values and objective
Practical modeling tips and pitfalls
– Scale coefficients properly — avoid mixing wildly different magnitudes if possible.
– Tighten formulations — add valid inequalities (e.g., upper/lower bounds) to speed up solving.
– Exploit structure — if your model decomposes (time periods, independent groups), use decomposition methods.
– Watch for symmetry — many symmetric variables can make branching inefficient; break symmetry if feasible (add ordering constraints).
– Check integer feasibility early — LP relaxations give bounds but may not reflect true integer feasibility.
– Keep logs and solver statistics — objective bound, optimality gap, and node counts guide tuning.
Computational considerations
– 0-1 integer programming is NP-hard in general — worst-case solving time grows rapidly with problem size.
– Modern MIP solvers with branch-and-cut, presolve, and heuristics often handle surprisingly large real-world instances efficiently.
– If exact optimality is infeasible, accept near-optimal solutions with small optimality gap, or use heuristic/metaheuristic approaches.
Further reading and resources
– Investopedia — basic overview of zero-one integer programming:
– R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics (for combinatorial background)
– G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization (classic text)
– Gurobi Optimization — documentation and modeling guides (commercial solver)
– Google OR-Tools — open-source optimization suite
Summary
Zero-one integer programming is a concise, flexible way to model binary decisions across finance and operations. Start by clearly defining your choices, express them as binary variables with a linear objective and linear constraints, and use modern solvers or heuristics to obtain high-quality solutions. For large or complex instances, refine formulations, exploit structure, and use sensitivity analysis to ensure decisions are robust.