Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0839.90135
Magnanti, Thomas L.; Wolsey, Laurence A.
Optimal trees. (English)
[A] Ball, M. O. (ed.) et al., Network models. Amsterdam: North-Holland. Handb. Oper. Res. Manage. Sci. 7, 503-615 (1995). ISBN 0-444-89292-3/hbk

This paper has two broad objectives. First, it describes a number of core results concerning tree optimization problems. These results show that even though trees are rather simple combinatorial objects, their analysis raises a number of facinating issues that require fairly deep insight to resolve. Second, because the analysis of optimal trees poses many of the same issues that arise in more general settings of combinatorial optimization and integer programming, the study of optimal trees provides an accessible and yet fertile areana for introducing many key ideas from the branch of combinatorial optimization known as polyhedral combinatorics (the study of integer polyhedra).\par In addressing these issues, we consider the following questions:\par $\bullet$ Can we devise computationally efficient algorithms for solving tree optimization problems?\par $\bullet$ What is the relationship between various (integer programming) formulations of tree optimization problems?\par $\bullet$ Can we describe the underlying mathematical structure of these models, particularly the structure of the polyhedra that are defined by relaxing the integrality restrictions in their integer programming formulations?\par $\bullet$ How can we use the study of optimal tree problems to learn about key ideas from the field of combinatorial optimization such as the design and analysis of combinatorial algorithms, the use of bounding procedures (particularly, Lagrangian relaxation) as an analytic tool, and basic approaches and proof methods from the field of polyhedral combinatorics?\par We begin in Section 2 with a taxonomy of tree optimization problems together with illustrations of optimal tree applications in such fields as telecommunications, electric power distribution, vehicle routing, computer chip design, and production planning. In Section 3, we study the renowned minimum spanning tree problem. We introduce and analyze a greedy solution procedure and examine the polyhedral structure of the convex hull of incidence vectors of spanning trees. In the context of this discussion, we examine the relationship between eight different formulations of the minimum spanning tree problem that are variants of certain packing, cut, and network flow models.\par In Section 4, we examine another basic tree optimization problem, finding an optimal rooted tree within a tree. After showing how to solve this problem efficiently using dynamic programming, we then use three different arguments (a network flow argument, a dynamic programming argument, and a general `optimal' inequality argument from the field of polyhedral combinatorics) to show that a particular linear programming formulation defines the convex hull of incidence vectors of rooted trees. Because the basic result in this section is fairly easy to establish, this problem provides an attractive setting for introducing these important proof techniques.\par In Section 5, we consider two other tree models that can be solved efficiently by combinatorial algorithms -- a degree constrained minimum spanning tree problem (with a degree constraint imposed upon a single node) and a directed version of the minimum spanning tree problem. For both problems, we describe an efficient algorithmic procedure and fully describe the underlying integer polyhedron.\par In Sections 6-9 we consider more general models that are, from the perspective of computational complexity theory, difficult to solve. For each of these problems, we provide a partial description of the underlying integer polyhedron and describe one or more solution approaches.\par We begin in Section 6 by studying a network version of the well-known Steiner tree problem. Actually, we consider a more general problem known as the node weighted Steiner tree problem. Generalizing our discussion of the spanning tree problem in Section 3, we examine the relationship between the polyhedron defined by five different formulations of the problem. For one model, we show that the objective value for a linear programming relaxation of the Steiner tree problem has an optimal objective value no more than twice the cost of an optimal Steiner tree. Using this result, we are able to show that a particular spanning tree heuristic always produces a solution whose cost is no more than twice the cost of an optimal Steiner tree. In this discussion, we also comment briefly on solution methods for solving the Steiner tree problem.\par In Section 7, we study the problem of packing rooted trees in a given tree. This model arises in certain applications in production planning (the economic lot-sizing problem) and in facility location on a tree (for example, in locating message handling facilities in a telecommunications network). We show how to solve uncapaciated versions of this problem by dynamic programming and, in this case, we completely describe the structure of the underlying integer polyhedron. For more complex constrained problems, we show how to `paste' together the convex hull of certain subproblems to obtain the convex hull of the overall problem (this is one of the few results of this type in the field of combinatorial optimization). We also describe three different solution approaches for solving the problem -- a cutting plane procedure, a column generation procedure, and a Lagrangian relaxation procedure.\par In Section 8, we consider the more general problem of packing subtrees in a general graph. This problem arises in such varied problem settings as multi-item production planning, clustering, computer networking, and vehilce routing. This class of models permits constraints that limit the number of subtrees or that limit the size (number of nodes) of any subtree. Our discussion focuses on extending the algorithms we have considered previously in Section 7 when we considered optimal subtrees of a tree.\par In Section 9, we briefly introduce one final set of models, hierarchical tree problems that contain two types of edges -- those with high reliability versus those with low reliability (or high capacity versus low capacity). In these instances, we need to connect certain `primary' nodes with the highly reliable (or high capacity) edges. We describe an integer programming formulation of this problem that combines formulations of the minimum spanning tree and Steiner tree problems as well as a heuristic algorithm; we also give a bound on how for both the heuristc solution and the optimal objective value of the linear programming relaxation can be from optimality.\par Section 10 is a brief summary of the chapter and Section 11 contains notes and references for each section.

MSC 2000:: *90C35 Network programming
05C05 Trees
90B10 Flows in networks
90C10 Integer programming
90C27 Combinatorial programming
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
90B18 Communication networks
90B06 Transportation, logistics

Keywords: tree optimization; polyhedral combinatorics; minimum spanning tree; Lagrangian relaxation

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]