Informatica

Spatial Global Optimization branch and bound (B&B) methods aim at enclosing global minimum points in a guaranteed way with a certain accuracy. We extend simplicial B&B (sBB) concepts to polytopal B&B (pBB), with polytope subsets. The main challenges are: polytope division and extension of monotonicity tests theoretically and algorithmically. We compare the performance of interval B&B with linear constraints (iBBLC), sBB and pBB algorithms, to determine the most efficient B&B algorithm for different types of instances.

The maximization problem for an objective function f given on a feasible region X is considered, where X is a compact subset of Rⁿ and f belongs to a set of continuous multiextremal functions on X can be evaluated at any point x in X without error, and its maximum M=max x∈Xf(x) together with a maximizer x^*(a point x^* in X such that M=f(x^*)) are to be approximated. We consider a class of the global random search methods, underlying an apparatus of the mathematical statistics and generalizing the so-called branch and bound methods.