Reference : Berge-acyclic multilinear 0-1 optimization problems
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Business & economic sciences : Quantitative methods in economics & management
Berge-acyclic multilinear 0-1 optimization problems
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 >]
European Journal of Operational Research
Yes (verified by ORBi)
[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

File(s) associated to this reference

Fulltext file(s):

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.