×

zbMATH — the first resource for mathematics

A lift-and-project cutting plane algorithm for mixed 0-1 programs. (English) Zbl 0796.90041
The paper is organized as follows. An iterated lifting/projecting procedure for obtaining the convex hull of the feasible set of mixed 0-1 linear program is suggested. In each iteration, the set is relaxed through nonlinearization, then linearized by using a known technique for linearization of quadratic function in 0-1 variables and finally projected into the space of the original variables. The advantage of the procedure over existing ones is in the less number of variables needed in the lifting phase. It is then shown that the procedure is equivalent to the sequential convexification procedure for facial disjunctive programs, introduced by Balas earlier. The next section discuss cutting plane algorithms for mixed 0-1 programs based on sequential convexification procedure. A specialized cutting plane algorithm is proposed and its finiteness is proved. The last section is in fact an extensive and very informative report on the computational behaviour of the algorithm with the primary intention to analyze and compare cuts on their own merit.
Reviewer: N.I.Yanev (Sofia)

MSC:
90C11 Mixed integer programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] E. Balas, ”Intersection cuts – A new type of cutting planes for integer programming,”Operations Research 19 (1971) 19–39. · Zbl 0219.90035
[2] E. Balas, ”Intersection cuts for disjunctive constraints,” MSRR No. 330, Carnegie Mellon University (Pittsburgh, PA, 1974).
[3] E. Balas, ”Disjunctive Programming: Properties of the convex hull of feasible points,” MSRR No. 348, Carnegie Mellon University (Pittsburgh, PA, 1974). · Zbl 0921.90118
[4] E. Balas, ”Disjunctive Programming,”Annals of Discrete Mathematics 5 (1979) 3–51. · Zbl 0409.90061
[5] E. Balas, ”Disjunctive Programming and a hierarchy of relaxations for discrete optimization problems,”SIAM Journal on Algebraic and Discrete Methods 6 (1985) 466–486. · Zbl 0592.90070
[6] E. Balas and R. Jeroslow, ”Strengthening cuts for mixed integer programs,”European Journal of Operations Research 4(4) (1980) 224–234. · Zbl 0439.90064
[7] E. Balas and C. Martin, ”Pivot and complement – A heuristic for 0–1 programming,”Management Science 26(1) (1980) 86–96. · Zbl 0442.90060
[8] E. Balas, J. Tama and J. Tind, ”Sequential convexification in reverse convex and disjunctive programming,”Mathematical Programming 44 (1989) 337–350. · Zbl 0683.90063
[9] B. Bouvier and G. Messoumian, ”Programmes linéaires en variables bivalentes – Algorithme de Balas,” Université de Grenoble (Grenoble, France, 1965).
[10] C. Carpaneto and P. Toth, ”Some new branching and bounding criteria for the asymmetric traveling salesman problem,”Management Science 26(7) (1980) 736–743. · Zbl 0445.90089
[11] H. Crowder, E. Johnson, M. Padberg, ”Solving large-scale zero–one linear programming problems,”Operations Research 31(5) (1983) 803–834. · Zbl 0576.90065
[12] M. Fischetti and P. Toth, ”An additive bounding procedure for the asymmetric traveling salesman problem,”Mathematical Programming 53(2) (1992) 173–197. · Zbl 0773.90082
[13] F. Glover, ”Convexity cuts and cut search,”Operations Research 21 (1973) 123–134. · Zbl 0263.90020
[14] R. Gomory, ”An algorithm for the mixed integer problem,” RM-2597, The Rand Corporation (Santa Monica, CA, 1960). · Zbl 0095.14502
[15] R. Jeroslow, ”A cutting plane game for facial disjunctive programs,”SIAM Journal on Control and Optimization 18(3) (1980) 264–280. · Zbl 0434.90063
[16] C. Lemke and K. Spielberg, ”A capital budgeting heuristic algorithm using exchange operations,”AIEE Transactions 6 (1974) 143–150.
[17] L. Lovász and A. Schrijver, ”Cones of matrices and set-functions and 0–1 optimization,”SIAM Journal on Optimization 1(2) (1991) 166–190. · Zbl 0754.90039
[18] M. Padberg and G. Rinaldi, ”Optimization of a 537-city TSP by branch and cut,”Operations Research Letters 6 (1987) 1–8. · Zbl 0618.90082
[19] C. Petersen, ”Computational experience with variants of the Balas algorithm applied to the selection of R&D projects,”Management Science 13 (1967) 736–750.
[20] B. Repetto, personal communication (1991).
[21] H. Salkin,Integer Programming (Addison-Wesley, Reading, MA, 1975).
[22] H. Sherali and W. Adams, ”A hierarchy of relaxations and convex hull representations for mixedinteger zero–one programming problems,” Technical Report, Virginia Tech (Blacksburg, VA, 1989).
[23] H. Sherali and W. Adams, ”A hierarchy of relaxations between the continuous and convex hull representations for zero–one programming problems,”SIAM Journal on Discrete Mathematics 3(3) (1990) 411–430. · Zbl 0712.90050
[24] T. Van Roy and L. Wolsey, ”Solving mixed integer programming problems using automatic reformulation,”Operations Research 35(1) (1987) 45–47. · Zbl 0614.90082
[25] W. White, ”On Gomory’s mixed integer algorithm,” Senior Thesis, Department of Mathematics, Princeton University (Princeton, NJ, 1961).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.