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

Introduce nonnegative slack variables $s_1=2+x_1-x_2$, $s_2=8-x_1-2x_2$ and $s_3=8-2x_1-x_2$, and write the objective as $Z$. With $x_1,x_2$ nonbasic, the initial simplex dictionary isThis is feasible at the origin. Enter $x_1$. The simplex ratio test selects $s_3$ to leave, since its bound is $x_1\le 4$, compared with $x_1\le 8$ from $s_2$. Pivoting givesNow enter $x_2$. The ratio test chooses $s_2$ to leave: its bound $8/3$ is smaller than $4$ from $s_1$ and $8$ from $x_1$. The resulting dictionary isAll basic values are nonnegative and all nonbasic objective coefficients are nonpositive. The simplex algorithm therefore certifiesThe negative objective coefficients also make this continuous optimum unique.

For integer $x_1,x_2$, all three original slacks are integers. Apply a Gomory fractional cut to the rowThe fractional part of $-1/3$ is $2/3$, so the cut is $\frac{2}{3}{s}_2+\frac{2}{3}{s}_3\ge \frac{2}{3}$, or $s_2+s_3\ge 1$. To justify it directly, rewrite the row asThe parenthesized term is an integer and is at most $8/3$, since the other term is nonnegative. It is therefore at most $2$, proving the cut. This retains every feasible integer solution and excludes the current fractional optimum. Since $s_2+s_3=16-3(x_1+x_2)$, the cut is equivalently $x_1+x_2\le 5$.

Introduce the integer-valued nonnegative slack $t=s_2+s_3-1$. Its dictionary row is $t=-1+s_2+s_3$, so primal feasibility fails while the objective row remains dual feasible. In the dual simplex algorithm, $t$ leaves; $s_2,s_3$ tie in the dual ratio test, each with ratio $1/3$. Choose $s_2$ to enter. Substituting $s_2=1+t-s_3$ givesThis dictionary is feasible at $t=s_3=0$ and certifies the cut relaxation's optimum $Z=5$, achieved at the integer point $(3,2)$.

To find every optimal integer point, the objective row forces $t=0$. Nonnegativity of all the remaining rows then reduces to $0\le s_3\le 1$. On this optimal edge, $(x_1,x_2)=(3-s_3,2+s_3)$. Since $s_3$ must be integral, only its two endpoints are possible:

An integer program for the travelling salesman problem must exclude disconnected cycle covers, not merely require one incoming and one outgoing edge. Here is a compact order formulation of the travelling salesman problem. The one-city case is trivial. For $n\ge 2$, use binary variables $x_{ij}$ for directed edges, $i\ne j$, and integer variables $u_i$ for $i=2,\dots ,n$. Minimize ${\sum }_{i\ne j}{d}_{ij}{x}_{ij}$ subject toThe degree equations give a collection of disjoint directed cycles. Along any selected edge between nondistinguished cities, the last inequality gives $u_j\ge u_i+1$. Summing around a cycle avoiding city $1$ would yield $0\ge k$ for its positive length $k$. Thus every cycle must contain city $1$, so there is exactly one tour. Conversely, number the cities after city $1$ in tour order, giving $u_i\in \{1,\dots ,n-1\}$. Selected edges satisfy the order inequalities. Unselected edges impose no additional restriction, since $u_i-u_j\le n-2$. This proves equivalence with tours, including symmetric-distance instances represented by directed variables.

There are $O(n^2)$ variables and rows. For the bit count, store only nonzero coefficients and their indices. The degree equations have $O(n^2)$ entries in total; each order inequality has three entries, so these too have $O(n^2)$ entries. Indices and the coefficients bounded by $n$ need $O(\log n)$ bits each. The objective has $O(n^2)$ distance coefficients, each needing at most $n+1$ bits because the PDF's bound is $2^n$. ThereforeWriting an unnecessarily dense constraint matrix would give a larger encoding; it is the sparse explicit encoding that establishes the requested bound. For the decision version add $\sum d_{ij}{x}_{ij}\le B$. A threshold can be capped at $n{2}^n$, so its relevant binary length is $O(n+\log n)$; negative thresholds can be rejected immediately for nonnegative distances.

A decision problem belongs to NP if its yes-instances have certificates of polynomial length checkable in deterministic polynomial time. It is NP-complete if it belongs to NP and every NP problem has a polynomial-time many-one reduction to it. The preceding construction is a polynomial-time reduction from travelling-salesman decision to integer-linear feasibility. If the former is NP-complete, the latter is consequently NP-hard.

For completeness we must also establish membership in NP for general integer-linear feasibility, rather than just for the binary instances produced by the reduction. An arbitrary feasible integer assignment could be numerically enormous; what is needed is the existence of a short one. We give a small integer feasibility witness by homogeneous cone decomposition.

