Informatica

– games theory;

– decision theory;

– utility theory;

– queuing theory;

– scheduling theory;

– discrete optimization.

These topics are illustrated and the connection with global optimization is shown considering the following mathematical models:

– competition model with fixed resource prices, Nash equilibrium;

– competition model with free resource prices, Walras equilibrium;

– Inspector's problem, multi-stage game model;

– “Star War” problem, differential game model;

– “Portfolio” problem, resource investment model;

– exchange rate prediction, auto-regression-moving-average (ARMA) model;

– optimal scheduling, Bayesian heuristic model;

– “Bride's” problem, sequential statistical decisions model.

The first seven models are solved using a set of algorithms of continuous global and stochastic optimization. The global optimization software GM (see Mockus, 1996) is used. The underlying theory of this software and algorithms of solution are described in Mockus (1989, 1996). The last model is an example of stochastic dynamic programming.

For better understanding, all the models are formulated in simplest terms as “classroom” examples. However, each of these models can be regarded as simple representations of important families of real-life problems. Therefore the models and solution algorithms may be of interest for application experts, too.

The paper is split into two parts. In the part one the first five models are described. In the part two the rest three models and accompanying software are considered.

We define the learning efficiency as a non-uniformity of optimal parameters while solving a set of randomly generated problems. We show that for flow-shop problems the non-uniformity of optimal parameters is significant. It means that the Bayesian learning is efficient in those problems.

We extend the traditional Bayesian Approach (BA) including heuristics. We call that a Bayesian Heuristic Approach (BHA).

We discuss how to overcome the computational difficulties using parallel computing. We illustrate the theoretical concepts by three examples: by discrete problems of flow-shop scheduling and parameter grouping, and by a continuous problem of batch operations scheduling.

We start by describing the Bayesian approach to the continuous global optimization. Then we show how to apply the results to the adaptation of parameters of randomized techniques of optimization. We assume that there exists a simple function which roughly predicts the consequences of decisions. We call it heuristics. We define the probability of a decision by a randomized decision function depending on heuristics. We fix this decision function, except for some parameters that we call the decision parameters.

We repeat the randomized decision procedure several times given the decision parameters and regard the best outcome as a result. We optimize the decision parameters to make the search more efficient. Thus we replace the original optimization problem by an auxiliary problem of continuous stochastic optimization. We solve the auxiliary problem by the Bayesian methods of global optimization. Therefore we call the approach as the Bayesian one.

We discuss the advantages and disadvantages of the Bayesian approach. We describe the applications to some of discrete programming problems, such as optimization of mixed Boolean bilinear functions including the scheduling of batch operations and the optimization of neural networks.