Lifting, Superadditivity, Mixed Integer Rounding and Single Node Flow Sets Revisited

Louveaux, Quentin; Wolsey, Laurence A.

doi:10.1007/s10479-007-0171-7

Request a copy

Article (Scientific journals)

Lifting, Superadditivity, Mixed Integer Rounding and Single Node Flow Sets Revisited

Louveaux, Quentin; Wolsey, Laurence A.

2007 • In Annals of Operations Research, 153 (1), p. 47-77

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/442

DOI
10.1007/s10479-007-0171-7

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

LiftingAnnals.pdf

Publisher postprint (564.42 kB)

Request a copy

This paper is a republication of a paper that appeared in 4OR. The published version is available at springer.com

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Lifting; Mixed-Integer Rounding; Superaddivity

Abstract :

[en] 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 com- bining 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 simultane- ously 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 superaddilifting. It is applied to several generalizations of the 0-1 single node flow set.

Disciplines :

Mathematics
Computer science

Author, co-author :

Louveaux, Quentin ; Université catholique de Louvain > CORE, INMA

Wolsey, Laurence A.; Université catholique de Louvain > CORE, INMA

Language :

English

Title :

Lifting, Superadditivity, Mixed Integer Rounding and Single Node Flow Sets Revisited

Publication date :

2007

Journal title :

Annals of Operations Research

ISSN :

0254-5330

eISSN :

1572-9338

Publisher :

Springer Science & Business Media B.V.

Volume :

153

Issue :

Pages :

47-77

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

http://www.springerlink.com/content/r862712566862674/?p=b145aca11e4042f8ab606c4fc8a5d05cπ=4

Funders :

F.R.S.-FNRS - Fonds de la Recherche Scientifique
BELSPO - SPP Politique scientifique - Service Public Fédéral de Programmation Politique scientifique

Available on ORBi :

since 14 August 2008

Statistics

Number of views

124 (13 by ULiège)

Number of downloads

6 (4 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

Atamtürk, A. (2001). Flow pack facets of the single node fixed-charge flow polytope. Operations Research Letters, 29, 107-114.
Atamtürk, A. (2003). On the facets of the mixed-integer knapsack polyhedron. Mathematical Programming, 98, 145-175.
Atamtürk, A., & Munoz (2004). A study of the lot-sizing polytope. Mathematical Programming, 99, 443-465.
Atamtürk, A., Nemhauser, G. L., & Savelsbergh, M. W. P. (2001). Valid inequalities for problems with additive variable upper bounds. Mathematical Programming, 91, 145-162.
Balas, E. (1975). A time indexed formulation of non-preemptive single machine scheduling problems. Mathematical Programming, 8, 146-164.
Ceria, S., Cordier, C., Marchand, H., & Wolsey, L. A. (1998). Cutting planes for integer programs with general integer variables. Mathematical Programming, 81, 201-214.
Crowder, H., Johnson, E. L., & Padberg, M. W. (1963). Solving large scale zero-one linear programming problems. Operations Research, 31, 803-834.
Goemans, M. X. (1989). Valid inequalities and separation for mixed 0-1 constraints with variable upper bounds. Operations Research Letters, 8, 315-322.
Gomory, R. E. (1960). An algorithm for the mixed integer problem. Research report RM-2597, The Rand Corporation.
Gu, Z., Nemhauser, G. L., & Savelsbergh, M. W. P. (1998). Lifted flow cover inequalities for 0-1 integer programs: computation. INFORMS J. of Computing, 10, 427-437.
Gu, Z., Nemhauser, G. L., & Savelsbergh, M. W. P. (1999). Lifted flow cover inequalities for mixed 0-1 integer programs. Mathematical Programming, 85, 439-468.
Gu, Z., Nemhauser, G. L., & Savelsbergh, M. W. P. (2000). Sequence independent lifting in mixed integer programing. Journal of Combinatorial Optimization, 4, 109-129.
Hammer, P. L., Johnson, E. L., & Peled, U. N. (1975). Facets of regular 0-1 polytopes. Mathematical Programming, 8, 179-206.
Jeroslow, R. G. (1979). An introduction to the theory of cutting planes. Annals of Discrete Mathematics, 5, 71-95.
Johnson, E. L. (1973). Cyclic groups, cutting planes and shortest paths. In T. C. Hu, S. Robinson (Eds.), Mathematical Programming (pp. 185-211). New York: Academic.
Louveaux, Q., & Wolsey, L. A. (2003). Lifting, superadditivity, mixed integer rounding and single node flow sets revisited. 40R, 1, 173-208.
Marchand, H., & Wolsey, L. A. (1999). The 0-1 knapsack problem with a single continuous variable. Mathematical Programming, 85, 15-33.
Marchand, H., & Wolsey, L. A. (2001). Aggregation and mixed integer rounding to solve MIPS. Operations Research, 49, 363-371.
Miller, A., Nemhauser, G. L., & Savelsbergh, M. W. P. (2003a). A multi-item production planning model with setup times: algorithms, reformulations, and polyhedral characterizations for a special case. Mathematical Programming B, 95, 71-90.
Miller, A., Nemhauser, G. L., & Savelsbergh, M. W. P. (2003b). On the polyhedral structure of a multi-item production planning model with setup times. Mathematical Programming B, 94, 375-406.
Nemhauser, G. L., & Wolsey, L. A. (1988). Integer and combinatorial optimization. New York: Wiley.
Nemhauser, G. L., & Wolsey, L. A. (1990). A recursive procedure for generating all cuts for 0-1 mixed integer programs. Mathematical Programming, 46, 379-390.
Oosten, M. (1996). A polyhedral approach to grouping problems. Ph.D. thesis, University of Maastricht
Padberg, M. (1973). On the facial structure of set packing polyhedra. Mathematical Programming, 5, 199-215.
Padberg, M. W., Van Roy, T. J., & Wolsey, L. A. (1985). Valid inequalities for fixed charge problems. Mathematical Programming, 33, 842-861.
Richard, J.-P. P., de Parias, I. R., & Nemhauser, G. L. (2002). Lifted inequalities for 0-1 mixed integer programming: basic theory and algorithms. In Lecture notes in computer science, vol. 2337. Proceedings of IPCO 2002 (pp. 161-175). Berlin: Springer.
Richard, J.-P. P., de Parias, I. R., & Nemhauser, G. L. (2003). Lifted inequalities for 0-1 mixed integer programming: superlinear lifting. Mathematical Programming, 98, 115-143.
Stallaert, J. I. A. (1997). The complementary class of generalized flow cover inequalities. Discrete Applied Mathematics, 77, 73-80.
Van Roy, T. J., & Wolsey, L. A. (1986). Valid inequalities for mixed 0-1 programs. Discrete Applied Mathematics, 14, 199-213.
Van Roy, T. J., & Wolsey, L. A. (1987). Solving mixed 0-1 programs by automatic reformulation. Operations Research, 35, 45-57.
Wolsey, L. A. (1975). Faces for linear inequalities in 0-1 variables. Mathematical Programming, 8, 165-178.
Wolsey, L. A. (1976). Facets and strong valid inequalities for integer programs. Operations Research, 24, 367-372.
Wolsey, L. A. (1977). Valid inequalities and superadditivity for 0-1 integer programs. Mathematics of Operations Research, 2, 66-77.
Wolsey, L. A. (1989). Submodularity and valid inequalities in capacitated fixed charge networks. Operations Research Letters, 8, 119-124.
Wolsey, L. A. (1990). Valid inequalities for mixed integer programs with generalised upper bound constraints. Discrete Applied Mathematics, 25, 251-261.