A knapsack intersection hierarchy |
| |
Affiliation: | Department of Computer Science, University of British Columbia, Canada |
| |
Abstract: | We introduce a knapsack intersection hierarchy for strengthening linear programming relaxations of packing integer programs. In level t of the hierarchy, all valid cuts are added for the integer hull of the intersection of all t-row relaxations. This model captures the maximum possible strength of t-row cuts, an approach often used by solvers for small t. We investigate the integrality gap of the strengthened formulations on the all-or-nothing flow problem in trees (also called unsplittable flow on trees). |
| |
Keywords: | Knapsack problem Packing integer program All-or-nothing flow Unsplittable flow Integer programming hierarchies |
本文献已被 ScienceDirect 等数据库收录! |