HANDBOOK OF APPLIED OPTIMIZATION
|
EDITED BY Panos M. Pardalos and Mauricio G. C. Resende Copyright © 2002 by Oxford University Press, Inc. Published by Oxford University Press, Inc.
|
Preface
Optimization
is a basic tool in applied research, engineering, business, and the
sciences. In the last decade, algorithmic advances as well as hardware
and software improvements have provided an excellent framework on which
to build optimization-based decision support systems, as well as
multidiscipline design tools. Despite the dynamic state of applied
optimization, we feel that the time is ripe to bring together in one
volume the major algorithmic and software advances in this field.
Leading experts in applied optimization have contributed to this volume. The Handbook
of Applied Optimization is aimed at engineers, scientists, operations
researchers, and other applications specialists who are looking for the
most appropriate and recent optimization tools to solve particular
problems. The handbook provides a broad spectrum of advances in applied
optimization with a focus on the algorithmic and computational aspect
of this field.
The handbook
consists of three main parts: algorithms, applications, and software.
In the algorithms section of the handbook, the important algorithms in
the major fields of optimization are described. The purpose of the
section on applications is to provide the practitioner with a
description of the relevant optimization issues in a number of specific
application areas. We include overview articles discussing broad
problem types, such as scheduling, vehicle routing, network design, bin
packing, inventory management, travelling salesman, satisfiability,
location, and assignment problems, as well as some examples of applied
optimization in specific areas. These applications cover a broad
spectrum of fields, such as transportation, agriculture, manufacturing,
aerospace, telecommunications, energy, biology, finance, and the
environment. In the software section of the handbook, the tools of
applied optimization are described, with an emphasis on practical
details: how to implement and test optimization algorithms, use
existing optimization packages and the Internet, and use modelling
languages to build optimization systems. We would like to take the
opportunity to thank Oxford University Press for inviting us to edit
this handbook, the authors for their
contributions, and the anonymous referees for their valuable comments
and suggestions.
Panos M. Pardalos and Mauricio G. C. Resende
CONTENTS
Preface xiii
Panos M. Pardalos and Mauricio G. C. Resende
Introduction xv
Panos M. Pardalos and Mauricio G. C. Resende
PART ONE: ALGORITHMS
1 Linear Programming 1
1.1 Introduction 1 [abstract]
Tamas Terlaky
1.2 Simplex-Type Algorithms 7 [abstract]
Tamas Terlaky
1.3 Interior-Point Methods for Linear Optimization 21 [abstract]
Kees Roos
2 Semidefinite Programming 40 [abstract]
Henry Wolkowicz
3 Combinatorial Optimization 51
3.1 Introduction 51 [abstract]
Panos M. Pardalos and Mauricio G. C. Resende
3.2 Branch-and-Bound Methods 53 [abstract]
Eva K. Lee
3.3 Branch-and-Cut Algorithms for Combinatorial Optimization
Problems 65 [abstract]
John E. Mitchell
3.4 Dynamic Programming Approaches 78 [abstract]
Augustine O. Esogbue
3.5 Local Search 104 [abstract]
Mutsunori Yagiura and Toshihide Ibaraki
3.6 Metaheuristics 123
3.6.1 Introduction 123 [abstract]
Bruce L. Golden and Edward A. Wasil
3.6.2 Ant Systems 130 [abstract]
Éric D. Taillard
3.6.3 Population Heuristics 138 [abstract]
John E. Beasley
3.6.4 Memetic Algorithms 157 [abstract]
Pablo Moscato
3.6.5 Greedy Randomized Adaptive Search Procedures 168 [abstract]
Leonidas S. Pitsoulis and Mauricio G. C. Resende
3.6.6 Scatter Search 183 [abstract]
Manuel Laguna
3.6.7 Tabu Search 194 [abstract]
Fred Glover and Manuel Laguna
3.6.8 Simulated Annealing 209 [abstract]
E. H. L. Aarts and H. M. M. Ten Eikelder
3.6.9 Variable Neighborhood Search 221 [abstract]
Pierre Hansen and Nenad Mladenovic
4 Quadratic Programming 235 [abstract]
Yinyu Ye
5 Nonlinear Programming 263
5.1 Introduction 263 [abstract]
Gianni Di Pillo and Laura Palagi
5.2 Unconstrained Nonlinear Programming 268 [abstract]
Gianni Di Pillo and Laura Palagi
5.3 Constrained Nonlinear Programming 285 [abstract]
Gianni Di Pillo and Laura Palagi
5.4 Nonsmooth Optimization 299 [abstract]
Manlio Gaudioso
6 Deterministic Global Optimization and Its Applications 311 [abstract]
Christodoulos A. Floudas
7 Decomposition Methods for Mathematical Programming 337 [abstract]
Philippe Mahey
8 Network Optimization 352
8.1 Introduction 352 [abstract]
Ravindra K. Ahuja, Thomas L. Magnanti, and
James B. Orlin
8.2 Maximum Flow Problem 363 [abstract]
Ravindra K. Ahuja, Thomas L. Magnanti, and
James B. Orlin
8.3 Shortest-Path Algorithms 375 [abstract]
Edith Cohen
8.4 Minimum-Cost Single-Commodity Flow 386 [abstract]
S. Thomas McCormick
8.5 Minimum-Cost Multicommodity Flow 404 [abstract]
Pierre Chardaire and Abdel Lisser
8.6 Minimum Spanning Tree Problem 422 [abstract]
Ravindra K. Ahuja, Thomas L. Magnanti, and
James B. Orlin
9 Integer Programming 431
9.1 Introduction 431 [abstract]
Nelson Maculan
9.2 Linear 0- 1 Programming 440 [abstract]
Nelson Maculan
9.3 Pseudo-Boolean Optimization 445 [abstract]
Yves Crama and Peter L. Hammer
9.4 Mixed-Integer Nonlinear Optimization 451 [abstract]
Christodoulos A. Floudas
9.5 Lagrangian Relaxation 465 [abstract]
Monique Guignard
9.6 Heuristics for 0 - 1 Mixed-Integer Programming 474 [abstract]
Arne Lřkketangen
10 Artificial Neural Networks in Optimization and Applications 478 [abstract]
Theodore B. Trafalis and Suat Kasap
11 Stochastic Programming 491 [abstract]
John R. Birge
12 Hierarchical Optimization 502 [abstract]
Hoang Tuy
13 Complementarity and Related Problems 514 [abstract]
Michael C. Ferris and Christian Kanzow
14 Data Envelopment Analysis 531 [abstract]
José H. Dulá
15 Parallel Algorithms in Optimization 544 [abstract]
Yair Censor and Stavros A. Zenios
16 Randomization in Discrete Optimization: Annealing Algorithms 560 [abstract]
Sanguthevar Rajasekaran
PART TWO: APPLICATIONS
17 Problem Types 569
17.1 Optimization and Heuristics of Scheduling 569 [abstract]
Chung-Yee Lee and Michael Pinedo
17.2 The Vehicle Routing Problem 584 [abstract]
John E. Beasley, Abilio Lucena, and Marcus Poggi de Aragăo
17.3 Network Designs: Approximations for Steiner Minimum Trees 595 [abstract]
Ding-Zhu Du
17.4 Approximate Solutions to Bin Packing Problems 607 [abstract]
Edward G. Coffman, Jr., Janos Csirik, and Gerhard J. Woeginger
17.5 The Traveling Salesman Problem 616 [abstract]
Rainer E. Burkard
17.6 Inventory Management 624 [abstract]
Dukwon Kim and Boghos D. Sivazlian
17.7 Location 632 [abstract]
Zvi Drezner
17.8 Algorithms for the Satisfiability (SAT) Problem 640 [abstract]
Jun Gu, Paul W. Purdom, John Franco, and Benjamin W. Wah
17.9 Assignment Problems 661 [abstract]
Eranda Çela
18 Application Areas 679
18.1 Transportation and Logistics 679 [abstract]
Warren B. Powell
18.2 Airline Optimization 689 [abstract]
Gang Yu and Benjamin G. Thengvall
18.3 Optimization in the Rail Industry 704 [abstract]
Alexandra M. Newman, Linda K. Nozick, and Candace Arai Yano
18.4 Forestry Industry 719 [abstract]
Andres Weintraub Pohorille and John Hof
18.5 Manufacturing Planning and Control 728 [abstract]
Stephen C. Graves
18.6 Semiconductor Production Planning 746 [abstract]
Robert C. Leachman
18.7 Optimization in the Aerospace Industry 763 [abstract]
Matthew E. Berge, John T. Betts, Sharon K. Filipowski,
William P. Huffman, and David P. Young
18.8 Energy 770
18.8.1 Optimization in Electrical Power Systems 770 [abstract]
Gerson Couto de Oliveira, Sergio Granville, and
Mario Pereira
18.8.2 Optimization Applications in Oil and Gas Recovery 808 [abstract]
Roland N. Horne
18.8.3 Natural Gas Pipeline Optimization 813 [abstract]
Roger Z. Ríos-Mercado
18.9 Optimization of Telecommunications Networks 826 [abstract]
G. Anandalingam
18.10 Optimization of Test Intervals in Nuclear Engineering 841 [abstract]
Stanislav Uryasev
18.11 Optimization in VLSI Design: Target Distance Models for Cell
Placement 851 [abstract]
Hussein A. Y. Etawil and Anthony Vannelli
18.12 Optimization Models in Transportation Planning 870 [abstract]
Michael Florian and Donald W. Hearn
18.13 Optimization in Computational Molecular Biology 885 [abstract]
Guoliang Xue
18.14 Optimization in the Financial Services Industry 901 [abstract]
Anna Nagurney
18.15 Applied Large-Scale Nonlinear Optimization for Optimal Control
of Partial Differential Equations and Differential Algebraic
Equations 918 [abstract]
J. B. Rosen, John H. Glick, and E. Michael Gertz
18.16 Optimization in Water Reservoir Systems 933 [abstract]
Kumaraswamy Ponnambalam
18.17 Optimization Problems in Air-Pollution Modeling 943 [abstract]
Ivan Dimov and Zahari Zlatev
18.18 Applied Optimization in Agriculture 957 [abstract]
Charles B. Moss
18.19 Optimization in Graph Drawing 967 [abstract]
Petra Mutzel
18.20 Optimization for Modeling of Nonlinear Interactions in
Mechanics 978 [abstract]
G. E. Stavroulakis
PART THREE: SOFTWARE
19 Optimization Modeling Languages 993 [abstract]
Emmanuel Fragniere and Jacek Gondzio
20 Optimization Software Packages 1008 [abstract]
Stephen J. Wright
21 Optimization Software Libraries 1016 [abstract]
Andreas Fink, Stefan Voss, and David L. Woodruff
22 Optimization Test Problem Libraries 1025 [abstract]
John E. Beasley
23 Parallel Computing Environments 1029 [abstract]
Simone de L. Martins, Celso C. Ribeiro, and Noemi Rodriguez
24 Experimental Analysis of Optimization Algorithms 1044 [abstract]
Catherine C. McGeoch
25 Object-Oriented Programming 1053 [abstract]
Andreas Fink, Stefan Voss, and David L. Woodruff
26 Optimization and the Internet 1063 [abstract]
Michael A. Trick
Directory of Contributors 1071
Index 1077
CONTRIBUTORS
E. H. L. Aarts
Department Head, Philips Research Laboratories; and Professor of Computing
Science, Eindhoven University of Technology, Netherlands
Ravindra K. Ahuja
Professor of Industrial and Systems Engineering, University of Florida,
Gainesville
G. Anandalingam
Professor of Management Science, R. H. Smith School of Business and
Institute for Systems Research, University of Maryland, College Park
John E. Beasley
Senior Lecturer in Operations Research, The Management School, Imperial
College, London, United Kingdom
Matthew E. Berge
Technical Fellow, The Boeing Company, Seattle, Washington
John T. Betts
Technical Fellow, The Boeing Company, Seattle, Washington
John R. Birge
Dean, McCormick School of Engineering and Applied Science, Northwestern
University, Evanston, Illinois
Rainer E. Burkard
Professor of Mathematics, Technische Universita"t Graz, Austria
Eranda Çela
Assistant Professor of Applied Mathematics, Institut fu"r Mathematik,
Technische Universita"t Graz, Austria
Yair Censor
Professor of Mathematics, University of Haifa, Israel
Pierre Chardaire
Reader in Computer Science, School of Information Systems, University
of East Anglia, United Kingdom
Edward G. Coffman, Jr.
Professor of Electrical Engineering, Columbia University, New York
Edith Cohen
Technology Consultant, AT&T Labs Research, Florham Park, New Jersey
Gerson Couto de Oliveira
Consultant of Power Systems Research, Inc., and Professor of Electrical
Engineering, Catholic University of Rio de Janeiro, Brazil
Yves Crama
Professor of Operations Research and Production Management, Ecole
d'Administration des Affaires, University of Lie`ge, Belgium
János Csirik
Professor of Computer Science, József Attila University of Szeged,
Hungary
Ivan Dimov
Professor, and Director of the Central Laboratory for Parallel Processing,
Bulgarian Academy of Sciences, Sofia
Gianni Di Pillo
Professor in Operations Research, Universitŕ di Roma "La Sapienza," Italy
Zvi Drezner
Professor of Management Science, California State University, Fullerton
Ding-Zhu Du
Professor of Computer Science, University of Minnesota, Minneapolis;
and Research Professor, Institute of Applied Mathematics, Chinese Academy
of Sciences, Beijing
José H. Dulá
Associate Professor of Production and Operations Management, School of
Business Administration, University of Mississippi
Augustine O. Esogbue
Professor, School of Industrial and Systems Engineering, Georgia Institute
of Technology, Atlanta
Hussein A. Y. Etawil
Senior Member of the Technical Staff, Sequence Design Incorporated,
Santa Clara, California
Michael C. Ferris
Professor of Computer Sciences and Industrial Engineering, University
of Wisconsin, Madison
Sharon K. Filipowski
Mathematics and Modeling Analyst, The Boeing Company, Seattle, Washington
Andreas Fink
Staff Member, Department of Business Administration, Information Systems,
and Information Management, Technische Universität Braunschweig, Germany
Michael Florian
Professor of Operations Research, Center for Research on Transportation,
University of Montreal, Quebec, Canada
Christodoulos A. Floudas
Professor of Chemical Engineering, Princeton University, New Jersey
Emmanuel Fragničre
Lecturer of Management Science, University of Bath, United Kingdom
John Franco
Geier Professor of Computer Science, University of Cincinnati, Ohio
Manlio Gaudioso
Professor of Operations Research, Universitŕ della Calabria, Rende, Italy
E. Michael Gertz
Postdoctoral Researcher, Northwestern University and Argonne National
Laboratory, Illinois
John H. Glick
Associate Professor of Mathematics and Computer Science, University of
San Diego, California
Fred Glover
MediaOne Professor of Systems Science, School of Business, University
of Colorado, Boulder
Bruce L. Golden
Professor and France-Merrick Chair in Management Science, University of
Maryland, College Park
Jacek Gondzio
Reader in Computational Optimization, University of Edinburgh, United
Kingdom
Sergio Granville
Technical Director of Power Systems Research, Inc., Rio de Janeiro, Brazil
Stephen C. Graves
Abraham J. Siegel Professor of Management Science and Engineering Systems,
Massachusetts Institute of Technology, Cambridge
Jun Gu
Professor of Computer Science, Hong Kong University of Science and
Technology, Kowloon
Monique Guignard
Professor of Operations and Information Management, The Wharton School;
and Professor of Systems Engineering, University of Pennsylvania,
Philadelphia
Peter L. Hammer
Professor, Rutcor, Rutgers University, New Brunswick, New Jersey
Pierre Hansen
Professor of Operations Research, École des Hautes Études Commerciales;
and Groupe d'etudes et de recherches en analyse des decisions (GERAD),
Montréal, Québec, Canada
Donald W. Hearn
Professor and Chair, Department of Industrial and Systems Engineering,
and Co-Director, Center for Applied Optimization, University of Florida,
Gainesville
John Hof
Chief Economist, Rocky Mountain Research Station, USDA Forest Service,
Fort Collins, Colorado
Roland N. Horne
Professor and Chairman, Petroleum Engineering, Stanford University,
California
William P. Huffman
Mathematics and Modeling Analyst, The Boeing Company, Seattle, Washington
Toshihide Ibaraki
Professor of Informatics, Kyoto University, Japan
Christian Kanzow
Assistant Professor, Department of Mathematics, University of Hamburg,
Germany
Suat Kasap
Graduate Assistant, School of Industrial Engineering, University of
Oklahoma, Norman
Dukwon Kim
Member of the Center for Applied Optimization, University of Florida,
Gainesville
Manuel Laguna
Associate Professor of Operations Management, Graduate School of Business
Administration, University of Colorado, Boulder
Robert C. Leachman
Professor of Industrial Engineering and Operations Research, University
of California, Berkeley
Chung-Yee Lee
Professor of Industrial Engineering, Texas A&M University, College Station
Eva K. Lee
Assistant Professor of Radiation Oncology, Emory University School of
Medicine; and Assistant Professor of Industrial and Systems Engineering,
Georgia Institute of Technology, Atlanta
Abdel Lisser
Head of Research and Development Group, France Telecom, Issy-Moulineaux
Arne Lřkketangen
Professor of Informatics, Molde College, Norway
Abilio Lucena
Full Professor, Departamento de Administraçăo, Universidade Federal
do Rio de Janeiro, Brazil
Nelson Maculan
Professor of Systems Engineering and Computer Science, Federal University
of Rio de Janeiro, Brazil
Thomas L. Magnanti
Dean of Engineering and Institute Professor, Massachusetts Institute of
Technology, Cambridge
Philippe Mahey
Professor, Institut Supérieur d'Informatique de Modélisation et de
leurs Applications (ISIMA), Université de Clermont Ferrand II, and LIMOS,
Centre National de la Recherche Scientifique (CNRS), Aubičre, France
Simone de L. Martins
Assistant Researcher, Bioinformatics Laboratory, Department of Applied
Mathematics, The National Laboratory of Scientific Computation, LNCC,
Rio de Janeiro, Brazil
S. Thomas McCormick
W. J. Van Dusen Professor of Management, University of British Columbia,
Vancouver, Canada
Catherine C. McGeoch
Professor of Computer Science, Amherst College, Massachusetts
John E. Mitchell
Associate Professor of Mathematical Sciences, Rensselaer Polytechnic
Institute, Troy, New York
Nenad Mladenovic
Higher Scientific Associate, Mathematical Institute, Serbian Academy of
Sciences and Arts, Belgrade, Yugoslavia
Pablo Moscato
Research Scientist, Meme Pool Project, Universidade Estadual de Campinas,
Brazil
Charles B. Moss
Professor of Food and Resource Economics, University of Florida,
Gainesville
Petra Mutzel
Professor for Algorithms and Data Structures, Vienna University of
Technology, Austria
Anna Nagurney
John F. Smith Memorial Professor, Department of Finance and Operations
Management, Isenberg School of Management, University of Massachusetts,
Amherst
Alexandra M. Newman
Assistant Professor of Operations Research, Division of Economics and
Business, Colorado School of Mines, Golden
Linda K. Nozick
Associate Professor of Systems Engineering, School of Civil and
Environmental Engineering, Cornell University, Ithaca, New York
James B. Orlin
Edward Pennell Brooks Professor of Operations Research, Massachusetts
Institute of Technology, Cambridge
Laura Palagi
Researcher in Operations Research, Universitŕ di Roma "La Sapienza,"
Italy
Panos M. Pardalos
Professor and Co-Director, Center for Applied Optimization, Industrial
and Systems Engineering Department, University of Florida, Gainesville
Mario Pereira
President of Power Systems Research, Inc., Rio de Janeiro, Brazil
Michael Pinedo
Professor of Operations Management, Stern School of Business, New York
University, New York
Leonidas S. Pitsoulis
Associate Professor, Department of Statistics, University of the Aegean,
Greece
Marcus Poggi de Aragăo
Professor of Computer Science, Catholic University of Rio de Janeiro,
Brazil
Kumaraswamy Ponnambalam
Associate Professor of Systems Design Engineering, University of Waterloo,
Ontario, Canada
Warren B. Powell
Professor of Operations Research and Financial Engineering, Princeton
University, New Jersey
Paul W. Purdom
Professor of Computer Science, Indiana University at Bloomington
Sanguthevar Rajasekaran
Professor of Computer and Information Science and Engineering, University
of Florida, Gainesville
Mauricio G. C. Resende
Technology Consultant, Algorithms and Optimization Research Department,
AT&T Labs Research, Florham Park, New Jersey
Celso C. Ribeiro
Professor of Computer Science, Catholic University of Rio de Janeiro,
Brazil
Roger Z. Ríos-Mercado
Assistant Professor, Systems Engineering Program, Universidad Autónoma
de Nuevo León, San Nicola's de los Garza, Mexico
Noemi Rodriguez
Associate Professor, Computer Science Department, Catholic University
of Rio de Janeiro, Brazil
Kees Roos
Professor of Applied Mathematics, Department of Information Technology
and Systems, Delft University of Technology, Netherlands
J. B. Rosen
Adjunct Research Professor of Computer Science, University of California,
San Diego
Boghos D. Sivazlian
Professor of Industrial and Systems Engineering, University of Florida,
Gainesville
G. E. Stavroulakis
Associate Professor of Mechanics, University of Ioannina, Greece; and
Privatdozent for Mechanics, Technical University of Braunschweig, Germany
Éric D. Taillard
Director of the Institute for Applied Computer Sciences, E'cole
d'Inge'nieurs du Canton de Vaud (EIVD), University of Applied Sciences
of Western Switzerland, Yverdon
H. M. M. Ten Eikelder
Assistant Professor of Biomedical Engineering, Eindhoven University of
Technology, Netherlands
Tamás Terlaky
Professor of Optimization, Department of Computing and Software,
Information Technology Center, McMaster University, Hamilton, Ontario,
Canada
Benjamin G. Thengvall
Operations Research Scientist, CALEB Technologies Corporation, Austin,
Texas
Theodore B. Trafalis
Associate Professor of Industrial Engineering, University of Oklahoma,
Norman
Michael A. Trick
Associate Professor of Operations Research, Graduate School of Industrial
Administration, Carnegie Mellon University, Pittsburgh, Pennsylvania
Hoang Tuy
Professor of Mathematics, Institute of Mathematics, National Center for
Science and Technology, Hanoi, Vietnam
Stanislav Uryasev
Associate Professor, Department of Industrial and Systems Engineering,
University of Florida, Gainesville
Andrés Weintraub Pohorille
Professor of Industrial Engineering, University of Chile, Santiago
Anthony Vannelli
Professor and Chair, Department of Electrical and Computer Engineering,
University of Waterloo, Ontario, Canada
Stefan Voss
Professor of Business Administration, Information Systems, and Information
Management, Technische Universita"t Braunschweig, Germany
Benjamin W. Wah
R. T. Chien Professor of Electrical and Computer Engineering, University
of Illinois at Urbana-Champaign
Edward A. Wasil
Professor of Management Science, Kogod School of Business, American
University, Washington, D.C.
Gerhard J. Woeginger
Professor of Mathematics, Technische Universita"t Graz, Austria
Henry Wolkowicz
Professor of Mathematics, University of Waterloo, Ontario, Canada
David L. Woodruff
Professor of Management, University of California, Davis
Stephen J. Wright
Professor of Computer Sciences, University of Wisconsin-Madison
Guoliang Xue
Professor, Department of Computer Science and Engineering, Arizona State
University, Tempe
Mutsunori Yagiura
Lecturer, Graduate School of Informatics, Kyoto University, Japan
Candace Arai Yano
Professor of Industrial Engineering and Operations Research, University
of California, Berkeley
Yinyu Ye
Henry B. Tippie Research Professor, Department of Management Sciences,
University of Iowa, Iowa City
David P. Young
Technical Fellow, The Boeing Company, Seattle, Washington
Gang Yu
Professor of Management Science and Information Systems, University of
Texas at Austin
Stavros A. Zenios
Professor of Management Science, and Dean of the School of Economics
and Management, University of Cyprus, Nicosia
Zahari Zlatev
Senior Researcher, Department for Atmospheric Environment, National
Environmental Research Institute, Roskilde, Denmark