Average complexity and the Bayesian heuristic approach to discrete optimization

We apply some concepts of Information-Based Complexity (IBC) to global and discrete optimization. We assume that only partial information on the objective is available. We gather this partial information by observations. We use the traditional IBC definitions and notions while defining formal aspects of the problem. We use the Bayesian framework to consider less formal aspects, such as expert knowledge and heuristics.

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.