Contents

1 Preface

This book shows how the Bayesian Approach (BA) improves well-known heuristics by randomizing and optimizing their parameters. That is the Bayesian Heuristic Approach (BHA).

The ten in-depth examples are designed to teach Operations Research using Internet. Each example is a simple representation of some important family of real-life problems.

The accompanying software can be run by remote Internet users. The supporting web-sites include software for Java, C++, and other languages.

A theoretical setting is described in which one can discuss a Bayesian adaptive choice of heuristics for discrete and global optimization problems. The techniques are evaluated in the spirit of the average rather than the worst case analysis. In this context, "heuristics" are understood to be an expert opinion defining how to solve a family of problems of discrete or global optimization. The term "Bayesian Heuristic Approach" means that one defines a set of heuristics and fixes some prior distribution on the results obtained. By applying BHA one is looking for the heuristic that reduces the average deviation from the global optimum.

The theoretical discussions serve as an introduction to examples that are the main part of the book. All the examples are interconnected. Different examples illustrate different points of the general subject. However, one can consider each example separately, too.

In part I, About the Bayesian Heuristic Approach, some well-known results are discussed to help understand what the Bayesian Heuristic Approach is about. First the general ideas of Bayesian related approaches are outlined. This is for readers who want to understand the place of BHA in the general optimization theory and applications. Then it is shown how BHA works by considering a simple example of the knapsack problem. This is for those who are interested in optimization algorithms and would like to skip the underlying theory. In Part II, Software for Global Optimization, different versions of software implementing the Bayesian and other approaches to global optimization are considered. A set of portable Fortran 77 programs, reflecting the early developments of global and local optimization software, is discussed. An interactive Turbo C version, designed for DOS environment, and an interactive C++ version, designed for Unix environment, are described. Three Java versions of global optimization software are presented. The Java software is run by standard Internet browsers.

In part III, Examples of Models, examples of global and discrete optimization are described. The choice of examples aims to help teaching. The teaching topics include: Operations Research, Theory of Games and Markets, Decision Theory, Utility Theory, Queuing Theory, Scheduling Theory, Stochastic Optimization, and Discrete Optimization.

Following mathematical models are considered:

The first nine models are solved using a set of algorithms of global and stochastic optimization. The last model is an example of stochastic dynamic programming. All the models are formulated in simple terms to serve as "classroom" examples. However, each of these models can be considered as simple representations of important families of real-life problems. Therefore, the models and the solution algorithms may be of interest for application experts, too.

This book is to describe underlying ideas of algorithms and models in mathematical terms supplemented by illustrative examples and explanations. The information is presented in two forms: hard copy and web-sites.

An advantage of the hard copy is that one does not need a computer to read it. The disadvantage is the static presentation. A hard copy cannot be updated. Therefore, new results must wait until the next edition.

The aim of supporting web-sites is to supplement the algorithms and models by software systems for different computing environments, using different languages and operating systems. An advantage of web-sites is the dynamic presentation. Thus, the results can be easily updated and made accessible free of charge for a wide range of readers. An additional advantage is the possibility to run the software directly by Internet. That is convenient teaching the programming using Internet.

The author considers the hard copy as a static introduction to the dynamic web-sites. There are two of them; they differ by volume and scope.
$http://mockus.org/optimum$
$http://optimum.mii.lt/\tilde{~}jonas$
$http://vaidila.vdu.lt/\tilde{~}iijomo$
The software presented on these sites is intended for "active" readers, who would like to apply the results to their own problems immediately.

Contact e-mail addresses:
$jonas@optimum.mii.lt$
$jonas@mockus.org$

Finally, I want to express my thanks to colleagues and students who directly or indirectly contributed to this book.


J. Mockus
January 2000


Subsections
jonas mockus 2004-03-20