• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International conference on integer programming and combinatorial optimization >Integer Programs with Prescribed Number of Solutions and a Weighted Version of Doignon-Bell-Scarf's Theorem
【24h】

Integer Programs with Prescribed Number of Solutions and a Weighted Version of Doignon-Bell-Scarf's Theorem

机译：具有规定解数和Doignon-Bell-Scarf定理的加权版本的整数程序

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

摘要

In this paper we study a generalization of the classical feasibility problem in integer linear programming, where an ILP needs to have a prescribed number of solutions to be considered solved. We first provide a generalization of the famous Doignon-Bell-Scarf theorem: Given an integer k, we prove that there exists a constant c(k, n), depending only on the dimension n and k, such that if a polyhedron {x:Ax ≤b} contains exactly k integer solutions, then there exists a subset of the rows of cardinality no more than c(k,n), defining a polyhedron that contains exactly the same k integer solutions. The second contribution of the article presents a structure theory that characterizes precisely the set Sg≥k(A) of all vectors b such that the problem Ax = b, x ≥ 0, x ∈ Z~n, has at least k-solutions. We demonstrate that this set is finitely generated, a union of translated copies of a semigroup which can be computed explicitly via Hilbert bases computation. Similar results can be derived for those right-hand-side vectors that have exactly k solutions or fewer than k solutions. Finally we show that, when n, k are fixed natural numbers, one can compute in polynomial time an encoding of Sg≥k(A) as a generating function, using a short sum of rational functions. As a consequence, one can identify all right-hand-side vectors that have exactly k solutions (similarly for at least k or less than k solutions). Under the same assumptions we prove that the k-Frobenius number can be computed in polynomial time.
机译：在本文中，我们研究了整数线性规划中经典可行性问题的一般化，其中ILP需要具有规定数量的解决方案才能被考虑。我们首先提供著名的Doignon-Bell-Scarf定理的一个推广：给定一个整数k，我们证明存在一个常数c（k，n），仅取决于维度n和k，使得如果多面体{x ：Ax≤b}包含正好为k的整数解，则基数行中的子集不超过c（k，n），从而定义了包含完全相同的k个整数解的多面体。本文的第二部分提出了一种结构理论，该结构理论精确地刻画了所有向量b的集合Sg≥k（A）的特征，使得问题Ax = b，x≥0，x∈Z〜n，至少具有k个解。我们证明了该集合是有限生成的，可以通过希尔伯特基数计算显式计算出一个半组的翻译副本的并集。对于那些恰好具有k个解或少于k个解的右侧向量，可以得出相似的结果。最终，我们证明，当n，k为固定自然数时，可以使用一小部分有理函数，在多项式时间内将Sg≥k（A）的编码作为生成函数进行计算。结果，可以识别出所有具有正好k个解的右侧向量（类似地至少k个或少于k个解）。在相同的假设下，我们证明可以在多项式时间内计算k-Frobenius数。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号