nach oben

2013 | Buch

Kapitel lesen Erstes Kapitel lesen

Facets of Combinatorial Optimization

Festschrift for Martin Grötschel

herausgegeben von: Michael Jünger, Gerhard Reinelt

Verlag: Springer Berlin Heidelberg

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Martin Grötschel is one of the most influential mathematicians of our time. He has received numerous honors and holds a number of key positions in the international mathematical community. He celebrated his 65th birthday on September 10, 2013. Martin Grötschel’s doctoral descendant tree 1983–2012, i.e., the first 30 years, features 39 children, 74 grandchildren, 24 great-grandchildren and 2 great-great-grandchildren, a total of 139 doctoral descendants.

This book starts with a personal tribute to Martin Grötschel by the editors (Part I), a contribution by his very special “predecessor” Manfred Padberg on “Facets and Rank of Integer Polyhedra” (Part II), and the doctoral descendant tree 1983–2012 (Part III). The core of this book (Part IV) contains 16 contributions, each of which is coauthored by at least one doctoral descendant.

The sequence of the articles starts with contributions to the theory of mathematical optimization, including polyhedral combinatorics, extended formulations, mixed-integer convex optimization, super classes of perfect graphs, efficient algorithms for subtree-telecenters, junctions in acyclic graphs and preemptive restricted strip covering, as well as efficient approximation of non-preemptive restricted strip covering.

Combinations of new theoretical insights with algorithms and experiments deal with network design problems, combinatorial optimization problems with submodular objective functions and more general mixed-integer nonlinear optimization problems. Applications include VLSI layout design, systems biology, wireless network design, mean-risk optimization and gas network optimization.

Computational studies include a semidefinite branch and cut approach for the max k-cut problem, mixed-integer nonlinear optimal control, and mixed-integer linear optimization for scheduling and routing of fly-in safari planes.

The two closing articles are devoted to computational advances in general mixed integer linear optimization, the first by scientists working in industry, the second by scientists working in academia.

These articles reflect the “scientific facets” of Martin Grötschel who has set standards in theory, computation and applications.

Inhaltsverzeichnis

Frontmatter

Martin Grötschel—Activist in Optimization

Frontmatter

Martin Grötschel—The Early Years in Bonn and Augsburg

Abstract

Martin Grötschel is one of the most influential mathematicians of our time. He has received numerous honors and serves in a number of key positions in the international mathematical community. A summary is sketched in the preceding short curriculum vitae taken from his professional homepage. Numerous scientific and popular articles recount his achievements and prominent role. These include articles in respected papers such as DIE ZEIT, Financial Times, Die Welt, and Der Tagesspiegel. His “scientific facets” will be covered in detail in the rest of this book.

When we first conceived of this chapter, we had a different perspective in mind. As his first doctoral descendants, we can tell a different story, because we were actively involved in his early career. This was the time when he developed from a scientific assistant in Bonn to a full professor in Augsburg. In the following, we recount some of our memories of this time, with no guarantee for either accuracy or completeness. Instead, these are the stories that came to mind when we sat together in Heidelberg and Cologne, preparing this chapter.

Michael Jünger, Gerhard Reinelt

Contribution by a Very Special Predecessor of Martin Grötschel

Frontmatter

Facets and Rank of Integer Polyhedra

Abstract

We discuss several methods of determining all facets of “small” polytopes and polyhedra and give several criteria for classifying the facets into different facet types, so as to bring order into the multitude of facets as, e.g., produced by the application of the double description algorithm (DDA). Among the forms that we consider are the normal, irreducible and minimum support representations of facets. We study symmetries of vertex and edge figures under permissible permutations that leave the underlying polyhedron unchanged with the aim of reducing the numerical effort to find all facets efficiently. Then we introduce a new notion of the rank of facets and integer polyhedra. In the last section, we present old and new results on the facets of the symmetric traveling salesman polytope \(\mathcal{Q}_{T}^{n}\) with up to n=10 cities based on our computer calculations and state a conjecture that, in the notion of rank ρ(P) introduced here, asserts \(\rho(\mathcal{Q}_{T}^{n}) = n - 5\) for all n≥5. This conjecture is supported by our calculations up to n=9 and, possibly, n=10.

