Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms

Jean Philippe P. Richard, Ismael R. De Farias, George L. Nemhauser

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

We study the mixed 0-1 knapsack polytope, which is defined by a single knapsack constraint that contains 0-1 and bounded continuous variables. We develop a lifting theory for the continuous variables. In particular, we present a pseudo-polynomial algorithm for the sequential lifting of the continuous variables. We introduce the concept of superlinear inequalities and show that our lifting scheme can be significantly simplified for them. Finally, we show that superlinearity results can be generalized to nonsuperlinear inequalities when the coefficients of the continuous variables lifted are large.

Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization - 9th International IPCO 2002 Conference, Proceedings
EditorsWilliam J. Cook, Andreas S. Schulz
PublisherSpringer-Verlag
Pages161-175
Number of pages15
ISBN (Print)9783540478676
DOIs
StatePublished - 2002
Event9th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2002 - Cambridge, MA, United States
Duration: May 27 2002May 29 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2337 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2002
Country/TerritoryUnited States
CityCambridge, MA
Period05/27/0205/29/02

Fingerprint

Dive into the research topics of 'Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms'. Together they form a unique fingerprint.

Cite this