Piecewise linear relaxation of bilinear programs using bivariate partitioning

Abstract

Several operational and synthesis problems of practical interest involve bilinear terms. Commercial global solvers such as BARON appear ineffective at solving some of these problems. Although recent literature has shown the potential of piecewise linear relaxation via ab initio partitioning of variables for such problems, several issues such as how many and which variables to partition, which partitioning scheme(s) and relaxation model(s) to use, placement of grid points, etc., need detailed investigation. To this end, we present a detailed numerical comparison of univariate and bivariate partitioning schemes. We compare several models for the two schemes based on different formulations such as incremental cost (IC), convex combination (CC), and special ordered sets (SOS). Our evaluation using four process synthesis problems shows a formulation using SOS1 variables to perform the best for both partitioning schemes. It also points to the potential usefulness of a 2-segment bivariate partitioning scheme for the global optimization of bilinear programs. We also prove some simple results on the number and selection of partitioned variables and the advantage of uniform placement of grid points (identical segment lengths for partitioning). © 2009 American Institute of Chemical Engineers.