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

Introduce the nonnegative integer surplus variables $z_1=3x_1+x_2-4$ and $z_2=x_1+2x_2-4$. Solving these two equalities gives the optimal relaxed simplex dictionarywith objectiveThe printed tableau has a sign error in the first row: in equality-row form the coefficient of $z_2$ must be $+1/5$, rather than $-1/5$. The defining constraints and the printed objective row both confirm this correction. The second row, from which the required cut is obtained, is unaffected.

The cutting-plane method solves the linear programming relaxation and, if the optimum is fractional, adds an inequality valid for every feasible integer point but violated by that optimum. For an all-integer tableau rowwrite each coefficient as its integer part plus its fractional part. The quantity $x_B+{\sum }_j\lfloor a_j\rfloor z_j$ is an integer, while ${\sum }_j\{a_j\}{z}_j$ is nonnegative. Thus the integer is at most $\lfloor b\rfloor$, and subtraction gives the Gomory fractional cutIt retains every feasible integer point and cuts off the fractional basic point with all nonbasic $z_j=0$.

Apply this to the row $x_2+\frac{1}{5}{z}_1-\frac{3}{5}{z}_2=\frac{8}{5}$. Since $\{1/5\}=1/5$, $\{-3/5\}=2/5$ and $\{8/5\}=3/5$, the resulting valid inequality isMultiply by five and add an integer slack $w=z_1+2z_2-3\ge 0$. Its row is $w-z_1-2z_2=-3$. At the old relaxed optimum, $w=-3$ is negative, while the minimization objective coefficients $2/5,9/5$ remain nonnegative. This is the starting configuration for the dual simplex algorithm: retain dual feasibility and pivot to repair the negative basic value.

The cut row permits either $z_1$ or $z_2$ to enter. The dual ratio test givesThus $z_1$ enters and $w$ leaves. Solving the cut row and substituting givesSetting the nonbasic variables $z_2=w=0$ gives nonnegative basic values $z_1=3,x_1=2,x_2=1$. The new objective coefficients are nonnegative, so this is optimal for the cut relaxation. Its decision variables are already integer and satisfy the original inequalities. ThereforeIndeed the positive coefficients of both nonbasic variables make this relaxed optimizer unique. No additional cut is needed.

Let $x$ be an extreme point and consider its active constraints. Their row vectors span ${\mathbb{R}}^n$. Otherwise a nonzero vector $h$ is orthogonal to every active row. All inactive inequalities have strictly positive slack; since there are finitely many, a sufficiently small $\epsilon >0$ makes both $x+\epsilon h$ and $x-\epsilon h$ feasible. Their midpoint is $x$, contradicting extremality.

Choose $n$ independent active rows and write the corresponding equalities as $Bx=d$. The matrix $B$ has integer entries, so $\det B$ is a nonzero integer and $|\det B|\ge 1$. By Cramer's rule,where $B_j$ replaces column $j$ by $d$. Every entry of $B_j$ has absolute value at most $U$, even when $b$ is real. The determinant expansion has $n!$ terms, each with absolute value at most $U^n$. ThereforeThis proves the integer-matrix vertex coordinate bound; only the denominator determinant requires integrality.

For an exact finite-input ellipsoid method, the numerical data must have a specified encoding. In the standard model the input is the dimensions, the integer matrix and a rational right-hand side in binary, together with bounds derived from their encoding lengths. The vertex estimate above remains valid for arbitrary real $b$, but arbitrary unencoded reals do not by themselves specify an exact computational decision problem. Clear the rational row denominators to obtain an equivalent integer system, and let $V\ge 1$ bound the resulting integer coefficients and right-hand sides.

Two precautions make a feasibility account valid even for unbounded or lower-dimensional polyhedra. First, nonempty polyhedra need not have extreme points. Nevertheless they have a feasible point in the box $[-R,R{]}^n$ with $R=n!V^n$. To prove this feasible-point box bound for a polyhedron with lines, intersect the polyhedron with an orthant containing one feasible point. Minimize the sum of the signed coordinates in that orthant. Its nonempty sublevel sets are closed and bounded, so the minimum is attained. The compact minimum face has an extreme point, which is also extreme in the orthant intersection. Its active rows come from the integer system and signed coordinate inequalities, still bounded by $V$. Applying the proved vertex estimate gives the box bound. This is an existence argument; the algorithm need not enumerate all orthants.

