## 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, through the lifting of continuous variables fixed at their upper bounds.We introduce the concept of a superlinear inequality and show that, in this case, lifting is significantly simpler than for general inequalities. We use the superlinearity theory, together with the traditional lifting of 0-1 variables, to describe families of facets of the mixed 0-1 knapsack polytope. Finally, we show that superlinearity results can be extended to nonsuperlinear inequalities when the coefficients of the variables fixed at their upper bounds are large.

Original language | English (US) |
---|---|

Pages (from-to) | 115-143 |

Number of pages | 29 |

Journal | Mathematical Programming |

Volume | 98 |

Issue number | 1-3 |

DOIs | |

State | Published - Dec 1 2003 |

Externally published | Yes |

## Keywords

- 0-1 mixed integer programming
- Polyhedral theory
- Superlinear lifting