Global optimization of nonconvex nonlinear programs using parallel branch and bound

A branch and bound algorithm for computing globally optimal solutions to non-convex nonlinear programs in continuous variables is presented. The algorithm is directly suitable for a wide class of problems arising in chemical engineering design. It can solve problems defined using algebraic functions and twice differentiable transcendental functions, in which finite upper and lower bounds can be placed on each variable. The algorithm uses rectangular partitions of the variable domain and a new bounding program based on convex/concave envelopes and positive definite combinations of quadratic terms. The algorithm is deterministic and obtains convergence with final regions of finite size. The partitioning strategy uses a sensitivity analysis of the bounding program to predict the best variable to split and the split location. Two versions of the algorithm are considered, the first using a local NLP algorithm (MINOS) and the second using a sequence of lower bounding programs in the search for local minima. Runtime results for both versions are presented for a set of 50 test problems. In addition, a parallel version of the branch and bound algorithm is presented and tested. Parallelism is achieved by applying a separate processor to the bounding of each region. Each processor maintains a list of regions to be analyzed, and a load balancing scheme is used to balance the quality and quantity of regions available in each processor's list.