• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >A new separation algorithm for the Boolean quadric and cut polytopes
【24h】

A new separation algorithm for the Boolean quadric and cut polytopes

机译：布尔二次曲面和切多边形的新分离算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A separation algorithm is a procedure for generating cutting planes. Up to now, only a few polynomial-time separation algorithms were known for the Boolean quadric and cut polytopes. These polytopes arise in connection with zero-one quadratic programming and the max-cut problem, respectively. We present a new algorithm, which separates over a class of valid inequalities that includes all odd bicycle wheel inequalities and (2p + 1, 2)- circulant inequalities. It exploits, in a non-trivial way, three known results in the literature: one on the separation of {0, 1/2 }-cuts, one on the symmetries of the polytopes in question, and one on an affine mapping between the polytopes.
机译：分离算法是生成切割平面的过程。到目前为止，对于布尔二次曲面和割多边形，只有少数多项式时间分离算法是已知的。这些多面体分别与零一二次编程和最大割问题有关。我们提出了一种新的算法，该算法将一类有效不等式分离开，该有效不等式包括所有奇数自行车车轮不等式和（2p + 1，2）-循环不等式。它以非平凡的方式利用了文献中的三个已知结果：一个关于{0，1/2}切口的分离，一个关于所讨论的多位构形的对称性，另一个关于两个多义词之间的仿射映射。多表位。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号