Second, a nonempty feasible set can have zero ambient volume. Use a small uniform relaxation with a certified rational infeasibility gap, rather than stopping on volume alone. For the integer system $\tilde{A}x\ge \tilde{b}$, putThe normalized integer Farkas infeasibility gap says that if the system is empty there is a multiplier $y\ge 0$ with ${\tilde{A}}^{T}y=0$, $1^{T}y=1$ and ${\tilde{b}}^{T}y\ge 1/D$. Its bound follows by maximizing the certificate's value in the normalized multiplier polytope: a vertex has at most $n+1$ positive entries, and a determinant denominator bounded by $D$. Any point satisfying the relaxed inequalities would then give the contradictionThus relaxation preserves emptiness. If the original system is nonempty, take its point $x_0\in [-R,R{]}^n$. The bounded relaxed setcontains a Euclidean ball around $x_0$ of radius $\rho =\min (1/2,\eta /(nV))$: each row changes by at most $\sqrt{n}V\rho \le \eta$, and the expanded box leaves room for the ball. Hence $Q$ is either empty or has an explicit positive inner-volume bound. This is the full-dimensional relaxation of integer inequalities principle.

Start with a ball, viewed as an ellipsoid, centered at zero with radius $n(R+1)$, which contains the search box. At each iteration test its center against all inequalities defining $Q$. If the center is feasible, the preserved-emptiness result answers that the original problem is nonempty. Otherwise a violated row supplies a separation oracle cut. Move that cut parallel to itself through the current center if necessary, and compute a smaller containing ellipsoid for the surviving half. Every feasible point remains in the new ellipsoid.

The central-cut ellipsoid volume bound gives a shrinkage factor at most $e^{-1/(2(n+1))}$ for $n\ge 2$. After $O(n^2\log (n(R+1)/\rho ))$ cuts, the volume is below that of a radius-$\rho$ ball. If no feasible center has been found, $Q$ and therefore the original system are empty. Dimension one uses interval bisection. The logarithms of $R$, $D$ and $1/\rho$ are polynomial in the encoded input size. Standard outward-controlled finite-precision ellipsoid updates preserve enclosure with polynomial bit complexity.

The coordinate bound therefore supplies the initial bounded search region; the rational gap supplies a valid stopping threshold. Neither unboundedness nor zero volume of the original polyhedron can be ignored when deciding emptiness.

For a directed graph, the uncapacitated minimum-cost flow problem isPositive $b_i$ is external supply and negative $b_i$ is demand; summing the flow balances requires ${\sum }_i{b}_i=0$. There are no finite upper arc capacities. Let $B$ be the oriented incidence matrix with tail $+1$ and head $-1$. For free dual potentials ${\pi }_i$, the Lagrangian isIts infimum over nonnegative flows is ${\pi }^{T}b$ exactly when every network reduced cost $r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$ is nonnegative; otherwise the infimum is minus infinity. Thus the dual maximizes ${\pi }^{T}b$ subject to these inequalities. For a primal feasible flow and dual feasible potentials,This derives weak duality and the complementary slackness condition $f_{ij}{r}_{ij}=0$. A feasible pair satisfying it has equal objectives and certifies optimality.

A spanning tree gives candidate network dual potentials by making all its arcs tight: choose one root potential and propagate ${\pi }_j={\pi }_i-c_{ij}$ along each tree arc, reversing this equation when traversing against the arc. An arbitrary tree does not automatically make the non-tree reduced costs nonnegative; those inequalities must be checked. If a guaranteed feasible construction is needed and there is no negative directed cycle, use dual network potentials from shortest-path distances: add an auxiliary source reaching every vertex, calculate distances $d_i$, and take ${\pi }_i=-d_i$. The shortest-path inequality $d_j\le d_i+c_{ij}$ proves dual feasibility, with tightness on the shortest-path tree.

For the printed dashed tree, set all non-tree flows to zero and solve the balances from the leaves. This givesThe remaining arcs $46,67,52,28,89$ have zero flow. The total initial cost is $20$. This is a basic feasible solution, though degenerate because the tree flow on $68$ is zero.

Normalize ${\pi }_1=0$. Tree tightness givesThe non-tree reduced costs areThe negative reduced cost on $89$ identifies an improving entering arc for the network simplex algorithm. Adding it to the tree creates a unique undirected cycle. Sending $\theta$ along $8\to 9$ increases the flows on $15,56,68,89$ by $\theta$ and decreases those on $14,43,37,79$ by $\theta$; all other flows are unchanged. This balanced displacement preserves every node equation. Nonnegativity limits $\theta$ to the minimum of the four decreasing flows, namely $2$. Choose arc $14$ to leave among the tied limiting arcs.

