Tightening simple mixed-integer sets with guaranteed bounds

DOI10.1007/s10107-010-0435-xzbMath1274.90294OpenAlexW2167525805MaRDI QIDQ431027

Benjamin McClosky, Bienstock, Daniel

Publication date: 26 June 2012

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-010-0435-x

zbMATH Keywords

combinatorial optimizationapproximation algorithmsextended formulations

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

Greedy algorithms for the single-demand facility location problem, Extended formulations in combinatorial optimization, Maximum utility product pricing models and algorithms based on reservation price, Extended formulations in combinatorial optimization, On the existence of compact $\varepsilon$-approximated formulations for knapsack in the original space, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• Approximate formulations for 0-1 knapsack sets
• Geometric algorithms and combinatorial optimization
• Lifted flow cover inequalities for mixed \(0\)-\(1\) integer programs
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Tree-width and the Sherali-Adams operator
• Approximate extended formulations
• Approximate fixed-rank closures of covering problems
• On the Matrix-Cut Rank of Polyhedra
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Primal-Dual Schema for Capacitated Covering Problems
• Valid Linear Inequalities for Fixed Charge Problems
• Subset Algebra Lift Operators for 0-1 Integer Programming
• When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
• On disjunctive cuts for combinatorial optimization