We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
An exact separation algorithm for unsplittable flow capacitated network design arc-set polyhedron.
- Authors
Chen, Liang; Chen, Wei-Kun; Yang, Mu-Ming; Dai, Yu-Hong
- Abstract
In this paper, we concentrate on generating cutting planes for the unsplittable capacitated network design problem. We use the unsplittable flow arc-set polyhedron of the considered problem as a substructure and generate cutting planes by solving the separation problem over it. To relieve the computational burden, we show that, in some special cases, a closed form of the separation problem can be derived. For the general case, a brute-force algorithm, called exact separation algorithm, is employed in solving the separation problem of the considered polyhedron such that the constructed inequality guarantees to be facet-defining. Furthermore, a new technique is presented to accelerate the exact separation algorithm, which significantly decreases the number of iterations in the algorithm. Finally, a comprehensive computational study on the unsplittable capacitated network design problem is presented to demonstrate the effectiveness of the proposed algorithm.
- Subjects
ALGORITHMS; PROBLEM solving
- Publication
Journal of Global Optimization, 2021, Vol 81, Issue 3, p659
- ISSN
0925-5001
- Publication type
Article
- DOI
10.1007/s10898-020-00967-z