Manfred W. Padberg

Martin Grötschel’s Doctoral Descendants

Frontmatter

Martin Grötschel’s Descendants and Their Doctoral Theses 1983–2012

Abstract

We present the tree of Martin Grötschel’s doctoral descendants along with their doctoral theses from 1983 to 2012, i.e., the first 30 years. Our format should be self-explanatory: Depth in the hierarchy is indicated by indentation and color: blue for the 39

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-642-38189-8_3/310675_1_En_3_IEq1_HTML.gif

, red for the 74

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-642-38189-8_3/310675_1_En_3_IEq2_HTML.gif

, cyan for the 24

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-642-38189-8_3/310675_1_En_3_IEq3_HTML.gif

, and magenta for the 2

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-642-38189-8_3/310675_1_En_3_IEq4_HTML.gif

. The doctoral thesis titles of these 139 descendants show the many fruits of Martin Grötschel’s original impetus.

Michael Jünger, Gerhard Reinelt

Contributions by Martin Grötschel’s Doctoral Descendants

Frontmatter

Constructing Extended Formulations from Reflection Relations

Abstract

There are many examples of optimization problems whose associated polyhedra can be described much nicer, and with way less inequalities, by projections of higher dimensional polyhedra than this would be possible in the original space. However, currently not many general tools to construct such extended formulations are available. In this paper, we develop the framework of polyhedral relations that generalizes inductive constructions of extended formulations via projections, and we particularly elaborate on the special case of reflection relations. The latter ones provide polynomial size extended formulations for several polytopes that can be constructed by iteratedly forming convex hulls of polytopes and (slightly modified) reflections of them at hyperplanes. We demonstrate the use of the framework by deriving small extended formulations for the G-permutahedra of all finite reflection groups G (generalizing both Goemans’ extended formulation of the permutahedron of size O(nlogn) and Ben-Tal and Nemirovski’s extended formulation with O(k) inequalities for the regular 2^k-gon) and for Huffman-polytopes (the convex hulls of the weight-vectors of Huffman codes). This work is an extension of an extended abstract presented at IPCO XV (2011).

Volker Kaibel, Kanstantsin Pashkovich

Mirror-Descent Methods in Mixed-Integer Convex Optimization

Abstract

In this paper, we address the problem of minimizing a convex function f over a convex set, with the extra constraint that some variables must be integer. This problem, even when f is a piecewise linear function, is NP-hard. We study an algorithmic approach to this problem, postponing its hardness to the realization of an oracle. If this oracle can be realized in polynomial time, then the problem can be solved in polynomial time as well. For problems with two integer variables, we show with a novel geometric construction how to implement the oracle efficiently, that is, in \(\mathcal {O}(\ln(B))\) approximate minimizations of f over the continuous variables, where B is a known bound on the absolute value of the integer variables. Our algorithm can be adapted to find the second best point of a purely integer convex optimization problem in two dimensions, and more generally its k-th best point. This observation allows us to formulate a finite-time algorithm for mixed-integer convex optimization.

Michel Baes, Timm Oertel, Christian Wagner, Robert Weismantel

Beyond Perfection: Computational Results for Superclasses

Abstract

We arrived at the Zuse Institute Berlin, Annegret as doctoral student in 1995 and Arnaud as postdoc in 2001, both being already fascinated from the graph theoretical properties of perfect graphs. Through encouraging discussions with Martin, we learned about the manifold links of perfect graphs to other mathematical disciplines and the resulting algorithmic properties based on the theta number (where Martin got famous for, together with Laci Lovász and Lex Schrijver).

This made us wonder whether perfect graphs are indeed completely unique and exceptional, or whether some of the properties and concepts can be generalized to larger graph classes, with similar algorithmic consequences—the starting point of a fruitful collaboration. Here, we answer this question affirmatively and report on the recently achieved results for some superclasses of perfect graphs, all relying on the polynomial time computability of the theta number. Finally, we give some reasons that the theta number plays a unique role in this context.

Arnaud Pêcher, Annegret K. Wagler

