loading subjects...
Ebook: Combinatorial Optimization
loading...
This book is a collection of six articles arising from the meeting of the NATO Advanced Study Institute (ASI) “Combinatorial Optimization: Methods and Applications”, which was held at the University of Montreal in June 2006. This ASI consisted of seven series of five one-hour lectures and one series of four one-hour lectures. It was attended by some sixty students of graduate or postdoctoral level from fifteen countries worldwide. Topics include: integer and mixed integer programming, facility location, branching on split disjunctions, convexity in combinatorial optimization, and VLSI design. Although drawn from the 2006 lecture series, the articles included in this volume were all either written or updated by the authors in 2010, so that this collection of papers reflects a state-of-the-art overview of combinatorial optimization methods and their applications.
This book consists of six articles that came out of the following eight lecture series given at the NATO Advanced Study Institute (ASI) “Combinatorial Optimization: Methods and Applications” held at Université de Montréal on June 19 – 30, 2006:
Gérard Cornuéjols
(Carnegie Mellon University, USA)
Mixed integer programming
Sanjeeb Dash
(IBM Thomas J. Watson Research Center, USA)
Mixed integer rounding cuts and cyclic group polyhedra
Yury Kochetov
(Sobolev Institute of Mathematics, Russia)
Facility location problems. Discrete models and local search methods
Bernhard Korte; substituted by Stephan Held after the first lecture
(Forschungsinstitut für Diskrete Mathematik, Germany)
Making chips faster
Gleb Koshevoy
(Russian Academy of Sciences, Russia)
Discrete convexity and its applications in combinatorics
Shmuel Onn
(Technion - Israel Institute of Technology, Israel)
Convex discrete optimization
Dieter Rautenbach
(Institut für Optimierung und Operations Research Universität Ulm, Ulm, Germany)
Optimization and timing in VLSI design
Jens Vygen
(Forschungsinstitut für Diskrete Mathematik, Germany)
Combinatorial optimization in VLSI placement and routing
The six articles are ordered alphabetically by the last name of their first author. The article by Nannicini et al. has been written in 2010 as a follow-up to the lectures given by Cornuéjols at the ASI. The article by Onn is a reprint of his monograph published by Springer in Encyclopedia of Optimization 2009, which follows the outline of his lectures given at the ASI. The remaining four articles also follow the lectures given at the ASI, but they have been updated in 2010.
We survey recent research on mixed-integer rounding (MIR) inequalities and a generalization, namely the two-step MIR inequalities defined by Dash and Günlük (2006). We discuss the master cyclic group polyhedron of Gomory (1969) and discuss how other subadditive inequalities, similar to MIR inequalities, can be derived from this polyhedron. Recent numerical experiments have shed much light on the strength of MIR inequalities and the closely related Gomory mixed-integer cuts, especially for the MIP instances in the MIPLIB 3.0 library, and we discuss these experiments and their outcomes. Balas and Saxena (2007), and independently, Dash, Günlük and Lodi (2007), study the strength of the MIR closure of MIPLIB instances, and we explain their approach and results here. We also give a short proof of the well-known fact that the MIR closure of a polyhedral set is a polyhedron. Finally, we conclude with a survey of the complexity of cutting-plane proofs which use MIR inequalities.
This survey is based on a series of 5 lectures presented at the Séminaire de mathématiques supérieures, of the NATO Advanced Studies Institute, held in the Université de Montréal, from June 19 – 30, 2006.
VLSI design is probably the most fascinating application area of combinatorial optimization. Virtually all classical combinatorial optimization problems, and many new ones, occur naturally as subtasks. Due to the rapid technological development and major theoretical advances the mathematics of VLSI design has changed significantly over the last ten to twenty years. This survey paper gives an up-to-date account on the key problems in layout and timing closure. It also presents the main mathematical ideas used in a set of algorithms called BonnTools, which are used to design many of the most complex integrated circuits in industry.
Discrete location theory is one of the most dynamic areas of operations research. We present the basic mathematical models used in this field, as well as their properties and relationship with pseudo-Boolean functions. We also investigate the theory of PLS-complete problems, average and worst case computational complexity of the local search algorithms, and approximate local search. Finally, we discuss computationally difficult test instances and promising directions for further research.
We explain what subsets of the lattice \mathbb{Z}n and what functions on the lattice \mathbb{Z}n could be called convex. The basis of the theory is the following three main postulates of classical convex analysis: concave functions are closed under sums; they are also closed under convolutions; and the superdifferential of a concave function is nonempty at each point of the domain. Interesting (and even dual) classes of discrete concave functions arise if we require either the existence of superdifferentials and closeness under convolutions or the existence of superdifferentials and closeness under sums. The corresponding classes of convex sets are obtained as the affinity domains of such discretely concave functions. The classes of the first type are closed under (Minkowski) sums, and the classes of the second type are closed under intersections. In both classes, the separation theorem holds true. Unimodular sets play an important role in the classification of such classes. The so-called polymatroidal discretely concave functions, most interesting for applications, are related to the unimodular system An := {±ei, ei − ej}. We demonstrate that such functions naturally appear in mathematical economics, in combinatorics, play an important role for solution of the Horn problem, for describing submodule invariants over discrete valuation rings, etc.
Branch-and-Cut is the most commonly used algorithm for solving Integer and Mixed-Integer Linear Programs. In order to reduce the number of nodes that have to be enumerated before optimality of a solution can be proven, branching on general disjunctions (i.e., split disjunctions involving more than one variable, as opposed to branching on simple disjunctions defined on one variable only) was shown to be very effective on particular classes of instances, but not much work has been done to study general purpose methods of this kind. In this paper, we survey known results related to this line of research, and we study the relationship between branching and cutting from a split disjunction.
We develop an algorithmic theory of convex optimization over discrete sets. Using a combination of algebraic and geometric tools we are able to provide polynomial time algorithms for solving broad classes of convex combinatorial optimization problems and convex integer programming problems in variable dimension. We discuss some of the many applications of this theory including to quadratic programming, matroids, bin packing and cutting-stock problems, vector partitioning and clustering, multiway transportation problems, and privacy and confidential statistical data disclosure. Highlights of our work include a strongly polynomial time algorithm for convex and linear combinatorial optimization over any family presented by a membership oracle when the underlying polytope has few edge-directions; a new theory of so-termed n-fold integer programming, yielding polynomial time solution of important and natural classes of convex and linear integer programming problems in variable dimension; and a complete complexity classification of high dimensional transportation problems, with practical applications to fundamental problems in privacy and confidential statistical data disclosure.