Reference : A class of valid inequalities for multilinear 0-1 optimization problems
Scientific journals : Article
Business & economic sciences : Quantitative methods in economics & management
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/196789
A class of valid inequalities for multilinear 0-1 optimization problems
English
Crama, Yves mailto [Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production >]
Rodriguez Heck, Elisabeth mailto [Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production >]
2017
Discrete Optimization
Elsevier
25
28-47
Yes (verified by ORBi)
International
1572-5286
1873-636X
[en] multilinear binary optimization ; pseudo-Boolean optimization ; integer nonlinear programming ; standard linearization
[en] This paper investigates the polytope associated with the classical standard
linearization technique for the unconstrained optimization of multilinear
polynomials in 0-1 variables. A new class of valid inequalities, called
2-links, is introduced to strengthen the LP relaxation of the standard linearization.
The addition of the 2-links to the standard linearization inequalities
provides a complete description of the convex hull of integer solutions
for the case of functions consisting of at most two nonlinear monomials.
For the general case, various computational experiments show that the 2-
links improve both the standard linearization bound and the computational
performance of exact branch & cut methods. The improvements are especially
significant for a class of instances inspired from the image restoration
problem in computer vision. The magnitude of this effect is rather surprising
in that the 2-links are in relatively small number (quadratic in the number of
terms of the objective function).
Belspo PAI P7/36
http://hdl.handle.net/2268/196789
10.1016/j.disopt.2017.02.001

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
A_class_of_valid_ineqs_multil_01_prog_Preprint.pdfAuthor preprint226.67 kBView/Open
Restricted access
DO reprint.pdfPublisher postprint830.93 kBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.