Optimization Software Class Libraries

Optimization Software Class Libraries

OPERATIONS RESEARCH/COMPUTER SCIENCE

INTERFACES SERIES

Series Editors

Professor Ramesh Sharda

Oklahoma State University

Prof. Dr. Stefan Voß

Technische Universität Braunschweig

Other published titles in the series:

Greenberg, Harvey J. / A Computer-Assisted Analysis System for Mathematical Programming Models and Solutions: A User’s Guide for ANALYZE

Greenberg, Harvey J. / Modeling by Object-Driven Linear Elemental Relations: A Users Guide for

MODLER

Brown, Donald/Scherer, William T. / Intelligent Scheduling Systems

Nash, Stephen G./Sofer, Ariela / The Impact of Emerging Technologies on Computer Science &

Operations Research

Barth, Peter / Logic-Based 0-1 Constraint Programming

Jones, Christopher V. / Visualization and Optimization

Barr, Richard S./ Helgason, Richard V./ Kennington, Jeffery L. / Interfaces in Computer

Science & Operations Research: Advances in Metaheuristics, Optimization, and Stochastic

Modeling Technologies

Ellacott, Stephen W./ Mason, John C./ Anderson, Iain J. / Mathematics of Neural Networks: Models, Algorithms & Applications

Woodruff, David L. / Advances in Computational & Stochastic Optimization, Logic Programming, and Heuristic Search

Klein, Robert / Scheduling of Resource-Constrained Projects

Bierwirth, Christian / Adaptive Search and the Management of Logistics Systems

Laguna, Manuel / González-Velarde, José Luis / Computing Tools for Modeling, Optimization

and Simulation

Stilman, Boris / Linguistic Geometry: From Search to Construction

Sakawa, Masatoshi / Genetic Algorithms and Fuzzy Multiobjective Optimization

Ribeiro, Celso C./ Hansen, Pierre / Essays and Surveys in Metaheuristics

Holsapple, Clyde/ Jacob, Varghese / Rao, H. R. / BUSINESS MODELLING: Multidisciplinary

Approaches — Economics, Operational and Information Systems Perspectives

Sleezer, Catherine M./ Wentling, Tim L./ Cude, Roger L. / HUMAN RESOURCE

DEVELOPMENT AND INFORMATION TECHNOLOGY: Making Global Connections

Optimization Software Class Libraries

Edited by

Stefan Voß

Braunschweig University of Technology, Germany

David L. Woodruff

University of California, Davis, USA

KLUWER ACADEMIC PUBLISHERS

NEW YORK, BOSTON, DORDRECHT, LONDON, MOSCOW

eBook ISBN: 0-306-48126-X

Print ISBN: 1-4020-7002-0

©2003 Kluwer Academic Publishers

New York, Boston, Dordrecht, London, Moscow

Print ©2002 Kluwer Academic Publishers

All rights reserved

No part of this eBook may be reproduced or transmitted in any form or by any means, electronic,

mechanical, recording, or otherwise, without written consent from the Publisher

Created in the United States of America

Visit Kluwer Online at: http://kluweronline.com

and Kluwer's eBookstore at: http://ebooks.kluweronline.com

Dordrecht

Contents

Preface

1

ix

1

2

3

20

23

25

25

26

36

43

49

51

57

59

60

61

65

69

74

77

78

Optimization Software Class Libraries

Stefan Voß and David L. Woodruff

1.1

1.2

1.3

1.4

Introduction

Component Libraries

Callable Packages and Numerical Libraries

Conclusions and Outlook

2

Distribution, Cooperation, and Hybridization for Combinatorial Optimization

Martin S. Jones, Geoff P. McKeown and Vic J. Rayward-Smith

2.1

2.2

2.3

2.4

2.5

2.6

2.7

Introduction

Overview of the Templar Framework

Distribution

Cooperation

Hybridization

Cost of Supporting a Framework

Summary

3

A Framework for Local Search Heuristics for Combinatorial Optimiza- tion Problems

Alexandre A. Andreatta, Sergio E.R. Carvalho and Celso C. Ribeiro

3.1

3.2

3.3

3.4

3.5

3.6

3.7

Introduction

Design Patterns

The Searcher Framework

Using the Design Patterns

Implementation Issues

Related Work

Conclusions and Extensions

vi OPTIMIZATION SOFTWARE CLASS LIBRARIES

81

81

83

85

103

137

146

153

155

177

177

178

179

180

182

186

190

190

193

193

196

198

202

211

215

219

219

221

225

239

249

250

4

HOTFRAME: A Heuristic Optimization Framework

Andreas Fink and Stefan Voß

4.1

4.2

4.3

4.4

4.5

