Tightening simple mixed-integer sets with guaranteed bounds

DOI10.1007/S10107-010-0435-XMaRDI QIDQ431027zbMATH OpenOpenAlexFDO

Authors Benjamin McClosky, Daniel Bienstock

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

approximation algorithmscombinatorial optimizationextended formulations

Mathematics Subject Classification ID

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

Review text

This paper shows that using combinatorial disjunctions, that depend on the problem structure, leads to tight, polynomially large formulations for 0/1 knapsack sets and some fixed-charge network flow sets.

Cites work

• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Approximate extended formulations
• Approximate fixed-rank closures of covering problems
• Approximate formulations for 0-1 knapsack sets
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• Geometric algorithms and combinatorial optimization
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3545380 (Why is no real title available?)
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• Lifted flow cover inequalities for mixed 0-1 integer programs
• On disjunctive cuts for combinatorial optimization
• On the matrix-cut rank of polyhedra.
• Primal-Dual Schema for Capacitated Covering Problems
• Subset Algebra Lift Operators for 0-1 Integer Programming
• Tree-width and the Sherali-Adams operator
• Valid Linear Inequalities for Fixed Charge Problems
• When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?

Cited in

(7)

• Greedy algorithms for the single-demand facility location problem
• On the existence of compact $\varepsilon$-approximated formulations for knapsack in the original space
• Small extended formulation for knapsack cover inequalities from monotone circuits
• A Polynomial-Time Algorithm to Check Closedness of Simple Second Order Mixed-Integer Sets
• Maximum utility product pricing models and algorithms based on reservation price
• Extended formulations in combinatorial optimization
• Extended formulations in combinatorial optimization

This page was built for publication: Tightening simple mixed-integer sets with guaranteed bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q431027)