Reference : Berge-acyclic 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/204059
Berge-acyclic multilinear 0-1 optimization problems
English
Buchheim, Christoph [TU Dortmund > Fakultät für Mathematik > > >]
Crama, Yves mailto [Université de Liège > HEC Liège : UER > Recherche opérationnelle et gestion de la production >]
Rodriguez Heck, Elisabeth mailto [Université de Liège > HEC Liège : UER > Recherche opérationnelle et gestion de la production >]
2018
European Journal of Operational Research
Elsevier
Yes (verified by ORBi)
International
0377-2217
1872-6860
Netherlands
[en] multilinear 0-1 optimization ; standard linearization ; Berge cycle ; balanced matrix ; signed hypergraph
[en] The problem of optimizing a multilinear polynomial f in 0–1 variables arises in applications from many different areas. We are interested in resolution methods based on reformulating the polynomial problem into an equivalent linear one, an approach that attempts to draw benefit from the extensive literature in integer linear programming. More precisely, we characterize instances for which the classical standard linearization procedure guarantees integer optimal solutions. We show that the standard linearization polytope P_H is integer if and only if the hypergraph H defined by the higher-degree monomials of f is Berge-acyclic, or equivalently, when the matrix defining P_H is balanced. This characterization follows from more general conditions that guarantee integral optimal vertices for a relaxed formulation depending on the sign pattern of the monomials of f.
HEC - QuantOM
Researchers
http://hdl.handle.net/2268/204059
10.1016/j.ejor.2018.07.045

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
article_perfect_SL_version5.pdfAuthor preprint149.03 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.