论文标题
0-1线性程序与加权线性编程等效的非负部分S-良好性
Nonnegative partial s-goodness for the equivalence of a 0-1 linear program to weighted linear programming
论文作者
论文摘要
来自许多NP-HARD组合优化问题的非负约束矩阵和目标向量e起源的0-1线性编程问题。在本文中，我们考虑从加权线性编程中恢复对问题的最佳解决方案。我们首先将问题等效地作为稀疏优化问题提出。接下来，我们考虑稀疏优化问题的最佳解决方案和加权线性编程问题的一致性。为了实现这一目标，我们建立了约束矩阵和加权向量的非负部分S-良好性。此外，我们使用两次数量来表征非负部分S-良好性的足够条件和必要条件。但是，这两个数量很难计算，因此，我们为两个数量之一提供了可计算的上限，以验证非负部分S-goodness。最后，我们举了三个例子，以说明我们的理论是有效且可验证的。
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.
