The 0-1 linear programming problem with nonnegative constraint matrix and objective vector e origins from many NP-hard combinatorial optimization problems. In this paper, we consider recovering an optimal solution to the problem from a weighted linear programming.We first formulate the problem equivalently as a sparse optimization problem. Next, we consider the consistency of the optimal solution of the sparse optimization problem and the weighted linear programming problem. In order to achieve this, we establish nonnegative partial s-goodness of the constraint matrix and the weighted vector. Further, we use two quantities to characterize a sufficient condition and necessary condition for the nonnegative partial s-goodness. However, the two quantities are difficult to calculate, therefore, we provide a computable upper bound for one of the two quantities to verify the nonnegative partial s-goodness. Finally, we give three examples to illustrate that our theory is effective and verifiable.
翻译：0-1 线性编程问题与非负约束矩阵和客观矢量 e 的线性编程问题源于许多NP-硬组合优化问题。 在本文中,我们考虑从加权线性编程中恢复这一问题的最佳解决办法。 我们首先将问题表述为微小优化问题。 我们接下来考虑稀薄优化问题的最佳解决办法和加权线性编程问题的一致性。 为了实现这一目标,我们确定了制约矩阵和加权矢量的非负部分质量。 此外,我们用两个数量来说明非负部分货物的充分条件和必要条件。 然而,我们很难计算这两个数量,因此,我们为这两个数量中的一个提供了可计算上限,以核实非负部分货物。 最后,我们举三个例子来说明我们的理论是有效和可核查的。
相关内容
微信扫码咨询专知VIP会员