×

zbMATH — the first resource for mathematics

A new technique for generating quadratic programming test problems. (English) Zbl 0795.90047
Summary: This paper describes a new technique for generating convex, strictly concave and indefinite (bilinear or not) quadratic programming problems. These problems have a number of properties that make them useful for test purposes. For example, strictly concave quadratic problems with their global maximum in the interior of the feasible domain and with an exponential number of local minima with distinct function values and indefinite and jointly constrained bilinear problems with nonextreme global minima, can be generated.
Unlike most existing methods our construction technique does not require the solution of any subproblems or systems of equations. In addition, the authors know of no other technique for generating jointly constrained bilinear programming problems.

MSC:
90C20 Quadratic programming
90C06 Large-scale problems in mathematical programming
Software:
MPGENR
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] F.A. Al-Khayyal, ”Jointly constrained bilinear programs and related problems: an overview,”Computers and Mathematics with Applications 19 (1990) 53–62. · Zbl 0706.90074 · doi:10.1016/0898-1221(90)90148-D
[2] R.H. Bartels and N. Mahdavi-Amiri, ”On generating test problems for nonlinear programming algorithms,”SIAM Journal on Scientific and Statistical Computing 7 (1986) 769–798. · Zbl 0609.65044 · doi:10.1137/0907052
[3] P.H. Calamai and L. Vicente, ”Generating quadratic bilevel programming test problems,” to appear in:ACM Transaction on Mathematical Software. · Zbl 0888.65068
[4] H.P. Crowder, R.S. Dembo and J.M. Mulvey, ”Reporting computational experiments in mathematical programming,”Mathematical Programming 15 (1978) 316–329. · Zbl 0389.65031 · doi:10.1007/BF01609036
[5] H.P. Crowder, R.S. Dembo and J.M. Mulvey, ”On reporting computational experiments with mathematical software,”ACM Transactions on Mathematical Software 5 (1979) 193–203. · doi:10.1145/355826.355833
[6] C.A. Floudas and P.M. Pardalos, ”A collection of test problems for constrained global optimization,”Lecture Notes in Computer Science No. 455 (Springer, Berlin, 1990). · Zbl 0718.90054
[7] W.W. Hager, P.M. Pardalos, I.M. Roussos and H.D. Sahinoglou, ”Active constraints, indefinite quadratic test problems, and complexity,”Journal of Optimization Theory and Applications 68 (1991) 499–511. · Zbl 0697.90059 · doi:10.1007/BF00940067
[8] J.J. Júdice and A.M. Faustino, ”A computational analysis of LCP methods for bilinear and concave quadratic programming,”Computers and Operations Research 18 (1991) 645–654. · Zbl 0741.90050 · doi:10.1016/0305-0548(91)90002-9
[9] B. Kalantari, ”Construction of difficulty linearly constrained concave minimization problems,”Operations Research 33 (1985) 222–227. · Zbl 0569.90067 · doi:10.1287/opre.33.1.222
[10] B. Kalantari, ”Quadratic functions with exponential number of local maxima,”Operations Research Letters 5 (1986) 47–49. · Zbl 0597.90067 · doi:10.1016/0167-6377(86)90100-8
[11] B. Kalantari and J.B. Rosen, ”Construction of large-scale global minimum concave quadratic test problems,”Journal of Optimization Theory and Applications 48 (1986) 303–313. · Zbl 0559.90066 · doi:10.1007/BF00940675
[12] M.K. Kozlov, S.P. Tarasov and L.G. Hačijan, ”Polynomial solvability of convex quadratic programming,”Soviet Mathematics Doklady 20 (1979) 1108–1111. · Zbl 0434.90071
[13] M. Lenard and M. Minkoff, ”Randomly generated test problems for positive definite quadratic programming,”ACM Transactions on Mathematical Software 10 (1984) 86–96. · Zbl 0545.90081 · doi:10.1145/356068.356075
[14] F.A. Lootsma, ”Comparative performance evaluation, experimental design, and generation of test problems in nonlinear optimization,” in: K. Schittkowski, ed.,Computational Mathematical Programming (Springer, Berlin, 1985) pp. 249–260. · Zbl 0583.90081
[15] W. Michaels and R.P. O’Neill, ”A mathematical program generator MPGENR,”ACM Transactions on Mathematical Software 6 (1980) 31–44. · Zbl 0432.90063 · doi:10.1145/355873.355876
[16] K.G. Murty and S.N. Kabadi, ”Some NP-complete problems in quadratic and linear programming,”Mathematical Programming 39 (1987) 117–129. · Zbl 0637.90078 · doi:10.1007/BF02592948
[17] P.M. Pardalos, ”Construction of test problems in quadratic bivalent programming,”ACM Transactions on Mathematical Software 17 (1991) 74–87. · Zbl 0900.65183 · doi:10.1145/103147.103156
[18] P.M. Pardalos, ”Generation of large-scale quadratic programs for use as global optimization test problems,”ACM Transactions on Mathematical Software 13 (1987) 133–137. · Zbl 0625.90080 · doi:10.1145/328512.328516
[19] P.M. Pardalos and J.B. Rosen, ”Constrained global optimization: algorithms and applications,”Lecture Notes in Computer Science No. 268 (Springer, Berlin, 1987). · Zbl 0638.90064
[20] P.M. Pardalos and G. Schnitger, ”Checking local optimality in constrained quadratic programming is NP-hard,”Operations Research Letters 7 (1988) 33–35. · Zbl 0644.90067 · doi:10.1016/0167-6377(88)90049-1
[21] P.M. Pardalos and S. Vavasis, ”Quadratic programming with one negative eigenvalue is NP-hard,”Journal of Global Optimization 1 (1991) 15–22. · Zbl 0755.90065 · doi:10.1007/BF00120662
[22] A.T. Phillips and J.B. Rosen, ”A parallel algorithm for constrained concave quadratic global minimiation,”Mathematical Programming 42 (1988) 421–448. · Zbl 0665.90071 · doi:10.1007/BF01589415
[23] J.B. Rosen, ”Global minimization of a linearly constrained concave function by partition of feasible domain,”Mathematics of Operations Research 8 (1983) 215–230. · Zbl 0526.90072 · doi:10.1287/moor.8.2.215
[24] J.B. Rosen and S. Suzuki, ”Construction of nonlinear programming test problems,”Communications of the ACM 8 (1965) 113. · doi:10.1145/363744.363779
[25] Y.Y. Sung and J.B. Rosen, ”Global minimum test problem construction,”Mathematical Programming 24 (1982) 353–355. · Zbl 0509.90067 · doi:10.1007/BF01585116
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.