Integer programming and network flows. (English) Zbl 0197.45701

Hu, T. C.

Reading, Mass. etc.: Addison-Wesley Publishing Company. xii, 452 p. (1969).

Lehrbücher über ganzzahlige Optimierung gibt es bisher recht wenig, so daß das Erscheinen dieses Werks eine wertvolle Bereicherung des Gebietes darstellt. Man mag es unter Umständen als Nachteil empfinden, daß nur Theorien und Methoden aufgenommen wurden, die sich aus den auf Gomory zurückgehenden Schnittverfahren ergeben und die branch-and-bound-Methoden nur in einem kurzen Anhang angedeutet werden. Diese Tatsache fällt jedoch aus mehreren Gründen kaum ins Gewicht. Zum ersten hat sich in letzter Zeit gezeigt, daß die Schnittverfahren im allgemeinen Falle numerisch günstiger als alle anderen Methoden sind; zum zweiten gibt der Verf. die aus den Arbeiten von Gomory ableitbaren Ergebnisse bis zu den neusten Entwicklungen – wie etwa die des asymptotischen Algorithmus durch Gomory selbst – sehr ausführlich wieder und zum dritten werden die engen und interessanten Verbindungen zur Graphentheorie behandelt, so daß die lehrbuchmäßig wohl erstmalig durchgeführte Synthese als recht glücklich erscheint.
Im Einzelnen soll das Inhaltsverzeichnis genügen:
1. Lineare Optimierung: Grundlagen – Simplexmethode – Dualität – Duale Simplexmethode – Revidierte Simplexmethode – Primal-duale Methode – Dekompositionsprinzip.
2. Ströme in Netzwerken: Maximalstrom – Maximalstrommatrix (multiterminal problem) – Kürzeste Wege und Ströme mit minimalen Kosten – Ströme verschiedenartiger Produkte (multicommodity flows) – Ströme in Kontinua.
3. Ganzzahlige Optimierung: Gewöhnlicher Gomory-Algorithmus – Algorithmus in ganzen Zahlen – Gemischt-ganzzahlige Optimierung – Ganzzahlige Probleme mit parabolischen Nebenbedingungen – Primaler Algorithmus – Knapsaek-Problem – Beziehungen zwischen linearen und ganzzahligen Problemen (insbesondere asymptotischer Algorithmus) – Randflächen (faces) ganzzahliger Polyeder.
In einem Anhang aus vier Teilen werden die Smithsche Normalform (Elementarteiler-Diagonalform einer ganzzahligen quadratischen Matrix), ein auf Dreyfus und Freimer zurückgehender neuer Zugang zur Dualitätstheorie, Algorithmen vom branch-and-bound-Typ und schließlich in Form einer tabellarischen Zusammenstellung Randflächen, Eckpunkte und Inzidenzmatrizen von Polyedern dargestellt.

Reviewer: Joachim Piehler (Merseburg)

MSC:

90C10	Integer programming
90C35	Programming involving graphs or networks
90-02	Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C05	Linear programming
90C27	Combinatorial optimization
90B10	Deterministic network models in operations research
90C46	Optimality conditions and duality in mathematical programming
90C57	Polyhedral combinatorics, branch-and-bound, branch-and-cut

Keywords:

integer programming; Gomory cut; network flows