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.

Bei dieser Ver6ffentlichung handelt es sich urn eine Zusaromen- stellung von Unterlagen fur einen yom Institut fur Operations Research der ETH Zurich gehaltenen Kurs. Sie sollen einerseits einen Ueberblick uber die Verfahren zur Behandlung verschie- dener Arten kombinatorischer Entscheidungsprobleme vermitteln und anderseits durch die Darstellung konkreter Beispiele zu weiteren Anwendungen anregen. Neben bewiihrten Methoden werden Aufsiitze neueren Datums, die noch keinen Eingang in die Lehrbuchliteratur gefunden haben, so- wie unpublizierte Arbeiten zu den vorliegenden Ueberblicksbei- triigen integriert. Entsprechende Literaturangaben gehen aus dem Text hervor. Herstellung des Manuskripts: Frau Maria Daniel Inhaltsverzeichnis 1. Kombinatorische Entscheidungsprobleme: Einfuhrung Thomas M. Liebling . . -. -----. -. ------. . --. -. -. -. -. . . . . . . -. . . 2. Optimierungsprobleme mit polynomial begrenzten Algorithmen (P-Probleme) Hansj6rg Benninger und Thomas M. Liebling . . . . -. . . . . . -. -. . . . 14 3. Fallstudie 1: Optimaler Fahrplan fur eine Privatbahn Jurg Mayer . . . -. . . -. . -. ---. -. -. . -. . . . . -. -. -. . . . . . . . . . . . . . . . . 56 4. Fallstudie 2: Optimaler Einsatz eines betriebseigenen Stra entransportsystems Jurg Mayer . . . . . . . . ---. -. . . --. . -. -. -. ---. ---. . -. . . . . . -. . . . . . 63 5. Fallstudie 3: Maschinelle Berechnung von Fahrdistanzen Walter Altherr und Jurg Mayer . --. -. -. . . . . -. . . . . . . . . . . . . . . . . 70 6. Optimierungsprobleme mit nicht polynomial begrenzten Algorithmen (NP-Probleme) Francisco Benito und Heinz Gr6flin . . . -. . . . . . . . . -. -. . . . . -. -. 81 7. Interessenkonflikte Max R6ssler . . -. . . . . . . . . . . --. . . . -. . . . . . . . . -. . -. . . -. . . . . -. . . - 122 8. Optimierung und Aufteilung der Kosten regionaler Abwasser- verbande Andres Polymeris ---. -. . . . -. . -. --. -. . . -. . . . -. . . . . . . . . -. . . . . . 151 9. Datenstrukturen J6rg Waldvogel . -. . . . . . . -. --. . . . . . -. -. . . . . . . . . -. -. . . . . . . . . . .

Die vorliegende Arbeit befasst sich mit den Problemkreisen der Standortwahl und der Tourenplanung. Zwischen diesen beiden Themen besteht meist grund- satzliche gegenseitige Abhangigkeit, ob sie nun in die konkrete Aufgaben- stellung miteinbezogen oder willentlich von ihr ausgeklammert werde: fiir die Festlegung von wirts chaftlichen Tourenplanen beis pielsweis e zum Zwecke der Belieferung von Filialgeschaften wird man wissen mussen, wie viele Filialgeschafte zu bedienen sind und wo sie ihren Standort haben, aber auch von wie vie len Bedienungspunkten aus dies geschehen solI und wo diese letzteren gefunden werden konnen. Umgekehrt lassen sich Zahl und Standorte der an einem solchen Verteilsystem gesamthaft angeschlossenen Umschlagpunkte zweifellos durch Mitberucksichtigung der Tourenplanung neben den anderen Einflussquellen in wirtschaftlicher Sicht bestimmen. Dennoch kann der Grad dieser gegenseitigen Abhangigkeit je nach Aufgaben- stellung recht unterschiedlich sein: die Wahl des genauen "Standorts" eines Flughafens innerhalb einer grosseren Region wird sich vermutlich weit weniger ausgepragt oder praktisch gar nicht auf die Wirtschaftlichkeit der internationa- len "Tourenplanung" von dort beheimateten Flugzeugen einer Fluggesellschaft auswirken verglichen mit der Bedeutung des Standorts eines Lagerhauses fiir die Wirtschaftlichkeit der Tourenplanung zwecks Belieferung von Detail- s chaften von dort aus, weil im ersteren FaIle die beiden Problem -Kreis e von anderen, unabhangigen Einflus sfaktoren dominierenden Charakters tiber- schattet werden. Beide erwahnten Aufgabentypen: Standortwahl und Festlegung von Bedienungs- touren sind vom Standpunkt des Operations Research aus gesehen anspruchs- voll und nicht ohne weiteres losbar. Die mathematische Behandlungsschwierig- keit steigt mit dem Grade der Berucksichtigung der gegenseitigen Abhangigkeit.