Lifting,superadditivity, mixed integer rounding and single node flow sets revisited |
| |
Authors: | Quentin Louveaux Laurence A Wolsey |
| |
Institution: | (1) CORE and INMA, Université Catholique de Louvain, Louvain-la-Neuve, Belgium;(2) Present address: CORE, Voie du Roman Pays, 1348 Louvain-la-Neuve, Belgium |
| |
Abstract: | In this survey we attempt to give a unified presentation of a variety of results on the lifting of valid inequalities, as
well as a standard procedure combining mixed integer rounding with lifting for the development of strong valid inequalities
for knapsack and single node flow sets. Our hope is that the latter can be used in practice to generate cutting planes for
mixed integer programs.
The survey contains essentially two parts. In the first we present lifting in a very general way, emphasizing superadditive
lifting which allows one to lift simultaneously different sets of variables. In the second, our procedure for generating strong
valid inequalities consists of reduction to a knapsack set with a single continuous variable, construction of a mixed integer
rounding inequality, and superadditive lifting. It is applied to several generalizations of the 0–1 single node flow set.
This paper appeared in 4OR, 1, 173–208 (2003).
The first author is supported by the FNRS as a chercheur qualifié. This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction
initiated by the Belgian State, Prime Minister’s Office, Science Policy Programming. The scientific responsibility is assumed
by the authors. |
| |
Keywords: | Lifting Mixed integer rounding Single node flow sets |
本文献已被 SpringerLink 等数据库收录! |
|