Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben

2010 | Buch

Solution of a Large-Scale Traveling-Salesman Problem Kapitel lesen Erstes Kapitel lesen

50 Years of Integer Programming 1958-2008

From the Early Years to the State-of-the-Art

herausgegeben von: Michael Jünger, Thomas M. Liebling, Denis Naddef, George L. Nemhauser, William R. Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, Laurence A. Wolsey

Verlag: Springer Berlin Heidelberg

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

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

In 1958, Ralph E. Gomory transformed the field of integer programming when he published a paper that described a cutting-plane algorithm for pure integer programs and announced that the method could be refined to give a finite algorithm for integer programming. In 2008, to commemorate the anniversary of this seminal paper, a special workshop celebrating fifty years of integer programming was held in Aussois, France, as part of the 12th Combinatorial Optimization Workshop.

It contains reprints of key historical articles and written versions of survey lectures on six of the hottest topics in the field by distinguished members of the integer programming community. Useful for anyone in mathematics, computer science and operations research, this book exposes mathematical optimization, specifically integer programming and combinatorial optimization, to a broad audience.

Inhaltsverzeichnis

Frontmatter

The Early Years

Frontmatter
Chapter 1. Solution of a Large-Scale Traveling-Salesman Problem
Abstract
The RAND Corporation in the early 1950s contained “what may have been the most remarkable group of mathematicians working on optimization ever assembled” [6]: Arrow, Bellman, Dantzig, Flood, Ford, Fulkerson, Gale, Johnson, Nash, Orchard-Hays, Robinson, Shapley, Simon, Wagner, and other household names. Groups like this need their challenges. One of them appears to have been the traveling salesman problem (TSP) and particularly its instance of finding a shortest route through Washington, DC, and the 48 states [4, 7].
Vašek Chvátal, William Cook, George B. Dantzig, Delbert R. Fulkerson, Selmer M. Johnson
Chapter 2. The Hungarian Method for the Assignment Problem
Abstract
This paper has always been one of my favorite “children,” combining as it does elements of the duality of linear programming and combinatorial tools from graph theory. It may be of some interest to tell the story of its origin.
Harold W. Kuhn
Chapter 3. Integral Boundary Points of Convex Polyhedra
Abstract
Here is the story of how this paper was written. (a) Independently, Alan and Joe discovered this easy theorem: if the “right hand side” consists of integers, and if the matrix is “totally unimodular”, then the vertices of the polyhedron defined by the linear inequalities will all be integral. This is easy to prove and useful. As far as we know, this is the only part of our theorem that anyone has ever used.
Alan J. Hoffman, Joseph B. Kruskal
Chapter 4. Outline of an Algorithm for Integer Solutions to Linear Programs and An Algorithm for the Mixed Integer Problem
Abstract
Later in 1957, as the end of my three-year tour of duty in the Navy was approaching, Princeton invited me to return as Higgins Lecturer in Mathematics. I had been aWilliams undergraduate and a then a graduate student at Cambridge and Princeton while getting my Ph.D. I had published 4 papers in non-linear differential equations, a subject to which I had been introduced by two wonderful people whose support and encouragement made an unforgettable and wonderful difference in my life: Professor Donald Richmond of Williams College and Professor Solomon Lefschetz of Princeton.
Ralph E. Gomory
Chapter 5. An Automatic Method for Solving Discrete Programming Problems
Abstract
In the late 1950s there was a group of teachers and research assistants at the London School of Economics interested in linear programming and its extensions, in particular Helen Makower, George Morton, Ailsa Land and Alison Doig. We had considered the ‘Laundry Van Problem’ until we discovered that it was known as the Traveling Salesman Problem, and had looked at aircraft timetabling, until quickly realizing that even the planning for the Scottish sector was beyond our capability! Alison Doig (now Harcourt) had studied the paper trim problem for her Masters project in Melbourne before coming to England.
Ailsa H. Land, Alison G. Doig
Chapter 6. Integer Programming: Methods, Uses, Computation
Abstract
This article exists because Robert Thrall, at the time Editor of Management Science, invited me to write a survey of the then new area of “integer programming.” First printed in 1965, it was subsequently reprinted in 1968 in Mathematics of the Decision Sciences (edited by George B. Dantzig and Arthur F Veinott, Jr., a volume of the AMS’s Lectures in Applied Mathematics) and in 1970 in Proceedings of the Princeton Symposium onMathematical Programming (edited by HaroldW. Kuhn, a Princeton University Press publication). In its last resurrection it was supplemented by 16 pages of “Recent Developments.” By then the bibliography had grown from the original 105 items to 232 items: the field was burgeoning.
Michel Balinski
Chapter 7. Matroid Partition
Abstract
This article, “Matroid Partition”, which first appeared in the book edited by George Dantzig and Pete Veinott, is important to me for many reasons: First for personal memories of my mentors, Alan J. Goldman, George Dantzig, and Al Tucker. Second, for memories of close friends, as well as mentors, Al Lehman, Ray Fulkerson, and Alan Hoffman. Third, for memories of Pete Veinott, who, many years after he invited and published the present paper, became a closest friend. And, finally, for memories of how my mixed-blessing obsession with good characterizations and good algorithms developed.
Jack Edmonds
Chapter 8. Reducibility Among Combinatorial Problems
Abstract
Throughout the 1960s I worked on combinatorial optimization problems including logic circuit design with Paul Roth and assembly line balancing and the traveling salesman problem with Mike Held. These experiences made me aware that seemingly simple discrete optimization problems could hold the seeds of combinatorial explosions. The work of Dantzig, Fulkerson, Hoffman, Edmonds, Lawler and other pioneers on network flows, matching and matroids acquainted me with the elegant and efficient algorithms that were sometimes possible. Jack Edmonds’ papers and a few key discussions with him drew my attention to the crucial distinction between polynomial-time and superpolynomial-time solvability. I was also influenced by Jack’s emphasis on min-max theorems as a tool for fast verification of optimal solutions, which foreshadowed Steve Cook’s definition of the complexity class NP. Another influence was George Dantzig’s suggestion that integer programming could serve as a universal format for combinatorial optimization problems.
Richard M. Karp
Chapter 9. Lagrangian Relaxation for Integer Programming
Abstract
It is a pleasure to write this commentary because it offers an opportunity to express my gratitude to several people who helped me in ways that turned out to be essential to the birth of [8]. They also had a good deal to do with shaping my early career and, consequently, much of what followed.
Arthur M. Geoffrion
Chapter 10. Disjunctive Programming
Abstract
In April 1967 I and my family arrived into the US as fresh immigrants from behind the Iron Curtain. After a fruitful semester spent with George Dantzig’s group in Stanford, I started working at CMU. My debut in integer programming and entry ticket into Academia was the additive algorithm for 0-1 programming [B65], an implicit enumeration procedure based on logical tests akin to what today goes under the name of constraint propagation. As it used only additions and comparisons, it was easy to implement and was highly popular for a while. However, I was aware of its limitations and soon after I joined CMU I started investigating cutting plane procedures, trying to use for this purpose the tools of convex analysis: support functions and their level sets, maximal convex extensions, polarity, etc.
Egon Balas

