Parallel interval-Newton using message passing: dynamic load balancing strategies

ABSTRACT

Branch-and-prune and branch-and-bound techniques are commonly used for intelligent search in finding all solutions, or the optimal solution, within a space of interest. The corresponding binary tree structure provides a natural parallelism allowing concurrent evaluation of subproblems using parallel computing technology. Of special interest here are techniques derived from interval analysis, in particular an interval-Newton/generalized-bisection procedure. In this context, we discuss issues of load balancing and work scheduling that arise in the implementation of parallel interval-Newton on a cluster of workstations using message passing, and describe and analyze techniques for this purpose. Results using an asynchronous diffusive load balancing strategy show that a consistently high efficiency can be achieved in solving nonlinear equations, providing excellent scalability, especially with the use of a two-dimensional torus virtual network. The effectiveness of the approach used, especially in connection with a novel stack management scheme, is also demonstrated in the consistent superlinear speedups observed in performing global optimization.

REFERENCES

• 1: Adjiman, C. S., Androulakis, I. P. & Floudas, C. A. (2000) Global optimization of mixed-integer nonlinear problems. AIChE J.,46, 1769.
• 2: Androulakis, I.P. & Floudas, C. A. (1998) Distributed branch and bound algorithms for global optimization. In Parallel Processing of Discrete Problems, ed. P. M. Pardalos, Springer-Verlag, Berlin.
• 3: Anstreicher, K. M., Brixius, N., Goux, J.-P. & Linderoth, J. (2000) Solving large quadratic assignment problems on computational grids. Presented at 17th International Symposium on Mathematical Programming, Atlanta, GA, August.
• 4: Balaji, G. V. & Seader, J. D. (1995) Application of interval-Newton method to chemical engineering problems. AIChE Symp. Ser.,91(304), 364.
• 5: Blumofe, R. D. & Leiserson, C. E. (1994) Scheduling multithreaded computations by work stealing. In Proceedings 35th Annual Symposium on Foundations of Computer Science, ed. S. Goldwasser, IEEE Computer Society Press, Los Alamitos, CA.
• 6: Robert D. Blumofe , Charles E. Leiserson, Scheduling multithreaded computations by work stealing, Journal of the ACM (JACM), v.46 n.5, p.720-748, Sept. 1999 [doi>10.1145/324133.324234]
• 7: Byrne, R. P. & Bogle, I. D. L. (2000) Global optimization of modular process flowsheets. Ind. Eng. Chem. Res.,39, 4296.
• 8: Clausen, J. & Traff, J. L. (1991) Implementations of parallel branch-and-bound algorithms-experience with the graph partitioning problem. Anns. Opns. Res.,33, 331.
• 9: Ricardo C. Corrêa, A parallel approximation scheme for the multiprocessor scheduling problem, Parallel Computing, v.26 n.1, p.47-72, Jan. 2000 [doi>10.1016/S0167-8191(99)00095-2]
• 10: Ricardo C. Corrêa , Afonso Ferreira, Parallel best-first branch-and-bound in discrete optimization: a framework, Solving Combinatorial Optimization Problems in Parallel - Methods and Techniques, p.171-200, January 1996
• 11: G. Cybenko, Dynamic load balancing for distributed memory multiprocessors, Journal of Parallel and Distributed Computing, v.7 n.2, p.279-301, October 1989 [doi>10.1016/0743-7315(89)90021-X]
• 12: Dijkstra, E. W., Feijen, W. H. & van Gasteren, A. J. M. (1983) Derivation of a termination detection algorithm for distributed computations. Inf. Process. Lett.,16, 217.
• 13: Dijkstra, E. W. & Scholten, C. S. (1980) Termination detection for diffusing computations. Inf. Process. Lett.,11, 1.
• 14: Thomas Guthrie Weidner Epperly , Ross E. Swaney, Global optimization of nonconvex nonlinear programs using parallel branch and bound, 1995
• 15: Raphael Finkel , Udi Manber, DIB—a distributed implementation of backtracking, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.2, p.235-256, April 1987 [doi>10.1145/22719.24067]
• 16: Ian Foster, Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 17: Frommer, A. & Mayer, G. (1989) Parallel interval multisplittings. Numer. Math.,56, 255.
• 18: Qi Gan , Qing Yang , Chenyi Hu, Parallel all-row preconditioned interval linear solver for nonlinear equations on multiprocessors, Parallel Computing, v.20 n.9, p.1249-1268, Sept. 1994 [doi>10.1016/0167-8191(94)90036-1]
• 19: Gau, C.-Y. & Stadtherr, M. A. (1998) Global nonlinear parameter estimation using interval analysis: Parallel computing strategies. Presented at AIChE Annual Meeting, Miami Beach, FL, November.
• 20: Gau, C.-Y. & Stadtherr, M. A. (2000) Reliable nonlinear parameter estimation using interval analysis: Error-in-variable approach. Comput. Chem. Eng.,24, 631.
• 21: Gendron, B. & Crainic, T. G. (1994) Parallel branch-and-bound algorithms-survey and synthesis. Oper. Res.,42, 1042.
• 22: Goux, J.-P., Kulkani, S., Linderoth, J. & Yoder, M. (2000) An enabling framework for master-worker computing applications on the computational grid. Technical Report, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL.
• 23: William Gropp , Ewing Lusk , Anthony Skjellum, Using MPI: portable parallel programming with the message-passing interface, MIT Press, Cambridge, MA, 1994
• 24: William Gropp , Rajeev Thakur , Ewing Lusk, Using MPI-2: Advanced Features of the Message Passing Interface, MIT Press, Cambridge, MA, 1999
• 25: Han, J. R., Manousiousthakis, V. & Choi, S. H. (1997) Global optimization of chemical processes using the interval analysis. Korean J. Chem. Eng.,14, 270.
• 26: Hansen, E. R. (1992). Global Optimization Using Interval Analysis, Marcel Dekkar, New York, NY.
• 27: Harding, S. T., Maranas, C. D., McDonald, C. M. & Floudas, C. A. (1997) Locating all homogeneous azeotropes in multicomponent mixtures. Ind. Eng. Chem. Res.,36, 160.
• 28: Harding, S. T. & Floudas, C. A. (2000) Locating all heterogeneous and reactive azeotropes in multicomponent mixtures. Ind. Eng. Chem. Res.,39, 1576.
• 29: Alan Heirich , James Arvo, A Competitive Analysis of Load Balancing Strategiesfor Parallel Ray Tracing, The Journal of Supercomputing, v.12 n.1-2, p.57-68, Jan./Feb., 1998 [doi>10.1023/A:1007977326603]
• 30: Heirich, A. & Taylor, S. (1995) Load balancing by diffusion. In Proceedings 24th International Conference on Parallel Programming, Vol. 3, CRC Press, Boca Raton, FL.
• 31: Hu, C. (1996) Parallel solutions for large-scale general sparse nonlinear systems of equations. J. Comput. Sci. Tech.,11, 257.
• 32: Hu, C., Frolov, A., Kearfott, R. B. & Yang, Q. (1995) A general iterative sparse linear solver and its parallelization for interval Newton methods. Reliable Computing,1, 251.
• 33: L. Kanal , V. Kumar, Search in Artificial Intelligence, Springer-Verlag, London, 1988
• 34: Kearfott, R. B. (1996). Rigorous Global Search: Continuous Problems, Kluwer Academic Publishers, Dordrecht, The Netherlands.
• 35: Klepeis, J. L. & Floudas, C. A. (2000) Deterministic global optimization and torsion angle dynamics for molecular structure prediction. Comput. Chem. Eng.,24, 1761.
• 36: Vipin Kumar , Ananth Grama , Anshul Gupta , George Karypis, Introduction to parallel computing: design and analysis of algorithms, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1994
• 37: Reinhard Lüling , Burkhard Monien, Two Strategies for Solving the Vertex Cover Problem on a Transputer Network, Proceedings of the 3rd International Workshop on Distributed Algorithms, p.160-170, September 26-28, 1989
• 38: McDonald, C.M. & Floudas, C. A. (1997) GLOPEQ: A new computational tool for the phase and chemical equilibrium problem. Comput. Chem. Eng.21, 1.
• 39: G. P. McKeown , V. J. Rayward-Smith , S. A. Rush, Parallel branch-and-bound, Advances in parallel algorithms, John Wiley & Sons, Inc., New York, NY, 1992
• 40: McKinnon, K. I. M., Millar, C. G. & Mongeau M. (1996) Global optimization for the chemical and phase equilibrium problem using interval analysis. In State of the Art in Global Optimization: Computational Methods and Applications, eds. C. A. Floudas & P. M. Pardalos, Kluwer Academic Publishers, Dordrecht, The Netherlands.
• 41: G. Mitra , I. Hai , M. T. Hajian, A distributed processing algorithm for solving integer programs using a cluster of workstations, Parallel Computing, v.23 n.6, p.733-753, June 29, 1997 [doi>10.1016/S0167-8191(97)00016-1]
• 42: Neumaier, A. (1990). Interval Methods for Systems of Equations, Cambridge University Press, Cambridge, UK.
• 43: P. M. Pardalos , G. P. Rodgers, Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture, Annals of Operations Research, v.22 n.1-4, p.271-292, Jan. 1990 [doi>10.1007/BF02023057]
• 44: J. Quinn, Analysis and Implementation of Branch-and-Bound Algorithms on a Hypercube Multicomputer, IEEE Transactions on Computers, v.39 n.3, p.384-387, March 1990 [doi>10.1109/12.48868]
• 45: V. Nageshwara Rao , Vipin Kumar, Parallel depth first search. Part I. implementation, International Journal of Parallel Programming, v.16 n.6, p.479-499, December 1987 [doi>10.1007/BF01389000]
• 46: Rump, S. M. (1999) Fast and parallel interval arithmetic. BIT,39, 534.
• 47: Rushmeier, R. A. (1993) Experiments with parallel branch-and-bound algorithms for the set covering problems. Oper. Res. Lett.,13, 277.
• 48: Schnepper, C. A. & Stadtherr, M. A. (1993) Application of a parallel interval Newton/generalized bisection algorithm to equation-based chemical process flowsheeting. Interval Computing,1993(4), 40.
• 49: Schnepper, C. A. & Stadtherr, M. A. (1996) Robust process simulation using interval methods. Comput. Chem. Eng.,20, 187.
• 50: Sinha, M., Achenie, L. E. K. & Ostrovsky, G. M. (1999) Parallel branch and bound global optimizer for product design. Presented at AIChE Annual Meeting, Dallas, TX, November.
• 51: Smith, E. M. B. & Pantelides, C. C. (1999) A symbolic reformulation/spatial branch-and-bound algorithm for the global optimization of nonconvex MINLPs. Comput. Chem. Eng.,23, 457.
• 52: Stradi, B. A., Brennecke, J. F., Kohn, J. P. & Stadtherr, M. A. (2001) Reliable computation of mixture critical points. AIChE J,47, 212.
• 53: Subrahmanyam, S., Kudva, G. K., Bassett, M. H. & Pekny, J. F. (1996) Application of distributed computing to batch plant design and scheduling. AIChE J.,42, 1648.
• 54: Shang-Hua Teng, Adaptive parallel algorithms for integral knapsack problems, Journal of Parallel and Distributed Computing, v.8 n.4, p.400-406, Apr. 1990 [doi>10.1016/0743-7315(90)90139-G]
• 55: Troya, J. & Ortega, M. (1989) A study of parallel branch-and-bound algorithms with best-bound-first search. Parallel Computing,11, 121.
• 56: Oliver Vornberger, Implementing Branch-and-Bound in a Ring of Processors, Conference on Algorithms and Hardware for Parallel Processing, p.157-164, September 17-19, 1986
• 57: Oliver Vornberger, Load Balancing in a Network of Transputers, Proceedings of the 2nd International Workshop on Distributed Algorithms, p.116-126, July 08-10, 1987
• 58: Xu, G., Scurto, A. M., Castier, M., Brennecke, J. F. & Stadtherr, M. A. (2000) Reliable computation of high pressure solid-fluid equilibrium. Ind. Eng. Chem. Res.,39, 1624.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Nonlinear approximation
      G.1.6 Optimization
          Subjects: Global optimization

General Terms:
Algorithms, Design, Performance

Keywords:
branch-and-bound, branch-and-prune, global optimization, interval analysis, nonlinear equations, parallel computing