Abstract
Capacitated fixed-charge network flows are used to model a variety of problems in telecommunication, facility location, production planning, and supply chain management. In this paper, we investigate capacitated path substructures and derive strong and easy-to-compute path cover and path pack inequalities. These inequalities are based on an explicit characterization of the submodular inequalities through a fast computation of parametric minimum cuts on a path, and they generalize the well-known flow cover and flow pack inequalities for the single-node relaxations of fixed-charge flow models. We provide necessary and sufficient facet conditions. Computational results demonstrate the effectiveness of the inequalities when used as cuts in a branch-and-cut algorithm.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 1943-1976 |
| Number of pages | 34 |
| Journal | SIAM Journal on Optimization |
| Volume | 27 |
| Issue number | 3 |
| DOIs | |
| State | Published - Sep 6 2017 |
Funding
\u2217Received by the editors July 29, 2015; accepted for publication (in revised form) June 23, 2017; published electronically September 6, 2017. http://www.siam.org/journals/siopt/27-3/M103300.html Funding: The work of the first and third authors was supported, in part, by the National Science Foundation grant 0970180 and by grant FA9550-10-1-0168 from the Office of the Assistant Secretary of Defense for Research and Engineering. The work of the second author was supported, in part, by the National Science Foundation grants 1732364 and 1733001. \u2020Department of Industrial Engineering & Operations Research, University of California, Berkeley, CA 94720 ([email protected], [email protected]). \u2021Department of Industrial and Systems Engineering, University of Washington, Seattle, WA 98195 ([email protected]).
Keywords
- Covers
- Fixed-charge networks
- Mixed-integer programming
- Packs
- Submodular functions
- Valid inequalities
ASJC Scopus subject areas
- Software
- Theoretical Computer Science