Abstract
The global minimization of large-scale concave quadratic problems over a bounded polyhedral set using a parallel branch and bound approach is considered. The objective function consists of both a concave part (nonlinear variables) and a strictly linear part, which are coupled by the linear constraints. These large-scale problems are characterized by having the number of linear variables much greater than the number of nonlinear variables. A linear underestimating function to the concave part of the objective is easily constructed and minimized over the feasible domain to get both upper and lower bounds on the global minimum function value. At each minor iteration of the algorithm, the feasible domain is divided into subregions and linear underestimating problems over each subregion are solved in parallel. Branch and bound techniques can then be used to eliminate parts of the feasible domain from consideration and improve the upper and lower bounds. It is shown that the algorithm guarantees that a solution is obtained to within any specified tolerance in a finite number of steps. Computational results are presented for problems with 25 and 50 nonlinear variables and up to 400 linear variables. These results were obtained on a four processor CRAY2 using both sequential and parallel implementations of the algorithm. The average parallel solution time was approximately 15 seconds for problems with 400 linear variables and a relative tolerance of 0.001. For a relative tolerance of 0.1, the average computation time appears to increase only linearly with the number of linear variables.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
V. Chvátal,Linear Programming (W.H. Freeman and Company, New York, 1983).
J.E. Falk and K.R. Hoffman, “A successive underestimation method for concave minimization problems,”Mathematics of Operations Research 1(3) (1976) 251–259.
D.H. Glinsman and J.B. Rosen, “Constrained concave quadratic global minimization by integer programming, “Technical Report 86-37, Computer Science Department, University of Minnesota, Minneapolis, MN (1986).
R. Horst, “An algorithm for nonconvex programming problems,”Mathematical Programming 10 (1976) 312–321.
B. Kalantari, “Large scale global minimization of linearly constrained concave quadratic functions and related problems,” Ph.D. diss., University of Minnesota, Minneapolis, MN (1984).
P.M. Pardalos and J.B. Rosen, “Methods for global concave minimization: A bibliographic survey,”SIAM Review 28(3) (1986) 367–379.
P.M. Pardalos and J.B. Rosen, “Constrained global optimization: Algorithms and applications,” in: G. Goos and J. Hartmans, eds.,Lecture Notes in Computer Science 268, Springer-Verlag, Berlin 1987).
A.T. Phillips and and J.B. Rosen, “Anomalous acceleration in parallel linear programming,” Technical Report UMSI 88/58, University of Minnesota Supercomputer Institute, Computer Science Department, University of Minnesota, Minneapolis, MN (1988).
A.T. Phillips and J.B. Rosen, “A parallel algorithm for constrained concave quadratic global minimization,” Technical Report 87-48, Computer Science Department, University of Minnesota, Minneapolis, MN (1987a).
A.T. Phillips and J.B. Rosen, “A parallel algorithm for constrained concave quadratic global minimization: Computational aspects, “Technical Report UMSI 87/101, University of Minnesota Supercomputer Institute, University of Minnesota, Minneapolis, MN (1987b).
M.J. Quinn,Designing Efficient Algorithms for Parallel Computers (McGraw-Hill, New York, 1987).
J.B. Rosen, “Global minimization of a linearly constrained concave function by partition of feasible domain,”Mathematics of Operations Research 8(2) 1987 215–230.
J.B. Rosen and P.M. Pardalos, “Global minimization of large-scale constrained concave quadratic problems by separable programming,”Mathematical Programming 34(2) (1986) 163–174.
J.B. Rosen and M. van Vliet, “A parallel stochastic method for the constrained concave global minimization problem,” Technical Report 87-31, Computer Science Department, University of Minnesota, Minneapolis, MN (1987).
E. Stuart, J.B. Rosen and A.T. Phillips, “Fast approximate solution to constrained global minimization problems,” Technical Report 88-9, Computer Science Department, University of Minnesota, Minneapolis, MN (1988).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Phillips, A.T., Rosen, J.B. A parallel algorithm for constrained concave quadratic global minimization. Mathematical Programming 42, 421–448 (1988). https://doi.org/10.1007/BF01589415
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01589415