Lifted inequalities for 0-1 mixed integer programming: superlinear lifting
type: Item
instance of: scholarly article
title: Lifted inequalities for 0-1 mixed integer programming: superlinear lifting
zbMATH Open document ID: 1082.90065
published in: Mathematical Programming. Series A. Series B
publication date: 2004-03-11T00:00:00Z
review text: In this paper the authors study the mixed 0-1 knapsack polytope (PS), which is defined by a single knapsack constraint that contains 0-1 and continuous variables. They focus on deriving strong inequalities of PS by sequential lifting of continuous variables fixed at 1 (lifting from 1). Using a former lifting result of their own, they introduce the notion of a superlinear inequality and show that if an inequality is superlinear, then the lifting of continuous variables from 1 is much simpler than in the general case. The superlinearity theory is used next to the lifting of 0-1 cover inequalities to obtain several polynomially computable classes of facets of the mixed 0-1 polytope. The authors show that the superlinearity results can be extended to nonsuperlinear inequalities when the coefficients of the variables fixed at their upper bounds are large.
reviewed by: Daniela Marinescu
Mathematics Subject Classification ID: 90C09
Mathematics Subject Classification ID: 90C11
Mathematics Subject Classification ID: 90C57
zbMATH DE Number: 2055176
zbMATH Keywords: 0-1 mixed integer programming
zbMATH Keywords: polyhedral theory
zbMATH Keywords: superlinear lifting
author: Jean-Philippe Richard
author: I. R. jun. de Farias
author: G. L. Nemhauser
MaRDI profile type: Publication
full work available at URL: s10107-003-0399-1
OpenAlex ID: W1995151259
DOI: 10.1007/S10107-003-0399-1
Recommended article: Q4737525
Recommended article: Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms
Recommended article: Lifted tableaux inequalities for \(0\)-\(1\) mixed-integer programs: a computational study
Recommended article: Lifting for mixed integer programs with variable upper bounds
Recommended article: Lifted flow cover inequalities for mixed \(0\)-\(1\) integer programs
Recommended article: Lifting for conic mixed-integer programming
Recommended article: Q3140425
Recommended article: Lifting convex inequalities for bipartite bilinear programs
Recommended article: Lifted Cover Inequalities for 0-1 Integer Programs: Complexity
description: scientific article; zbMATH DE number 2055176