Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 38 (Mathematics of Operational Research)

The dual linear program is the minimization problemIndeed, for $y\ge 0$ the optimization Lagrangian $c^{T}x+y^T(b-Ax)$ bounds the primal objective above on its feasible points. Its supremum over $x\ge 0$ is finite precisely when $A^{T}y\ge c$, and then equals $b^{T}y$. The two labelled parts below establish the relevant weak duality and strong duality conclusions.

For the subsequent infeasibility argument, introduce nonnegative slack variables $s$ and the convex coneThis is generated by the columns of $A$ and the coordinate vectors. Here is why this finitely generated cone is closed. Any representation with a minimal number of positive coefficients uses linearly independent generators: otherwise subtract a suitable multiple of a dependence until one positive coefficient vanishes, preserving nonnegativity. For each fixed independent selection of generators, its nonnegative combinations form a closed set, because the inverse coordinate map on its span is continuous. There are finitely many selections, so their union $C$ is closed. This is the closedness of finitely generated cones used in Farkas' lemma.

When the primal linear program is infeasible, $b\notin C$. Let $p$ be the nearest point of $C$ to $b$, and set $h=p-b$. The minimizing property gives $h^T(z-p)\ge 0$ for every $z\in C$. Taking $z=0,2p$ gives $h^{T}p=0$. ConsequentlyIn particular $h\ge 0$ and $A^{T}h\ge 0$. Rescaling $h$ by the positive number $-h^{T}b$ produces the requested Farkas' lemma certificate:Now a feasible point of the relaxed inequalities would satisfySince ${\lambda }^{T}b=-1$, the sum of the nonnegative ${\lambda }_i$ is positive. Thus robust infeasibility under uniform constraint relaxation givesThe ellipsoid method makes progress by reducing the volume of a containing ellipsoid. A nonempty linear polyhedron may have empty interior, so small volume alone cannot certify that the original system is infeasible. Relaxing the inequalities remedies this difficulty, but must not make an infeasible system appear feasible. The displayed positive gap proves exactly that sufficiently small relaxations preserve infeasibility. For rational input, determinant bounds give a Farkas' lemma certificate of polynomial encoding length, so a sufficiently small rational relaxation can be chosen from the input encoding length. Together with a bounding box and bounds on the volume of a relaxed feasible system, this lets the ellipsoid method distinguish infeasibility from a feasible system of very small or zero original volume in polynomial time. The certificate argument alone does not assert a polynomial precision bound for arbitrary unencoded real coefficients.

Fix a primal feasible point $x_0$. For every dual feasible point $y$, nonnegativity and the primal and dual inequalities giveHence the dual objective is bounded below by $c^T{x}_0$ wherever it is feasible, which is weak duality. This is the meaning of “bounded” in this assertion; it does not say that the dual feasible set is bounded, or that it is nonempty. For example, with $A=0$, $b=0$, $c=1$ and a single variable, the primal is feasible and unbounded above, while its dual would require $0\ge 1$ and is infeasible.

Let the finite primal supremum be $v$. First it is attained. The setis a finitely generated cone, hence closed by the argument in the root Solution. For a sequence of primal feasible points whose values approach $v$, the pairs $(b,c^{T}x)$ belong to $K$. Their limit $(b,v)$ therefore belongs to $K$. It gives a feasible point $x_{\ast }$ with $c^T{x}_{\ast }\ge v$, so necessarily $c^T{x}_{\ast }=v$.

Let $I$ index the tight primal inequalities at $x_{\ast }$ and let $Z$ index its zero coordinates. Consider the closed convex cone generated by $A_i^T$ for $i\in I$ and $-e_j$ for $j\in Z$. If $c$ were outside this cone, separation from a closed convex cone would give a direction $d$ withFor sufficiently small positive $\delta$, $x_{\ast }+\delta d$ remains a feasible point: the active constraints have the required signs, and every inactive constraint retains its positive slack. Its larger objective contradicts optimality. Therefore there are $y_i\ge 0$, supported on $I$, and ${\mu }_j\ge 0$, supported on $Z$, such thatThis makes $y$ a dual feasible point. Moreover, the support restrictions giveTogether with weak duality, this proves strong duality and dual attainment:

