DCABB - A DISTRIBUTED CONTROL ARCHITECTURE FOR BRANCH-AND-BOUND CALCULATIONS

The solution of large combinatorial optimization problems is becoming increasingly important in diverse areas of chemical engineering such a s batch process design and scheduling, molecular simulation, and proce ss control. Branch and bound is a well established framework that is a t the core of existing methods for rigorously solving hard combinatori al optimization problems. Parallel and distributed computers offer gre at promise in reducing the execution times of branch and bound computa tions. However, the time and effort needed to parallelize algorithms e xacerbates the already arduous task of algorithm development. This has prevented the routine use of parallel and distributed computers in so lving combinatorial optimization problems. In this paper we discuss th e development of a tool that is aimed at reducing the burden associate d with designing and implementing branch and bound algorithms in a dis tributed environment. The design goal of DCABB is to automate the impl ementation aspects of the distributed algorithm without imposing rigid protocol formats that restrict the customizability of the algorithm. Algorithm flexibility is achieved by allowing user written modules to customize various components of a branch and bound algorithm. The tool consists of a programmer interface and a runtime environment. Since t he tool is aimed towards a network environment, workload balancing, pr ocessor connectivity and robustness of the system with respect to mach ine and/or network failures are important issues. We report computatio nal results to show the viability of the DCABB parallelization paradig m.