Nonnegative partial s-goodness for the equivalence of a 0-1 linear program to weighted linear programming

Abstract

The 0-1 linear programming problem with non-negative constraint matrix and objective vector ${\textbf{e}}$ origins from many NP-hard combinatorial optimization problems. In this paper, we consider under what condition an optimal solution of the 0-1 problem can be obtained from a weighted linear programming. To this end, we first formulate the 0-1 problem as a sparse minimization problem. Any optimal solution of the 0-1 linear programming problem can be obtained by rounding up an optimal solution of the sparse minimization problem. Then, we establish a condition under which the sparse minimization problem and the weighted linear programming problem have the same optimal solution. The condition is based on the defined non-negative partial s-goodness of the constraint matrix and the weight vector. Further, we use two quantities to characterize a sufficient condition and necessary condition for the non-negative 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 non-negative partial s-goodness. Furthermore, we propose two operations of the constraint matrix and weight vector that still preserve non-negative partial s-goodness. Finally, we give some examples to illustrate that our theory is effective and verifiable.