From the Beginnings to the State-of-the-Art

Frontmatter
Chapter 11. Polyhedral Approaches to Mixed Integer Linear Programming
Abstract
This survey presents tools from polyhedral theory that are used in integer programming. It applies them to the study of valid inequalities for mixed integer linear sets, such as Gomory’s mixed integer cuts.
Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli
Chapter 12. Fifty-Plus Years of Combinatorial Integer Programming
Abstract
Throughout the history of integer programming, the field has been guided by research into solution approaches to combinatorial problems. We discuss some of the highlights and defining moments of this area.
William Cook
Chapter 13. Reformulation and Decomposition of Integer Programs
Abstract
We examine ways to reformulate integer and mixed integer programs. Typically, but not exclusively, one reformulates so as to obtain stronger linear programming relaxations, and hence better bounds for use in a branch-and-bound based algorithm. First we cover reformulations based on decomposition, such as Lagrangean relaxation, the Dantzig-Wolfe reformulation and the resulting column generation and branch-and-price algorithms. This is followed by an examination of Benders’ type algorithms based on projection. Finally we discuss extended formulations involving additional variables that are based on problem structure. These can often be used to provide strengthened a priori formulations. Reformulations obtained by adding cutting planes in the original variables are not treated here.
François Vanderbeck, Laurence A. Wolsey

Current Topics

