Path cover and path pack inequalities for the capacitated fixed-charge network flow problem
From MaRDI portal
Publication:5355207
DOI10.1137/15M1033009zbMATH Open1370.90151arXiv1705.05920OpenAlexW2616750249MaRDI QIDQ5355207FDOQ5355207
Authors: Alper Atamtürk, Simge Küçükyavuz, Birce Tezel 
Publication date: 7 September 2017
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
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 emph{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.
Full work available at URL: https://arxiv.org/abs/1705.05920
Recommendations
- Valid inequalities and separation for capacitated fixed charge flow problems
- Three-partition flow cover inequalities for constant capacity fixed-charge network flow problems
- Submodularity and valid inequalities in capacitated fixed charge networks
- Flow pack facets of the single node fixed-charge flow polytope
- Fixed-charge transportation on a path: linear programming formulations
mixed-integer programmingvalid inequalitiessubmodular functionsfixed-charge networkscovers and packs
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Mixed integer programming (90C11)
Cites Work
- Title not available (Why is that?)
- Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems
- A Faster Deterministic Maximum Flow Algorithm
- A branch‐and‐cut algorithm for the single‐commodity, uncapacitated, fixed‐charge network flow problem
- Lot Sizing with Inventory Bounds and Fixed Costs: Polyhedral Study and Computation
- Uncapacitated lot sizing with backlogging: the convex hull
- Valid inequalities for mixed 0-1 programs
- Lot-size models with backlogging: Strong reformulations and cutting planes
- The complementary class of generalized flow cover inequalities
- Polyhedra for lot-sizing with Wagner-Whitin costs
- Valid Linear Inequalities for Fixed Charge Problems
- Flow pack facets of the single node fixed-charge flow polytope
- Lifted flow cover inequalities for mixed \(0\)-\(1\) integer programs
- Lot-sizing with fixed charges on stocks: the convex hull
- A note on ``Lot-sizing with fixed charges on stocks: the convex hull
- Submodularity and valid inequalities in capacitated fixed charge networks
- Valid inequalities and separation for uncapacitated fixed charge networks
- Fixed-charge transportation on a path: optimization, LP formulations and separation
- Three-partition flow cover inequalities for constant capacity fixed-charge network flow problems
Cited In (18)
- Sequence independent lifting for a set of submodular maximization problems
- Submodular function minimization and polarity
- Fixed-charge transportation on a path: linear programming formulations
- Valid inequalities and separation for capacitated fixed charge flow problems
- Fixed-charge transportation on a path: optimization, LP formulations and separation
- Title not available (Why is that?)
- Sequence Independent Lifting for the Set of Submodular Maximization Problem
- Theoretical challenges towards cutting-plane selection
- Weak flow cover inequalities for the capacitated facility location problem
- A repeated route-then-schedule approach to coordinated vehicle platooning: algorithms, valid inequalities and computation
- Convex hull results for generalizations of the constant capacity single node flow set
- Flow pack facets of the single node fixed-charge flow polytope
- Supermodularity and valid inequalities for quadratic optimization with indicators
- Two-level lot-sizing with inventory bounds
- Flows with Unit Path Capacities and Related Packing and Covering Problems
- Submodularity and valid inequalities in capacitated fixed charge networks
- Minimum‐cost flow problems having arc‐activation costs
- Three-partition flow cover inequalities for constant capacity fixed-charge network flow problems
This page was built for publication: Path cover and path pack inequalities for the capacitated fixed-charge network flow problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5355207)
