检索结果-内蒙古大学图书馆

The pseudo-Boolean polytope and polynomial-size extended formulations for binary polynomial optimization

MATHEMATICAL PROGRAMMING 2024年 1-45页

作者： Del Pia, Alberto Khajavirad, Aida Univ Wisconsin Inst Discovery Dept Ind & Syst Engn & Wisconsin Madison WI USA Lehigh Univ Dept Ind & Syst Engn Bethlehem PA 18018 USA

With the goal of obtaining strong relaxations for binary polynomial optimization problems, we introduce the pseudo-Boolean polytope defined as the set of binary points z is an element of {0, 1}(V boolean OR S) satisfying a collection of equalities of the form z(s) = Pi(v is an element of s) sigma(s)(z(v)), for all s is an element of S, where sigma(s) (z(v)) is an element of {z(v), 1 - z(v)}, and where S is a multiset of subsets of V. By representing the pseudo-Boolean polytope via a signed hypergraph, we obtain sufficient conditions under which this polytope has a polynomial-size extended formulation. Our new framework unifies and extends all prior results on the existence of polynomial-size extended formulations for the convex hull of the feasible region of binary polynomial optimization problems of degree at least three.

关键词： binary polynomial optimization Pseudo-Boolean optimization Pseudo-Boolean polytope Signed hypergraph polynomial-size extended formulation

来源：评论

学校读者我要写书评

暂无评论

Simple odd β-cycle inequalities for binary polynomial optimization

引用

MATHEMATICAL PROGRAMMING 2024年第1-2期206卷 203-238页

作者： Del Pia, Alberto Walter, Matthias Univ Wisconsin Dept Ind & Syst Engn Madison WI USA Univ Wisconsin Wisconsin Inst Discovery Madison WI USA Univ Twente Dept Appl Math Enschede Netherlands

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.

关键词： binary polynomial optimization Cutting planes Separation algorithm

来源：评论

学校读者我要写书评

暂无评论

On the strength of recursive McCormick relaxations for binary polynomial optimization

引用

OPERATIONS RESEARCH LETTERS 2023年第2期51卷 146-152页

作者： Khajavirad, Aida Lehigh Univ Dept Ind & Syst Engn Bethlehem PA 18015 USA

Recursive McCormick relaxations are among the most popular convexification techniques for binary polynomial optimization. It is well-understood that both the quality and the size of these relaxations depend on the recursive sequence and finding an optimal sequence amounts to solving a difficult combinatorial optimization problem. We prove that any recursive McCormick relaxation is implied by the extended flower relaxation, a linear programming relaxation, which for binary polynomial optimization problems with fixed degree can be solved in strongly polynomial time.(c) 2023 Elsevier B.V. All rights reserved.

关键词： binary polynomial optimization Recursive McCormick relaxations Multilinear polytope Extended flower relaxation Cutting planes

来源：评论

学校读者我要写书评

暂无评论

Sum-of-squares hierarchies for binary polynomial optimization

引用

MATHEMATICAL PROGRAMMING 2023年第2期197卷 621-660页

作者： Slot, Lucas Laurent, Monique Ctr Wiskunde & Informat CWI Amsterdam Netherlands Tilburg Univ Tilburg Netherlands

We consider the sum-of-squares hierarchy of approximations for the problem of minimizing a polynomial f over the boolean hypercube B-n = {0, 1}(n). This hierarchy provides for each integer r epsilon N a lower bound f((r)) on the minimum f(min) of f, given by the largest scalar lambda for which the polynomial f - lambda is a sum-of-squares on B-n with degree at most 2r. We analyze the quality of these bounds by estimating the worstcase error f(min) - f((r)) in terms of the least roots of the Krawtchouk polynomials. As a consequence, for fixed t epsilon [0, 1/2], we can show that this worst-case error in the regime r approximate to t . n is of the order 1/2- root t(1 - t) as n tends to infinity. Our proof combines classical Fourier analysis on B-n with the polynomial kernel technique and existing results on the extremal roots of Krawtchouk polynomials. This link to roots of orthogonal polynomials relies on a connection between the hierarchy of lower bounds f((r)) and another hierarchy of upper bounds f((r)), for which we are also able to establish the same error analysis. Our analysis extends to the minimization of a polynomial over the q-ary cube (Z/qZ)(n). Furthermore, our results apply to the setting ofmatrix-valued polynomials.