4.6

4.7

Introduction

A Brief Overview

Analysis

Design

Implementation

Application

Conclusions

5

Writing Local Search Algorithms Using EASYLOCAL++

Luca Di Gaspero and Andrea Schaerf

5.1

5.2

5.3

5.4

5.5

5.6

Introduction

An Overview of EASYLOCAL++

The COURSE TIMETABLING Problem

Solving COURSE TIMETABLING Using EASYLOCAL++

Debugging and Running the Solver

Discussion and Conclusions

6

Integrating Heuristic Search and One-Way Constraints in the iOpt Toolkit

Christos Voudouris and Raphaël Dorne

Introduction

One-Way Constraints

Constraint Satisfaction Algorithms for One-Way Constraints

The Invariant Library of iOpt

The Heuristic Search Framework of iOpt

Experimentation on the Graph Coloring and the Vehicle Routing Problem

Related Work and Discussion

Conclusions

6.1

6.2

6.3

6.4

6.5

6.6

6.7

6.8

7

The OptQuest Callable Library

Manuel Laguna and Rafael Martí

7.1

7.2

7.3

7.4

7.5

7.6

Introduction

Scatter Search

The OCL Optimizer

OCL Functionality

OCL Application

Conclusions

8

A Constraint Programming Toolkit for Local Search

Paul Shaw, Vincent Furnon and Bruno De Backer

8.1

8.2

8.3

8.4

8.5

8.6

Introduction

Constraint Programming Preliminaries

The Local Search Toolkit

Industrial Example: Facility Location

Extending the Toolkit

Specializing the Toolkit: ILOG Dispatcher

155

156

161

162

172

174

Contents vii

259

260

263

263

265

269

276

279

290

294

295

296

304

317

319

328

331

335

357

8.7

8.8

Related Work

Conclusion

9

The Modeling Language OPL – A Short Overview

Pascal Van Hentenryck and Laurent Michel

9.1

9.2

9.3

9.4

9.5

9.6

9.7

Introduction

Frequency Allocation

Sport Scheduling

Job-Shop Scheduling

The Trolley Application

Research Directions

Conclusion

10

Genetic Algorithm Optimization Software Class Libraries

Andrew R. Pain and Colin R. Reeves

10.1

10.2

10.3

10.4

10.5

Introduction

Class Library Software

Java Class Library Software

Genetic Algorithm Optimization Software Survey

Conclusions

Abbreviations

References

Index

This page intentionally left blank

Preface

Optimization problems in practice are diverse and evolve over time, giving rise to re￾quirements both for ready-to-use optimization software packages and for optimization

software libraries, which provide more or less adaptable building blocks for appli￾cation-specific software systems. In order to apply optimization methods to a new

type of problem, corresponding models and algorithms have to be “coded” so that

they are accessible to a computer. One way to achieve this step is the use of a model￾ing language. Such modeling systems provide an excellent interface between models

and solvers, but only for a limited range of model types (in some cases, for example,

linear) due, in part, to limitations imposed by the solvers. Furthermore, while mod￾eling systems especially for heuristic search are an active research topic, it is still an

open question as to whether such an approach may be generally successful. Modeling

languages treat the solvers as a “black box” with numerous controls. Due to variations,

for example, with respect to the pursued objective or specific problem properties, ad￾dressing real-world problems often requires special purpose methods. Thus, we are

faced with the difficulty of efficiently adapting and applying appropriate methods to

these problems. Optimization software libraries are intended to make it relatively easy

and cost effective to incorporate advanced planning methods in application-specific

software systems.

A general classification provides a distinction between callable packages, numeri￾cal libraries, and component libraries. Component libraries provide useful abstractions

for manipulating algorithm and problem concepts. Object-oriented software technol￾ogy is generally used to build and apply corresponding components. To enable adap￾tation, these components are often provided at source code level. Corresponding class

libraries support the development of application-specific software systems by provid￾ing a collection of adaptable classes intended to be reused. However, the reuse of

algorithms may be regarded as “still a challenge to object-oriented programming”.

Component libraries are the subject of this edited volume. That is, within a careful

collection of chapters written by experts in their fields we aim to discuss all relevant

aspects of component libraries. To allow for wider applicability, we restrict the expo￾sition to general approaches opposed to problem-specific software.

x OPTIMIZATION SOFTWARE CLASS LIBRARIES

Acknowledgements

Of course such an ambitious project like publishing a high quality book would not

have been possible without the most valuable input of a large number of individuals.

First of all, we wish to thank all the authors for their contributions, their patience and

fruitful discussion. We are grateful to the whole team at the University of Technology

Braunschweig, who helped in putting this book together, and to Gary Folven at Kluwer

