Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms |
| |
| Authors: | J-PP Richard IR de Farias Jr GL Nemhauser |
| |
| Institution: | (1) School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205, USA;(2) Center for Operations Research and Econometrics, 34 Voie du Roman Pays, 1348 Louvain-La-Neuve, Belgium;(3) School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205, USA |
| |
| 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 and we discuss its practical use.This research was supported by NSF grants DMI-0100020 and DMI-0121495Mathematics Subject Classification (2000): 90C11, 90C27 |
| |
| Keywords: | 0-1 mixed integer programming polyhedral theory lifting |
| 本文献已被 SpringerLink 等数据库收录！ |
|
