Path cover and path pack inequalities for the capacitated fixed-charge network flow problem

DOI10.1137/15M1033009MaRDI QIDQ5355207zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1705.05920

zbMATH Keywords

mixed-integer programmingvalid inequalitiessubmodular functionsfixed-charge networkscovers and packs

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Mixed integer programming (90C11)

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.

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

Cites work

• scientific article; zbMATH DE number 1416629 (Why is no real title available?)
• A Faster Deterministic Maximum Flow Algorithm
• A branch‐and‐cut algorithm for the single‐commodity, uncapacitated, fixed‐charge network flow problem
• A note on ``Lot-sizing with fixed charges on stocks: the convex hull
• Fixed-charge transportation on a path: optimization, LP formulations and separation
• Flow pack facets of the single node fixed-charge flow polytope
• Lifted flow cover inequalities for mixed 0-1 integer programs
• Lot Sizing with Inventory Bounds and Fixed Costs: Polyhedral Study and Computation
• Lot-size models with backlogging: Strong reformulations and cutting planes
• Lot-sizing with fixed charges on stocks: the convex hull
• Polyhedra for lot-sizing with Wagner-Whitin costs
• Submodularity and valid inequalities in capacitated fixed charge networks
• The complementary class of generalized flow cover inequalities
• Three-partition flow cover inequalities for constant capacity fixed-charge network flow problems
• Uncapacitated lot sizing with backlogging: the convex hull
• Valid Linear Inequalities for Fixed Charge Problems
• Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems
• Valid inequalities and separation for uncapacitated fixed charge networks
• Valid inequalities for mixed 0-1 programs

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
• scientific article; zbMATH DE number 7040611 (Why is no real title available?)
• Theoretical challenges towards cutting-plane selection
• Sequence Independent Lifting for the Set of Submodular Maximization Problem
• Weak flow cover inequalities for the capacitated facility location problem
• Convex hull results for generalizations of the constant capacity single node flow set
• A repeated route-then-schedule approach to coordinated vehicle platooning: algorithms, valid inequalities and computation
• 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
• Submodularity and valid inequalities in capacitated fixed charge networks
• Flows with Unit Path Capacities and Related Packing and Covering Problems
• 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)