Integer Programs

Adding four words to a program, "and these must be whole numbers", changes what kind of problem it is. The feasible set stops being a region and becomes a scatter of isolated points inside one.

The formulation unit established when a linear program is the wrong model, and named indivisible decisions as one of the reasons. This unit starts after that judgement has been made: integrality is required, so what exactly have you written down, and how does it behave?

The short answer is that one extra line changes the problem completely. The feasible region stops being a region. The optimum stops sitting at a corner. The method you have spent this course learning no longer applies. None of that is obvious from how small the addition looks on the page.

This unit assumes you can formulate a linear program and classify a feasible region.

Solve a linear program and the answer comes back $x_1=3.7$ lorries. If a lorry is something you either send or do not, that is not a near-miss; it describes a situation that does not exist.

The repair looks trivial. Require the variable to be a whole number.

Now look at what the feasible set became. It was a solid shape with flat faces and straight edges. It is now the scattering of dots inside that shape whose coordinates happen to be whole numbers. There is nothing between the dots. No direction to move in, no edge to slide along, no corner where the answer has to be, because the corners belong to the shape, and the answers no longer live in the shape.

Everything that made linear programs tractable was a fact about that shape. Convexity, the vertex characterisation of optima, a step that walks from one corner to an adjacent one: all of it describes the polyhedron, and the polyhedron is now scenery rather than the search space.

The consequence that matters in practice is the one people resist. An integer program is not a linear program with a rounding step bolted on the end. Rounding can leave the region altogether, and even when it does not, the best whole-number point is often nowhere near the fractional one.

So integer programs need their own methods, and those methods cost far more. A linear program with thousands of variables is routine; an integer program of the same size may be out of reach. Requiring integrality is a decision about computation as much as about meaning.

An integer linear program is

where $I$ indexes the variables required to take whole-number values.

Three cases. When $I$ is every variable, the program is pure integer. When $I$ is a non-empty proper subset, it is mixed-integer. The commonest case in practice, since most situations mix indivisible choices with divisible quantities. When the integer variables also carry bounds $0\le x_j\le 1$ they are binary.

The feasible set. Write $P$ for the polyhedron defined by $Ax\le b$, $x\ge 0$. The feasible set of the integer program is

the points of $P$ whose restricted coordinates are whole numbers. It is generally not convex, not connected, and has no interior.

What ceases to hold. The optimum need not be at a vertex of $P$, and usually is not. Convexity arguments do not apply. There is no local move with a direction, so there is no simplex step.

What still holds. The objective and constraints are linear, and feasibility is still decided by substitution. If every integer variable is bounded, the feasible set is finite, so an optimum exists whenever a feasible point does.

Take

As a linear program. The binding constraints meet where $2x_1+3x_2=12$ and $3x_1+x_2=9$. From the second, $x_2=9-3x_1$; substituting, $2x_1+27-9x_1=12$, so $-7x_1=-15$ and $x_1=15/7$, giving $x_2=9-45/7=18/7$. The optimum is $(15/7,18/7)\approx (2.14,2.57)$ with value $33/7\approx 4.71$, at a vertex.

Now require $x_1,x_2\in \mathbb{Z}$. The feasible points are the whole-number pairs inside the region. Checking those with the largest sums: $(2,2)$ gives $4+6=10\le 12$ and $6+2=8\le 9$, feasible, value $4$. $(3,0)$ gives $6\le 12$ and $9\le 9$, feasible, value $3$. $(0,4)$ gives $12\le 12$ and $4\le 9$, feasible, value $4$. $(1,3)$ gives $2+9=11\le 12$ and $3+3=6\le 9$, feasible, value $4$.

The integer optimum is $4$, attained at $(2,2)$, $(1,3)$ and $(0,4)$.

What to notice. The continuous optimum was $4.71$ at a vertex; the integer optimum is $4$ and is attained at three points, none of them a vertex of the polygon. The value fell, the location moved, and the vertex account gave no guidance at all.

Problem. A depot operator plans next week. They may open any of three regional depots, each with a weekly fixed cost. They will ship tonnes of product from whichever depots open, and they hire delivery vans by the day. Say which variables require integrality.

Goal. A variable list with a justified restriction on each, and the resulting classification.

Relevant principle. Integrality is required when a fractional value has no meaning in the situation, not when the answer is expected to come out whole.

Step 1: the depot decisions. Opening a depot is a yes-or-no choice; there is no such thing as opening two-fifths of a depot. Three binary variables $y_1,y_2,y_3\in \{0,1\}$, with $1$ meaning open.

Step 2: the shipped quantities. Tonnes are divisible. Shipping $17.4$ tonnes is a perfectly sensible plan. These are continuous: $q_1,q_2,q_3\ge 0$.

