Semi-Infinite Mixed Binary and Disjunctive Programs: Applications to Set-Covering with Infinite Demand Points and Implicit Hitting Set Problems

Sherali and Adams [Discrete Applied Math. 157: 1319-1333, 2009] derived convex hull of semi-infinite mixed binary linear programs (SIMBLPs) using Reformulation-Linearization Technique (RLT). In this paper, we study semi-infinite disjunctive programs (SIDPs -- a generalization of SIMBLPs) and present linear programming equivalent and valid inequalities for them. We utilize these results for deriving a hierarchy of relaxations for SIMBLPs along with solution approaches for them. This also establishes a direct connection between RLT and linear programming equivalent for disjunctive programs, even without sequential convexification and the requirement of computing projections multiple times. Additionally, we present an exact algorithm for SIBLPs with implicity defined constraints (SIBLP-IC), and formulate set-covering problem with infinite number of demand points or spatial representation of demand as SIBLP-IC. Based on our computational results for solving the set-covering (and equivalent implicit hitting set) problem instances, we observe that the foregoing approach is computationally efficient in comparison to Gurobi 9.5.2 and an algorithm of Moreno-Centeno and Karp [Operations Research 61(2): 453-468, 2013] for implicit hitting set problem (a special case of SIBLP-IC).

Article

Download

View Semi-Infinite Mixed Binary and Disjunctive Programs: Applications to Set-Covering with Infinite Demand Points and Implicit Hitting Set Problems