From Vertex-Telecenters to Subtree-Telecenters

Abstract

Let T be a tree and v a vertex in T. It is well-known that the branch-weight of v is defined as the maximum number of vertices in the components of T−v and that a vertex of T with the minimum branch-weight is called a vertex-centroid of T. Mitchell (Discrete Math. 24:277–280, 1978) introduced a type of a central vertex called the telephone center or the vertex-telecenter of a tree and showed that v is a vertex-centroid of T if and only if it is a vertex-telecenter of T. In this paper we introduce the notions of the subtree-centroid and the subtree-telecenter of a tree which are natural extensions of the vertex-centroid and the vertex-telecenter, and generalize two theorems of Mitchell (Discrete Math. 24:277–280, 1978) in the extended framework of subtree-centroids and subtree-telecenters. As a consequence of these generalized results we also obtain an efficient solution method which computes a subtree-telecenter of a tree.

Zaw Win, Cho Kyi Than

Algorithms for Junctions in Acyclic Digraphs

Abstract

Given targets u and v in a digraph D, we say that a vertex s is a junction of u and v if there are in D internally vertex-disjoint directed paths from s to u and from s to v. In this paper, we show how to characterize junctions in acyclic digraphs. We also consider the following problem and derive an efficient algorithm to solve it. Given an acyclic digraph D, a vertex s in D and k pairs of targets {u ₁,v ₁},…,{u _k,v _k}, determine the pairs of targets {u _i,v _i} for which s is a junction. This problem arises in an application brought to our attention by an anthropologist. In this application the digraph represents the genealogy of an ethnic group in Brazilian Amazon region, and the pairs of targets are individuals that are married. We apply our algorithm to find all the junctions of k pairs of targets on those kinship networks. Experiments have shown that our algorithm had a good performance for the inputs considered. Some results are described in this paper.

Carlos Eduardo Ferreira, Álvaro Junio Pereira Franco

Algorithms for Scheduling Sensors to Maximize Coverage Time

Abstract

We study a one-dimensional sensor cover problem, known as the Restricted Strip Cover (RSC) problem, defined as follows. We are given an interval U of the real line, and a set of n sensors, each of which covers some subinterval of U and is powered with a battery of limited duration. The RSC problem consists in finding a scheduling of the sensors (that is, an assignment of the activating times of the given sensors) so that the whole interval U is covered for as long as possible. We investigate two variants of this problem: one denoted simply as RSC, the non-preemptive variant; and the other, denoted as RSCP, the preemptive variant. In the first, each sensor can be activated at most once and it remains on through the duration of its battery. In the second variant, preemption is allowed, that is, each sensor can be activated and deactivated many times along the duration of its battery. Buchsbaum, Efrat, Jain, Venkatasubramanian and Yi showed that RSC is NP-hard and designed an O(loglogn)-approximation algorithm. More recently, Gibson and Varadarajan presented a greedy-like algorithm which they proved to have approximation ratio at most 5. We prove that the approximation ratio of this algorithm is 4, and exhibit an instance showing that this ratio analysis is tight. We also show an integer programming formulation for this problem and present some computational results obtained with the implementation of this approach. For the same set of instances, we compute the quality of the solution found by the approximation algorithm. For the preemptive variant RSCP, we present an exact polynomial-time algorithm.

Rafael da Ponte Barbosa, Yoshiko Wakabayashi

How Many Steiner Terminals Can You Connect in 20 Years?

Abstract

Steiner trees are constructed to connect a set of terminal nodes in a graph. This basic version of the Steiner tree problem is idealized, but it can effectively guide the search for successful approaches to many relevant variants, from both a theoretical and a computational point of view. This article illustrates the theoretical and algorithmic progress on Steiner tree type problems on two examples, the Steiner connectivity and the Steiner tree packing problem.

Ralf Borndörfer, Nam-Dũng Hoang, Marika Karbstein, Thorsten Koch, Alexander Martin

The Maximum Weight Connected Subgraph Problem

Abstract