Worth pausing on. It is tempting to make these integers too, on the grounds that the answer will look tidier. That would add restrictions the situation does not impose, make the program far harder to solve, and potentially exclude the genuine optimum. Integrality costs; it should be bought only where needed.

Step 3: the vans. A van-day is indivisible, half a van does not deliver. This is a general integer variable $v\in \mathbb{Z}$, $v\ge 0$. Note it is not binary: the operator may hire several.

Step 4: classify. The program has binary variables, a general integer variable, and continuous variables together. It is a mixed-integer program.

Step 5: what follows. The feasible set is not a polyhedron. Solving the continuous version would return fractional depot decisions, $y_1=0.62$, an instruction nobody can carry out, so the relaxed answer is not a plan. The vertex characterisation does not apply, and a simplex solve alone will not produce an implementable answer.

Check. Each restriction traces to a fact about the situation: depots are opened or not, tonnes divide, vans do not. No variable carries integrality because the answer was expected to be whole.

Not an integer program: a divisible quantity that happened to come out whole. A blending model returns exactly $40$ kg of an ingredient. Nothing about kilograms is indivisible, and adding $x\in \mathbb{Z}$ to enforce what the arithmetic produced anyway makes the program dramatically harder and can exclude a better fractional plan.

Not an integer restriction: a bound. $x\le 5$ restricts the size of a quantity, not its divisibility. $x=4.3$ satisfies it. Bounds and integrality are independent, and a variable can carry either, both, or neither.

Not binary: a general integer variable. Hiring vans is indivisible but not a yes-or-no choice; $v=3$ is meaningful. Writing $v\in \{0,1\}$ forbids hiring more than one van, which is a restriction the situation never stated.

Not a repair: rounding the continuous answer. Rounding $(2.14,2.57)$ to $(2,3)$ in the earlier example gives , infeasible. Rounding down to $(2,2)$ is feasible and optimal there, but that is luck rather than method, and the unit on relaxation shows cases where rounding is feasible and far from optimal.

Not an integer program: a linear program the modeller intends to round. If integrality is not written into the program it is not part of the problem, whatever anyone plans to do with the output. The solver optimises what it is given.

The most common account of integer programming is that you solve the linear program and round. It is wrong in two separate ways, shown concretely below.

Rounding can be infeasible. In the example above the continuous optimum is $(15/7,18/7)\approx (2.14,2.57)$. Round to nearest, giving $(2,3)$, and check the first constraint: . The plan violates a constraint outright. Rounding moved the point off the region, and nothing in the rounding step could notice.

Rounding can be feasible and wrong. Consider

The relaxation pushes everything into $x_2$: $x_2=21/11\approx 1.909$, $x_1=0$, value $\approx 19.09$. Round down to $(0,1)$, which is feasible, value $10$. But $(1,1)$ satisfies $10+11=21\le 21$ and has value $11$, which is better. The rounded answer was feasible, plausible, and not optimal, and no amount of care in the rounding would have found the improvement, because it required increasing a variable the relaxation had set to zero.

Why this keeps happening. The continuous and integer optima are answers to different questions. The constraints binding at one need not bind at the other, so there is no reason the integer optimum should be near the fractional one. In larger problems they can be far apart.

What the relaxation is actually for. Not the answer. A bound, and a starting point for methods that search properly. That is the subject of its own unit, and the distinction between a bound and an answer is the thing to carry there.

1. A bakery decides how many ovens to install, how many kilograms of flour to buy weekly, and whether to lease a delivery vehicle. Classify each variable and say what kind of program results.

2. For $max2x_1+x_2$ subject to $4x_1+3x_2\le 12$, $x_1,x_2\ge 0$ and integer, find the continuous optimum and then the integer optimum by checking feasible whole-number points. Are they at the same place?

3. Explain why adding integrality to a variable measuring litres of liquid is usually a modelling error rather than a precaution.

4. A colleague says the feasible set of an integer program is a polyhedron with some points removed, so convexity still applies to what is left. What is wrong with that?

5. Give a situation needing a general integer variable that is not binary, and say what writing it as binary would forbid.

An integer program is a linear program with some variables restricted to whole numbers. The restriction is part of the program, not a plan for the answer.

Pure integer when every variable carries it, mixed-integer when only some do, the usual case, and binary when the integer variables are confined to zero and one.

The feasible set becomes the whole-number points inside the polyhedron: not convex, not connected, no interior. With bounded integer variables it is finite, so an optimum exists whenever a feasible point does.

What is lost is the geometry. The optimum need not be at a vertex and generally is not, convexity arguments do not apply, and there is no local step from one feasible point to a neighbour. The simplex method solves the relaxation, which is a different problem.

What is kept is linearity of the objective and constraints, and feasibility by substitution.

Require integrality where a fractional value is meaningless, and nowhere else. It is expensive, an integer program can be out of reach at a size where a linear program is routine, and requiring it of a divisible quantity buys nothing while potentially excluding the genuine optimum.