Past exam of the integer programming course of the University of Oxford

Source release: Oxford examination archive. The cover dates this examination to 9 June 2011, 9.30–11.00am. All 12 answer parts are solved below. The two numbered conditions inside 3(c) are hypotheses of its single optimality proof.

Use vertices $1,2,3,4,5$. Reading each symmetric off-diagonal pair once gives the edge setHere $ij$ abbreviates the undirected edge $\{i,j\}$. The diagram displays these seven edges and no loops. The displayed square matrix is an adjacency matrix in the usual terminology: its two indices both label vertices. A vertex-edge incidence matrix would instead have one index for vertices and one for edges. This explains how the source's node-node terminology is being read.

Use the maximum-weight version of Kruskal's algorithm: sort the edges by decreasing weight, start with no edges, and add an edge exactly when it joins different current connected components of a graph. For the maximum over all forests, skip negative-weight edges; removing a negative edge always preserves a forest and increases its weight. Zero-weight edges are optional. The matroid greedy algorithm for the graphic matroid proves this procedure optimal; it maximizes over independent sets rather than requiring a full basis.

The positive edges are considered in the orderAdmit $12$ and $15$. Reject $25$, since it closes the triangle on $1,2,5$. Admit $23$. Reject $35$, since $3$ and $5$ are already joined by the path $3,2,1,5$. Skip both negative edges incident with vertex four. ThereforeVertex four is isolated. Requiring a spanning tree would force a negative edge and solve a different optimization problem. With a disjoint-set data structure, sorting dominates the running time, giving $O(|E|\log |E|)$.

On a finite ground set $E$, a submodular rank function is a set function $r:2^E\to \mathbb{R}$ with the following properties:These are normalization, monotonicity, submodularity, and unit integer increments. In particular its values are nonnegative integers with $r(A)\le |A|$. Equivalently, one can require an integer-valued normalized monotone submodular function with $r(\{e\})\le 1$: diminishing returns then bounds every marginal increment by one. A general real-valued submodular function need not be a matroid rank.

The associated matroid isThus the graph's edges are the ground set, and the members of $\mathcal{I}$ are its matroid independent sets.

For the specified rank, if $(V,A)$ is a forest, $A$ itself is an allowed choice in the rank maximum, so $r(A)=|A|$. Conversely, if $r(A)=|A|$, some forest $F\subseteq A$ has $|F|=|A|$. Finiteness forces $F=A$, so $(V,A)$ is a forest. Hence the independent sets are exactly all forests in $G$, including the empty forest and forests with isolated vertices.

The matroid independence axioms can also be checked directly. The empty set is a forest, and deleting edges cannot create a cycle. For exchange, let forests $I,J$ have $|I|<|J|$. If every edge of $J$ joined vertices within one component of $(V,I)$, its restriction to each component $S$ would have at most $|S|-1$ edges. Summing would give $|J|\le |I|$, a contradiction. Thus some edge of $J\setminus I$ joins two components of $I$ and can be added without creating a cycle. This proves augmentation and identifies $M$ as the graphic matroid.

For $A\subseteq E$, write $x(A)={\sum }_{e\in A}{x}_e$, and let $\kappa (A)$ count the connected components of $(V,A)$, including isolated vertices. A maximal forest in each component has one fewer edge than vertices, so $r(A)=|V|-\kappa (A)$. The required forest polytope isWe prove both inclusions, using the matroid independence polytope argument explicitly.

If $I$ is a forest, $I\cap A$ is an independent subset of $A$, so $1_I(A)=|I\cap A|\le r(A)$. Its indicator is nonnegative. All convex combinations of these indicators therefore lie in $P$.

For the converse, take any real objective vector $c$. List just its positive-weight edges as $e_1,\dots ,e_k$ with $c_1\ge \cdots \ge c_k>0$, put $c_{k+1}=0$, and set $S_i=\{e_1,\dots ,e_i\}$. Run the forest greedy algorithm on these edges and call the output $I$. At every prefix, the accepted edges form a maximal forest of $(V,S_i)$, soIndeed a previously rejected edge still has its endpoints joined later; therefore no rejected prefix edge can augment the chosen forest. A maximal forest spans every prefix component and has the stated size.

