A Grid-enabled Framework for Exact Optimization Algorithms

摘要

In this paper we present a framework for writing exact optimization algorithms distributed on a grid environment. It presents a new way of reusing design and code for multi-objective optimization methods in conjunction with assistant methods. These kinds of methods are used mainly for reducing the search space, or for using a mono-objective method for solving a multi-objective problem, or both. We use a master-slave paradigm for the parallelization of the work units and a branch and bound algorithm as a default assistant method. The branch and bound algorithm is also distributed on grids which allows a two level parallelism for the optimization. We show how the different objects are codified in order to allow less communication while at the same time maintaining the reusability requirement. A sample instantiation of the framework is presented using the Parallel Partitioning Method (PPM). Preliminary results are shown using different Flowshop instances.