Encode a vertex of a polytope by three bits: bit $j$ records whether the lower or upper bound of coordinate $j$ is tight. Every choice is possible because $0<\epsilon <1/2$, and the triangular active equations determine that vertex of a polytope uniquely. Its three adjacent vertices of a polytope are obtained by changing one bit. The geometric Bland pivoting rule specified here chooses the smallest-index active facet that can be left while increasing $x_3$. It produces the following path; the final column records the facet left on arrival at the next vertex of a polytope:For example, at the origin all three outgoing edges improve the objective, but leaving facet 1 has priority. At bit string $110$, switching bit 2 decreases $x_3$, so the rule switches bit 1, leaving facet 2. At $010$, neither of the earlier-coordinate switches improves $x_3$, so the rule finally leaves facet 5. The upper face reverses the direction in which changes of $x_2$ improve $x_3$, and the remaining three horizontal pivots follow. The objective values in the table are strictly increasing for the stated range of $\epsilon$.

Thus the simplex method takes seven pivots although the optimum is directly adjacent to the starting point. The same Klee-Minty cube in $n$ dimensions has $2n$ inequalities and $2^n$ vertices of a polytope. On its lower last-coordinate face, increasing $x_n$ means increasing $x_{n-1}$, and the first $n-1$ coordinates follow the corresponding lower-dimensional path before the last-coordinate facet can be left. On the upper face, increasing $x_n$ means decreasing $x_{n-1}$, and the smallest-index rule traverses that path in reverse. The reverse-path assertion follows by the same induction, interchanging maximization and minimization on each face. Hence the pivot count satisfies $T_n=2T_{n-1}+1$, $T_1=1$, andThe usual Bland pivoting rule prevents cycling, including degenerate pivots, but this exponential example shows that it does not give a polynomial worst-case pivot bound. For rational fixed $\epsilon$, the constraints have polynomial encoding length. Arithmetic cost per pivot does not remove the exponential obstruction.

For a lower bound that applies to every pivot choice, use $0\le x_i\le 1$ and maximize ${\sum }_{i=1}^n{x}_i$, starting at the origin. Each edge of this cube changes only one coordinate, whereas the unique optimal vertex of a polytope is $(1,\dots ,1)$. Every coordinate must therefore be changed along at least one edge. Every route of adjacent pivots takes at least $n$ pivots, and every strictly improving route takes exactly $n$.

For Dantzig pivot rule, the rate is the objective increase per unit entering nonbasic variable, as in standard reduced cost pricing. Rescale the three coordinates byThe transformed linear program still maximizes $y_3$, now with boundsWhen the active facet for coordinate $i$ is freed, the other active equations give $|d{x}_3/d{x}_i|={\epsilon }^{3-i}$. The positive rates per unit $y_i$ are thereforefor $i=1,2,3$, respectively. Equivalently, use the nonnegative lower- and upper-bound slack variables of these displayed, normalized inequalities: freeing coordinate $i$ changes its entering slack by $|d{y}_i|$. Thus Dantzig pivot rule chooses the lowest coordinate index among improving edges and follows the same seven-pivot path. In $n$ dimensions set $y_i={\epsilon }^{2(n-i)}{x}_i$; the rates ${\epsilon }^{-(n-i)}$ give the same $2^n-1$ pivots. These statements concern coordinate/slack pricing, not objective increase per unit Euclidean edge length, which defines a different pivot rule.

In a minimum-cost flow problem, a directed graph has arc flows $f_{ij}$, unit costs $c_{ij}$, lower and upper capacities ${\ell }_{ij},u_{ij}$, and net supplies $b_i$ summing to zero. The linear program minimizes ${\sum }_{ij}{c}_{ij}{f}_{ij}$ subject to the flow balances ${\sum }_j{f}_{ij}-{\sum }_j{f}_{ji}=b_i$ and ${\ell }_{ij}\le f_{ij}\le u_{ij}$.

Give each graph vertex a network dual potential ${\pi }_i$. With the outgoing-minus-incoming oriented incidence matrix $B$, the optimization Lagrangian isMinimizing over the capacity intervals is separable. A candidate feasible flow minimizes this optimization Lagrangian if it takes its lower bound whenever the network reduced cost is positive, its upper bound whenever that network reduced cost is negative, and any allowed value when that network reduced cost is zero. Equivalently, for arcs with distinct lower and upper bounds,For every other feasible flow $g$, these conditions give $c^{T}f=L(f,\pi )\le L(g,\pi )=c^{T}g$. This proves the Lagrangian sufficiency theorem certificate, rather than merely stating the capacitated flow optimality conditions.

