Cutting planes from extended LP formulations (Q507316): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 4 users not shown) | |||
Property / review text | |||
The authors show that for every 0-1 mixed integer set with \(n\) integer and \(k\) continuous variables, there is an extended LB formulation with \(2n+k-1\) variables whose elementary split closure is integral. The given proof is constructive but it requires an inner description of the LP relaxation. The authors also present computational results on the two-row continuous group relaxation showing the strength of cutting planes derived from extended LP formulations. | |||
Property / review text: The authors show that for every 0-1 mixed integer set with \(n\) integer and \(k\) continuous variables, there is an extended LB formulation with \(2n+k-1\) variables whose elementary split closure is integral. The given proof is constructive but it requires an inner description of the LP relaxation. The authors also present computational results on the two-row continuous group relaxation showing the strength of cutting planes derived from extended LP formulations. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Hans Benker / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C11 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6680629 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
LP formulations | |||
Property / zbMATH Keywords: LP formulations / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
cutting planes | |||
Property / zbMATH Keywords: cutting planes / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
mixed-integer | |||
Property / zbMATH Keywords: mixed-integer / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s10107-016-1005-7 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2335169303 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Mixed-integer sets from two rows of two adjacent simplex bases / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Inequalities from Two Rows of a Simplex Tableau / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Projection, lifting and extended formulation integer and combinatorial optimization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The perfectly matchable subgraph polytope of a bipartite graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5635469 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On cutting-plane proofs in combinatorial optimization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Extended formulations in combinatorial optimization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Chvátal closures for mixed integer programming problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the rank of mixed 0,1 polyhedra. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Mixing Inequalities: Rank, Closure, and Cutting-Plane Proofs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Rank of Disjunctive Cuts / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A note on the split rank of intersection cuts / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Practical Strength of Two-Row Tableau Cuts / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Linear vs. semidefinite extended formulations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Mixing mixed-integer inequalities / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4530626 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Split cuts and extended formulations for mixed integer conic quadratic programming / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Properties of vertex packing and independence system polyhedra / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Matching Polytope has Exponential Extension Complexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 09:52, 13 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Cutting planes from extended LP formulations |
scientific article |
Statements
Cutting planes from extended LP formulations (English)
0 references
3 February 2017
0 references
The authors show that for every 0-1 mixed integer set with \(n\) integer and \(k\) continuous variables, there is an extended LB formulation with \(2n+k-1\) variables whose elementary split closure is integral. The given proof is constructive but it requires an inner description of the LP relaxation. The authors also present computational results on the two-row continuous group relaxation showing the strength of cutting planes derived from extended LP formulations.
0 references
LP formulations
0 references
cutting planes
0 references
mixed-integer
0 references
0 references
0 references