GLOBAL MINIMIZATION BY REDUCING THE DUALITY GAP

We derive a general principle demonstrating that by partitioning the f easible set, the duality gap, existing between a nonconvex program and its lagrangian dual, can be reduced, and in important special cases, even eliminated. The principle can be implemented in a Branch and Boun d algorithm which computes an approximate global solution and a corres ponding lower bound on the global optimal value. The algorithm involve s decomposition and a nonsmooth local search. Numerical results for ap plying the algorithm to the pooling problem in oil refineries are give n.