A reduced dimension branch-and-bound algorithm for molecular design

This paper addresses the solution of mixed-integer nonlinear mathematical programs in which the number of linear constraints far exceed the number of nonlinear constraints, and with most variables participating in the nonconvex terms. Some computer-aided molecular design models have these features. A branch-and-bound (BB) algorithm is proposed that is specifically tailored to solving such problems. In a conventional BB algorithm, branching is performed on all the search variables that appear in the nonlinear terms. This translates to a large number of node traversals. To overcome this problem, we have proposed a new strategy for branching on a set of branching functions, which depend linearly on the search variables. The branching functions are determined from a special tree function (STF) representation of both the objective function and constraints. In order to construct the corresponding linear underestimators, we have developed the Sweep method. The proposed algorithm scales well with problem size. Specifically, as the problem size increases, the computational effort increases almost linearly. The computational efficiency of the algorithm is demonstrated by solving a molecular design problem to global optimality. (C) 2002 Elsevier Science Ltd. All rights reserved.