2015/11/25 by Gustavo Angulo, Angulo, Gustavo, Mathieu Van Vyve +1
Computer Science · Mathematics · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.DM #math.OC
paper · pdf · doi:10.48550/arxiv.1511.08179
arxiv created 2015/11/25 · arxiv updated 2015/11/26
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.