TY - GEN
T1 - Relaxations of multilinear convex envelopes
T2 - 11th International Symposium on Experimental Algorithms SEA 2012
AU - Costa, Alberto
AU - Liberti, Leo
PY - 2012/8/1
Y1 - 2012/8/1
N2 - Bilinear, trilinear, quadrilinear and general multilinear terms arise naturally in several important applications and yield nonconvex mathematical programs, which are customarily solved using the spatial Branch-and-Bound algorithm. This requires a convex relaxation of the original problem, obtained by replacing each multilinear term by appropriately tight convex relaxations. Convex envelopes are known explicitly for the bilinear case, the trilinear case, and some instances of the quadrilinear case. We show that the natural relaxation obtained using duality performs more efficiently than the traditional method.
AB - Bilinear, trilinear, quadrilinear and general multilinear terms arise naturally in several important applications and yield nonconvex mathematical programs, which are customarily solved using the spatial Branch-and-Bound algorithm. This requires a convex relaxation of the original problem, obtained by replacing each multilinear term by appropriately tight convex relaxations. Convex envelopes are known explicitly for the bilinear case, the trilinear case, and some instances of the quadrilinear case. We show that the natural relaxation obtained using duality performs more efficiently than the traditional method.
KW - Global optimization
KW - MINLP
KW - mathematical programming
U2 - 10.1007/978-3-642-30850-5_9
DO - 10.1007/978-3-642-30850-5_9
M3 - Conference contribution
AN - SCOPUS:84864376189
SN - 9783642308499
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 87
EP - 98
BT - Experimental Algorithms - 11th International Symposium, SEA 2012, Proceedings
Y2 - 7 June 2012 through 9 June 2012
ER -