Julius Zilinskas
Kaunas University of Technology
Lithuania
email: Julius.Zilinskas@ktu.lt
and
Antanas Zilinskas
IMI, Vilnius, Lithuania
and Cardiff University, UK
email: antanasz@ktl.mii.lt
One of the main approaches to global optimization of multimodal functions of continuous variables is a combination of a Branch-and-Bound (BB) technique with interval arithmetic to compute bounds for the function values of an objective function. Branching is implemented via selection and subdivision rules, where a box from a set of boxes covering the feasible region is selected for further subdivision. The decrease of a box implies comming closer upper and lower bounds, eventually indicating the boxes not containing the global minimizers. These boxes are excluded from the further consideration decreasing the potential solution set. The optimization is terminated when the solution is localized with prescribed accuracy. Applications of BB algorithms normally are computationally intensive even for the problems of modest dimensionality. The tightening of bounds, e.g. by means of reducing the dependency influence, can decrease the number of branching, and consequently the number of calls of the subroutine of the objective function. On the other hand, the tightening of bounds increases the time of auxiliary computations. A theoretical justification of trade off between these two criteria is difficult. We compare experimentally several versions of the BB algorithm with different tightness of bounds modeled using two special cases. The first case corresponds to the bounds computed by means of standard interval arithmetic. The second case corresponds to the exact bounds computed by means of global optimization over the considered boxes. The bounds for the intermediate cases are chosen between these two special cases. An implementation using exact bounds requests repeated solution of auxiliary global minimization and maximization problems during a run of the algorithm for every test function. Therefore experimental investigation is computationally intensive, and the parallel implementation of the considered algorithm is a strict prerequisite for the investigation. We refer to the papers [1],[2],[3] for the discussion on the enhancment of performance of BB algorithms by means of a parallel implementation. For our experiments a parallel version of the considered BB algorithm is constructed using the master-slave paradigm. The master runs the core BB algorithm and holds yet not explored boxes. The slaves use the standard interval global optimization algorithm to find the exact bounds for function values over the box got from the master. The master-slave paradigm seems appropriate since the slave tasks of global minimization and maximization are time consuming and therefore the communications are not too frequent. The experimental results are summarised as a quantitative assessment of the trade-off between the tigteness of bounds and performance of the algorithm.
References:
[1]Clausen J. (1997). Parallel branch-and-bound - principles and personal experiences. In:
A. Migdalas, P.M. Pardalos and S. Storoy (eds), Parallel Computing in Optimization, Kluwer
Academic Publishers, 239-267.
[2]Gau, C. Y. and M. A. Stadtherr (2001). Parallel branch-and-bound for chemical engineering
applications: Load balancing and scheduling issues. Lect. Notes in Comp. Sci., v.1981, 273-300.
[3]Gendron B. and T. Crainic (1994). Parallel Branch-and-Bound algorithms -
Survey and Synthesis. Operations Research, v.42, 1042-1066.