Past exam of the computer science course of the University of Oxford / 2015 / Advanced data structures and algorithms / 3

Using the standard maximum form of a linear program, writewhere $x\in {\mathbb{R}}^n$, $A\in {\mathbb{R}}^{m\times n}$, $b\in {\mathbb{R}}^m$, and $c\in {\mathbb{R}}^n$. The inequalities are coordinatewise, and $c^{T}x$ is the objective function. General linear programs can be put in this form: reverse the sign of a minimization objective function, reverse lower-bound linear inequalities, replace an equality by two opposite linear inequalities, and replace each unrestricted variable by the difference of two nonnegative variables. Some conventions instead call the equality-constraint version standard form; the convention here is the maximum-with-upper-bounds convention.

Introduce nonnegative slack variables $x_{n+i}=b_i-{\sum }_{j=1}^n{a}_{ij}{x}_j$. The equivalent slack form of a linear program isThe original variables are initially nonbasic and the slack variables basic. More generally, a slack form of a linear program specifies disjoint index sets $N,B$ and writesThus each basic variable and the objective function are expressed using only nonbasic variables. Setting all nonbasic variables to zero gives the associated basic solution, which is a feasible solution exactly when the resulting basic values are nonnegative. The slack form of a linear program does not itself require that initial basic solution to be feasible.

A vertex cover of an undirected graph $G=(V,E)$ is a subset $C\subseteq V$ containing at least one endpoint of every edge. The optimization version of the vertex cover problem minimizes $|C|$; the vertex cover decision problem asks whether a cover of size at most a given bound exists.

Let $x_v=1$ mean that vertex $v$ is selected. An integer program for minimum-size vertex cover isThe linear programming relaxation replaces $x_v\in \{0,1\}$ by $0\le x_v\le 1$. The edge inequalities enforce coverage, and the objective function counts selected vertices in the integer program.

For a graph triangle with vertices $1,2,3$, the three covering constraints areAdding them gives $2(x_1+x_2+x_3)\ge 3$. Therefore the relaxed objective function is at least $3/2$. The feasible solution $x_1=x_2=x_3=1/2$ attains that lower bound, soIn contrast, one vertex leaves the opposite edge uncovered and any two vertices cover all three edges, giving integer optimum $2$. The example exhibits a genuinely non-integer optimal value, rather than merely a fractional feasible solution.

Assume job sizes $t_i\ge 0$ and machine speeds $s_j>0$, with at least one machine. Let $y_{ij}\ge 0$ be the amount of job $T_i$ assigned to machine $M_j$, and let $T\ge 0$ be the proposed makespan. Use the linear programThe first family of constraints assigns every job completely. The second bounds each machine's completion time by $T$, since $L_j/s_j\le T$ is equivalent to $L_j\le s_{j}T$. It is a linear inequality because $s_j$ is an input constant. There is no integrality restriction: jobs are divisible as specified in this scheduling model.

To verify the formulation, any actual allocation defines the variables above, with $T$ equal to its largest completion time, and satisfies every constraint. Conversely, from a feasible solution, assign amount $y_{ij}$ to machine $M_j$ and process its assigned pieces consecutively. Its total time is at most $T$, so the linear program realizes the claimed makespan.

There is also a useful exact check. Put $W={\sum }_i{t}_i$ and $S={\sum }_j{s}_j$. Summing machine constraints gives $W\le ST$, so $T\ge W/S$. Assigningmakes every machine's completion time $W/S$, provingThis relies on the paper's divisible-work model, in which machine completion times depend only on total assigned size. If $W=0$, the optimum is $0$.

A feasible point $x$ is an extreme point solution of a linear program if it cannot be written as a nontrivial convex combination of two distinct feasible points. Explicitly, ifthen $y=z=x$. Equivalently, $x$ lies in no open line segment joining two distinct feasible points. Being an extreme point concerns the feasible region; it does not by itself mean that $x$ optimizes the objective function.

Let $G=(L\cup R,E)$ be the given bipartite graph. A matching in a graph selects edges with no shared endpoint. For each edge $e$, introduce an indicator $x_e$ for selection. The integer program for a maximum cardinality matching isIts linear programming relaxation iswith the same objective function. Explicit upper bounds $x_e\le 1$ may be included, but they already follow from a constraint at either endpoint.

We prove that every extreme point of $P$ is integral by showing that any feasible point with a fractional coordinate admits a two-sided perturbation. Given such an $x$, form the fractional support graph $H$ with exactly those edges for which $0<x_e<1$. This is a nonempty bipartite graph. A vertex incident to one of these edges cannot also meet an edge with value $1$, because its incident sum would exceed $1$.

First suppose $H$ contains a graph cycle. Choose a simple one, $e_1,\dots ,e_q$. Its length $q$ is even since $H$ is a bipartite graph. Define a nonzero vector $h$ by alternating $+1,-1$ along the graph cycle and putting $0$ on other edges. At each vertex on the graph cycle, the two changed coordinates have opposite signs, so its incident sum is unchanged. ChooseThen $x^{+}=x+\epsilon h$ and $x^{-}=x-\epsilon h$ are distinct feasible points: no coordinate leaves $[0,1]$ and all incident sums are unchanged. Since $x=(x^{+}+x^{-})/2$, it is not an extreme point.

Otherwise $H$ is a forest. Choose a connected component of a graph containing an edge, and a simple graph path in it between two tree leaves. Alternate $+1,-1$ along the graph path to define $h$. Every internal vertex of the graph path still has unchanged incident sum, including any additional edges branching from it. At either endpoint, exactly one incident edge has fractional value; all other incident coordinates are $0$, since a coordinate $1$ is impossible there. Thus each endpoint has strictly positive slack $1-{\sum }_{e\ni v}{x}_e$ in its degree constraint. Choose $\epsilon >0$ smaller than these two slacks and smaller than every $x_e$ and $1-x_e$ along the graph path. Both $x+\epsilon h$ and $x-\epsilon h$ remain feasible: the endpoint sums can increase or decrease by $\epsilon$, and the internal sums do not change. Again $x$ is the midpoint of distinct feasible points, contradicting extremality.

Both cases exclude fractional coordinates at an extreme point. ThereforeThe nonempty bounded linear polyhedron $P$ has an optimal extreme point for the stated linear function, so the relaxation yields a maximum cardinality matching. This is stronger than the existence of one integral optimum: it proves integrality of every extreme point. It does not claim that every optimal feasible point is integral; convex mixtures of distinct optimal matchings in a graph can be fractional.