After this one pivot the nonzero flows areand every other arc flow is zero. The objective decreases by $\theta r_{89}=-2$, giving cost $18$.

For the new tree, tight potentials normalized at vertex 1 areAll tree reduced costs are zero. For the non-tree arcs $14,46,67,52,28$ they are $1,1,1,2,1$, respectively, so the potentials are dual feasible. Their dual objective ismatching the primal cost. Complementary slackness therefore provesThis is the stopping test of the network simplex method: maintain a feasible tree flow, compute tight potentials, enter a negative-reduced-cost non-tree arc, make a maximal feasible cycle adjustment and exchange a limiting tree arc, until all reduced costs are nonnegative. Here exactly one improving step suffices.

For a transferable utility game on player set $N$, its characteristic function of a coalitional game is $v:2^N\to \mathbb{R}$, where $v(S)$ is the maximum transferable surplus attainable by coalition $S$ and $v(\varnothing )=0$. An imputation is a payoff vector satisfying efficiency ${\sum }_{i\in N}{x}_i=v(N)$ and individual rationality $x_i\ge v(\{i\})$. The core of a cooperative game consists of the efficient payoff vectors satisfyingThese conditions prevent any coalition from blocking the allocation; singleton constraints include individual rationality.

The Shapley value payoff isEquivalently, it is the expected marginal contribution of player $i$ when the players arrive in uniformly random order. The factorial weight counts the orders with exactly $S$ preceding $i$. Summing marginal contributions telescopes along each order, proving Shapley efficiency.

In the four-player market a coalition creates one unit of surplus exactly when it contains the seller and at least one buyer. ThusAll singleton values are zero and $v(N)=1$. Core constraints for the pairs $\{1,j\}$ require $x_1+x_j\ge 1$ for every buyer $j$. Since all payoffs are nonnegative and sum to one, the other two buyers' payoffs must be zero for each such pair. Therefore every buyer receives zero and the seller receives one. This vector satisfies all coalition inequalities, soThe seller's marginal contribution is one unless he arrives before all three buyers, which happens with probability $1/4$. A given buyer contributes one exactly when the seller is first and that buyer is second, with probability $(1/4)(1/3)=1/12$. HenceIn particular the Shapley allocation need not lie in this market's core.

For the market with $k$ sellers and $3k$ buyers, a coalition containing $s$ sellers and $b$ buyers can make precisely $\min (s,b)$ trades, each producing unit surplus. Thus $v(S)=\min (s(S),b(S))$ and $v(N)=k$. Let $s_k$ and $b_k$ denote the common Shapley payoffs within the two roles. Role symmetry and the telescoping efficiency identity giveIt remains to prove $s_k\to 1$, rather than infer it only from competitive intuition.

Generate a uniformly random arrival order by giving every player an independent uniform time in $[0,1]$. Conditional on a specified seller's arrival time $t$, the number $B$ of preceding buyers and number $S$ of preceding other sellers are independent, withThe seller adds a trade precisely when $B>S$. ConsequentlyFor $t>0$, the difference $D=B-S$ has mean $(2k+1)t$ and variance $(4k-1)t(1-t)\le 4kt$. By Chebyshev's inequality,Split the integral at $\delta =k^{-1/2}$. Using the trivial bound one on the first piece givesThis proves the Shapley limit in a buyer-heavy exchange market. Since $b_k=(1-s_k)/3$, we concludeThe proof accounts for sellers arriving very early, where a fixed-time concentration argument alone would not be uniform.

For the metric travelling salesman problem, a tour is a polynomial-size complexity certificate: list the vertices in cyclic visiting order. In polynomial time verify that every vertex occurs exactly once, add the encoded integer edge costs and compare the sum with the threshold. The certificate has $O(n\log n)$ bits, and addition uses a number of bits polynomial in the input length. If validity of the metric input is not treated as a promise, nonnegativity, symmetry and all triangle inequalities can also be checked in polynomial time. Therefore the decision problem belongs to NP.

An evaluation algorithm immediately decides a threshold instance by computing the optimum and comparing it with $L$. Conversely, suppose there is a polynomial-time decision algorithm. The optimum is an integer in $[0,nM]$, where $M$ is the largest edge cost; any fixed cyclic ordering gives the upper bound. Binary search on this interval using threshold queries finds the exact minimum. It makes $O(\log (nM+1))$ queries, and every queried threshold has polynomial encoding length. Thus the time is polynomial in the bit length, even when $M$ is numerically large. Zero-cost and trivial small instances can be handled directly. ConsequentlyThis concerns the optimum value; constructing an optimal tour is the separate optimization task.