Split each unrestricted integer variable into the difference of two nonnegative integer variables and add nonnegative integer slacks to inequalities. This gives $Bz=b$, $z\ge 0$, with $N$ variables and integer data bounded in absolute value by $M\ge 1$. Both $N$ and $\log M$ are polynomially bounded by the original input length. Consider the homogeneous coneEvery vector in this cone is a nonnegative combination of at most $N+1$ support-minimal rays. To prove this, choose a nonnegative kernel vector $h$ of minimal nonempty support contained in the support of a given vector, subtract $\lambda h$ with $\lambda$ the smallest positive coordinate ratio, and repeat. Each subtraction strictly reduces support. On a minimal support the kernel is one-dimensional: an independent kernel direction would let us perturb a positive vector to the boundary of its support without making it zero, contradicting minimality. Cofactors of independent rows therefore give an integer nonnegative generator of each such ray. Every coordinate is bounded byusing the elementary determinant bound. This proves the needed support-minimal rays of a nonnegative kernel facts directly.

Start with any integer feasible $z$ and decompose $(z,1)$ in this way. A ray whose last coordinate is a positive integer $q$ normalizes to a point $v$ with $Bv=b$ and $0\le v_i\le D$; the coefficients of these normalized points sum to one. Rays with last coordinate zero have integer nonnegative first coordinates $r_j$ with $B{r}_j=0$ and coordinates at most $D$. Hencewith at most $N+1$ ray terms. Subtract ${\sum }_j\lfloor t_j\rfloor r_j$ from $z$. The result $z^{\prime }$ is still integer, nonnegative and feasible, and satisfiesIts binary length is polynomial, since $\log D=O(N\log N+N\log M)$. The assignment can be checked by exact integer arithmetic in polynomial time. Thus general integer-linear feasibility is in NP. Combining this with the reduction proves

If the center $z$ violates a constraint, choose a row $a^T$ with $a^{T}z<b_i$. Under the assumption of nonempty $P$, this row cannot have $a=0$. Every $x\in P$ satisfies $a^{T}x\ge b_i>a^{T}z$. Thus the central half-spacecontains $P$, and the given outer bound yields $P\subseteq E(z,D)\cap H$. Checking the rows of $A$ therefore supplies a separation oracle. If a violated row has zero normal, it instead certifies that $P$ is empty.

Whiten the ellipsoid by $x=z+D^{1/2}y$ and rotate the cut normal to $e_1$. The normalized current ellipsoid is the unit ball centered at zero. In the stated covering ellipsoid, for $n\ge 2$, the shape matrix has eigenvalue $n^2/(n+1{)}^2$ in the $e_1$ direction and $n^2/(n^2-1)$ in each of the other $n-1$ directions. The center does not affect volume, soUsing $\log (1-a)<-a$ for $0<a<1$ and $\log (1+b)<b$ for $b>0$ givesThereforeThis is the central-cut ellipsoid volume bound. Affine transformations preserve the ratio. The displayed matrix formula is undefined when $n=1$; in that case interval bisection gives the stronger ratio $1/2$.

Undoing the normalization gives the general central-cut updateIt preserves containment of the feasible region while reducing volume geometrically. After $k$ cuts the volume is less than $V_0{e}^{-k/(2(n+1))}$. If a feasible region has a known positive-volume lower bound $V_{\min }$, more than $2(n+1)\log (V_0/V_{\min })$ unsuccessful cuts would be impossible. For rational inputs, outer-radius and positive-volume bounds of exponential size in a polynomial of the bit length therefore translate into a polynomial iteration count.

For a full ellipsoid method proof, two qualifications matter. A nonempty rational polyhedron may be lower-dimensional and have zero volume, so shrinking below a volume threshold alone cannot certify its emptiness. One uses a bounded-feasibility reduction and a sufficiently small rational relaxation or an affine-hull treatment, with input-dependent rational separation bounds. Also ellipsoid updates involve square roots, so a bit-complexity proof rounds with controlled outward error to preserve containment and a fixed volume decrease. With these precision bounds, and the polynomial-time row separation oracle here, the method establishes polynomial-time linear programming. The volume calculation is its essential geometric step, not by itself the entire complexity proof.

In a transferable utility game, the characteristic function of a coalitional game assigns each coalition $S$ the total payoff $v(S)$ that its members can attain or guarantee together, normalized by $v(\varnothing )=0$. If disjoint coalitions $S,T$ can combine their separate strategies without interference, their union can secure both payoffs, givingThis is a superadditive coalitional game. The pooling assumption explains the intended assertion, but superadditivity is not automatic for an abstract characteristic function: the two-player values $v(\{1\})=v(\{2\})=v(\{1,2\})=1$, with empty value zero, are a counterexample. Thus the word “always” requires either that pooling assumption or a definition restricting the class of games to superadditive ones.