For every $x\in P$, dropping nonpositive objective terms and telescoping now givesThe last equality uses the same telescoping identity for the greedy indicator. If there are no positive coefficients, the empty forest attains the bound zero. Thus every linear objective over $P$ is maximized by a forest indicator.

The singleton inequalities give $0\le x_e\le r(\{e\})\le 1$, so $P$ is compact. The convex hull $Q$ of the finitely many forest indicators is also compact. If some $x\in P$ were outside $Q$, the finite-dimensional separating hyperplane theorem would give $c$ with $c^{T}x>{\max }_{y\in Q}{c}^{T}y$, contradicting the bound just proved. Therefore $P\subseteq Q$, completing the convex-hull proof.

An equivalent system indexed by vertex sets iswhere $E(S)$ contains all edges with both ends in $S$. The rank system implies this since $r(E(S))\le |S|-1$. Conversely, split any edge set $A$ into its vertex components $S_1,\dots ,S_t$. Nonnegativity and the vertex inequalities give $x(A)\le {\sum }_{j}x(E(S_j))\le {\sum }_j(|S_j|-1)=|V|-\kappa (A)$. Hence this second system describes the same polytope.

Let item $j$ have weight $a_j$ and profit $p_j$. Define $D(j,b)$ as the largest profit obtainable from the first $j$ items with capacity at most the nonnegative integer $b$. Set $D(0,b)=0$. The last item is either absent or present once, giving the dynamic programming recursionThe two alternatives exhaust the feasible binary decisions. In the second alternative, deleting item $j$ leaves exactly the smaller subproblem with capacity $b-a_j$, which proves the recurrence.

Fill rows $j=1,\dots ,4$, and within each row capacities $b=0,\dots ,7$. Store which alternative attains each maximum. Backtrack from $(4,7)$: when exclusion was chosen, set $x_j=0$ and move to $(j-1,b)$; when inclusion was chosen, set $x_j=1$ and move to $(j-1,b-a_j)$. Ties may be resolved either way. Thus the stored values yield an actual optimal selection, not just its objective value.

For $n$ items and capacity $B$, the algorithm uses $O(nB)$ arithmetic operations and $O(nB)$ space with the full backtracking table. It is a pseudo-polynomial algorithm, since $B$ is a numerical capacity rather than its bit length. A value-only version can use one row, but must update capacities in decreasing order to avoid reusing the same item.

Applying the recurrence in source item order gives the complete tableAt $(4,7)$ inclusion wins, since $25+D(3,2)=40>D(3,7)=39$. Thus $x_4=1$ and the residual capacity is two. Items three and two are too heavy for it, and item one exactly fits. ConsequentlyIts weight is $2+5=7$. The recurrence proves that no binary selection with capacity seven has greater profit.

For each branch and bound node, relax the unfixed binary variables to $[0,1]$. The fractional knapsack problem is solved by decreasing profit-to-weight ratios, hereIts value is an upper bound for the node's integer optimum. At the root, greedy filling gives $x=(1,1,1/2,0)$ and upper bound $\boxed{43.5}$, so branch on $x_3$.

In the child $x_3=0$, the relaxed optimum is $(1,1,0,2/5)$ with value $43$. Branch on $x_4$. Taking $x_4=1$ leaves capacity two, giving the integral solution $(1,0,0,1)$ of value $40$, our incumbent. Taking $x_4=0$ gives the integral relaxed optimum $(1,1,0,0)$ of value $33$, so that node is closed.

In the child $x_3=1$, item four cannot be selected in any integer feasible solution, since their combined weight is nine. Fixing $x_4=0$ is therefore valid binary feasibility propagation. Its LP optimum is $(1,1/3,1,0)$ with value $42$. Branch on $x_2$. The child $x_2=1$ leaves no residual capacity and has integral solution $(0,1,1,0)$ of value $39$. The child $x_2=0$ has integral solution $(1,0,1,0)$ of value $36$. Both are below the incumbent.

The complete short search isAll integer feasible solutions lie in these branches, and every terminal node is integral with value at most forty. Therefore the LP bounds and incumbent certify $\boxed{z_{\mathrm{IP}}=40}$ independently of the dynamic program.

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

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.