Relations between facets of low- and high-dimensional group problems
type: Item
instance of: scholarly article
title: Relations between facets of low- and high-dimensional group problems
zbMATH Open document ID: 1194.90062
author: Santanu S. Dey
author: Jean-Philippe Richard
published in: Mathematical Programming. Series A. Series B
publication date: 2010-04-15T00:00:00Z
review text: The paper studies facets of low- and high-dimensional infinite group problems which are important for deriving strong cutting planes for mixed integer programs. The authors aim to improve results obtained from one-dimensional groups by considering higher dimensional groups. They first review the group approach and prove some results that are used later to prove that certain functions are facet defining. They then introduce a sequential merge procedure, which allows to derive facets of general high-dimensional infinite group problems from facets of lower-dimensional group problems. Finally, they analyze the types of inequalities that can be generated for low-dimensional group problems using high-dimensional sequential merge group cuts.
reviewed by: Matthias Ehrgott
Mathematics Subject Classification ID: 90C11
Mathematics Subject Classification ID: 90C57
zbMATH DE Number: 5693208
zbMATH Keywords: mixed integer programming
zbMATH Keywords: cutting plane
zbMATH Keywords: valid inequality
zbMATH Keywords: polyhedron
zbMATH Keywords: group problem
MaRDI profile type: Publication
full work available at URL: s10107-009-0303-8
OpenAlex ID: W2031068814
cites work: Non-standard approaches to integer programming
cites work: Q5514010
cites work: Cyclic group and knapsack facets
cites work: MIP: Theory and practice -- closing the gap
cites work: Progress in computational mixed integer programming -- a look back from the other side of the tipping point
cites work: Two-step MIR inequalities for mixed integer programs
cites work: Valid inequalities based on simple mixed-integer sets
cites work: On the strength of Gomory mixed-integer cuts as group cuts
cites work: Sequential-Merge Facets for Two-Dimensional Group Problems
cites work: Facets of Two-Dimensional Infinite Group Problems
cites work: On the extreme inequalities of infinite group problems
cites work: Mixed-integer cuts from cyclic groups
cites work: Some polyhedra related to combinatorial problems
cites work: Some continuous functions related to corner polyhedra
cites work: Some continuous functions related to corner polyhedra, II
cites work: T-space and cutting planes
cites work: Corner polyhedra and their connection with cutting planes
cites work: Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition
cites work: Cutting planes in integer and mixed integer programming
cites work: New inequalities for finite and infinite group problems from approximate lifting
cites work: Valid inequalities for mips and group polyhedra from approximate liftings
DOI: 10.1007/S10107-009-0303-8
description: scientific article; zbMATH DE number 5693208