Fixed-charge transportation problems on trees

Angula, Gustavo;Van Vyve, Mathieu
(2017) Operations Research Letters — Vol. 45, n° 3, p. 275-281 (2017)

Files

Rep2848.pdf
  • Closed Access
  • Adobe PDF
  • 970.76 KB
Request a copy

Details

Authors
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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Angula, G., & Van Vyve, M. (2017). Fixed-charge transportation problems on trees. Operations Research Letters, 45(3), 275-281. https://doi.org/10.1016/j.orl.2017.04.001 (Original work published 2017)