Pontificia Universidad Católica de Chile Pontificia Universidad Católica de Chile
Ángulo G. and Van Vyve M. (2017)

Fixed-charge transportation problems on trees

Revista : Operations Research Letters
Volumen : 45
Número : 3
Páginas : 275-281
Tipo de publicación : ISI Ir a publicación


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.