...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >A polyhedral study on 01 knapsack problems with disjoint cardinality constraints: Strong valid inequalities by sequence-independent lifting
【24h】

A polyhedral study on 01 knapsack problems with disjoint cardinality constraints: Strong valid inequalities by sequence-independent lifting

机译：具有不相交的基数约束的01背包问题的多面体研究：通过独立于序列的提升，产生有效的不等式

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

摘要

We study the set of 01 integer solutions to a single knapsack constraint and a set of non-overlapping cardinality constraints (MCKP), which generalizes the classical 01 knapsack polytope and the 01 knapsack polytope with generalized upper bounds. We derive strong valid inequalities for the convex hull of its feasible solutions using sequence-independent lifting. For problems with a single cardinality constraint, we derive two-dimensional superadditive lifting functions and prove that they are maximal and non-dominated under some mild conditions. We then show that these functions can be used to build strong valid inequalities for problems with multiple disjoint cardinality constraints. Finally, we present preliminary computational results aimed at evaluating the strength of the cuts obtained from sequence-independent lifting with respect to those obtained from sequential lifting.
机译：我们研究了单个背包约束和一组非重叠基数约束（MCKP）的01个整数解的集合，该集合泛化了经典的01背包多面体和带有广义上界的01背包多面体。我们使用与序列无关的提升为其可行解的凸包得出了强大的有效不等式。对于具有单个基数约束的问题，我们导出了二维超加性提升函数，并证明它们在某些温和条件下是最大且非支配的。然后，我们证明这些函数可用于为具有多个不相交基数约束的问题建立强大的有效不等式。最后，我们提出了初步的计算结果，旨在评估相对于顺序提升所获得的与顺序无关的提升所获得的切割强度。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号