Academic Publishers for his help and encouragement.

The Editors:

Stefan Voß

David L. Woodruff

1 OPTIMIZATION SOFTWARE CLASS

LIBRARIES

Stefan Voß1

and David L. Woodruff2

1

Technische Universität Braunschweig

Institut für Wirtschaftswissenschaften

Abt-Jerusalem-Straße 7, D-38106 Braunschweig, Germany

stefan.voss@tu—bs.de

2

Graduate School of Management

University of California at Davis

Davis, California 95616, USA

[email protected]

Abstract: Many decision problems in business and engineering may be formulated as

optimization problems. Optimization problems in practice are diverse, often complex and

evolve over time, so one requires both ready-to-use optimization software packages and

optimization software libraries, which provide more or less adaptable building blocks for

application-specific software systems.

To provide a context for the other chapters in the book, it is useful to briefly survey

optimization software. A general classification provides a distinction between callable

packages, numerical libraries, and component libraries. In this introductory chapter, we

discuss some general aspects of corresponding libraries and give an overview of avail￾able libraries, which provide reusable functionality with respect to different optimization

methodologies. To allow for wider applicability we devote little attention to problem￾specific software so we can focus the exposition on general approaches.

OPTIMIZATION SOFTWARE CLASS LIBRARIES

1.1 INTRODUCTION

New information technologies continuously transform decision processes for man￾agers and engineers. This book is the result of the confluence of recent developments

in optimization techniques for complicated problems and developments in software

development technologies. The confluence of these technologies is making it possible

for optimization methods to be embedded in a host of applications.

Many decision problems in business and engineering may be formulated as opti￾mization problems. Optimization problems in practice are diverse, often complex and

evolve over time, so one requires both ready-to-use optimization software packages

and optimization software libraries, which provide more or less adaptable building

blocks for application-specific software systems. To provide a context for the other

chapters in the book, it is useful to briefly survey optimization software.

In order to apply optimization methods to a new type of problem, corresponding

models and algorithms have to be “coded” so that they are accessible to a computer

program that can search for a solution. Software that can take a problem in canonical

form and find optimal or near optimal solutions is referred to as a solver. The transla￾tion of the problem from its physical or managerial form into a form usable by a solver

is a critical step.

One way to achieve this step is the use of a modeling language. Such modeling

systems provide an excellent interface between models and solvers, but only for a

limited range of model types (in some extreme cases, e.g., linear). This is partly due

to limitations imposed by the solvers. Furthermore, while modeling systems are an

active research topic, it is still an open question whether such an approach may be

successful for complex problems. Modeling languages treat the solvers as a “black

box” with numerous controls.

Due to variations, for example, with respect to the pursued objective or specific

problem properties, addressing real-world problems often requires special purpose

methods. Thus, we are faced with the difficulty of efficiently adapting and applying

appropriate methods to these problems. Optimization software libraries are intended

to make it relatively easy and cost effective to incorporate advanced planning methods

in application-specific software systems.

Callable packages allow users to embed optimization functionality in applications,

and are designed primarily to allow the user’s software to prepare the model and feed

it to the package. Such systems typically also include routines that allow manipulation

of the model and access to the solver’s parameters. As with the modeling language

approach, the solver is treated essentially as an opaque object, which provides a clas￾sical functional interface, using procedural programming languages such as C. While

there are only restricted means to adapt the corresponding coarse-grained functional￾ity, the packages do often offer callbacks that facilitate execution of user code during

the solution process.

Numerical libraries provide similar functionality, except that the model data is

treated using lower levels of abstraction. For example, while modeling languages

and callable packages may allow the user to provide names for sets of variables and

indexes into the sets, numerical libraries facilitate only the manipulation of vectors

and matrices as numerical entities. Well-known solution techniques can be called as

2

OPTIMIZATION SOFTWARE CLASS LIBRARIES 3

subroutines, or can be built from primitive operations on vectors and matrices. These

libraries provide support for linear algebra, numerical computation of gradients, and

support for other operations of value, particularly for continuous optimization.

Component libraries provide useful abstractions for manipulating algorithm and

problem concepts. Object-oriented software technology is generally used to build

and deploy components. To enable adaptation these components are often provided

at source code level. Class libraries support the development of application-specific

software systems by providing a collection of adaptable classes intended to be reused.

Nevertheless, the reuse of algorithms may be regarded as “still a challenge to object￾oriented programming” (Weihe (1997)). As we point out later, there is no clear di￾viding line between class libraries and frameworks. Whereas class libraries may be

more flexible, frameworks often impose a broader structure on the whole system. Here

we use the term component library or componentware that should embrace both class

libraries and frameworks, but also other concepts that build on the idea of creating

