Cutting planes from extended LP formulations
type: Item
instance of: scholarly article
title: Cutting planes from extended LP formulations
zbMATH Open document ID: 1356.90089
author: Merve Bodur
author: Sanjeeb Dash
author: Oktay Günlük
published in: Mathematical Programming. Series A. Series B
publication date: 2017-02-03T00:00:00Z
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.
reviewed by: Hans Benker
Mathematics Subject Classification ID: 90C11
zbMATH DE Number: 6680629
zbMATH Keywords: LP formulations
zbMATH Keywords: cutting planes
zbMATH Keywords: mixed-integer
MaRDI profile type: Publication
full work available at URL: s10107-016-1005-7
OpenAlex ID: W2335169303
cites work: Mixed-integer sets from two rows of two adjacent simplex bases
cites work: Inequalities from Two Rows of a Simplex Tableau
cites work: Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
cites work: Projection, lifting and extended formulation integer and combinatorial optimization
cites work: The perfectly matchable subgraph polytope of a bipartite graph
cites work: Q5635469
cites work: Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
cites work: Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse
cites work: On cutting-plane proofs in combinatorial optimization
cites work: Extended formulations in combinatorial optimization
cites work: Chvátal closures for mixed integer programming problems
cites work: On the rank of mixed 0,1 polyhedra.
cites work: On Mixing Inequalities: Rank, Closure, and Cutting-Plane Proofs
cites work: On the rank of disjunctive cuts
cites work: A note on the split rank of intersection cuts
cites work: On the Practical Strength of Two-Row Tableau Cuts
cites work: Linear vs. semidefinite extended formulations
cites work: Mixing mixed-integer inequalities
cites work: Q4530626
cites work: Split cuts and extended formulations for mixed integer conic quadratic programming
cites work: Properties of vertex packing and independence system polyhedra
cites work: The Matching Polytope has Exponential Extension Complexity
cites work: A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
DOI: 10.1007/S10107-016-1005-7
description: scientific article; zbMATH DE number 6680629