论文标题
整数线性优化的线性优化松弛的邻居持久性
Neighborhood persistency of the linear optimization relaxation of integer linear optimization
论文作者
论文摘要
对于整数线性优化（ILO）问题，其线性优化（LO）放松的持久性是一个属性，对于将整数值分配给某些变量的每个最佳解决方案，都存在ILO问题的最佳解决方案，其中这些变量保留相同的值。尽管持久性已被用于开发启发式，近似和固定参数算法的特殊情况，但其适用性在文献中仍然未知。在本文中，我们揭示了ILO的最大子类，使其放松具有持久性。具体而言，我们表明，ILO在单位二值（UTVPI）系统上具有持久性，并且在某种意义上是此类ILO的最大程度。我们的持久性结果概括了Nemhauser和Trotter，Hochbaum等人和Fiorini等。更重要的是，我们提出了一个更强的属性，称为\ emph {邻居持久性}，并表明iLo在UTVPI系统上的Lo lo放宽具有此属性。使用此更强的结果，我们获得了固定参数算法（参数为解决方案大小），以及在目标函数和变量不含的UTVPI系统上，ILO对ILO的另一种证明。
For an integer linear optimization (ILO) problem, persistency of its linear optimization (LO) relaxation is a property that for every optimal solution of the relaxation that assigns integer values to some variables, there exists an optimal solution of the ILO problem in which these variables retain the same values. Although persistency has been used to develop heuristic, approximation, and fixed-parameter algorithms for special cases of ILO, its applicability remains unknown in the literature. In this paper we reveal a maximal subclass of ILO such that its LO relaxation has persistency. Specifically, we show that the LO relaxation of ILO on unit-two-variable-per-inequality (UTVPI) systems has persistency and is (in a certain sense) maximal among such ILO. Our persistency result generalizes the results of Nemhauser and Trotter, Hochbaum et al., and Fiorini et al. Even more, we propose a stronger property called \emph{neighborhood persistency} and show that the LO relaxation of ILO on UTVPI systems in general has this property. Using this stronger result, we obtain a fixed-parameter algorithm (where the parameter is the solution size) and another proof of two-approximability for ILO on UTVPI systems where objective functions and variables are non-negative.
