A Branch-and-Cut algorithm for the single commodity uncapacitated fixed charge network flow problem
(2003) Networks — Vol. 41, n° 3, p. 143-158 (2003)
Files
No attached file found for this publication.
Details
- Authors
- Abstract
- We present a branch-and-cut algorithm to solve the single-commodity, uncapacitated, fixed-charge network flow problem, which includes the Steiner tree problem, uncapacitated lot-sizing problems, and the fixed-charge transportation problem as special cases. The cuts used are simple dicut inequalities and their variants. A crucial problem when separating these inequalities is to find the right cut set on which to generate the inequalities. The prototype branch-and-cut system, bc-nd, includes a separation heuristic for the dicut inequalities and problem-specific primal heuristics, branching, and pruning rules. Computational results show that bc-nd is competitive compared to a variety of special purpose algorithms for problems with explicit flow costs. We also examine how general purpose MIP systems perform on such problems when provided with formulations that have been tightened a priori with dicut inequalities.
- Affiliations
Louvain School of Management Operations and Information
Citations
Wolsey, L., & Ortega, F. (2003). A Branch-and-Cut algorithm for the single commodity uncapacitated fixed charge network flow problem. Networks, 41(3), 143-158. https://hdl.handle.net/2078.5/249419 (Original work published 2003)