Put $t=f_{23}$. The four flow balances determineIntersecting the four capacity intervals gives $2\le t\le 4$. In particular,is a feasible flow. Write $C=c_{12}+c_{23}+c_{34}+c_{41}$. Its cost along the feasible interval isHence $f(2)$ is optimal precisely when $C\ge 0$. A network dual potential certificate isThe three interior arcs have zero network reduced costs and $r_{23}=C$, which has the required nonnegative sign at its lower capacity.

For the network simplex algorithm, start with the network simplex tree basis consisting of arcs $12,34,41$, and fix nonbasic arc $23$ at its lower bound 2. These are exactly the potentials just found. If $C\ge 0$, no improving pivot is needed. If $C<0$, arc $23$ enters and its fundamental graph cycle increases all four flows by the same amount. At $f(2)$ the remaining upper capacities are $(3,3,2,4)$, so the simplex ratio test allows an increase of 2. Arc $34$ reaches its upper bound and leaves the tree. The new network simplex tree basis has arcs $12,23,41$, with potentialsNow only the nonbasic arc $34$ has a possibly nonzero network reduced cost, namely $r_{34}=C<0$. It is at its upper bound, so the sign is optimal. Thus for all real costs the complete answer isWhen $C=0$, both endpoint basic feasible solutions and every intermediate feasible flow have the same cost.

To count basic solutions, a network simplex tree basis omits one arc of the four-cycle and fixes that arc at either bound. The possibilities areThere are eight tree/bound basic representations, seven distinct basic flow vectors, and two basic feasible solutions. The distinction in the first count matters: the upper bounds on $12$ and $23$ both give the identical flow $(8,5,6,7)$ at $t=5$. Thus if “basic solutions” counts vectors rather than basis representations, the answer to (i) is seven; the frequently used count of basis/bound choices is eight. The answer to (ii) is unambiguously two, since only $t=2,4$ satisfy all capacities.

Assume the finite graph is connected, as is necessary for a spanning tree to exist. For a disconnected graph, the same procedures operate separately on its connected components of a graph and produce a minimum spanning forest.

Let $T$ be a minimum spanning tree. If it omitted the unique lightest edge $e$ across the specified cut of a graph, adding $e$ would make exactly one graph cycle: the graph path in $T$ between its endpoints, followed by $e$. Since those endpoints are on opposite sides of the cut of a graph, that graph path contains another crossing edge $f$. Distinct weights give $w_f>w_e$. The graph $T+e-f$ is still a spanning tree, but has smaller total weight, contradicting minimality. Thus every minimum spanning tree contains $e$, the minimum spanning tree cut property.

Prim algorithm starts from one graph vertex, repeatedly choosing the lightest edge from the reached graph vertices to an unreached graph vertex. Connectivity ensures that such an edge exists until all graph vertices have been reached. Each choice adds one new graph vertex and creates no graph cycle. By the minimum spanning tree cut property, every chosen edge belongs to every minimum spanning tree. After $|V|-1$ choices the selected edges form a spanning tree, necessarily a minimum spanning tree.

For Kruskal algorithm, suppose the next accepted edge $e$ joins two different components of the current forest, and let $S$ be one of those components. No previously considered lighter edge crosses $S$: an accepted one already joins graph vertices within a current component, while a rejected one had its endpoints connected when it was rejected and therefore still has them in a single current component. Consequently $e$ is lightest across the cut of a graph defined by $S$. The minimum spanning tree cut property again places every accepted edge in every minimum spanning tree. At termination the accepted forest must be connected, since otherwise a crossing edge of the original connected graph would have been accepted when considered. It is therefore a minimum spanning tree.

This reasoning also proves the minimum spanning tree is unique. Either procedure produces a spanning tree all of whose $|V|-1$ edges belong to every minimum spanning tree; another minimum spanning tree cannot have any different edge.

For the minimum spanning tree cycle property, suppose a spanning tree $T$ contained the unique heaviest edge $e$ of a graph cycle $C$. Removing $e$ splits $T$ into two components. The remainder of $C$ connects the endpoints of $e$, so it contains an edge $f$ across these components. This edge cannot belong to $T-e$, and $w_f<w_e$. Hence $T-e+f$ is a lighter spanning tree. Thus no minimum spanning tree contains $e$.

