Practice: Integer Programs

Variables and restrictions.

Clinic commissioning. Four binary variables $y_1,\dots ,y_4\in \{0,1\}$, with $1$ meaning commissioned. Running three-fifths of a clinic is not a plan.

Nursing hours. Continuous, $h_i\ge 0$. Hours divide, $37.5$ hours is an ordinary quantity, so no integrality.

Consumables by weight. Continuous, $w\ge 0$. Weight is divisible.

Agency staff. A general integer variable $a\in \mathbb{Z}$ with $0\le a\le 6$. Indivisible, but not binary: hiring four is meaningful, so restricting to $\{0,1\}$ would forbid something the situation allows.

Classification. Binary, general integer and continuous variables together: a mixed-integer program.

The feasible set. Not a polyhedron. Take the polyhedron defined by the linear constraints, then keep only the points whose clinic and staffing coordinates are whole numbers. The result is a family of slices, for each of the $16$ clinic combinations and each of the $7$ staffing levels, a continuous region in the remaining coordinates. It is not convex and not connected.

What that costs. The optimum need not sit at a vertex of the underlying polyhedron, convexity arguments do not apply, and the simplex method alone will not produce an implementable answer: relaxed, it would return $y_1=0.62$, which is not an instruction anyone can follow.

On what was left continuous. Making hours or consumables integer would look tidier and would be a modelling error. It imposes restrictions the situation does not, raises cost sharply, and may exclude the true optimum.

Check the proposed answer first. $(2,3)$ against the first constraint: . Infeasible. The plan violates a constraint outright, so it is not the integer optimum and not a plan at all.

The true integer optimum. Checking feasible whole-number points: $(2,2)$ gives $4+6=10\le 12$ and $6+2=8\le 9$, feasible, value $4$. $(1,3)$ gives $2+9=11\le 12$ and $3+3=6\le 9$, feasible, value $4$. $(0,4)$ gives $12\le 12$ and $4\le 9$, feasible, value $4$. $(3,0)$ gives $6\le 12$ and $9\le 9$, feasible, value $3$. The optimum is $4$, attained at three points.

The method is wrong, not merely unlucky. Rounding moves a point off the region, and nothing in the rounding step can detect that, checking feasibility afterwards is already more work than rounding claimed to save. It also fails in the other direction: a rounded point can be feasible and still beaten by a plan rounding cannot reach, because rounding only adjusts each coordinate to a neighbour.

The deeper error in the first sentence. An integer program is not a linear program whose answer must be whole. Integrality is a restriction in the program, and it changes the feasible set from a polyhedron into the whole-number points inside it, not convex, not connected, no interior. The optimum need not be at a vertex, and here it is not: $(2,2)$, $(1,3)$ and $(0,4)$ are interior lattice points, not corners of the polygon.

What follows for practice. The continuous answer is still useful, as a bound. It tells you no integer plan exceeds $33/7\approx 4.71$, and since we found a plan with value $4$ and values are whole here, $4$ is optimal. That is the correct use of the relaxation, and it is a different thing from rounding it.

Why model A is fast. Its feasible set is a polyhedron, and the optimum of a linear objective over a polyhedron sits at a vertex. That reduces the search to a finite set of algebraically describable points, and the simplex method walks between adjacent ones improving each step. The geometry does the work.

Why model B is slow. Integrality destroys that geometry. The feasible set becomes the whole-number points inside the polyhedron, not convex, not connected, no interior. The optimum need not be at a vertex and generally is not, so the vertex reduction is unavailable and there is no local step with a direction to follow.

What replaces it. Methods that search systematically while pruning: solve the relaxation for a bound, branch on a fractional variable, and discard whole regions whose bound cannot beat the best plan found. The work is in the search tree, and forty integer variables give an enormous number of ways to fix them.

What the reported range means. Two numbers bracketing the optimum. The relaxation-based bound says no plan can be better than one end; the best integer plan found so far says the optimum is at least as good as the other. The solver has not failed. It is reporting exactly what it has proved, which is more informative than a single number with no guarantee attached.

Why it is not a defect. The difficulty is in the problem, not the software. There is no known method that solves integer programs in time comparable to linear ones, and this is believed to be intrinsic rather than a gap in current technique. A linear program with thousands of variables is routine; an integer program of the same size may be out of reach.

The practical consequence. Requiring integrality is a decision about computation as well as meaning. Impose it where a fractional value is meaningless, and nowhere else. Every unnecessary integer variable multiplies the search.