Tightening simple mixed-integer sets with guaranteed bounds
type: Item
instance of: scholarly article
title: Tightening simple mixed-integer sets with guaranteed bounds
zbMATH Open document ID: 1274.90294
author: Benjamin McClosky
author: Daniel Bienstock
published in: Mathematical Programming. Series A. Series B
publication date: 2012-06-26T00:00:00Z
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.
reviewed by: Erwin Pesch
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 6050455
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: extended formulations
zbMATH Keywords: approximation algorithms
MaRDI profile type: Publication
full work available at URL: s10107-010-0435-x
OpenAlex ID: W2167525805
cites work: Q4120330
cites work: A lift-and-project cutting plane algorithm for mixed 0-1 programs
cites work: Approximate formulations for 0-1 knapsack sets
cites work: Tree-width and the Sherali-Adams operator
cites work: Subset Algebra Lift Operators for 0-1 Integer Programming
cites work: Approximate fixed-rank closures of covering problems
cites work: Primal-Dual Schema for Capacitated Covering Problems
cites work: Q4952606
cites work: On the matrix-cut rank of polyhedra.
cites work: Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
cites work: When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
cites work: Geometric algorithms and combinatorial optimization
cites work: Lifted flow cover inequalities for mixed \(0\)-\(1\) integer programs
cites work: On disjunctive cuts for combinatorial optimization
cites work: Q4040221
cites work: Valid Linear Inequalities for Fixed Charge Problems
cites work: A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
cites work: Approximate extended formulations
DOI: 10.1007/S10107-010-0435-X
description: scientific article; zbMATH DE number 6050455