A knapsack intersection hierarchy

DOI10.1016/j.orl.2022.12.001zbMath1525.90278OpenAlexW4313350206MaRDI QIDQ6161286

Adam Jozefiak, Noah Weninger, F. Bruce Shepherd

Publication date: 27 June 2023

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2022.12.001

zbMATH Keywords

knapsack problemunsplittable flowpacking integer programall-or-nothing flowinteger programming hierarchies

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Chvátal closures for mixed integer programming problems
• On the membership problem for the elementary closure of a polyhedron
• Semidefinite programming relaxations for semialgebraic problems
• Theoretical challenges towards cutting-plane selection
• Polyhedral properties for the intersection of two knapsacks
• Edmonds polytopes and a hierarchy of combinatorial problems
• The All-or-Nothing Multicommodity Flow Problem
• A quasi-PTAS for unsplittable flow on line graphs
• On the Practical Strength of Two-Row Tableau Cuts
• Submodular Unsplittable Flow on Trees
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Multicommodity demand flow in a tree and packing integer programs
• Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
• Solving Large-Scale Zero-One Linear Programming Problems
• Cones of Matrices and Set-Functions and 0–1 Optimization
• To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack
• On Linear Programming Relaxations for Unsplittable Flow in Trees
• A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths

This page was built for publication: A knapsack intersection hierarchy