关键词： binary polynomial optimization Lasserre hierarchy Sum-of-squares polynomials Fourier analysis Krawtchouk polynomials polynomial kernels Semidefinite programming polynomial matrices

来源：评论

学校读者我要写书评

暂无评论

On the Complexity of binary polynomial optimization Over Acyclic Hypergraphs

引用

ALGORITHMICA 2023年第8期85卷 2189-2213页

作者： Del Pia, Alberto Di Gregorio, Silvia Univ Wisconsin Madison Dept Ind & Syst Engn 1513 Univ Ave Madison WI 53706 USA Univ Wisconsin Madison Wisconsin Inst Discovery 330 North Orchard St Madison WI 53715 USA Tech Univ Dresden Fac Comp Sci Nothnitzer Str 46 D-01187 Dresden Germany

In this work, we advance the understanding of the fundamental limits of computation for binary polynomial optimization (BPO), which is the problem of maximizing a given polynomial function over all binary points. In our main result we provide a novelclass of BPO that can be solved efficiently both from a theoretical and computational perspective. In fact, we give a strongly polynomial-time algorithm for instances whosec orresponding hypergraph is beta-acyclic. We note that the beta-acyclicity assumption isnatural in several applications including relational database schemes and the liftedmulticut problem on trees. Due to the novelty of our proving technique, we obtainan algorithm which is interesting also from a practical viewpoint. This is becauseour algorithm is very simple to implement and the running time is a polynomial ofvery low degree in the number of nodes and edges of the hypergraph. Our result completely settles the computational complexity of BPO over acyclic hypergraphs,since the problem is NP-hard on alpha-acyclic instances. Our algorithm can also be appliedto any general BPO problem that contains beta-cycles. For these problems, the algorithmreturns a smaller instance together with a rule to extend any optimal solution of thesmaller instance to an optimal solution of the original instance.

关键词： binary polynomial optimization Strongly polynomial-time algorithm Acyclic hypergraphs Hardness of approximation

来源：评论

学校读者我要写书评

暂无评论

Simple Odd β-Cycle Inequalities for binary polynomial optimization 1

引用

23rd International Conference on Integer Programming and Combinatorial optimization (IPCO)

作者： Del Pia, Alberto Walter, Matthias Univ Wisconsin Wisconsin Inst Discovery Dept Ind & Syst Engn Madison WI USA Univ Twente Dept Appl Math Enschede Netherlands

ISBN: (数字)9783031069017

ISBN: (纸本)9783031069017;9783031069000

We consider the multilinear polytope which arises naturally in binary polynomial optimization. Del Pia and Di Gregorio introduced the class of odd beta-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 beta-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.

关键词： binary polynomial optimization Cutting planes Separation algorithm

来源：评论

学校读者我要写书评

暂无评论

Sum-of-Squares Hierarchies for binary polynomial optimization 1

引用

22nd International Conference on Integer Programming and Combinatorial optimization (IPCO)

作者： Slot, Lucas Laurent, Monique Ctr Wiskunde & Informat CWI Amsterdam Netherlands Tilburg Univ Tilburg Netherlands

ISBN: (数字)9783030738792

ISBN: (纸本)9783030738792;9783030738785

