Edmonds starts off by confidently stating:
Many discrete programming algorithms are being proposed. One thing most of them have in common is that they do not work very well.
He focuses on ‘better than finite’ algorithms, particularly for loco problems (linear-objective combinatorial). By this, he means an optimization problem with a linear objective subject to . The set is a collection of real vectors (not necessarily integer or 0-1), though they are often 0-1 vectors. In the 0-1 loco problem, one should choose an optimal cost subset of elements from a ground set such that the chosen subset belongs to . Often one represents the chosen subset as a (binary) characteristic vector, where entry is 1 if element is chosen to be in the subset (and zero otherwise).
A nice class of problems is the set of ‘matroidal’ problems, where the greedy algorithm is simple and efficient. A matroid is a pair of sets where is a (usually finite) ground set of elements and is a collection of subsets of satisfying these three conditions:
- implies , and
- for implies that there exists such that .
The greedy algorithm works by starting with the empty set (which will be feasible if is a matroid). In each iteration, we start with and add to it the maximum (minimum) cost element such that belongs to . Stop when no single element can be added (i.e., it is maximal). The resulting set is an optimal basis for .
Consider a matroid defined for a graph in the following way. Let the edge set be the ground set, and let be the collection of all subsets of edges that induce a forest. Applying the greedy matroid algorithm here equates to Kruskal’s minimum spanning tree algorithm.
Matroid polyhedra are particularly interesting. Suppose we want to formulate the matroid problem as a 0-1 program. Let represent the characteristic vector of a subset of . It turns out that solutions to the matroid problem are precisely the vertices of the polyhedron defined by the nonnegativity inequalities and the rank inequalities . Here, is the rank of , defined as the cardinality of the largest subset of that belongs to .
He mentions yet another elegant result concerning matroid polyhedra. Let denote the set of vertices of the polyhedron , and consider matroids and defined on the same ground set with associated polyhedra and . Then .
A minor complaint: Despite the paper’s obvious strengths in terms of content, its formatting and structure made it difficult to follow. Each paragraph is numbered–zero to eighty-one–which is distracting. It is also not divided into sections.
Next up: M. Held and R. Karp, The Traveling-Salesman Problem and Minimum Spanning Trees, Operations Research 18 (1970), 1138.