Approximate Submodularity in Network Design Problems

Levi DeValve (), Saša Pekeč () and Yehua Wei ()
Additional contact information
Levi DeValve: Booth School of Business, University of Chicago, Chicago, Illinois 60637
Saša Pekeč: The Fuqua School of Business, Duke University, Durham, North Carolina 27708
Yehua Wei: The Fuqua School of Business, Duke University, Durham, North Carolina 27708

Operations Research, 2023, vol. 71, issue 4, 1021-1039

Abstract: Network design problems, such as flexibility design, are ubiquitous in modern marketplaces where firms constantly innovate new ways to match supply and demand. We develop a primal-dual based approach to analyze the flexibility design problem, and establish that the problem possesses a novel structural property. The property, which we call cover modularity , can be interpreted as an approximate form of submodularity in the sense that local changes in the objective function can be used to bound global changes. We use this structure to analyze a class of greedy heuristics and establish the first constant factor approximation guarantee for solving the general flexibility design problem. Furthermore, we identify a significant practical byproduct of our primal-dual analysis: The dual solutions we construct can be used as surrogates to guide the heuristics, leading to order of magnitude gains in computational efficiency without loss of optimization performance. Finally, we extend our analysis by demonstrating the presence of cover modularity in a general class of linear programming formulations, indicating applicability of our approach to a wide range of network design problems distinct from flexibility design.

Keywords: Operations and Supply Chains; network design; process flexibility; approximate submodularity (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2408 (application/pdf)

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:inm:oropre:v:71:y:2023:i:4:p:1021-1039

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().