Semi-infinite mixed binary and disjunctive programs: Applications to set-covering with infinite demand points and implicit hitting set problems

Simple item page
dc.contributor.authorBansal, Manishen
dc.date.accessioned2023-02-20T18:30:50Zen
dc.date.available2023-02-20T18:30:50Zen
dc.date.issued2023-02en
dc.date.updated2023-02-19T15:06:25Zen
dc.description.abstractSherali 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).en
dc.description.versionSubmitted versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.orcidBansal, Manish [0000-0002-5617-3862]en
dc.identifier.urihttp://hdl.handle.net/10919/113881en
dc.language.isoenen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.titleSemi-infinite mixed binary and disjunctive programs: Applications to set-covering with infinite demand points and implicit hitting set problemsen
dc.title.serialINFORMS Journal on Optimizationen
dc.typeArticleen
dc.type.dcmitypeTexten
dc.type.otherArticleen
pubs.organisational-group/Virginia Techen
pubs.organisational-group/Virginia Tech/Engineeringen
pubs.organisational-group/Virginia Tech/Engineering/Industrial and Systems Engineeringen
pubs.organisational-group/Virginia Tech/All T&R Facultyen
pubs.organisational-group/Virginia Tech/Engineering/COE T&R Facultyen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Bansal-SemiInfiniteDisjunctiveMixedBinaryPrograms-OO-1.pdf
Size:
2.6 MB
Format:
Adobe Portable Document Format
Description:
Submitted version
Download

Collections

All Faculty Deposits
Scholarly Works, Industrial and Systems Engineering