Mathieu Van Vyve

Fixed-charge transportation problems on trees

  • Gustavo Angulo
  • Mathieu Van Vyve
    • Categories (Mixed) Integer Linear Programming, Network Optimization

    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 … Read more

    A NOTE ON THE EXTENSION COMPLEXITY OF THE KNAPSACK POLYTOPE

  • Sebastian Pokutta
  • Mathieu Van Vyve
    • Categories 0-1 Programming, Integer Programming, Polyhedra Tags , ,

    We show that there are 0-1 and unbounded knapsack polytopes with super-polynomial extension complexity. More specifically, for each n in N we exhibit 0-1 and unbounded knapsack polyhedra in dimension n with extension complexity \Omega(2^\sqrt{n}). ArticleDownload View PDF