An exact separation algorithm for unsplittable flow capacitated network design arc-set polyhedron
From MaRDI portal
Publication:2052386
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.
Recommendations
- On splittable and unsplittable flow capacitated network design arc-set polyhedra.
- Unsplittable non-additive capacitated network design using set functions polyhedra
- Capacitated multi-layer network design with unsplittable demands: polyhedra and branch-and-cut
- The splittable flow arc set with capacity and minimum load constraints
- On capacitated network design cut-set polyhedra
- A pseudopolynomial network flow formulation for exact knapsack separation
- A characterization of the uncapacitated network design polytope
- A combinatorial arc tolerance analysis for network flow problems
- A hybrid algorithm for solving convex separable network flow problems
- Capacitated Network Design—Polyhedral Structure and Computation
Cites work
- A computational study of exact knapsack separation for the generalized assignment problem
- A Minimal Algorithm for the Bounded Knapsack Problem
- An implementation of exact knapsack separation
- Backbone Network Design Tools with Economic Tradeoffs
- Benchmarking optimization software with performance profiles.
- Exploiting erraticism in search
- Fenchel Cutting Planes for Integer Programs
- Generating Fenchel Cutting Planes for Knapsack Polyhedra
- Modeling and Solving the Two-Facility Capacitated Network Loading Problem
- On capacitated network design cut-set polyhedra
- On cut-based inequalities for capacitated network design polyhedra
- On the Convergence of Fenchel Cutting Planes in Mixed-Integer Programming
- Polyhedral results for the edge capacity polytope.
- SCIP: solving constraint integer programs
- Separation algorithms for 0-1 knapsack polytopes
- Solving the capacitated local access network design problem
- Source sink flows with capacity installation in batches
- The dual simplex method, techniques for a fast and stable implementation
- The M{\texttt{CF}}-separator: Detecting and exploiting multi-commodity flow structures in MIPs
- Unsplittable non-additive capacitated network design using set functions polyhedra
Cited in
(3)
This page was built for publication: An exact separation algorithm for unsplittable flow capacitated network design arc-set polyhedron
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2052386)