Frontmatter
Chapter 14. Integer Programming and Algorithmic Geometry of Numbers
A tutorial
Abstract
This chapter surveys a selection of results from the interplay of integer programming and the geometry of numbers. Apart from being a survey, the text is also intended as an entry point into the field. I therefore added exercises at the end of each section to invite the reader to delve deeper into the presented material.
Friedrich Eisenbrand
Chapter 15. Nonlinear Integer Programming
Abstract
Research efforts of the past fifty years have led to a development of linear integer programming as a mature discipline of mathematical optimization. Such a level of maturity has not been reached when one considers nonlinear systems subject to integrality requirements for the variables. This chapter is dedicated to this topic. The primary goal is a study of a simple version of general nonlinear integer problems, where all constraints are still linear. Our focus is on the computational complexity of the problem, which varies significantly with the type of nonlinear objective function in combination with the underlying combinatorial structure. Numerous boundary cases of complexity emerge, which sometimes surprisingly lead even to polynomial time algorithms.We also cover recent successful approaches for more general classes of problems. Though no positive theoretical efficiency results are available, nor are they likely to ever be available, these seem to be the currently most successful and interesting approaches for solving practical problems. It is our belief that the study of algorithms motivated by theoretical considerations and those motivated by our desire to solve practical instances should and do inform one another. So it is with this viewpoint that we present the subject, and it is in this direction that we hope to spark further research.
Raymond Hemmecke, Matthias Köppe, Jon Lee, Robert Weismantel
Chapter 16. Mixed Integer Programming Computation
Abstract
The first 50 years of Integer and Mixed-Integer Programming have taken us to a very stable paradigm for solving problems in a reliable and effective way. We run over these 50 exciting years by showing some crucial milestones and we highlight the building blocks that are making nowadays solvers effective from both a performance and an application viewpoint. Finally, we show that a lot of work must still be done for improving the solvers and extending their modeling capability.
Andrea Lodi
Chapter 17. Symmetry in Integer Linear Programming
Abstract
An integer linear program (ILP) is symmetric if its variables can be permuted without changing the structure of the problem. Areas where symmetric ILPs arise range from applied settings (scheduling on identical machines), to combinatorics (code construction), and to statistics (statistical designs construction). Relatively small symmetric ILPs are extremely difficult to solve using branch-and-cut codes oblivious to the symmetry in the problem. This paper reviews techniques developed to take advantage of the symmetry in an ILP during its solution. It also surveys related topics, such as symmetry detection, polyhedral studies of symmetric ILPs, and enumeration of all non isomorphic optimal solutions.
François Margot
Chapter 18. Semidefinite Relaxations for Integer Programming
Abstract
We survey some recent developments in the area of semidefinite optimization applied to integer programming. After recalling some generic modeling techniques to obtain semidefinite relaxations for NP-hard problems, we look at the theoretical power of semidefinite optimization in the context of the Max-Cut and the Coloring Problem. In the second part, we consider algorithmic questions related to semidefinite optimization, and point to some recent ideas to handle large scale problems. The survey is concluded with some more advanced modeling techniques, based on matrix relaxations leading to copositive matrices.
Franz Rendl
Chapter 19. The Group-Theoretic Approach in Mixed Integer Programming
Abstract
In this chapter, we provide an overview of the mathematical foundations and recent theoretical and computational advances in the study of the grouptheoretic approach in mixed integer programming. We motivate the definition of group relaxation geometrically and present methods to optimize linear functions over this set. We then discuss fundamental results about the structure of group relaxations. We describe a variety of recent methods to derive valid inequalities for master group relaxations and review general proof techniques to show that candidate inequalities are strong (extreme) for these sets. We conclude by discussing the insights gained from computational studies aimed at gauging the strength of grouptheoretic relaxations and cutting planes for mixed integer programs.
Jean-Philippe P. Richard, Santanu S. Dey
Backmatter
Metadaten
Titel
50 Years of Integer Programming 1958-2008
herausgegeben von
Michael Jünger
Thomas M. Liebling
Denis Naddef
George L. Nemhauser
William R. Pulleyblank
Gerhard Reinelt
Giovanni Rinaldi
Laurence A. Wolsey
Copyright-Jahr
2010
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-540-68279-0
Print ISBN
978-3-540-68274-5
DOI
https://doi.org/10.1007/978-3-540-68279-0

Premium Partner

    Bildnachweise