.png){kind=icon}
返回
Berge-acyclic multilinear 0-1 optimization problems
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2018.07.045.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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 off 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. (C) 2018 Elsevier B.V. All rights reserved.
Keyword:
Nonlinear programming
Integer programming
Standard linearization
Balanced matrix
Signed hypergraph
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
引用论文
.png){kind=icon}
分享收藏分享收藏
查看更多内容