Past exam of the integer programming course of the University of Oxford / 2011 / 3

The assignment constraint matrix has one row for each outgoing sum and one for each incoming sum. The column for $x_{ij}$ has a one in outgoing row $i$ and incoming row $j$. Negate all incoming rows. Each column now has exactly one $+1$ and one $-1$, the node-arc incidence matrix of the directed bipartite graph from row vertices to column vertices.

Here is a direct proof that this signed matrix is totally unimodular. Consider any square submatrix and induct on its size. If a column has no nonzero entry, its determinant is zero. If a column has one nonzero entry, expansion along it reduces the determinant to plus or minus a smaller subdeterminant, hence to $0,1$ or $-1$. If every column has two nonzero entries, they have opposite signs, so each column sum is zero. The rows are then dependent and the determinant is zero. The size-one case is immediate, completing the induction.

Negating rows only changes signs of square subdeterminants. Thus the original assignment matrix is also a totally unimodular matrix. This proves the total unimodularity of directed incidence matrices argument directly in the required setting.

The integrality theorem for totally unimodular systems says that $\{x\ge 0:Ax=b\}$ has integral vertices when $A$ is totally unimodular and $b$ is integral. Redundant equalities cause no problem. Here the row sums also force $x_{ij}\le 1$, so every integral feasible vertex is a binary assignment. The bounded nonempty LP relaxation has an optimal vertex, and therefore an optimal assignment. Hence the assignment problem can be solved by linear programming without a binary search; dedicated methods such as the Hungarian algorithm also exploit its polynomial-time structure. Multiple optimal assignments can have fractional convex combinations, so the conclusion concerns an optimal integral vertex, not every optimal LP point.

For any feasible assignment, the unit row and column sums giveThus the transformed objective differs by the fixed constantEvery feasible assignment shifts by that same amount, so all objective comparisons and all optimal assignments remain unchanged. The calculation also holds for fractional feasible points of the assignment LP relaxation. The numbers $u_i,v_j$ are assignment dual potentials.

Since every reduced weight is nonpositive and every feasible variable is nonnegative, any feasible assignment $x$ satisfiesFor $x^{\ast }$, each selected entry has zero reduced weight, and each unselected entry has zero variable. Thus every product ${\bar{c}}_{ij}{x}_{ij}^{\ast }$ vanishes and equality holds:The two hypotheses therefore form one optimality certificate: the first provides a universal upper bound, and the second makes the proposed assignment attain it. This is weak duality plus complementary slackness for the maximization assignment problem. For a minimization assignment, the sign reverses: $u_i+v_j\le c_{ij}$ gives a lower bound, with equality on the selected arcs certifying optimality.

Use the minimization form in this part. Treat every diagonal arc as forbidden, not as a zero-cost loop. The assignment relaxation of the travelling salesman problem requires one incoming and one outgoing arc at each city but permits several disjoint directed cycles. Its optimum is a lower bound on the tour optimum.

At the root chooseFor every allowed arc, $u_i+v_j\le c_{ij}$. Their total is seven. The assignmentuses only tight arcs and has cost $1+1+1+2+2=7$. The minimization certificate from part (c) therefore provesIt is not a tour, because it has a three-cycle and a two-cycle.

Branch on the two-cycle. Every five-city tour omits at least one of $3\to 4$ and $4\to 3$, so the children $x_{34}=0$ and $x_{43}=0$ cover every possible tour. They may overlap, which does not invalidate the bounds.

For the child $x_{34}=0$, useThese satisfy $u_i+v_j\le c_{ij}$ on every allowed arc of that child and sum to ten. The tourhas cost $1+1+3+2+3=10$ and uses tight arcs, certifying that the child assignment bound is exactly ten.

For the child $x_{43}=0$, interchange the roles of cities three and four in those potentials. Its lower bound is again ten, attained bywith cost $3+2+3+1+1=10$. Thus both first-level assignment optima are already tours.

There is a useful direct interpretation of the improved bound. Split the cities into $A=\{1,2,5\}$ and $B=\{3,4\}$. A forbidden arc of the two-cycle forces an assignment arc from $B$ to $A$, and balance forces at least one from $A$ to $B$. Relative to the root potentials, each crossing arc has reduced cost $3-3/2=3/2$, so any child assignment costs at least $7+2(3/2)=10$.

The first branching therefore completes the search: each child's lower bound equals a feasible tour value. Hence