Past exam of the integer programming course of the University of Oxford / 2011 / 1

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.