Integer Programming
You cannot build half a warehouse, buy 2.7 machines, or send a truck on 40% of a route — many real decisions are indivisible, or simply yes-or-no. Integer programming is linear programming with the extra demand that some variables be whole numbers, and that one small requirement changes everything: the smooth geometry of the simplex method gives way to a lattice of discrete points, rounding the linear-programming answer can be wrong or even infeasible, and the true power of the model appears — binary variables that encode logic, turning "either–or", "if–then", and fixed setup costs into linear constraints.
- The three kinds of integer program — pure, mixed, and binary (0–1).
- The LP relaxation, the bound it gives, and the integrality gap.
- Why rounding the LP optimum can be wrong — or infeasible.
- When integrality comes for free (total unimodularity) — and when it does not.
- Modeling yes/no decisions and logic — either–or, if–then, at-most-\(k\) — with binary variables and Big-M.
- The classic 0–1 models: knapsack, set covering, fixed-charge, and facility location.
What Is Integer Programming?
An integer program (IP) is a linear program with the added requirement that some or all variables take integer values. Depending on which variables are restricted, three types arise:
| Type | Restriction | Typical use |
|---|---|---|
| Pure integer (IP) | All variables integer | Counting indivisible units — machines, crews, vehicles |
| Mixed integer (MIP) | Some variables integer, others continuous | Production levels (continuous) with setup decisions (integer) |
| Binary / 0–1 (BIP) | Variables restricted to \(\{0,1\}\) | Yes/no choices — build or not, select or not, route or not |
The binary case is the workhorse: a variable \(x_j \in \{0,1\}\) is a switch, \(1\) for "do it" and \(0\) for "don't", and combining such switches lets a linear model express genuinely non-linear logic. We will meet the standard 0–1 models in §15-7.
The LP Relaxation
Drop the integer requirement and you are left with an ordinary linear program — the LP relaxation of the IP. Because the relaxation has more feasible points (every fraction is now allowed), its optimum is at least as good as the integer optimum. For a maximization problem this gives an upper bound:
The difference \(z_{\text{LP}}^{*} - z_{\text{IP}}^{*}\) is the integrality gap. This bound is the single most useful fact about integer programming: it is what every solution method — including the branch and bound of Chapter 16 — uses to prune away regions that cannot possibly contain the integer optimum.
Consider the small binary-friendly example we will carry through the chapter:
Its LP relaxation is solved at the fractional vertex \((x_1, x_2) = (3.75,\ 2.25)\) with \(z_{\text{LP}}^{*} = 41.25\). No integer solution can beat \(41.25\).
Why Rounding Fails
It is tempting to just round the LP optimum to the nearest integers. This is unreliable for two reasons: the rounded point may be infeasible, and even when feasible it may be far from optimal. In the running example, rounding \((3.75, 2.25)\) up to \((4, 2)\) violates the second constraint \((9(4)+5(2)=46 > 45)\); rounding down to \((3, 2)\) is feasible but gives only \(z = 34\). The true integer optimum is elsewhere entirely — at \((5, 0)\) with \(z = 40\).
When Integrality Is Free
Sometimes the LP relaxation hands you integers automatically, and no special method is needed. This happens exactly when the constraint matrix is totally unimodular (every square submatrix has determinant \(0\), \(+1\), or \(-1\)) and the right-hand sides are integers — then every vertex of the feasible region is integer-valued.
This is precisely why the transportation, assignment, and network-flow problems of Chapters 12–14 never needed branch and bound: their node–arc structure is totally unimodular, so ordinary LP already produces whole-number answers. When a problem lacks this structure — as most scheduling, selection, and location models do — the integer requirement bites, and genuine integer-programming methods become necessary.
Modeling with Binary Variables
The real art of integer programming is formulation. A binary variable \(x_j \in \{0,1\}\) records a single yes/no decision, and simple linear inequalities among such variables capture surprisingly rich logic. Let \(y, y_1, y_2\) be binary throughout the table below:
| Condition to model | Linear constraint |
|---|---|
| Choose at most one of two options | \(y_1 + y_2 \le 1\) |
| Choose exactly \(k\) of \(n\) options | \(\sum_{j=1}^{n} y_j = k\) |
| Option 2 only if option 1 (\(y_2 \Rightarrow y_1\)) | \(y_2 \le y_1\) |
| Options 1 and 2 both or neither | \(y_1 = y_2\) |
| Activity \(x\) allowed only if \(y = 1\) | \(x \le M y\) |
The last row is the key link between a continuous quantity \(x\) and a binary switch \(y\): if \(y = 0\) the constraint forces \(x = 0\); if \(y = 1\) it becomes \(x \le M\), effectively no restriction when \(M\) is a large enough constant. This device — the Big-M link — underlies almost every logical model.
Logical Constraints & Big-M
Two constraints that would otherwise be non-linear become linear once a binary variable and a large constant \(M\) are introduced.
Either–or constraints. Suppose at least one of two constraints \(g_1(\mathbf{x}) \le b_1\) or \(g_2(\mathbf{x}) \le b_2\) must hold (but not necessarily both). Introduce a binary \(y\) and relax whichever is switched off:
When \(y = 0\) the first constraint is enforced and the second is relaxed (its right side becomes huge); when \(y = 1\) the roles swap. If–then constraints ("if \(x_1 > 0\) then \(x_2 \ge d\)") are built the same way, by attaching a Big-M term that is switched on or off by a binary indicator.
Classic 0–1 Models
A handful of binary formulations reappear across operations research, engineering, and computer science. Recognising them is half the battle:
Knapsack. Choose a subset of items, each with value \(v_j\) and weight \(w_j\), to maximise value within a capacity \(W\):
Set covering. Choose the fewest facilities (or fewest crews, sensors, warehouses) so that every requirement \(i\) is served by at least one chosen set \(S_j\), where \(a_{ij} = 1\) if set \(j\) covers requirement \(i\):
Fixed-charge / facility location. A cost is incurred only if an activity is switched on. Opening facility \(j\) costs a fixed \(f_j\) and lets it ship at unit cost \(c_{ij}\) to customer \(i\); a binary \(y_j\) opens the facility and links to the shipping variables through \(x_{ij} \le M y_j\):
How are these actually solved? The dominant approach — branch and bound — repeatedly solves LP relaxations, splitting on a fractional variable and using the relaxation bound to discard hopeless branches; cutting-plane methods instead add valid inequalities that trim fractional vertices away. Both are the subject of Chapter 16, previewed by the tree below.
Worked Examples
Problem. A plant chooses continuous production levels \(p_1, p_2 \ge 0\) and binary open/close decisions \(y_1, y_2\). Which type of integer program is this?
Solution. Some variables are continuous \((p_1, p_2)\) and some are integer — in fact binary \((y_1, y_2)\). It is a mixed-integer program. If the \(p_j\) were also required integer, it would be a pure IP; with only the \(y_j\) it is a mixed 0–1 model.
Problem. For the running example, what does \(z_{\text{LP}}^{*} = 41.25\) tell you about the integer optimum?
Solution. Since the LP relaxation contains every integer-feasible point, \(z_{\text{IP}}^{*} \le 41.25\). As the objective is integer-valued at integer points, we can even tighten this to \(z_{\text{IP}}^{*} \le 41\). The true optimum turns out to be \(40\), inside this bound.
Problem. Show that rounding the LP optimum \((3.75, 2.25)\) does not give the integer optimum.
Solution. Rounding up to \((4, 2)\) violates \(9x_1 + 5x_2 \le 45\) since \(46 > 45\) — infeasible. Rounding down to \((3, 2)\) is feasible but gives \(z = 34\). The actual optimum \((5, 0)\) gives \(z = 40\), differing from the LP point in both coordinates.
Problem. A project may use technology A or technology B but not both. Write the constraint.
Solution. With binaries \(y_A, y_B \in \{0,1\}\) indicating selection, impose \(y_A + y_B \le 1\). If exactly one must be chosen, use \(y_A + y_B = 1\). If B may be chosen only when A is, add \(y_B \le y_A\).
Problem. Producing any positive amount \(x\) on a machine costs a setup \(K = 100\) plus \(c = 4\) per unit, up to \(x \le 60\). Model the cost linearly.
Solution. Introduce a binary \(y\) (machine on) and link \(x \le 60\,y\). The cost term is \(100\,y + 4\,x\). If \(y = 0\) then \(x = 0\) and cost \(= 0\); if \(y = 1\) then \(x\) may be positive and the setup \(100\) is charged. The Big-M here is the natural bound \(60\).
Problem. Four items have values \((10, 13, 18, 31)\) and weights \((2, 3, 4, 7)\); the capacity is \(7\). Write the model and reason about the answer.
Solution. \(\max 10x_1 + 13x_2 + 18x_3 + 31x_4\) s.t. \(2x_1 + 3x_2 + 4x_3 + 7x_4 \le 7,\ x_j \in \{0,1\}\). Item 4 alone fills the knapsack for value \(31\); items 1 and 3 together weigh \(6 \le 7\) for value \(28\); items 2 and 3 weigh \(7\) for \(31\). The optimum is \(31\), achieved two different ways — a reminder that 0–1 optima need not be unique.
Chapter Summary
Pure integer, mixed integer, and binary (0–1) programs — the last encodes logic.
Dropping integrality gives a bound: \(z_{\text{IP}}^{*} \le z_{\text{LP}}^{*}\) for maximization.
The rounded LP point may be infeasible or far from the integer optimum.
Totally unimodular \(A\) with integer \(b\) makes every LP vertex integer.
Either–or, if–then, and at-most-\(k\) via binaries and the Big-M link \(x \le My\).
Knapsack, set covering, fixed-charge, and facility location; solved by branch and bound.
Problems
Formulate each model carefully and, where asked, reason about the relaxation and its bound. Difficulty rises down the list.
- Define pure, mixed, and binary integer programs, and give one engineering example of each.
- State the relationship between \(z_{\text{IP}}^{*}\) and \(z_{\text{LP}}^{*}\) for a maximization problem, and explain why it holds.
- Give a two-variable example where rounding the LP optimum down is feasible but not optimal.
- Explain the integrality gap and why a small gap is desirable for solution methods.
- State the total-unimodularity condition and name three earlier chapters whose problems satisfy it.
- Write binary constraints for: (a) choose exactly two of five options; (b) if option 1 then option 3; (c) options 2 and 4 both or neither.
- Model an either–or requirement that at least one of \(2x_1 + x_2 \le 10\) or \(x_1 + 3x_2 \le 12\) must hold, using a binary and Big-M.
- A furnace costs \(K = 500\) to start and \(c = 8\) per tonne, up to \(40\) tonnes. Write the fixed-charge cost expression and its linking constraint.
- Formulate the 0–1 knapsack for items with values \((6, 10, 12)\), weights \((1, 2, 3)\), capacity \(4\); find the optimum by inspection.
- Write the set-covering model to place the fewest ambulances so that every one of five zones is within reach of at least one station, given a coverage table \(a_{ij}\).
- Formulate a facility-location model for 2 candidate plants and 3 customers with fixed costs \(f_j\), shipping costs \(c_{ij}\), and demands \(d_i\); state the role of each binary.
- For the running example \(\max 8x_1 + 5x_2\) subject to \(x_1 + x_2 \le 6,\ 9x_1 + 5x_2 \le 45,\ x_1,x_2 \ge 0\) integer, list every integer-feasible point with \(x_1 \ge 3\), evaluate the objective at each, and confirm that \((5, 0)\) with \(z = 40\) is optimal.