We begin by developing a unifying theory of domain reduction strategies as a consequence of which we derive new as well as most range-reduction strategies currently used in nonlinear and integer linear programming. This reduction theory is based on conjugate/linear programming duality and leads to a learning heuristic that improves initial branching decisions by relaying data across siblings in a branch and bound tree. We then develop novel strategies for constructing linear relaxations of mixed integer nonlinear programs and prove that these relaxations enjoy quadratic convergence properties. Finally, we improve the standard branch and bound algorithm by allowing postponement of nodes and incorporating branching strategies that guarantee finiteness for certain classes of continuous global optimization problems.
We describe our implementation, BARON, discussing, wherever appropriate, the use of suitable data-structures and associated algorithms. We present extensive computational experience with 435 test problems from various classes of global optimization problems, including indefinite quadratic programs, multiplicative programs, fractional 0-1 programs, and applications in pooling, engineering design, facility location and capacity expansion, fixed charge programming, power economies of scale, just-in-time manufacturing, and molecular design.
Email Address: 
URL: http://web.ics.purdue.edu/~mtawarma/