• 主题
高级搜索  >
历史搜索 清空历史
首页> 美国政府科技报告 >Branch-and-Cut Algorithms for Independent Set Problems: Integrality Gap and An Application to Protein Structure Alignment
【24h】

Branch-and-Cut Algorithms for Independent Set Problems: Integrality Gap and An Application to Protein Structure Alignment

机译：独立集问题的分支切割算法：完整性差距及其在蛋白质结构比对中的应用

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We discuss the effectiveness of branch and cut for solving large instances of the independent set problem. Typical LP formulations, even strengthened by clique inequalities, yield poor bounds for this problem. We prove that a strong bound is obtained by the use of the so called 'rank inequalities', which generalize the clique inequalities. For some problems the clique inequalities imply the rank inequalities, and then a strong bound is guaranteed already by the simpler formulation. This is the case of the contact map overlap problem, which was proposed as a measure for protein structure alignments. We formalize this problem as a particular, large independent set problem, which we solve by integer programming. We strengthen our formulation by the use of clique inequality cuts. Although there are exponentially many cliques, we show how to separate over them in polynomial time. Unprecedented computational results on real data show the effectiveness of our approach.

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号