Simple odd β-cycle inequalities for binary polynomial optimization
成果类型：
Article
署名作者：
Del Pia, Alberto; Walter, Matthias
署名单位：
University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; University of Twente
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-023-01992-y
发表日期：
2024
页码：
203-238
关键词：
摘要：
We consider themultilinear polytope which arises naturally in binary polynomial optimization. Del Pia and Di Gregorio introduced the class of odd ss-cycle inequalities valid for this polytope, showed that these generally have Chvatal rank 2 with respect to the standard relaxation and that, together with flower inequalities, they yield a perfect formulation for cycle hypergraph instances. Moreover, they describe a separation algorithm in case the instance is a cycle hypergraph. We introduce a weaker version, called simple odd ss-cycle inequalities, for which we establish a strongly polynomial-time separation algorithm for arbitrary instances. These inequalities still have Chvatal rank 2 in general and still suffice to describe the multilinear polytope for cycle hypergraphs. Finally, we report about computational results of our prototype implementation. The simple odd ss-cycle inequalities sometimes help to close more of the integrality gap in the experiments; however, the preliminary implementation has substantial computational cost, suggesting room for improvement in the separation algorithm.
来源URL：