Capacitated Trees, Capacitated Routing, and Associated Polyhedra
J. Rafael Araque G.,
Leslie A. Hall, and
Thomas L. Magnanti
August 1990, revised June 1993
Abstract
We study the polyhedral structure of two
related core combinatorial problems:
the subtree cardinality-constrained
minimal spanning tree problem and the
identical customer vehicle routing problem.
For each of these problems, and for
a forest relaxation of the minimal spanning
tree problem, we introduce a number
of new valid inequalities and specify
conditions for ensuring when these
inequalities are facets for the associated
integer polyhedra. The inequalities
are defined by one of several underlying
support graphs:
(i) a multistar,
a ``star'' with a clique replacing the central vertex;
(ii) a clique cluster,
a collection of cliques intersecting at a single vertex,
or more generally at a ``central'' clique; and
(iii) a ladybug,
consisting of a multistar as a head and a clique as a body.
We also consider packing
(generalized subtour elimination) constraints,
as well as several variants of our basic
inequalities, such as partial multistars,
whose satellite vertices need
not be connected to all of the central
vertices. Our development highlights
the relationship between the capacitated
tree and capacitated forest polytopes
and a so-called path-partitioning polytope,
and shows how to use monotone
polytopes and a set of simple exchange
arguments to prove that valid
inequalities are facets.
Research supported in part by NSF grant DDM-9210979.