For the given bankruptcy game, the total deficit is $19-15=4$, so the coalition value is $({\sum }_{i\in S}{c}_i-4{)}_{+}$. Its computed values areIt is indeed superadditive: for disjoint claim sums $p,q\ge 0$, $(p+q-4{)}_{+}\ge (p-4{)}_{+}+(q-4{)}_{+}$. If both right-hand terms are positive the difference is $4$; if only one is positive, adding the other claim sum cannot reduce the value; if neither is positive the right side is zero.

A payoff allocation is Pareto efficient if no feasible allocation weakly increases every player's payoff and strictly increases at least one. Here feasibility requires total payment at most the available estate. The proposed payments haveAny such improvement would have total payment greater than $15$, which is impossible. Each payment is also between zero and its claim, and exceeds its singleton coalition value. Hence the allocation is an imputation and

The Shapley value is the expected marginal contribution of a player when the players join in uniformly random order. Equivalently,For three players, the weights for predecessor sets of sizes $0,1,2$ are $1/3,1/6,1/3$. Using the computed values,Thus

For an imputation $y$, the excess of a coalition is $e(S,y)=v(S)-{\sum }_{i\in S}{y}_i$. Arrange these excesses in decreasing order. The nucleolus is the imputation that lexicographically minimizes this ordered vector: minimize the largest complaint first, then the next largest among ties, and so on. The empty and grand-coalition excesses are fixed at zero for every efficient allocation, so they can be omitted without changing the lexicographic comparison.

For every efficient $y$ the three pair excesses have sumHence at least one pair has excess at least $-4/3$, and the largest proper-coalition excess is at least $-4/3$. At the proposed allocation all three pair excesses equal $-4/3$, while all three singleton excesses equal $-8/3$. It therefore attains the best possible largest proper-coalition excess.

Moreover, any allocation attaining this bound must have all three pair excesses equal $-4/3$, since they are individually at most that value and sum to $-4$. This forceswhose unique solution is $y=x$. It is already an imputation, so the first nonconstant lexicographic stage has a unique minimizer; there are no later choices to resolve. Therefore

The core of a cooperative game consists of efficient allocations satisfying ${\sum }_{i\in S}{x}_i\ge v(S)$ for every coalition, so no coalition can obtain a greater total payoff by leaving. Efficiency has already been checked. For singletons,For pairs,The empty constraint is automatic and the grand constraint is equality. Thus every core inequality holds andAll four assertions about this allocation are true, although their definitions impose different requirements.

A buyer accepts a posted price precisely when their valuation exceeds it; equality has probability zero. The independent uniform valuations therefore give probability $p^2$ that neither accepts, for $0\le p\le 1$. The seller's expected revenue isThe interior critical point is $p=1/\sqrt{3}$, with negative second derivative; the endpoint revenues are zero. Prices above one make no sale and nonpositive prices cannot improve on this positive optimum. HenceWhich willing buyer is served if both accept does not affect this revenue.

In an ideal continuous-price English auction, staying active until one's private valuation is optimal: dropping earlier can forgo positive surplus, while staying later risks paying more than the car is worth. The highest-valued buyer therefore wins, paying the price at which the other buyer drops out, namely $\min (V_1,V_2)$.

For $0\le t\le 1$, independence gives $\mathrm{Pr}(\min (V_1,V_2)>t)=(1-t{)}^2$. Integrating this tail probability gives“Pays his bid” in this ascending auction does not mean that the winning buyer pays his full valuation; the competing buyer's dropout determines the winning price.

With reserve price $r\in [0,1]$, an English auction makes no sale if both valuations are below $r$. If exactly one exceeds it, the price is $r$; if both exceed it, the price is their minimum. ThusThe first term accounts for one qualifying buyer, and the integral uses the density $2(1-t)$ of the smaller valuation. Differentiation gives $R_c^{\prime }(r)=2r(1-2r)$. It increases up to $r=1/2$ and decreases afterwards, while the endpoints give $1/3$ and zero. ThereforeThe strict sale condition at the reserve changes only a probability-zero event.

The resulting revenue comparison for two uniform private values isThus the optimally reserved ascending auction is best, followed by the optimal posted price, followed by the ascending auction without a reserve. These values are in the normalized monetary units used for the valuations.

The revenue equivalence theorem for symmetric independent private values applies to mechanisms with the same allocation probabilities at every type and the same expected utility for the lowest type, under the usual incentive and risk-neutrality assumptions. The reserved and unreserved auctions have different allocation rules. Without a reserve, a bidder of valuation $v$ wins with probability $G(v)=v$. With reserve $r$, that probability is zero for $v<r$ and $v$ for $v>r$. In particular the car is withheld when even the highest valuation is below $r$.

