Zero-One Integer Programming

Key takeaways
* Zero-one (0–1) integer programming is an optimization method where decision variables take only the values 0 or 1, representing mutually exclusive yes/no choices.
* It is used to model selection, assignment, scheduling, routing, and many binary decision problems (e.g., which projects to fund, whether to open a facility).
* Typical solution approaches include linear programming relaxation, branch-and-bound/branch-and-cut, and heuristics; many 0–1 problems are NP-hard.

What it is

Zero-one integer programming is a special case of integer programming in which every decision variable x_i is binary: x_i ∈ {0,1}. A binary variable commonly denotes a yes/no decision (select/reject, on/off, build/do not build). Problems are usually formulated with a linear objective function and linear constraints:

Maximize or minimize: c1 x1 + c2 x2 + … + cn xn
Subject to: a11 x1 + a12 x2 + … + a1n xn ≤ b1
…
x_i ∈ {0,1} for all i

Because variables are restricted to 0 or 1, 0–1 integer programs can model logical structure (mutual exclusivity, precedence, capacity limits) in a compact, linear way.

Why it’s useful

• Models discrete choices directly (e.g., which projects to fund, which machines to use).
• Encodes combinatorial constraints (at most k items, exactly one of a set, implication relationships).
• Widely applicable: capital budgeting, knapsack problems, facility location, scheduling, network design, feature selection.

Simple example: capital rationing

A company must choose which projects to fund within a budget.

Let x1, x2, x3 be binary decisions for projects A, B, C.
Profits: p = [40, 30, 50]
Costs: c = [20, 30, 40]
Budget: 50

Formulation:
Maximize 40 x1 + 30 x2 + 50 x3
Subject to 20 x1 + 30 x2 + 40 x3 ≤ 50
x1, x2, x3 ∈ {0,1}

Feasible options and profits:
* A only (1,0,0): cost 20, profit 40
B only (0,1,0): cost 30, profit 30
C only (0,0,1): cost 40, profit 50
A+B (1,1,0): cost 50, profit 70 ← optimal
Other combinations exceed budget

Solution: select A and B (x1 = x2 = 1, x3 = 0) for maximum profit 70 within the budget.

Solution methods

• Linear programming (LP) relaxation: solve the LP with 0 ≤ x_i ≤ 1 to get bounds or fractional solutions.
• Branch-and-bound/branch-and-cut: systematic tree search using LP bounds and cutting planes to enforce integrality.
• Heuristics and metaheuristics: greedy algorithms, local search, genetic algorithms—useful for very large instances when exact methods are impractical.
• Commercial and open-source solvers (e.g., Gurobi, CPLEX, CBC) implement these methods efficiently.

Computational considerations

Many 0–1 integer programming problems are NP-hard (e.g., knapsack, set covering). Problem size, constraint structure, and coefficient properties affect difficulty. Exploiting problem-specific structure, valid inequalities, preprocessing, and good initial solutions can greatly improve solvability.

When to use 0–1 integer programming

Use 0–1 integer programming when decisions are inherently binary and constraints/objectives are linear or can be linearized. It provides an exact, expressive way to model discrete optimization problems common in operations research, finance, logistics, and engineering.