We consider the sum-of-squares hierarchy of approximations for the problem of minimizing a polynomial f over the boolean hypercube B-n = {0, 1}(n). This hierarchy provides for each integer r is an element of N a lower bound f(r) on the minimum fmin of f, given by the largest scalar lambda for which the polynomial f-lambda is a sum-of-squares on B-n with degree at most 2r. We analyze the quality of these bounds by estimating the worst-case error f(min) - f((r)) in terms of the least roots of the Krawtchouk polynomials. As a consequence, for fixed t is an element of[0, 1/2], we can show that this worst-case error in the regime r approximate to t center dot n is of the order 1/2-root t(1 - t) as n tends to infinity. Our proof combines classical Fourier analysis on B-n with the polynomial kernel technique and existing results on the extremal roots of Krawtchouk polynomials. This link to roots of orthogonal polynomials relies on a connection between the hierarchy of lower bounds f((r)) and another hierarchy of upper bounds f((r)), for which we are also able to establish the same error analysis. Our analysis extends to the minimization of a polynomial over the q-ary cube (Z/qZ)(n).

关键词： binary polynomial optimization Lasserre hierarchy Sum-of-squares polynomials Fourier analysis Krawtchouk polynomials polynomial kernels Semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs

引用

MATHEMATICAL PROGRAMMING 2024年第1-2期207卷 269-301页

作者： Del Pia, Alberto Khajavirad, Aida Univ Wisconsin Madison Dept Ind & Syst Engn Madison WI USA Univ Wisconsin Madison Wisconsin Inst Discovery Madison WI USA Lehigh Univ Dept Ind & Syst Engn Bethlehem PA 18015 USA

We consider the multilinear polytope defined as the convex hull of the set of binary points z, satisfying a collection of equations of the form z(e) = Pi (upsilon is an element of e) z(upsilon) for all e is an element of E. The complexity of the facial structure of the multilinear polytope is closely related to the acyclicity degree of the underlying hypergraph. We obtain a polynomial-size extended formulation for the multilinear polytope of ss-acyclic hypergraphs, hence characterizing the acyclic hypergraphs for which such a formulation can be constructed.

关键词： binary polynomial optimization Multilinear polytope Hypergraph acyclicity polynomial-size extended formulation

来源：评论

学校读者我要写书评

暂无评论

Multilinear sets with two monomials and cardinality constraints

引用

DISCRETE APPLIED MATHEMATICS 2023年 324卷 67-79页

作者： Chen, Rui Dash, Sanjeeb Gunluk, Oktay Cornell Tech New York NY 10044 USA IBM Res Armonk NY USA Cornell Univ Ithaca NY 14853 USA

binary polynomial optimization is equivalent to the problem of minimizing a linear function over the intersection of the multilinear set with a polyhedron. Many families of valid inequalities for the multilinear set are available in the literature, though giving a polyhedral characterization of the convex hull is not tractable in general as binary polynomial optimization is NP-hard. In this paper, we study the cardinality constrained multilinear set in the special case when the number of monomials is exactly two. We give an extended formulation, with two more auxiliary variables and exponentially many inequalities, of the convex hull of solutions of the standard linearization of this problem. We also show that the separation problem can be solved efficiently. (c) 2022 Elsevier B.V. All rights reserved.

关键词： binary polynomial optimization Cardinality constraint Polyhedral combinatorics

来源：评论

学校读者我要写书评

暂无评论

On optimization problems in acyclic hypergraphs

引用

INFORMATION PROCESSING LETTERS 2023年 182卷

作者： Kamiyama, Naoyuki Kyushu Univ Inst Math Ind Fukuoka Japan

binary polynomial optimization (BPO) is the problem of maximizing a polynomial function on the Boolean domain. This problem can be formulated by using a hypergraph, and various properties of the input hypergraph have been investigated from the viewpoint of polynomial-time solvability. In this paper, we especially focus on beta-acyclic hypergraphs. For BPO over gamma-acyclic hypergraphs, Del Pia and Di Gregorio proposed a polynomial -time algorithm. We prove that the algorithm proposed by Del Pia and Di Gregorio can be extended to a more general optimization problem in beta-acyclic hypergraphs. (c) 2023 Elsevier B.V. All rights reserved.

关键词： binary polynomial optimization Hypergraph 3-acyclicity Algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：