Finally consider the reverse-delete algorithm, processing edges from largest to smallest weight. Whenever an edge is retained because its deletion would disconnect the current graph, it is a bridge in a graph; deleting other edges later cannot create an alternative path around it, so it remains a bridge in a graph. If a currently processed edge $e$ is deletable, it lies on a current graph cycle. None of that graph cycle's other edges can be an earlier retained heavier edge, since those are bridges in a graph. Thus all other edges on the graph cycle are lighter than $e$. The minimum spanning tree cycle property says that deleting $e$ removes no edge of any minimum spanning tree of the original graph. Throughout, connectivity and the presence of the unique minimum spanning tree are preserved. At termination a surviving graph cycle is impossible: any of its edges was deletable when considered, since that entire surviving graph cycle already existed then. The final connected graph is a tree, and hence is exactly the minimum spanning tree.

Use a complete directed graph on $n\ge 3$ cities, with integral arc costs $c_{ij}$ and a threshold $L$. A symmetric cost matrix also represents the undirected travelling salesman problem by orienting a tour. Let the binary variable $x_{ij}$ indicate that city $j$ follows city $i$, and forbid self-arcs. The decision integer programming formulation asks whether the following system has a solution:The in-degree and out-degree equations make the selected arcs a cycle cover of a directed graph. Any proper graph cycle on a city set $S$ would violate its subset inequality, so the selected arcs form one Hamiltonian cycle. Conversely, a Hamiltonian cycle obeys every inequality: a proper subset cannot contain all the successor arcs of its graph vertices. Thus the binary feasibility system is equivalent to the decision travelling salesman problem. The subset formulation has exponentially many inequalities, which is harmless for this formulation; verifying a proposed tour does not require listing them.

To call this decision problem NP-complete means two separate things. It belongs to NP: a yes-instance has a polynomial-length certificate in computational complexity, namely the cyclic ordering of the cities, and a deterministic algorithm checks distinct visits, the return to the start, and the total cost in polynomial time in the binary input length. It is also NP-hard: every decision problem in NP has a polynomial-time many-one reduction to it, preserving yes and no answers. This is a statement about worst-case computation on finite encodings, not a proof that every individual tour is hard to find or that no polynomial algorithm exists; that last conclusion would require $\mathrm{P}\ne \mathrm{NP}$.

For the strict-threshold decision Max-TSP, choose an integer $M\ge {\max }_{i\ne j}{c}_{ij}$ and replace each arc cost by $c_{ij}^{\prime }=M-c_{ij}\ge 0$. Every tour uses exactly $n$ arcs, soSet the new threshold to $L^{\prime }=nM-L-1$. Its encoding length, the transformed matrix's encoding length and the computation time are all polynomial in the original input length. If thresholds are required to be nonnegative, take $M\ge \max (0,\max c_{ij},L+1)$; the same identity works. Symmetry of costs is preserved. This is a polynomial-time many-one reduction from decision travelling salesman problem to decision Max-TSP, so the latter is NP-hard. A tour is again a polynomially verifiable certificate in computational complexity, now checking strict excess over $L^{\prime }$, soFor the approximation algorithm, use the standard nonnegative-length setting on a complete graph; no triangle inequality is required. Solve the maximum-weight assignment problem with diagonal assignments forbidden, for example by applying the Hungarian algorithm to the negative weights. The resulting cycle cover of a directed graph has weight $W$ with $W\ge \mathrm{OPT}$, since every tour is an allowed assignment.

If it already has a single graph cycle, it is an optimal tour. Otherwise remove a least-weight arc from each graph cycle. A graph cycle of $r\ge 2$ arcs and weight $W_r\ge 0$ loses at most $W_r/r\le W_r/2$. The remaining arcs form vertex-disjoint graph paths covering all cities. Join the endpoint of each graph path to the start of the next, cyclically. The required arcs exist by completeness, and their nonnegative weights cannot diminish the retained weight. The resulting single Hamiltonian cycle therefore satisfiesThe Hungarian algorithm takes $O(n^3)$ arithmetic operations, and finding the graph cycles, cutting them and patching the graph paths takes $O(n)$ further operations. For rational or integer weights these operations have polynomial encoding length, giving polynomial time. With symmetric costs, the same directed construction is a valid undirected tour after forgetting its orientation. This is the cycle-cover patching half-approximation for Max-TSP.

