Upper Bounds on the Number of Solutions of Binary Integer Programs

机译：二进制整数程序解数的上限

获取原文

获取原文并翻译 | 示例

页面导航

摘要
著录项
相似文献
相关主题

摘要

We present a new method to compute upper bounds of the number of solutions of binary integer programming (BIP) problems. Given a BIP, we create a dynamic programming (DP) table for a redundant knapsack constraint which is obtained by surrogate relaxation. We then consider a Lagrangian relaxation of the original problem to obtain an initial weight bound on the knapsack. This bound is then refined through subgradient optimization. The latter provides a variety of Lagrange multipliers which allow us to filter infeasible edges in the DP table. The number of paths in the final table then provides an upper bound on the number of solutions. Numerical results show the effectiveness of our counting framework on automatic recording and market split problems.

机译：我们提出了一种新的方法来计算二进制整数规划（BIP）问题的解数的上限。给定一个BIP，我们为通过代理松弛获得的冗余背包约束创建了一个动态规划（DP）表。然后，我们考虑原始问题的拉格朗日松弛，以在背包上获得初始重量约束。然后通过次梯度优化来优化此界限。后者提供了各种拉格朗日乘数，使我们能够过滤DP表中不可行的边。然后，最终表中的路径数提供了解决方案数的上限。数值结果表明我们的计数框架在自动记录和市场拆分问题上的有效性。

著录项

来源
《Integration of AI and OR techniques in constraint programming for combinatorial optimization problems》|2010年|p.203-218|共16页
会议地点 Bologna(IT);Bologna(IT)
作者
Siddhartha Jain; Serdar Kadioglu; Meinolf Sellmann;
展开▼
作者单位

Brown University, Department of Computer Science, 115 Waterman Street, P.O. Box 1910, Providence, RI 02912;

Brown University, Department of Computer Science, 115 Waterman Street, P.O. Box 1910, Providence, RI 02912;

Brown University, Department of Computer Science, 115 Waterman Street, P.O. Box 1910, Providence, RI 02912;

展开▼
会议组织
原文格式 PDF
正文语种 eng
中图分类计算机软件;
关键词
solution counting; cp-based lagrangian relaxation; surrogate relaxation; dynamic programming;

机译：溶液计数；基于cp的拉格朗日松弛替代松弛动态编程;

相似文献

外文文献
中文文献
专利

1. An upper bound of radio k-coloring problem and its integer linear programming model [J] . Badr Elsayed M., Moussa Mahmoud I. Wireless Networks . 2020,第7期

机译：无线电K-着色问题的上限及其整数线性编程模型
2. Lifting for mixed integer programs with variable upper bounds [J] . Shebalov Sergey, Park Young Woong, Klabjan Diego Discrete Applied Mathematics . 2015,第Null期

机译：提升具有可变上限的混合整数程序
3. Sequence independent lifting for mixed integer programs with variable upper bounds [J] . Shebalov S, Klabjan D Mathematical Programming . 2006,第2a3期

机译：具有可变上限的混合整数程序的与序列无关的提升
4. Upper Bounds on the Number of Solutions of Binary Integer Programs [C] . Siddhartha Jain, Serdar Kadioglu, Meinolf Sellmann International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems . 2010

机译：上限对二进制整数程序的解数
5. Polyhedra study of mixed integer programs with variable upper bounds. [D] . Shebalov, Sergey. 2004

机译：具有可变上限的混合整数程序的多面体研究。
6. Nonasymptotic Upper Bounds on Binary Single Deletion Codes via Mixed Integer Linear Programming [O] . Albert No 2019

机译：通过混合整数线性规划二进制单删除代码对二元删除码的巨大上限
7. Upper Bounds on the Number of Solutions of Binary Integer Programs [O] . Siddhartha Jain, Serdar Kadioglu, Meinolf Sellmann 2012

机译：二进制整数程序解的数量的上界
8. A Bounding Technique for Integer Linear Programming with Binary Variables [R] . Hillier, F. S., Jacqmin, N. E. 1979

机译：二元变量整数线性规划的一种束缚技术

Upper Bounds on the Number of Solutions of Binary Integer Programs

摘要

著录项

相似文献

相关主题

期刊订阅