The Maximum (Node-) Weight Connected Subgraph Problem (MWCS) searches for a connected subgraph with maximum total weight in a node-weighted (di)graph. In this work we introduce a new integer linear programming formulation built on node variables only, which uses new constraints based on node-separators. We theoretically compare its strength to previously used MIP models in the literature and study the connected subgraph polytope associated with our new formulation. In our computational study we compare branch-and-cut implementations of the new model with two models recently proposed in the literature: one of them using the transformation into the Prize-Collecting Steiner Tree problem, and the other one working on the space of node variables only. The obtained results indicate that the new formulation outperforms the previous ones in terms of the running time and in terms of the stability with respect to variations of node weights.

Eduardo Álvarez-Miranda, Ivana Ljubić, Petra Mutzel

Exact Algorithms for Combinatorial Optimization Problems with Submodular Objective Functions

Abstract

Many combinatorial optimization problems have natural formulations as submodular minimization problems over well-studied combinatorial structures. A standard approach to these problems is to linearize the objective function by introducing new variables and constraints, yielding an extended formulation. We propose two new approaches for constrained submodular minimization problems. The first is a linearization approach that requires only a small number of additional variables. We exploit a tight polyhedral description of this new model and an efficient separation algorithm. The second approach uses Lagrangean decomposition to create two subproblems which are solved with polynomial time algorithms; the first subproblem corresponds to the objective function while the second consists of the constraints. The bounds obtained from both approaches are then used in branch and bound-algorithms. We apply our general results to problems from wireless network design and mean-risk optimization. Our experimental results show that both approaches compare favorably to the standard techniques.

Frank Baumann, Sebastian Berckey, Christoph Buchheim

A Primal Heuristic for Nonsmooth Mixed Integer Nonlinear Optimization

Abstract

Complex real-world optimization tasks often lead to mixed-integer nonlinear problems (MINLPs). However, current MINLP algorithms are not always able to solve the resulting large-scale problems. One remedy is to develop problem specific primal heuristics that quickly deliver feasible solutions. This paper presents such a primal heuristic for a certain class of MINLP models. Our approach features a clear distinction between nonsmooth but continuous and genuinely discrete aspects of the model. The former are handled by suitable smoothing techniques; for the latter we employ reformulations using complementarity constraints. The resulting mathematical programs with equilibrium constraints (MPEC) are finally regularized to obtain MINLP-feasible solutions with general purpose NLP solvers.

Martin Schmidt, Marc C. Steinbach, Bernhard M. Willert

A New Algorithm for MINLP Applied to Gas Transport Energy Cost Minimization

Abstract

In this article, we present a new algorithm for the solution of nonconvex mixed-integer nonlinear optimization problems together with an application from gas network optimization, the gas transport energy cost minimization problem. Here, the aim is to transport gas through the network at minimum operating cost. The proposed algorithm is based on the adaptive refinement of a new class of MIP-relaxations and has been developed within an industry project on gas network optimization. Since therefore the implementation is not as general as it could be, our computational results are restricted to instances from gas network optimization at this point of time. However, as these problems are real-world applications and turn out to be rather hard to solve with the aid of state-of-the-art MINLP-solvers we believe that our computational results reveal the potential of this new approach and motivate further research on the presented techniques.

Björn Geißler, Antonio Morsi, Lars Schewe

Solving k-Way Graph Partitioning Problems to Optimality: The Impact of Semidefinite Relaxations and the Bundle Method

Abstract

This paper is concerned with computing global optimal solutions for maximum k-cut problems. We improve on the SBC algorithm of Ghaddar, Anjos and Liers in order to compute such solutions in less time. We extend the design principles of the successful BiqMac solver for maximum 2-cut to the general maximum k-cut problem. As part of this extension, we investigate different ways of choosing variables for branching. We also study the impact of the separation of clique inequalities within this new framework and observe that it frequently reduces the number of subproblems considerably. Our computational results suggest that the proposed approach achieves a drastic speedup in comparison to SBC, especially when k=3. We also made a comparison with the orbitopal fixing approach of Kaibel, Peinhardt and Pfetsch. The results suggest that, while their performance is better for sparse instances and larger values of k, our proposed approach is superior for smaller k and for dense instances of medium size. Furthermore, we used CPLEX for solving the ILP formulation underlying the orbitopal fixing algorithm and conclude that especially on dense instances the new algorithm outperforms CPLEX by far.

