Fixed-charge transportation problems on trees

DOI10.1016/J.ORL.2017.04.001MaRDI QIDQ1728231zbMATH OpenOpenAlexFDO

Authors Gustavo Angulo, Mathieu Van Vyve

Publication date 22 February 2019

Published in Operations Research Letters (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programmingfixed-charge transportation problempseudo-polynomial extended formulationsingle-node flow polytope

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Dynamic programming (90C39) Mixed integer programming (90C11) Transportation, logistics and supply chain management (90B06)

Abstract: We consider a class of fixed-charge transportation problems over graphs. We show that this problem is strongly NP-hard, but solvable in pseudo-polynomial time over trees using dynamic programming. We also show that the LP formulation associated to the dynamic program can be obtained from extended formulations of single-node flow polytopes. Given these results, we present a unary expansion-based formulation for general graphs that is computationally advantageous when compared to a standard formulation, even if its LP relaxation is not stronger.

Recommendations

• Fixed-charge transportation on a path: optimization, LP formulations and separation
• Fixed-charge transportation on a path: linear programming formulations
• Fixed-charge transportation problem: facets of the projection polyhedron
• LP extreme points and cuts for the fixed-charge network design problem
• A set covering reformulation of the pure fixed charge transportation problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Cutting planes from extended LP formulations
• Fixed-charge transportation on a path: optimization, LP formulations and separation
• Fixed-charge transportation problem: facets of the projection polyhedron
• Lifted flow cover inequalities for mixed 0-1 integer programs
• Polyhedral Characterization of Discrete Dynamic Programming
• Solving Mixed Integer Programming Problems Using Automatic Reformulation
• Valid Linear Inequalities for Fixed Charge Problems

Cited in

(5)

• Fixed-charge transportation on a path: linear programming formulations
• Fixed-charge transportation on a path: optimization, LP formulations and separation
• An uncertain two-echelon fixed charge transportation problem
• Binary extended formulations of polyhedral mixed-integer sets
• Fixed-charge transportation problem: facets of the projection polyhedron

This page was built for publication: Fixed-charge transportation problems on trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1728231)