Valid Inequalities and Convex Hulls for Multilinear Functions
MILLER, Andrew J.
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
MILLER, Andrew J.
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
< Reduce
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Language
en
Article de revue
This item was published in
Electronic Notes in Discrete Mathematics. 2010, vol. 36, p. 805-812
Elsevier
English Abstract
We study the convex hull of the bounded, nonconvex set of a product of n variables for any n ≥ 2. We seek to derive strong valid linear inequalities for this set, which we call M_n; this is motivated by the fact that many ...Read more >
We study the convex hull of the bounded, nonconvex set of a product of n variables for any n ≥ 2. We seek to derive strong valid linear inequalities for this set, which we call M_n; this is motivated by the fact that many exact solvers for nonconvex problems use polyhedral relaxations so as to compute a lower bound via linear programming solvers. We present a class of linear inequalities that, together with the well-known McCormick inequalities, defines the convex hull of M_2. This class of inequalities, which we call lifted tangent inequalities, is uncountably infinite, which is not surprising given that the convex hull of M_n is not a polyhedron. This class of inequalities generalizes directly to M_n for n > 2, allowing us to define strengthened relaxations for these higher dimensional sets as well.Read less <
Origin
Hal imported