Past exam of the integer programming course of the University of Oxford / 2010 (B22a, DMAB 0282, DCOM 0282, DMCN 0282)

The two pieces of a one-tree can be optimized independently. Compute a minimum spanning tree $F$ on vertices $\{2,\dots ,n\}$ and choose the two cheapest distinct edges incident to vertex one. Return their union.

Every feasible one-tree contains such a spanning tree and such a pair, so its cost is at least the sum of these two independent minima. Their union is itself feasible, attaining that lower bound. This proves optimality.

Use Prim's algorithm for $F$: repeatedly add a cheapest edge crossing from the current tree to an unvisited vertex. The minimum spanning tree cut property makes each chosen edge safe. With the dense weight matrix of a complete graph, maintain the best connection to each unvisited vertex and select the least one by a scan. There are $n-2$ iterations with $O(n)$ work apiece. A further scan finds the two cheapest incident edges. Thus the total complexity is $\boxed{O(n^2)}$, with $O(n)$ additional working storage beyond the input matrix.

Delete vertex one and its two incident edges from a Hamiltonian cycle. The remaining edges form a Hamiltonian path through all other vertices, hence a spanning tree. Thus every tour is a one-tree, and both problems use the same edge-cost objective. The relaxation enlarges the feasible set, givingConversely, a one-tree in which every vertex has degree two is connected and two-regular, so it is a Hamiltonian cycle. Such a minimum one-tree therefore also solves the travelling-salesman problem. This is the one-tree travelling-salesman bound.

Write $ij$ for the undirected edge $\{i,j\}$. At the root of the branch and bound search, the minimum spanning tree on $\{2,3,4\}$ is $\{24,34\}$ of cost $6+4=10$. The cheapest edges incident to vertex one are $12,14$, of cost $3+7=10$. The root lower bound is therefore twenty, attained byIt is not a tour: vertex four has degree three and vertex three degree one.

A tour must omit at least one edge from $\{14,24,34\}$, since its degree at vertex four is two. Partition tours according to the first omitted edge in that ordered list. This gives three disjoint, exhaustive children, retaining included and excluded edges when recomputing the one-tree relaxation:

All tours belong to one of the three children, and no remaining child can improve the incumbent. ThereforeThe branching rule is motivated by a violated tour degree equation, rather than by an arbitrary costly edge. This is degree branching with a one-tree bound.

A totally unimodular matrix has the property that every square submatrix has determinant zero, one or minus one. This includes the one-by-one submatrices, so every entry belongs to $\{0,1,-1\}$.

Its importance is integrality of linear-programming vertices: if $A$ is totally unimodular and $b$ is integral, every vertex of $\{x:Ax\le b,x\ge 0\}$ is integral. Adding rows of the identity preserves total unimodularity. A nonsingular active basis therefore has determinant $\pm 1$ and an integer inverse by the cofactor formula, making its basic solution integral. Thus a finite optimum attained at a vertex of the linear programming relaxation gives an integer optimum without branching.

One sufficient condition is: entries belong to $\{0,1,-1\}$, each column has at most two nonzero entries, and any column with two has one $+1$ and one $-1$. This is the signed column condition for total unimodularity, satisfied by directed vertex-edge incidence matrices. It is sufficient, not necessary.

The constraints give the valid upper boundFor example $(x_1,x_2,x_3,x_4)=(0,1,3,4)$ satisfies every constraint: the first left side is four, the next three are three, five and two, and $x_4\ge 1$. Its objective is eight. Hence the upper bound is attained by an integer point, provingAll optimal solutions can also be identified. Equality forces $x_1=0$, $x_3=3$ and $x_2+x_4=5$. The remaining constraints reduce to $x_2\ge 1$ and $x_4\ge 1$. Thus exactly four integer optima occur:This is an optimality certificate by a valid relaxation bound and a feasible integer solution; no assumption of total unimodularity is needed. The source's ${\mathbb{Z}}_{+}$ denotes nonnegative integers, as is also necessary for its assignment equations in the next question.

The retained integer assignment constraints have only two feasible matrices,Their $(a\cdot x,b\cdot x,c\cdot x)$ totals are $(4,5,10)$ and $(3,6,8)$ respectively. For nonnegative Lagrange multipliers $\lambda ,\mu$, add $\lambda (3.5-a\cdot x)+\mu (5.5-b\cdot x)$ to the maximization objective. Each feasible point gains a nonnegative amount, so maximizing over the retained assignment set gives an upper bound:The Lagrangian dual problem minimizes this convex piecewise-linear function over $\lambda ,\mu \ge 0$. Put $d=\lambda -\mu$; every real $d$ can occur. The two affine terms average to nine, so their maximum is at least nine, with equality exactly when $d=2$. ThusNeither integer assignment satisfies both side constraints: $D$ violates the $a$ bound and $O$ the $b$ bound. The finite dual bound is therefore not evidence that the integer primal is feasible. The following part shows why this Lagrangian relaxation of an assignment with side constraints has a finite value anyway.

The assignment equalities parameterize every feasible matrix of the linear programming relaxation asThe side totals and objective becomeThe first side constraint gives $t\le 1/2$ and the second gives $t\ge 1/2$, so the relaxation has the unique feasible pointDirect elimination of the assignment equalities has solved this one-dimensional linear program. Its value matches the Lagrangian dual problem value because the retained assignment polytope is the convex hull of the two integer assignments; it does not make the side-constrained integer problem feasible.

With the new right sides, the dual function isTake $\lambda =\mu =t\to \infty$. Then ${\theta }_{\mathrm{new}}(t,t)=10-t\to -\infty$, so the minimization dual is unbounded below:By weak duality, any feasible integer point with finite objective would have to have objective at most every dual value, which is impossible. Thus the modified integer program is infeasible and has no optimal solution. This is an infeasibility certificate from an unbounded Lagrangian dual.

There is also a direct certificate: the assignment equalities force $(a+b)\cdot x=9$, while the new bounds force it to be at most $3+5=8$. Even the modified linear relaxation is infeasible. The earlier $3.5,5.5$ problem also had no integer solution, but there its fractional feasible point kept the dual value finite.