The interim payment identity makes the difference explicit. With lowest-type utility zero, the ordinary auction has expected payment $m(v)=v^2/2$. The reserved auction hasSumming the two bidders' ex ante payments gives $2{\int }_r^1{m}_r(v)dv=1/3+r^2-4r^3/3$, exactly the revenue calculated above. Hence there is no conflict with revenue equivalence: its equal-allocation hypothesis does not hold.

Let $z_i\in \{0,1\}$ indicate that item $i$ is placed in the first bin; otherwise it is placed in the second. The two-bin load balancing problem has the familiar mixed-integer formulationThe continuous variable $y$ becomes the maximum of the two bin loads at an optimum. A pure binary integer program, avoiding any integrality assumption on the weights or on $y$, is obtained by labelling a heavier bin as the first bin:The constraint ensures that the first load is at least the second, so the objective is their maximum. Every partition can be relabelled in this way, and every binary solution gives a partition. Thus this all-integer assignment formulation has exactly the original optimal value.

Use the relative-error approximation for minimization convention: an $\epsilon$-approximation returns a feasible solution of value $Y$ with $Y\le (1+\epsilon )Y^{\ast }$ on every instance, where $Y^{\ast }$ is the optimum. Equivalently the relative excess is at most $\epsilon$; the multiplicative-ratio convention reports $1+\epsilon$ instead.

Before item $j$ is assigned, the total load already placed is ${\sum }_{i<j}{w}_i$. The lighter of two bins has load at most half that total. Positivity of the weights givesChoose a bin attaining the final maximum load $Y$, and let $j$ be its last assigned item. No later item enters that bin, soEvery feasible schedule has $Y^{\ast }\ge s/2$ and $Y^{\ast }\ge w_{\max }$. HenceThe ordered weights $1,1,2$ make the greedy loads $1,1$ after two assignments and then $3,1$, regardless of how the final tie is resolved. The optimal partition has loads $2,2$. Thus the factor $3/2$ is attained, not merely a loose bound. We conclude the sharp greedy two-bin scheduling bound

Several other approaches illustrate the range between fast heuristics, certified bounds and approximation schemes.

Sorting weights in decreasing order before greedy assignment avoids the example $1,1,2$: it starts with the weight $2$, then places both unit weights in the other bin, giving the optimum. This is a useful scheduling heuristic, although improvement on one example is not a proof of an arbitrary claimed approximation ratio. Local improvement can additionally move a single item or swap items between bins whenever it reduces the maximum load; it produces a local optimum, which need not be global.

A linear-programming relaxation replaces $z_i\in \{0,1\}$ by $0\le z_i\le 1$. The choice $z_i=1/2$ for every item gives load $s/2$ in both bins, and summing the load constraints shows that no smaller relaxed value is possible. Together with the indivisibility bound $w_{\max }$ this provides a lower bound $L=\max (s/2,w_{\max })$ on the integer optimum. Any feasible heuristic schedule gives an upper bound $U$. Their ratio $U/L$ is a computable quality certificate. Branch-and-bound can improve these bounds by fixing assignment variables and solving subproblems, although worst-case exact running time need not be polynomial.

For integer weights one can instead solve the problem exactly by dynamic programming. Start with attainable subset sums $T_0=\{0\}$ and updatediscarding values above $\lfloor s/2\rfloor$. Let $q$ be the largest retained sum. Choosing that subset for one bin gives loads $q,s-q$ and maximum $s-q$, which is optimal because every partition has a lighter side of weight at most $s/2$. The running time $O(ns)$ is pseudopolynomial: it depends on numeric magnitude, not merely the binary length of $s$.

This exact algorithm also yields rounded dynamic programming for two-bin load balancing. For rational weights and $0<\epsilon <1$, choose $K=\epsilon s/(2n)$ and scaled integer weights $q_i=\lfloor w_i/K\rfloor$. Their total is at most $2n/\epsilon$, so exact dynamic programming on them costs $O(n^2/\epsilon )$ arithmetic operations. Let $Y^{\prime }$ be its optimal scaled maximum load. The original optimal partition is feasible for the scaled problem with load at most $Y^{\ast }/K$, so $K{Y}^{\prime }\le Y^{\ast }$. When the scaled partition is lifted, each bin contains at most $n$ rounding errors, each smaller than $K$. Therefore its original maximum load satisfiesThis is a fully polynomial-time approximation scheme: for each requested tolerance it gives a certified feasible solution in time polynomial in the encoded rational input and $1/\epsilon$, with rational arithmetic accounted for. It works here because two-bin balancing has the subset-sum structure; one cannot infer that arbitrary combinatorial optimization problems admit such a scheme.