Valid Inequalities and Convex Hulls for Multilinear Functions
| hal.structure.identifier | Department of Industrial and Systems Engineering [Lehigh] [ISE] | |
| dc.contributor.author | BELOTTI, Pietro | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | MILLER, Andrew J. | |
| hal.structure.identifier | Department of Industrial and Systems Engineering [Wisconsin-Madison] [ISyE] | |
| dc.contributor.author | NAMAZIFAR, Mahdi | |
| dc.date.accessioned | 2024-04-04T02:27:36Z | |
| dc.date.available | 2024-04-04T02:27:36Z | |
| dc.date.issued | 2010 | |
| dc.identifier.issn | 1571-0653 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/190032 | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.publisher | Elsevier | |
| dc.title.en | Valid Inequalities and Convex Hulls for Multilinear Functions | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1016/j.endm.2010.05.102 | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.journal | Electronic Notes in Discrete Mathematics | |
| bordeaux.page | 805-812 | |
| bordeaux.volume | 36 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00547924 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00547924v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Electronic%20Notes%20in%20Discrete%20Mathematics&rft.date=2010&rft.volume=36&rft.spage=805-812&rft.epage=805-812&rft.eissn=1571-0653&rft.issn=1571-0653&rft.au=BELOTTI,%20Pietro&MILLER,%20Andrew%20J.&NAMAZIFAR,%20Mahdi&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||