Optimization Software Class Libraries

by Voss, Stefan; Woodruff, David L.

• ISBN13: 9781402070020
• ISBN10: 1402070020
• Format: Hardcover
• Copyright: 2002-03-01
• Publisher: Kluwer Academic Pub

Summary

Stefan Voß and David Woodruff have edited a carefully refereed volume by experts on optimization software class libraries. The book focuses on flexible and powerful collections of computational objects for addressing complex optimization problems. These component class libraries are suitable for use in the increasing number of optimization applications that stand alone or are imbedded in advanced planning, engineering, and bioinformatics applications. Most researchers today use a number of modeling language software packages and a number of software solvers to solve computational problems. This book outlines packaged software class libraries to enable researchers to find cost-effective and efficient methods of getting problems coded into the computer, or into a modeling language package or into optimizing solvers - hence providing software coding solutions to whatever specialized needs a specific problem might require.Optimization Software Class Libraries provides the reader with a rich overview of the variety of components for framing problems. With the growing number of application-specific software systems and advance planning methods for specific classes of problems, class libraries for optimization are increasingly useful, practical, and needed. Benefits of Optimization Software Class Libraries are:Researchers will be able to invest more effort in examining better algorithms, performing experiments, and making use of problem-specific knowledge;The libraries that encapsulate general-purpose algorithms as reusable, high-quality software components are themselves significant contributions to ongoing research; andIn addition to the research benefits, the libraries described provide substantial practical value to organizations that adopt them.

Table of Contents

Preface	ix
Optimization Software Class Libraries	1	(24)
Stefan Voß
David L. Woodruff
Introduction	2	(1)
Component Libraries	3	(17)
Callable Packages and Numerical Libraries	20	(3)
Conclusions and Outlook	23	(2)
Distribution, Cooperation, and Hybridization for Combinatorial Optimization	25	(34)
Martin S. Jones
Geoff P. McKeown
Vic J. Rayward-Smith
Introduction	25	(1)
Overview of the Templar Framework	26	(10)
Distribution	36	(7)
Cooperation	43	(6)
Hybridization	49	(2)
Cost of Supporting a Framework	51	(6)
Summary	57	(2)
A Framework for Local Search Heuristics for Combinatorial Optimization Problems	59	(22)
Alexandre A. Andreatta
Sergio E.R. Carvalho
Celso C. Ribeiro
Introduction	60	(1)
Design Patterns	61	(4)
The Searcher Framework	65	(4)
Using the Design Patterns	69	(5)
Implementation Issues	74	(3)
Related Work	77	(1)
Conclusions and Extensions	78	(3)
Hotframe: A Heuristic Optimization Framework	81	(74)
Andreas Fink
Stefan Voß
Introduction	81	(2)
A Brief Overview	83	(2)
Analysis	85	(18)
Design	103	(34)
Implementation	137	(9)
Application	146	(7)
Conclusions	153	(2)
Writing Local Search Algorithms Using Easylocal++	155	(22)
Luca Di Gaspero
Andrea Schaerf
Introduction	155	(1)
An Overview of EASYLOCAL++	156	(5)
The COURSE TIMETABLING Problem	161	(1)
Solving COURSE TIMETABLING Using EASYLOCAL++	162	(10)
Debugging and Running the Solver	172	(2)
Discussion and Conclusions	174	(3)
Integrating Heuristic Search and One-Way Constraints in the iOpt Toolkit	177	(16)
Christos Voudouris
Raphael Dorne
Introduction	177	(1)
One-Way Constraints	178	(1)
Constraint Satisfaction Algorithms for One-Way Constraints	179	(1)
The Invariant Library of iOpt	180	(2)
The Heuristic Search Framework of iOpt	182	(4)
Experimentation on the Graph Coloring and the Vehicle Routing Problem	186	(4)
Related Work and Discussion	190	(1)
Conclusions	190	(3)
The OptQuest Callable Library	193	(26)
Manuel Laguna
Rafael Marti
Introduction	193	(3)
Scatter Search	196	(2)
The OCL Optimizer	198	(4)
OCL Functionality	202	(9)
OCL Application	211	(4)
Conclusions	215	(4)
A Constraint Programming Toolkit for Local Search	219	(44)
Paul Shaw
Vincent Furnon
Bruno De Backer
Introduction	219	(2)
Constraint Programming Preliminaries	221	(4)
The Local Search Toolkit	225	(14)
Industrial Example: Facility Location	239	(10)
Extending the Toolkit	249	(1)
Specializing the Toolkit: ILOG Dispatcher	250	(9)
Related Work	259	(1)
Conclusion	260	(3)
The Modeling Language OPL -- A Short Overview	263	(32)
Pascal Van Hentenryck
Laurent Michel
Introduction	263	(2)
Frequency Allocation	265	(4)
Sport Scheduling	269	(7)
Job-Shop Scheduling	276	(3)
The Trolley Application	279	(11)
Research Directions	290	(4)
Conclusion	294	(1)
Genetic Algorithm Optimization Software Class Libraries	295	(36)
Andrew R. Pain
Colin R. Reeves
Introduction	296	(8)
C++ Class Library Software	304	(13)
Java Class Library Software	317	(2)
Genetic Algorithm Optimization Software Survey	319	(9)
Conclusions	328	(3)
Abbreviations	331	(4)
References	335	(22)
Index	357