S.Berner, K.I.M. McKinnon and C. Millar
Technical Report MS 96-004a
Abstract
A chemical mixture under conditions of constant temperature and
pressure may split into different phases. The number of phases and the
composition of each may be determined by globally minimizing the Gibbs
free energy of the system. This can be done by iterating between an
easy local minimization problem with a high number of variables and a
difficult global search and verification problem in a small number of
variables. The global problem can be solved by a branch and bound
method using bounds from interval analysis. When implemented in
parallel, the method has lower communication requirements than other
related branch and bound approaches for general global
minimization. We present a parallel implementation on a network
cluster of workstations that exploits this characteristic. On
difficult instances, utilizations of over 90% are obtained using up
to 14 processors. The algorithm copes well with varying workstation
loads and has low communication overheads. A method of assessing the
performance of a parallel algorithm on a shared heterogeneous network
of workstations is developed.
Key words: Global optimization, interval-analysis, parallel programming, branch and bound, Gibbs free energy, phase equilibrium, primal-dual methods.
amsmos: 90C90, 90C99, 65Y05, 68Q22, 80-08, 80A10, 80A15