Handbook of Applied Optimization

by Pardalos, Panos M.; Resende, Mauricio G. C.

• ISBN13: 9780195125948
• ISBN10: 0195125940
• Format: Hardcover
• Copyright: 2002-02-22
• Publisher: Oxford University Press

Summary

Optimization is an essential tool in every project in every large-scale organization, whether in business, industry, engineering, and science. In recent years, algorithmic advances and software and hardware improvements have given managers a powerful framework for making key decisions abouteverything from production planning to scheduling distribution. This comprehensive resource brings together in one volume the major advances in the field. Distinguished contributors focus on the algorithmic and computational aspects of optimization, particularly the most recent methods for solving a wide range of decision-making problems. The book is divided into three main sections: algorithms, covering every type of programming; applications, where computational tools are put to work solving tasks in planning, production, distribution, scheduling and other decisions in project management; and software, a comprehensive introductionto languages and systems. Designed as a practical resource for programmers and project planners and managers, it covers optimization problems in a wide range of settings, from the airline and aerospace industries to telecommunications, finance, health systems, biomedicine, and engineering.

Table of Contents

Preface	xiii
Panos M. Pardalos
Mauricio G. C. Resende
Introduction	xv
Panos M. Pardalos
Mauricio G. C. Resende
PART ONE: ALGORITHMS
Linear Programming	1	(39)
Introduction	1	(6)
Tamas Terlaky
Simplex-Type Algorithms	7	(14)
Tamas Terlaky
Interior-Point Methods for Linear Optimization	21	(19)
Kees Roos
Semidefinite Programming	40	(11)
Henry Wolkowicz
Combinatorial Optimization	51	(184)
Introduction	51	(2)
Panos M. Pardalos
Mauricio G. C. Resende
Branch-and-Bound Methods	53	(12)
Eva K. Lee
Branch-and-Cut Algorithms for Combinatorial Optimization Problems	65	(13)
John E. Mitchell
Dynamic Programming Approaches	78	(26)
Augustine O. Esogbue
Local Search	104	(19)
Mutsunori Yagiura
Toshihide lbaraki
Metaheuristics	123	(112)
Introduction	123	(7)
Bruce L. Golden
Edward A. Wasil
Ant Systems	130	(8)
Eric D. Taillard
Population Heuristics	138	(19)
John E. Beasley
Memetic Algorithms	157	(11)
Pablo Moscato
Greedy Randomized Adaptive Search Procedures	168	(15)
Leonidas S. Pitsoulis
Mauricio G. C. Resende
Scatter Search	183	(11)
Manuel Laguna
Tabu Search	194	(15)
Fred Glover
Manuel Laguna
Simulated Annealing	209	(12)
E. H. L. Aarts
H. M. M. Ten Eikelder
Variable Neighborhood Search	221	(14)
Pierre Hansen
Nenad Mladenovic
Quadratic Programming	235	(28)
Yinyu Ye
Nonlinear Programming	263	(48)
Introduction	263	(5)
Gianni Di Pillo
Laura Palagi
Unconstrained Nonlinear Programming	268	(17)
Gianni Di Pillo
Laura Palagi
Constrained Nonlinear Programming	285	(14)
Gianni Di Pillo
Laura Palagi
Nonsmooth Optimization	299	(12)
Manlio Gaudioso
Deterministic Global Optimization and Its Applications	311	(26)
Christodoulos A. Floudas
Decomposition Methods for Mathematical Programming	337	(15)
Philippe Mahey
Network Optimization	352	(79)
Introduction	352	(11)
Ravindra K. Ahuja
Thomas L. Magnanti
James B. Orlin
Maximum Flow Problem	363	(12)
Ravindra K. Ahuja
Thomas L. Magnanti
James B. Orlin
Shortest-Path Algorithms	375	(11)
Edith Cohen
Minimum-Cost Single-Commodity Flow	386	(18)
S. Thomas McCormick
Minimum-Cost Multicommodity Flow	404	(18)
Pierre Chardaire
Abdel Lisser
Minimum Spanning Tree Problem	422	(9)
Ravindra K. Ahuja
Thomas L. Magnanti
James B. Orlin
Integer Programming	431	(47)
Introduction	431	(9)
Nelson Maculan
Linear 0-1 Programming	440	(5)
Nelson Maculan
Pseudo-Boolean Optimization	445	(6)
Yves Crama
Peter L. Hammer
Mixed-Integer Nonlinear Optimization	451	(14)
Christodoulos A. Floudas
Lagrangian Relaxation	465	(9)
Monique Guignard
Heuristics for 0-1 Mixed-Integer Programming	474	(4)
Arne Lokketangen
Artificial Neural Networks in Optimization and Applications	478	(13)
Theodore B. Trafalis
Suat Kasap
Stochastic Programming	491	(11)
John R. Birge
Hierarchical Optimization	502	(12)
Hoang Tuy
Complementarity and Related Problems	514	(17)
Michael C. Ferris
Christian Kanzow
Data Envelopment Analysis	531	(13)
Jose H. Dula
Parallel Algorithms in Optimization	544	(16)
Yair Censor
Stavros A. Zenios
Randomization in Discrete Optimization: Annealing Algorithms	560	(9)
Sanguthevar Rajasekaran
PART TWO: APPLICATIONS
Problem Types	569	(110)
Optimization and Heuristics of Scheduling	569	(15)
Chung-Yee Lee
Michael Pinedo
The Vehicle Routing Problem	584	(11)
John E. Beasley
Abilio Lucena
Marcus Poggi de Aragao
Network Designs: Approximations for Steiner Minimum Trees	595	(12)
Ding-Zhu Du
Approximate Solutions to Bin Packing Problems	607	(9)
Edward G. Coffman, Jr.
Janos Csirik
Gerhard J. Woeginger
The Traveling Salesman Problem	616	(8)
Rainer E. Burkard
Inventory Management	624	(8)
Dukwon Kim
Boghos D. Sivazlian
Location	632	(8)
Zvi Drezner
Algorithms for the Satisfiability (SAT) Problem	640	(21)
Jun Gu
Paul W. Purdom
John Franco
Benjamin W. Wah
Assignment Problems	661	(18)
Eranda Cela
Application Areas	679	(314)
Transportation and Logistics	679	(10)
Warren B. Powell
Airline Optimization	689	(15)
Gang Yu
Benjamin G. Thengvall
Optimization in the Rail Industry	704	(15)
Alexandra M. Newman
Linda K. Nozick
Candace Arai Yano
Forestry Industry	719	(9)
Andres Weintraub Pohorille
John Hof
Manufacturing Planning and Control	728	(18)
Stephen C. Graves
Semiconductor Production Planning	746	(17)
Robert C. Leachman
Optimization in the Aerospace Industry	763	(7)
Matthew E. Berge
John T. Betts
Sharon K. Filipowski
William P. Huffman
David P. Young
Energy	770	(56)
Optimization in Electical Power Systems	770	(38)
Gerson Couto de Oliveira
Sergio Granville
Mario Pereira
Optimization Applications in Oil and Gas Recovery	808	(5)
Roland N. Horne
Natural Gas Pipeline Optimization	813	(13)
Roger Z. Rios-Mercado
Optimization of Telecommunications Networks	826	(15)
G. Anandalingam
Optimization of Test Intervals in Nuclear Engineering	841	(10)
Stanislav Uryasev
Optimization in VLSI Design: Target Distance Models for Cell Placement	851	(19)
Hussein A. Y. Etawil
Anthony Vannelli
Optimization Models in Transportation Planning	870	(15)
Michael Florian
Donald W. Hearn
Optimization in Computational Molecular Biology	885	(16)
Guoliang Xue
Optimization in the Financial Services Industry	901	(17)
Anna Nagurney
Applied Large-Scale Nonlinear Optimization for Optimal Control of Partial Differential Equations and Differential Algebraic Equations	918	(15)
J. B. Rosen
John H. Glick
E Michael Gertz
Optimization in Water Reservoir Systems	933	(10)
Kumaraswamy Ponnambalam
Optimization Problems in Air-Pollution Modeling	943	(14)
Ivan Dimov
Zahari Zlatev
Applied Optimization in Agriculture	957	(10)
Charles B. Moss
Optimization in Graph Drawing	967	(11)
Petra Mutzel
Optimization for Modeling of Nonlinear Interactions in Mechanics	978	(15)
G. E. Stavroulakis
PART THREE: SOFTWARE
Optimization Modeling Languages	993	(15)
Emmanuel Fragniere
Jacek Gondzio
Optimization Software Packages	1008	(8)
Stephen J. Wright
Optimization Software Libraries	1016	(9)
Andreas Fink
Stefan Vob
David L. Woodruff
Optimization Test Problem Libraries	1025	(4)
John E. Beasley
Parallel Computing Environments	1029	(15)
Simone de L. Martins
Celso C. Ribeiro
Noemi Rodriguez
Experimental Analysis of Optimization Algorithms	1044	(9)
Catherine C. McGeoch
Object-Oriented Programming	1053	(10)
Andreas Fink
Stefan Vob
David L. Woodruff
Optimization and the Internet	1063	(8)
Michael A. Trick
Directory of Contributors	1071	(6)
Index	1077