Facets of Two-Dimensional Infinite Group Problems
Facets of Two-Dimensional Infinite Group Problems
复制标题
二维无限群问题的各个方面
DOI：
--
复制
发表时间：
2008
影响因子：
1.7
通讯作者：
Jean
中科院分区：
文献类型：
--
作者：
Santanu S. Dey;Jean
本文为二维混合整数无限群问题（2DMIIGP）的研究奠定了基础。我们引入工具来确定给定的二维无限群上的连续分段线性函数是否为次加性，并确定它是否定义了2DMIIGP的一个面。然后，我们提出了两种不同的结构，它们产生了第一个已知的2DMIIGP的面定义不等式族。第一个结构使用一维整数无限群问题（1DIIGP）的有效不等式作为创建二维整数无限群问题（2DIIGP）不等式的构建块。我们证明了这种构造产生了具有两个梯度的二维群问题的所有连续分段线性面。我们给出的第二种构造有三个梯度，并给出了二维混合整数无限群问题（1DMIIGP）的面定义不等式，其连续系数不受一维混合整数无限群问题（1DMIIGP）的面控制。
In this paper, we lay the foundation for the study of the two-dimensional mixed integer infinite group problem (2DMIIGP). We introduce tools to determine if a given continuous and piecewise linear function over the two-dimensional infinite group is subadditive and to determine whether it defines a facet of 2DMIIGP. We then present two different constructions that yield the first known families of facet-defining inequalities for 2DMIIGP. The first construction uses valid inequalities of the one-dimensional integer infinite group problem (1DIIGP) as building blocks for creating inequalities for the two-dimensional integer infinite group problem (2DIIGP). We prove that this construction yields all continuous piecewise linear facets of the two-dimensional group problem that have exactly two gradients. The second construction we present has three gradients and yields facet-defining inequalities of 2DMIIGP whose continuous coefficients are not dominated by those of facets of the one-dimensional mixed integer infinite group problem (1DMIIGP).