Miguel F. Anjos, Bissan Ghaddar, Lena Hupp, Frauke Liers, Angelika Wiegele

On Perspective Functions and Vanishing Constraints in Mixed-Integer Nonlinear Optimal Control

Abstract

Logical implications appear in a number of important mixed-integer nonlinear optimal control problems (MIOCPs). Mathematical optimization offers a variety of different formulations that are equivalent for boolean variables, but result in different relaxations. In this article we give an overview over a variety of different modeling approaches, including outer versus inner convexification, generalized disjunctive programming, and vanishing constraints. In addition to the tightness of the respective relaxations, we also address the issue of constraint qualification and the behavior of computational methods for some formulations. As a benchmark, we formulate a truck cruise control problem with logical implications resulting from gear-choice specific constraints. We provide this benchmark problem in AMPL format along with different realistic scenarios. Computational results for this benchmark are used to investigate feasibility gaps, integer feasibility gaps, quality of local solutions, and well-behavedness of the presented reformulations of the benchmark problem. Vanishing constraints give the most satisfactory results.

Michael N. Jung, Christian Kirches, Sebastian Sager

Scheduling and Routing of Fly-in Safari Planes Using a Flow-over-Flow Model

Abstract

The scheduling and routing of small planes for fly-in safaris is a challenging planning problem. Given a fleet of planes and a set of flight requests with bounds on the earliest departure and latest arrival times, the planes must be scheduled and routed so that all demands are satisfied. Capacity restrictions on the load and fuel also must be satisfied. Moreover the refueling of the planes, which can only be done in certain locations, must be scheduled. We present a mixed-integer linear programming based formulation for this problem. For its solution we develop a primal heuristic based on randomized local search. We try to enhance the local search by using exact methods to solve subproblems that only involve a small number of planes. Using a branch-and-cut solver, the MILP formulation can be solved to proven optimality only for small instances. To achieve better dual bounds we present a set partitioning based formulation, where new columns are generated on demand by heuristics and exact methods. We also present a new formulation where the time windows are relaxed, and later reintroduced by incumbent branching. Numerical results on real-world instances show that this time-free approach gives the best results.

Armin Fügenschuh, George Nemhauser, Yulian Zeng

Mixed Integer Programming: Analyzing 12 Years of Progress

Abstract

Back in 2001, Bixby et al. (The Sharpest Cut: The Impact of Manfred Padberg and His Work, pp. 309–325, 2004) provided an analysis of the performance impact of the main mixed integer programming features and improvements up to CPLEX 8.0 for a workshop in honor of Manfred Padberg’s 60th birthday, which was later published in a Festschrift edited by Martin Grötschel (The Sharpest Cut: The Impact of Manfred Padberg and His Work, 2004). Now, 12 years later, Grötschel’s own 65th birthday celebration seems to be the ideal opportunity to provide an update on the state of affairs.

In this paper, we outline an unbiased way to analyze benchmark results and apply this scheme to assess the contribution of the main components in CPLEX 12.5 to the ability to solve MIPs. We highlight some of the more recent features, in particular the deterministic parallel optimizer.

Tobias Achterberg, Roland Wunderling

Progress in Academic Computational Integer Programming

Abstract

This paper discusses issues related to the progress in computational integer programming. The first part deals with the question to what extent computational experiments can be reproduced at all. Afterward the performance measurement of solvers and their comparison are investigated. Then academic progress in solving mixed-integer programming at the examples of the solver SIP and its successor SCIP is demonstrated. All arguments are supported by computational results. Finally, we discuss the pros and cons of developing academic software for solving mixed-integer programs.

Thorsten Koch, Alexander Martin, Marc E. Pfetsch

Titel: Facets of Combinatorial Optimization
herausgegeben von: Michael Jünger
Gerhard Reinelt
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-38189-8
Print ISBN: 978-3-642-38188-1
DOI: https://doi.org/10.1007/978-3-642-38189-8