Nonnegativity is essential to this multiplicative guarantee. If arbitrary signed weights were allowed, giving every arc cost $-1$ would make every tour have weight $-n$, while half the optimum is $-n/2$. No tour could achieve the requested bound. Thus “length” has its usual nonnegative meaning in the approximation assertion.

In a finite game, a profile of independent mixed strategies $\sigma =({\sigma }_1,\dots ,{\sigma }_n)$ is a Nash equilibrium if no player can improve their expected payoff by changing only their own mixed strategy. In symbols,Because expectation is linear in a player's own mixed strategy, checking this inequality for all their pure strategies suffices. Nothing requires the players' payoffs to sum to zero.

For the symmetric finite game, write $e_i(p)=e(i,p)$ and $\bar{e}(p)={\sum }_i{p}_i{e}_i(p)$. Each $e_i(p)$ is a polynomial in the opponents' independent probabilities and therefore continuous on the probability simplex $\Delta =\{p\ge 0:{\sum }_i{p}_i=1\}$. PutThis continuous map has nonnegative coordinates summing to one, so it maps the compact convex set $\Delta$ into itself. The Brouwer fixed-point theorem gives $p=F(p)$. At that fixed point $r_i=p_{i}S$. If $S>0$, every $i$ in the strategy support has $r_i>0$ and therefore $e_i(p)>\bar{e}(p)$. Butwhereas every supported term would be strictly positive, a contradiction. Thus $S=0$, all pure payoffs are at most $\bar{e}(p)$, and their weighted average equals $\bar{e}(p)$. Every supported pure strategy is consequently a best response to the common opposing mixed strategy. The profile in which every player uses $p$ is a symmetric Nash equilibrium. This proves the gain-map proof of symmetric equilibrium for any finite number of players, including boundary fixed points of the probability simplex.

In the least unique bid auction, let $p$ be the common probability of bid 1. Bidding 1 wins only when the other two bids are both 2, and its winning payoff is $3-1=2$. Bidding 2 wins only when the other two bids are both 1, and its winning payoff is $3-2=1$. Hence the two expected payoffs areNeither symmetric pure strategy profile is an equilibrium: against two bids of 1 a deviation to 2 earns 1 instead of 0, and against two bids of 2 a deviation to 1 earns 2 instead of 0. An interior symmetric equilibrium must make the two expected payoffs equal. Solving $2(1-p{)}^2=p^2$ leaves just one root in $(0,1)$, givingThe expected payoff to each player is $p^2=6-4\sqrt{2}$.

To count all nonsymmetric Nash equilibria, let $p_i$ be player $i$'s probability of bidding 1. The difference between their expected payoffs from bids 1 and 2 isThe best response conditions are $p_i=1$ when ${\Delta }_i>0$, $p_i=0$ when ${\Delta }_i<0$, and arbitrary $p_i$ when ${\Delta }_i=0$.

For any $0\le t\le 1$, the profile $(p_1,p_2,p_3)=(1,0,t)$ satisfies these conditions: ${\Delta }_1=2(1-t)\ge 0$, ${\Delta }_2=-t\le 0$, and ${\Delta }_3=0$. Thus every permutation of this profile is a Nash equilibrium. At $t=0,1$ these give the six pure profiles with at least one bid of each kind; for $0<t<1$, one player mixes freely and the other two use opposite pure strategies.

There are no other nonsymmetric equilibria. If all three probabilities are interior, every ${\Delta }_i$ must vanish. Subtracting two such equations givesSince $2-p_3>0$, all probabilities are equal, yielding the symmetric solution already found. If exactly two players mix and the third uses bid 2, either mixer strictly prefers bid 1 because $\Delta =2(1-p_j)>0$. If the third uses bid 1, either mixer strictly prefers bid 2 because $\Delta =-p_j<0$. Both cases are impossible. If exactly one player mixes, their indifference requires the other players to use opposite bids. Finally, with no mixing, the all-equal pure profiles fail and the remaining six satisfy the best response conditions.

Consequently the complete Nash equilibrium set consists of the single symmetric mixed profile together with the six closed one-parameter families given by permutations of $(1,0,t)$. Their endpoints overlap at the six pure equilibria. In particular,Counting only the six pure ones would miss the interior points of these families in the two-bid three-player least unique bid auction.