software systems by selecting, possibly adapting, and combining appropriate modules

from a huge set of existing modules.

In the following sections we provide a brief survey on callable packages and numer￾ical libraries (Section 1.3) as well as component libraries (Section 1.2). Our survey

in this chapter must necessarily be cursory and incomplete; it is not intended to be

judgmental and in some cases one has to rely on descriptions provided by software

vendors. Therefore, we include several references (literature and WWW) that provide

further information; cf. Fink et al. (2001).

As our main interest lies in optimization software class libraries and frameworks

for heuristic search, we provide a somewhat more in depth treatment of heuristics and

metaheuristics within the section on component libraries to let the reader visualize the

preliminaries of this rapidly evolving area; cf. Voß (2001).

1.2 COMPONENT LIBRARIES

Class libraries support the development of application-specific software systems by

providing a collection of (possibly semi-finished) classes intended to be reused. The

approach to build software by using class libraries corresponds to the basic idea of

object-oriented software construction, which may be defined as building software sys￾tems as “structured collections of possibly partial abstract data type implementations”

(Meyer (1997)). The basic object-oriented paradigm is to encapsulate abstractions of

all relevant concepts of the considered domain in classes. To be truly reusable, all these

classes have to be applicable in different settings. This requires them to be polymor￾phic to a certain degree, i.e., to behave in an adaptable way. Accordingly, there have

to be mechanisms to adapt these classes to the specific application. Class libraries

are mostly based on dynamic polymorphism by factoring out common behavior in

general classes and providing the specialized functionality needed by subclassing (in￾heritance). Genericity, which enables one to leave certain types and values unspecified

until the code is actually instantiated and used (compiled) is another way - applicable

orthogonal to inheritance - to define polymorphic classes.

One approach primarily devoted to the goal to achieve a higher degree of reuse is

the framework approach; see, e.g., Bosch et al. (1999), Fayad and Schmidt (1997b)

Most discrete optimization problems are nearly impossible to solve to optimality.

Many can be formally classified as (Garey and Johnson (1979)). Moreover,

the modeling of the problem is often an approximate one, and the data are often impre￾cise. Consequently, heuristics are a primary way to tackle these problems. The use of

appropriate metaheuristics generally meets the needs of decision makers to efficiently

generate solutions that are satisfactory, although perhaps not optimal. The common

incorporation of advanced metaheuristics in application systems requires a way to

reuse much of such software and to redo as little as possible each time. However, in

1.2.1 Libraries for Heuristic Optimization

and Johnson and Foote (1988). Taking into account that for the development of ap￾plication systems for given domains quite similar software is needed, it is reasonable

to implement such common aspects by a generic design and embedded reusable soft￾ware components. Here, one assumes that reuse on a large scale cannot only be based

on individual components, but there has to be to a certain extent a reuse of design.

Thus, the components have to be embedded in a corresponding architecture, which

defines the collaboration between the components. Such a framework may be defined

as a set of classes that embody an abstract design for solutions to a family of related

problems (e.g., heuristics for discrete optimization problems), and thus provides us

with abstract applications in a particular domain, which may be tailored for individual

applications. A framework defines in some way a definition of a reference application

architecture (“skeleton”), providing not only reusable software elements but also some

type of reuse of architecture and design patterns (Buschmann et al. (1996b), Gamma

et al. (1995)), which may simplify software development considerably. (Patterns, such

as frameworks and components, may be classified as object-oriented reuse techniques.

Simply put a pattern describes a problem to be solved, a solution as well as the context

in which the solution applies.) Thus, frameworks represent implementation-oriented

generic models for specific domains.

There is no clear dividing line between class libraries and frameworks. Whereas

class libraries may be more flexible, frameworks often impose a broader structure

on the whole system. Frameworks, sometimes termed as component libraries, may

be subtly differentiated from class libraries by the “activeness” of components, i.e.,

components of the framework define application logic and call application-specific

code. This generally results in a bi-directional flow of control.

In the following, we will use the term component library or componentware that

should embrace both class libraries and frameworks, but also other concepts that build

on the idea of creating software systems by selecting, possibly adapting, and com￾bining appropriate modules from a large set of existing modules. The flexibility of

a component library is dependent on the specific possibilities for adaptation. As cer￾tain aspects of the component library application cannot be anticipated, these aspects

have to be kept flexible, which implies a deliberate incompleteness of generic software

components.

Based on these considerations we chose the title optimization software class li￾braries. In the sequel we distinguish between libraries for heuristic search (Sec￾tion 1.2.1) and constraint programming (Section 1.2.2).

4 OPTIMIZATION SOFTWARE CLASS LIBRARIES