Lifted inequalities for 0-1 mixed integer programming: superlinear lifting (Q1424282): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
RedirectionBot (talk | contribs)
Removed claims
Property / author
 
Property / author: Jean-Philippe P. Richard / rank
Normal rank
 
Property / author
 
Property / author: Ismael Regis jun. de Farias / rank
Normal rank
 
Property / author
 
Property / author: Nemhauser, George I. / rank
Normal rank
 

Revision as of 22:26, 9 February 2024

scientific article
Language Label Description Also known as
English
Lifted inequalities for 0-1 mixed integer programming: superlinear lifting
scientific article

    Statements

    Lifted inequalities for 0-1 mixed integer programming: superlinear lifting (English)
    0 references
    11 March 2004
    0 references
    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.
    0 references
    0-1 mixed integer programming
    0 references
    polyhedral theory
    0 references
    superlinear lifting
    0 references

    Identifiers