Tightening simple mixed-integer sets with guaranteed bounds (Q431027): Difference between revisions

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.

0 references

reviewed by

Erwin Pesch

0 references

zbMATH Keywords

combinatorial optimization

0 references

extended formulations

0 references

approximation algorithms

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/s10107-010-0435-x

0 references

cites work

Q4120330

0 references

A lift-and-project cutting plane algorithm for mixed 0-1 programs

0 references

Approximate formulations for 0-1 knapsack sets

0 references

Tree-width and the Sherali-Adams operator

0 references

Subset Algebra Lift Operators for 0-1 Integer Programming

0 references

Approximate fixed-rank closures of covering problems

0 references

Primal-Dual Schema for Capacitated Covering Problems

0 references

Q4952606

0 references

On the Matrix-Cut Rank of Polyhedra

0 references

Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses

0 references

When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?

0 references

Geometric algorithms and combinatorial optimization

0 references

Lifted flow cover inequalities for mixed \(0\)-\(1\) integer programs

0 references

On disjunctive cuts for combinatorial optimization

0 references

Q4040221

0 references

Valid Linear Inequalities for Fixed Charge Problems

0 references

A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems

0 references

Approximate extended formulations

0 references

Identifiers

zbMATH Open document ID

1274.90294

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

10.1007/S10107-010-0435-X

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:431027

@@ Property / DOI @@
-.1007/s10107-010-0435-x
@@ Property / DOI: 10.1007/s10107-010-0435-x / rank @@
-Normal rank
@@ Property / author @@
-Bienstock, Daniel
@@ Property / author: Bienstock, Daniel / rank @@
-Normal rank
@@ Property / author @@
+Bienstock, Daniel
@@ Property / author: Bienstock, Daniel / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/s10107-010-0435-x
+Normal rank
@@ Property / OpenAlex ID @@
+W2167525805
@@ Property / OpenAlex ID: W2167525805 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4120330
@@ Property / cites work: Q4120330 / rank @@
+Normal rank
@@ Property / cites work @@
+A lift-and-project cutting plane algorithm for mixed 0-1 programs
+Normal rank
@@ Property / cites work @@
+Approximate formulations for 0-1 knapsack sets
@@ Property / cites work: Approximate formulations for 0-1 knapsack sets / rank @@
+Normal rank
@@ Property / cites work @@
+Tree-width and the Sherali-Adams operator
@@ Property / cites work: Tree-width and the Sherali-Adams operator / rank @@
+Normal rank
@@ Property / cites work @@
+Subset Algebra Lift Operators for 0-1 Integer Programming
+Normal rank
@@ Property / cites work @@
+Approximate fixed-rank closures of covering problems
+Normal rank
@@ Property / cites work @@
+Primal-Dual Schema for Capacitated Covering Problems
+Normal rank
@@ Property / cites work @@
+Q4952606
@@ Property / cites work: Q4952606 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Matrix-Cut Rank of Polyhedra
@@ Property / cites work: On the Matrix-Cut Rank of Polyhedra / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
+Normal rank
@@ Property / cites work @@
+When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
+Normal rank
@@ Property / cites work @@
+Geometric algorithms and combinatorial optimization
+Normal rank
@@ Property / cites work @@
+Lifted flow cover inequalities for mixed \(0\)-\(1\) integer programs
+Normal rank
@@ Property / cites work @@
+On disjunctive cuts for combinatorial optimization
+Normal rank
@@ Property / cites work @@
+Q4040221
@@ Property / cites work: Q4040221 / rank @@
+Normal rank
@@ Property / cites work @@
+Valid Linear Inequalities for Fixed Charge Problems
+Normal rank
@@ Property / cites work @@
+A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
+Normal rank
@@ Property / cites work @@
+Approximate extended formulations
@@ Property / cites work: Approximate extended formulations / rank @@
+Normal rank
@@ Property / DOI @@
+.1007/S10107-010-0435-X
@@ Property / DOI: 10.1007/S10107-010-0435-X / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:431027