2022/01/09 by Jozefiak, Adam, Shepherd, F. Bruce, Weninger, Noah
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2201.02914
We introduce a natural knapsack intersection hierarchy for strengthening linear programming relaxations of packing integer programs, i.e., max\wTx:x∈ P∩\0,1\n\ where P=\x∈[0,1]n:Ax ≤ b\ and A,b,w≥0. The tth level Pt 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 Pm is the integer hull of P and P1 corresponds to adding cuts for each associated single-row knapsack problem. Thus, even separating over P1 is NP-hard. However, for fixed t and any ε>0, results of Pritchard imply there is a polytime (1+ε)-approximation for Pt. 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 Pt is O(n/t) and give examples where the gap is Ω(n/t). We then examine the stronger formulation Prank where all rank constraints are added. For Prankt, our best lower bound drops to Ω(1/c) at level t=nc 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 nc.