Combinatorial Optimization

1. Front Matter

   Pages I-XI

   PDF

2. Variable Decomposition, Constraint Decomposition and Cross Decomposition in General Mathematical Programming

   • Olaf E. Flippo, Alexander H. G. Rinnooy Kan

   Pages 1-18

3. Surrogate Constraint Methods for Linear Inequalities

   • Kai Yang, Katta G. Murty

   Pages 19-38

4. An Evaluation of Algorithmic Refinements and Proper Data Structures for the Preflow-Push Approach for Maximum Flow

   • U. Derigs, W. Meier

   Pages 39-62

5. A Cutting Plane Algorithm for the Single Machine Scheduling Problem with Release Times

   • G. L. Nemhauser, M. W. P. Savelsbergh

   Pages 63-83

6. The Linear Assignment Problem

   • Mustafa Akgül

   Pages 85-122

7. Cost Allocation In The Oil Industry: An Example

   • Kurt O. Jørnsten

   Pages 123-132

8. On Preference Orders for Sequencing Problems Or, What Hath Smith Wrought?

   • E. L. Lawler

   Pages 133-159

9. Dynamic Basis Partitioning for Network Flows with Side Constraints

   • Wonjoon Choi, Süleyman Tüfekçi

   Pages 161-185

10. Combinatorial Optimization Models Motivated by Robotic Assembly Problems

    • Horst W. Hamacher

    Pages 187-198

11. Job Shop Scheduling

    • J. K. Lenstra

    Pages 199-207

12. On the Construction of the Set of K-best Matchings and Their Use in Solving Constrained Matching Problems

    • U. Derigs, A. Metz

    Pages 209-223

13. Solving Large Scale Multicommodity Networks Using Linear—Quadratic Penalty Functions

    • Mustafa Ç Pinar, Stavros A. Zenios

    Pages 225-230

14. An Analysis of the Minimal Spanning Tree Structure

    • Elzbieta Trybus

    Pages 231-234

15. Genetic Algorithms: A New Approach to the Timetable Problem

    • Alberto Colorni, Marco Dorigo, Vittorio Maniezzo

    Pages 235-239

16. A New Approximation Technique for Hypergraph Partitioning Problem

    • Scott W. Hadley

    Pages 241-244

17. Optimal Location of Concentrators in a Centralized Teleprocessing Network

    • M. G. de Oliveira

    Pages 245-248

18. A Column Generation Algorithm for the Vehicle Routing Problem with Time Windows

    • Martin Desrochers, Jacques Desrosiers, Marius Solomon

    Pages 249-252

19. The Linear Complementary Problem, Sufficient Matrices and the Criss-Cross Method

    • D. den Hertog, C. Roos, T. Terlaky

    Pages 253-257

20. A Characterization of Lifted-Cover Facets of Knapsack Polytope with GUB Constraints

    • George L. Nemhauser, Gabriele Sigismondi, Pamela Vance

    Pages 259-261

There have been significant developments in the theory and practice of combinatorial optimization in the last 15 years. This progress has been evidenced by a continuously increasing number of international and local conferences, books and papers in this area. This book is also another contribution to this burgeoning area of operations research and optimization. This volume contains the contributions of the participants of the recent NATO Ad­ vanced Study Institute, New Frontiers in the Theory and Practice of Combinatorial Op­ timization, which was held at the campus of Bilkent University, in Ankara, Turkey, July 16-29, 1990. In this conference, we brought many prominent researchers and young and promising scientists together to discuss current and future trends in the theory and prac­ tice of combinatorial optimization. The Bilkent campus was an excellent environment for such an undertaking. Being outside of Ankara, the capital of Turkey, Bilkent University gave the participants a great opportunity for exchanging ideas and discussing new theories and applications without much distraction. One of the primary goals of NATO ASIs is to bring together a group of scientists and research scientists primarily from the NATO countries for the dissemination of ad­ vanced scientific knowledge and the promotion of international contacts among scientists. We believe that we accomplished this mission very successfully by bringing together 15 prominent lecturers and 45 promising young scientists from 12 countries, in a university environment for 14 days of intense lectures, presentations and discussions.

• Anwendungen
• Applications of Combinatorial Optimization
• Combinatorics
• Diskrete Optimierung
• Kombinatorische Optimierung
• Models of Discrete Optimization
• Network Flow Problems
• Optimierungsmodelle
• combinatorial optimization
• communication
• optimization
• algorithm analysis and problem complexity

• Department of Industrial Engineering, Bilkent University, Ankara, Turkey

  Mustafa Akgül

• Fachbereich Mathematik, Universität Kaiserslautern, Kaiserslautern, Germany

  Horst W. Hamacher

• Department of Industrial and Systems Engineering, University of Florida, Gainesville, USA

  Süleyman Tüfekçi

Policies and ethics