Back to search

University of British Columbia

Approximate extended formulations for multidimensional knapsack and the unsplittable flow problem on trees

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Weninger, Noah J. B.
Contributors dc:contributor
  • Shepherd, F. Bruce (Frederick Bruce)

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/79478

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Weninger, Noah J. B.. Approximate extended formulations for multidimensional knapsack and the unsplittable flow problem on trees. master's thesis, University of British Columbia, 2021. http://hdl.handle.net/2429/79478