›› 2012, Vol. 27 ›› Issue (4): 744-753.doi: 10.1007/s11390-012-1260-x

• Regular Papers • Previous Articles     Next Articles

A Parallel Interval Computation Model for Global Optimization with Automatic Load Balancing

Yong Wu1 (吴勇) and Arun Kumar2   

  1. 1. Department of International Business and Asian Studies, Griffith University, QLD 4222, Australia;
    2. School of Aerospace, Mechanical and Manufacturing Engineering, RMIT University, Melbourne, Australia
  • Received:2010-12-10 Revised:2012-02-24 Online:2012-07-05 Published:2012-07-05

In this paper, we propose a decentralized parallel computation model for global optimization using interval analysis. The model is adaptive to any number of processors and the workload is automatically and evenly distributed among all processors by alternative message passing. The problems received by each processor are processed based on their local dominance properties, which avoids unnecessary interval evaluations. Further, the problem is treated as a whole at the beginning of computation so that no initial decomposition scheme is required. Numerical experiments indicate that the model works well and is stable with different number of parallel processors, distributes the load evenly among the processors, and provides an impressive speedup, especially when the problem is time-consuming to solve.

[1] Hansen P, Jaumard B. Lipschitz optimization. In Handbookof Global Optimization, Horst R, Pardalos P M (eds.), Dordrecht:Kluwer Academic Pulishers, 1995, pp.407-493.

[2] Özdamar L, Demirhan M B. Experiments with new stochasticglobal optimization search techniques. Computers and OperationsResearch, 2000, 27(9): 841-865.

[3] Hansen E. Global Optimization Using Interval Analysis. New York: Marcel Dekker, 1992.

[4] Kearfott R B. Rigorous Global Search: Continuous Problems.Dordrecht: Kluwer Academic Publisher, 1996.

[5] Pintér J. Branch and bound algorithms for solving global optimizationproblems with lipschitzian structure. Optimization,1988, 19: 101-110.

[6] Tang Z B. Adaptive partitioned random search to global optimization.IEEE Transactions on Automatic Control, 1994,39(11): 2235-2244.

[7] Ratschek H, Rokne J. Interval methods. In Handbook ofGlobal Optimization, Horst R, Pardalos P M (eds.), KluwerAcademic Publishers, 1995, pp.751-828.

[8] Skillicorn D B, Talia D. Models and languages for parallelcomputation. ACM Computing Surveys, 1998, 30(2): 123-169.

[9] Skelboe S. Computation of rational interval functions. BITNumerical Mathematics, 1974, 14(1): 87-95.

[10] Hansen E, Sengupta S. Global constrained optimization usinginterval analysis. In Interval Mathematics, Nickel K (ed.),Berlin: Springer-Verlag, 1980, pp.25-47.

[11] Moore R E. Interval Analysis. Engelwood Cliffs: PrenticeHall, 1966.

[12] Ratz D, Csendes T. On the selection of subdivision directionsin interval branch-and-bound methods for global optimization.Journal of Global Optimization, 1995, 7(2): 183-207.

[13] Casado L G, García I, Csendes T. A heuristic rejection criterionin interval global optimization algorithms. BIT NumericalMathematics, 2001, 41(4): 683-692.

[14] Casado L G, Martínez J A, García I. Experiments with a newselection criterion in a fast interval optimization algorithm.Journal of Global Optimization, 2001, 19(3): 247-264.

[15] Csendes T. New subinterval selection criteria for intervalglobal optimization. Journal of Global Optimization, 2001,19(3): 307-327.

[16] Pedamallu C S, Özdamar L, Csendes T, Vinkó T. Efficient intervalpartitioning for constrained global optimization. Journalof Global Optimization, 2008, 42(3): 369-384.

[17] Sun M. A fast memoryless interval-based algorithm for globaloptimization. Journal of Global Optimization, 2010, 47(2):247-271.

[18] Henriksen T, Madsen K. Use of a depth-first strategy in parallelglobal optimization. Technical Report 92-10, Institute ofNumerical Analysis, Technical University of Denmark, Lyngby,1992.

[19] Eriksson J, Lindstrom P. A parallel interval method implementationfor global optimization using dynamic load balancing.Reliable Computing, 1995, 1(1): 77-91.

[20] Benyoub A, Daoudi E M. Parallelization of the continuousglobal optimization problem with inequality constraints byusing interval arithmetic. In Proc. the 9th InternationalConference on High-Performance Computing and Networking,June 2001, pp.595-602.

[21] Ibraev S. A new parallel method for verified global optimization

[PhD Thesis]. University of Wuppertal, Germany, 2001.

[22] Gau C Y, Stadtherr M A. Parallel interval-Newton using messagepassing: Dynamic load balancing strategies. In Proc.the 2001 ACM/IEEE Conference on Supercomputing, Denver,Colorado, Nov. 2001, Article No.23.

[23] Berner S. Parallel methods for verified global optimizationpractice and theory. Journal of Global Optimization, 1996,9(1): 1-22.

[24] Message Passing Interface Forum. MPI: The message passinginterface standard. 1994, http://www.mpi-forum.org, 2011.

[25] Wu Y, Kumar A. Interval subdivision strategies for constrainedoptimization. In Proc. the International Conferenceof Numerical Analysis and Applied Mathematics, Sept. 2005,pp.593-596.

[26] Ratschek H, Rokne J. New Computer Methods for GlobalOptimization. Ellis Horwood Limited, 1988.

[27] Floudas C A, Pardalos P M, Adjiman C S, Esposito W R,Gümüs Z H, Harding S T, Klepeis J L, Meyer C A, SchweigerC A. Handbook of Test Problems in Local and Global Optimization.Kluwer Academic Publishers, 1999.

[28] Michalewicz Z. Genetic Algorithms + Data Structures = EvolutionPrograms. Springer, 1996.

[29] Törn A, ?ilinskas A. Global Optimization. Berlin: Springer-Verlag, 1989.

[30] Mäkelä M M, Neittaanmäki P. Nonsmooth Optimization.World Scientific, 1992.

[31] CUTEr. CUTEr: A constrained and unconstrained testingenvironment, revisited. http://cuter.rl.ac.uk/, 2011.

[32] Knüppel O. PROFILE/BIAS-A fast interval library. Computing,1994, 53: 277-287.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved