A Knapsack Intersection Hierarchy Applied to All-or-Nothing Flow in Trees
share
We introduce a natural knapsack intersection hierarchy for strengthening linear programming relaxations of packing integer programs, i.e., max{w^Tx:x∈ P∩{0,1}^n} where P={x∈[0,1]^n:Ax ≤ b} and A,b,w≥0. The t^th level P^t corresponds to adding cuts associated with the integer hull of the intersection of any t knapsack constraints (rows of the constraint matrix). This model captures the maximum possible strength of "t-row cuts", an approach often used by solvers for small t. If A is m × n, then P^m is the integer hull of P and P^1 corresponds to adding cuts for each associated single-row knapsack problem. Thus, even separating over P^1 is NP-hard. However, for fixed t and any ϵ>0, results of Pritchard imply there is a polytime (1+ϵ)-approximation for P^t. We then investigate the hierarchy's strength in the context of the well-studied all-or-nothing flow problem in trees (also called unsplittable flow on trees). For this problem, we show that the integrality gap of P^t is O(n/t) and give examples where the gap is Ω(n/t). We then examine the stronger formulation P_rank where all rank constraints are added. For P_rank^t, our best lower bound drops to Ω(1/c) at level t=n^c for any c>0. Moreover, on a well-known class of "bad instances" due to Friggstad and Gao, we show that we can achieve this gap; hence a constant integrality gap for these instances is obtained at level n^c.
READ FULL TEXT