Article (Scientific journals)
A class of valid inequalities for multilinear 0-1 optimization problems
Crama, Yves; Rodriguez Heck, Elisabeth
2017In Discrete Optimization, 25, p. 28-47
Peer Reviewed verified by ORBi
 

Files


Full Text
A_class_of_valid_ineqs_multil_01_prog_Preprint.pdf
Author preprint (232.11 kB)
Download
Full Text Parts
DO reprint.pdf
Publisher postprint (850.87 kB)
Request a copy

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
multilinear binary optimization; pseudo-Boolean optimization; integer nonlinear programming; standard linearization
Abstract :
[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).
Disciplines :
Mathematics
Quantitative methods in economics & management
Author, co-author :
Crama, Yves  ;  Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production
Rodriguez Heck, Elisabeth ;  Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production
Language :
English
Title :
A class of valid inequalities for multilinear 0-1 optimization problems
Publication date :
2017
Journal title :
Discrete Optimization
ISSN :
1572-5286
eISSN :
1873-636X
Publisher :
Elsevier
Volume :
25
Pages :
28-47
Peer reviewed :
Peer Reviewed verified by ORBi
Name of the research project :
Pôles d'attraction interuniversitaires (PAI) 7/36
Funders :
BELSPO - Politique scientifique fédérale [BE]
Available on ORBi :
since 15 May 2016

Statistics


Number of views
227 (42 by ULiège)
Number of downloads
605 (12 by ULiège)

Scopus citations®
 
30
Scopus citations®
without self-citations
28
OpenCitations
 
21

Bibliography


Similar publications



Contact ORBi