Scholarlink

<p>We investigate the semigroup of integer points inside a convex cone. We extend classical results in integer linear programming to integer conic programming. We show that the semigroup associated with nonpolyhedral cones can sometimes have a notion of finite generating set with the help of a group action. We show this is true for the cone of positive semidefinite matrices (PSD) and the second-order cone (SOC). Both cones have a finite generating set of integer points, similar in spirit to Hilbert bases, under the action of a finitely generated group. We also extend notions of total dual integrality, Gomory-Chvátal closure, and Carathéodory rank to integer points in arbitrary cones.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Integer points in arbitrary convex cones: the case of the PSD and SOC cones

  • 期刊论文

  • 发表日期：

    2025年1月16日

查看全文
  • Jesús A. De Loera,
  • Brittney Marsters,
  • Luze Xu,
  • Shixuan Zhang

摘要

We investigate the semigroup of integer points inside a convex cone. We extend classical results in integer linear programming to integer conic programming. We show that the semigroup associated with nonpolyhedral cones can sometimes have a notion of finite generating set with the help of a group action. We show this is true for the cone of positive semidefinite matrices (PSD) and the second-order cone (SOC). Both cones have a finite generating set of integer points, similar in spirit to Hilbert bases, under the action of a finitely generated group. We also extend notions of total dual integrality, Gomory-Chvátal closure, and Carathéodory rank to integer points in arbitrary cones.