UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Approximate extended formulations for multidimensional knapsack and the unsplittable flow problem on trees Weninger, Noah J. B.


In this thesis, we study the Multidimensional Knapsack Problem (MKP) and two closely related special cases: the Unsplittable Flow Problem on Trees (UFPT), and the Unsplittable Flow Problem on Paths (UFPP). For these problems, when the natural integer programming formulation is relaxed to a linear program, the integrality gap is O(n). Previous work on UFPT and UFPP has established that the addition of rank constraints to the linear program can be effective in some cases at reducing the integrality gap. However, Friggstad and Gao proved that even with all rank constraints added, the integrality gap of UFPT is Ω(√(log n)). Faenza and Sanità showed that a formulation for these problems which approximates the integer hull arbitrarily well must either have exponentially many facets or be described as an extended formulation (i.e., described in a higher dimensional space). We are interested in polynomially sized formulations, so we focus our study on extended formulations. Our first contribution is a greedy algorithm which finds an optimal solution to the linear programming relaxation for the special case of UFPT where all requests share a common endpoint. We apply this to tighten the analysis of hard instances described in the literature. Following this, we describe two approximate extended formulations for MKP using disjunctive programming. The first is a formulation which improves upon the integrality gap of the linear relaxation using only a small number of extra variables and constraints. The second is a polyhedral (1 - ε)-approximate extended formulation for MKP for any 0 < ε ≤ 1, which was originally given by Pritchard. We then introduce a new hierarchy of strengthened formulations for MKP, which we study in the context of UFPT. The strengthened formulations are NP-Hard to separate over, but they can be (1 - ε)-approximated using the aforementioned result. We conclude by evaluating the strength of this hierarchy when applied to the known hard instances from the literature. Our results suggest that this hierarchy may be most useful in conjunction with the rank constraints, but open questions remain.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International