Lifting, Mixed-Integer Rounding, Single Node Flow Sets
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 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, empha-
sizing 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, construc-
tion of a mixed integer rounding inequality, and superadditive lifting. It is applied
to several generalizations of the 0-1 single node flow set.
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
Atamturk A (2001) Flow pack facets of the single node fixed-charge flow polytope. Operations Research Letters 29: 107-114.
AtamtürkA (2002) On the facets of single-constraint mixed-integer sets. Research Report Revised June, Department of Industrial and Operations Research, University of California at Berkeley.
Atamtürk A, Munoz (2002) A study of the lot-sizing polytope. Research Report BCOL. 02. 01, Department of Industrial and Operations Research, University of California at Berkeley.
AtamtürkA, Nemhauser GL, SavelsberghMWP(2001)Valid inequalities for problems with additive variable upper bounds. Mathematical Programming 91: 145-162.
Balas E (1975)Atime indexed formulation of non-preemptive single machine scheduling problems. Mathematical Programming 8: 146-164.
Ceria S, Cordier C, Marchand H, Wolsey LA (1998) Cutting planes for integer programs with general integer variables. Mathematical Programming 81: 201-214.
Crowder H, Johnson EL, Padberg MW (1963) Solving large scale zero-one linear programming problems. Operations Research 31: 803-834.
Goemans MX (1989) Valid inequalities and separation for mixed 0-1 constraints with variable upper bounds. Operations Research Letters 8: 315-322.
Gomory RE (1960) An algorithm for the mixed integer problem. Research Report RM-2597. The Rand Corporation.
Gu Z, Nemhauser GL, Savelsbergh MWP (2000) Sequence independent lifting in mixed integer programing. Journal of Combinatorial Optimization 4: 109-129.
Hammer PL, Johnson EL, Peled UN (1975) Facets of regular 0-1 polytopes. Mathematical Programming 8: 179-206.
JeroslowRG(1979) An introduction to the theory of cutting planes. Annals of Discrete Mathematics 5: 71-95.
Johnson EL (1973) Cyclic groups, cutting planes and shortest paths. In: Hu TC, Robinson S (eds) Mathematical Programming. Academic Press, pp 185-211.
Marchand H, Wolsey LA (1999) The 0-1 knapsack problem with a single continous variable. Mathematical Programming 85: 15-33.
Marchand H, Wolsey LA(2001) Aggregation and mixed integer rounding to solve mips. Operations Research 49: 363-371.
Miller A, Nemhauser GL, Savelsbergh MWP (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 GL, Savelsbergh MWP (2003b) On the polyhedral structure of a multi-item production planning model with setup times. Mathematical Programming B 94: 375-406.
Nemhauser GL, Wolsey LA (1988) Integer and Combinatorial Optimization. Wiley, NewYork.
Nemhauser GL, Wolsey LA (1990) A recursive procedure for generating all cuts for 0-1 mixed integer programs. Mathematical Programming 46: 379-390.
OostenM(1996)Apolyhedral approach to grouping problems. PhD thesis, University of Maastricht.
Padberg M (1973) On the facial structure of set packing polyhedra. Mathematical Programming 5: 199-215.
Padberg MW, Van Roy TJ, Wolsey LA (1985) Valid inequalities for fixed charge problems. Mathematical Programming 33: 842-861.
Richard J-PP, de Farias IR, Nemhauser GL (2002a) Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms. Research Report 2002, School of Industrial and Systems Engineering, Georgia Institute of Technology.
Richard J-PP, de Farias IR, Nemhauser GL (2002b) Lifted inequalities for 0-1 mixed integer programming: Superlinear lifting. Research Report 2002, School of Industrial and Systems Engineering, Georgia Institute of Technology.
Van Roy TJ, Wolsey LA (1986) Valid inequalities for mixed 0-1 programs. Discrete Applied Mathematics 14: 199-213.
Van Roy TJ, Wolsey LA (1987) Solving mixed 0-1 programs by automatic reformulation. Operations Research 35: 45-57.
Stallaert JIA (1997) The complementary class of generalized flow cover inequalities. Discrete Applied Mathematics 77: 73-80.
Wolsey LA (1975) Faces for linear inequalities in 0-1 variables. Mathematical Programming 8: 165-178.
Wolsey LA (1976) Facets and strong valid inequalities for integer programs. Operations Research 24: 367-372.
Wolsey LA (1977) Valid inequalities and superadditivity for 0-1 integer programs. Mathematics of Operations Research 2: 66-77.
Wolsey LA (1989) Submodularity and valid inequalities in capacitated fixed charge networks. Operations Research Letters 8: 119-124.
Wolsey LA (1990) Valid inequalities for mixed integer programs with generalised upper bound constraints. Discrete Applied Mathematics 25: 251-261.
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.