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

Meijia Han () and Wenxing Zhu ()
Additional contact information
Meijia Han: Fuzhou University
Wenxing Zhu: Fuzhou University

Journal of Combinatorial Optimization, 2023, vol. 45, issue 5, No 14, 37 pages

Abstract: Abstract The 0-1 linear programming problem with non-negative constraint matrix and objective vector $${\textbf{e}}$$ 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.

Keywords: Integer programming; Non-negative partial s-goodness; Weighted linear programming; Sparse optimization (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01054-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:45:y:2023:i:5:d:10.1007_s10878-023-01054-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-023-01054-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().