Reformulation and convex relaxation techniques for global optimization

We survey the main results obtained by the author in his PhD dissertation supervised by Prof. Costas Pantelides. It was defended at the Imperial College, London. The thesis is written in English and is available from http://or.elet.polimi.it/people/Liberti/phdtesis.ps.gz. The most widely employed deterministic method for the global solution of nonconvex NLPs and MINLPs is the spatial Branch-and-Bound (sBB) algorithm, and one of its most crucial steps is the computation of the lower bound at each sBB node. We investigate different reformulations of the problem so that the resulting convex relaxation is tight. In particular, we suggest a novel technique for reformulating a wide class of bilinear problems so that some of the bilinear terms are replaced by linear constraints. Moreover, an in-depth analysis of a convex envelope for piecewise-convex and concave terms is performed. All the proposed algorithms were implemented in ooOPS, an object-oriented callable library for constructing MINLPs in structured form and solving them using a variety of local and global solvers.