zbMATH — the first resource for mathematics

Computational study of a family of mixed-integer quadratic programming problems. (English) Zbl 0855.90090
Summary: We present computational experience with a branch-and-cut algorithm to solve quadratic programming problems where there is an upper bound on the number of positive variables. Such problems arise in financial applications. The algorithm solves the largest real-life problems in a few minutes of run-time.

90C11 Mixed integer programming
90C20 Quadratic programming
65Y05 Parallel numerical computation
Full Text: DOI
[1] E. Balas, Intersection cuts–a new type of cutting planes for integer programming.Operations Research 19 (1971) 19–39. · Zbl 0219.90035 · doi:10.1287/opre.19.1.19
[2] E. Balas, S. Ceria and G. Cornuéjols. A lift-and-project cutting plane algorithm for mixed 0–1 programs,Mathematical Programming 58 (1993) 295–324. · Zbl 0796.90041 · doi:10.1007/BF01581273
[3] E. Balas, S. Ceria and G. Cornuéjols. Mixed 0–1 programming by lift-and-project in a branch-and-cut framework,Management Science (to appear). · Zbl 0880.90105
[4] W. Cook, personal communication.
[5] R. Bixby, personal communication.
[6] R. Bixby, W.J. Cook, A. Cox and E. Lee, Parallel mixed-integer programming, manuscript (1994). · Zbl 0937.90073
[7] Cplex Optimization, Inc.
[8] J. Eckstein, Parallel branch-and-bound algorithms for general mixed integer programming on the CM-5,SIAM Journal on Optimization 4 (1994) 794–814. · Zbl 0819.90063 · doi:10.1137/0804046
[9] R. Fletcher,Practical Methods of Optimization, Vol. 2 (Wiley, 1981). · Zbl 0474.65043
[10] H. Konno and K. Suzuki, A fast algorithm for solving large scale mean-variance models by compact factorization of covariance matrices, Report IHSS 91-32, Institute of Human and Social Sciences, Tokyo Institute of Technology (1991). · Zbl 0763.90004
[11] G.L. Nemhauser and L.A. Wolsey,Integer and Combinatorial Optimization (Wiley, New York, 1988). · Zbl 0652.90067
[12] D.G. Luenberger,Linear and Nonlinear Programming (Addison Wesley, 1984). · Zbl 0571.90051
[13] A.F. Perold, Large-scale protfolio optimization,Management Science 30 (1984) 1143–1160. · Zbl 0548.90008 · doi:10.1287/mnsc.30.10.1143
[14] M. Savelsbergh, personal communication (1995).
[15] L.A. Wolsey, personal communication.
[16] R.J. Vanderbei and T.J. Carpenter, Symmetric indefinite systems for interior point methods,Mathematical Programming 58 (1993) 1–32. · Zbl 0791.90033 · doi:10.1007/BF01581257
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.