For the hardness reduction, start with an undirected graph $G$ on $n\ge 3$ vertices and form the complete graph with costsThese costs satisfy the triangle inequality, since every direct cost is at most two and every two-edge path costs at least two. Set the threshold to $n$. Every tour has exactly $n$ edges, each costing at least one. Hence it has cost at most $n$ precisely when all its edges came from $G$, which is precisely the existence of a Hamiltonian cycle in $G$. The construction and threshold encoding are polynomial-time. Thus the assumed NP-completeness of the Hamiltonian circuit problem gives NP-hardness of metric TSP; together with its NP membership this proves NP-completeness of metric TSP decision.

For the approximation, compute a minimum spanning tree $T$. Deleting any one edge of an optimal tour leaves a spanning tree, so nonnegative costs implyDouble every tree edge. The resulting connected multigraph has even degrees and hence an Euler circuit, of cost $2c(T)$. Traverse it and skip previously visited vertices, except for the final return to the start. Each skip replaces a path by its direct edge; repeated use of the triangle inequality shows that no replacement increases cost. The result is a tour visiting every vertex exactly once and satisfyingThe Euler traversal and shortcutting take polynomial time, so the assumed polynomial-time MST routine supplies the requested polynomial-time algorithm. This is the double-tree approximation for metric TSP. In the relative-error convention, $c/\mathrm{OPT}-1\le 1$ when the optimum is positive, explaining the printed term “1-approximation”; in the multiplicative convention it is a factor-two approximation. If the optimum is zero, the same bound forces the returned tour to have zero cost as well.

For a bimatrix game with row and column payoff matrices $A,B$, an equilibrium pair is a pair of mixed strategies $(p,q)$ for which neither player gains by a unilateral change:This is a Nash equilibrium, or mutual best response pair. Every finite game with nonempty finite pure-strategy sets has at least one mixed-strategy equilibrium by Nash's theorem. Equivalently, the strategy domains are compact convex probability simplexes and the expected payoffs are continuous and linear in each player's own strategy. The existence assertion need not hold if only pure strategies are allowed.

Write the probability vectors in the order Bach, Mozart, Schubert. Against $q=(q_B,q_M,q_S)$ the row player's three pure-action payoffs areAgainst $p=(p_B,p_M,p_S)$ the column player's payoffs areA supported action must attain the corresponding maximum, and an omitted action must give no larger payoff.

We first justify that both players have the same support of a mixed strategy, rather than assume it. Each player's maximum payoff is strictly positive for every opponent probability vector. Thus $p_M>0$ implies $q_M>0$, $q_B>0$ implies $p_B>0$, and $p_S>0$ is equivalent to $q_S>0$. If $p_B>0$ but $q_B=0$, then either $q_M>0$, making Mozart's payoff $2q_M$ strictly exceed Bach's $q_M$, or $q_S=1$, making Bach's payoff zero and Schubert's positive. Both contradict best response. Therefore $p_B>0$ also implies $q_B>0$. Similarly, if $q_M>0$ but $p_M=0$, then $p_B>0$ makes the column payoff for Bach $2p_B$ exceed Mozart's $p_B$, or $p_S=1$ makes Mozart's payoff zero and Schubert's positive. Thus $q_M>0$ implies $p_M>0$. The supports coincide, and there are only seven nonempty possibilities.

For singleton supports the three matching pure pairs are equilibria. For each two-element support, solve the two players' indifference equations and normalize their probabilities. For example, on Bach–Mozart, the equations are $4q_B=q_M$ and $p_B=4p_M$, giving $q=(1/5,4/5,0)$ and $p=(4/5,1/5,0)$. On Bach–Schubert they are $4q_B=3q_S$ and $2p_B=3p_S$. On Mozart–Schubert they are $2q_M=3q_S$ and $4p_M=3p_S$. In each case the omitted action gives strictly less than the common supported payoff.

For full support, the row indifference equations give $q_M=4q_B$ and $3q_S=2q_M$; the column equations give $p_B=4p_M$ and $3p_S=2p_B$. Normalization determines the remaining pair. The full list, with row strategy first, isAll displayed supported probabilities are positive. The supported payoff pairs in the four nonpure cases are respectively $(8/5,8/5)$, $(12/7,6/5)$, $(6/5,12/7)$ and $(24/23,24/23)$; these values also verify the omitted-action inequalities directly. The common-support argument excludes every other support pair, and each indifference system has a unique solution. Hence there are exactly seven equilibrium pairs, three pure and four genuinely mixed. This is a complete support enumeration for a bimatrix game, not just a list of selected equilibria.