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

THE BOOLEAN QUADRIC POLYTOPE - SOME CHARACTERISTICS, FACETS AND RELATIVES

MATHEMATICAL programming 1989年第1期45卷 139-172页

作者： PADBERG, M 1.Stern School of Business New York University Washington Square 10003 New York NY USA

We study unconstrained quadratic zero–one programming problems havingn variables from a polyhedral point of view by considering the Boolean quadric polytope QP n inn(n+1)/2 dimensions that results from the lineariza... 详细信息

We study unconstrained quadratic zero–one programming problems havingn variables from a polyhedral point of view by considering the Boolean quadric polytope QPⁿ inn(n+1)/2 dimensions that results from the linearization of the quadratic form. We show that QPⁿ has a diameter of one, descriptively identify three families of facets of QPⁿ and show that QPⁿ is symmetric in the sense that all facets of QPⁿ can be obtained from those that contain the origin by way of a mapping. The naive linear programming relaxation QPⁿ _LP of QPⁿ is shown to possess the Trubin-property and its extreme points are shown to be {0,1/2,1}-valued. Furthermore, O(n ³) facet-defining inequalities of QPⁿ suffice to cut off all fractional vertices of QPⁿ _LP, whereas the family of facets described by us has at least O(3ⁿ) members. The problem is also studied for sparse quadratic forms (i.e. when several or many coefficients are zero) and conditions are given for the previous results to carry over to this case. Polynomially solvable problem instances are discussed and it is shown that the known polynomiality result for the maximization of nonnegative quadratic forms can be obtained by simply rounding the solution to the linear programming relaxation. In the case that the graph induced by the nonzero coefficients of the quadratic form is series-parallel, a complete linear description of the associated Boolean quadric polytope is given. The relationship of the Boolean quadric polytope associated to sparse quadratic forms with the vertex-packing polytope is discussed as well.

关键词： unconstrained zero–one quadratic programming polyhedral combinatorics facets polytopes vertex-packing series-parallel graphs polynomial solvability

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：