Chapter II 0-1 Integer Programming

Booleans in disguise

Linear algebra and Boolean logic are the same problem with different makeup.

A 0-1 integer program asks whether a system of linear inequalities admits a solution where every variable is restricted to zero or one. The whole problem fits in a single line:

A x \geq b, x \in {0, 1}^{n} . (1)

Karp's reduction from SAT is one step. Each Boolean variable becomes a 0-1 integer; each clause becomes an inequality. Take a three-literal clause where the second variable is negated:

x_{1} \lor \neg x_{2} \lor x_{3} .

It turns into the linear constraint

x_{1} + (1 - x_{2}) + x_{3} \geq 1. (2)

Read (2) carefully: every literal contributes a 1 if it is satisfied, and the sum being at least 1 means at least one literal is satisfied — exactly what the clause requires. Stack one such inequality per clause, and form (1) is a SAT instance in 0-1 IP clothing.

Drop linearity for nonlinear terms and you get general integer programming, which is also NP-hard. Drop the integrality and you get linear programming, which is in P (Khachiyan 1979). The whole modern field of mixed-integer programming — Gurobi, CPLEX, COIN-OR — is industrial-strength infrastructure for problems that, formally, are this one.

Figures, in plain terms

(1)

The capital A is a matrix and x is a column vector of unknowns. Their product Ax is a column vector of linear combinations — each row of A multiplied entry-wise against x, then summed.

The b on the right is the matching column of lower bounds, one per row.

The ≥ is component-wise: every row of Ax must be at least the matching row of b. So (1) is a whole stack of "weighted-sum-of-variables ≥ some bound" inequalities, written compactly with vector notation.

The trailing x ∈ {0, 1}ⁿ says every entry of x is either 0 or 1 — no fractions allowed. The superscript n is the count of variables.

Put together: find a yes/no setting of n variables that satisfies all the row-by-row inequalities at once.

(2)

Each variable here represents one literal of the original clause. x₁ is 1 when literal "x₁" is true, 0 when false.

For the negated literal "¬x₂", we use the trick (1 − x₂). When x₂ is 0 (the variable is false, so ¬x₂ is true), this term equals 1. When x₂ is 1, it equals 0. Negation, built from arithmetic.

Now sum the three terms. Each term is 1 if its literal is true and 0 if false, so the sum counts how many literals in the clause are true.

The final ≥ 1 says at least one literal in the clause must be true — exactly the OR semantics, expressed without an OR symbol.