PICO: An object-oriented framework for parallel branch and bound This paper describes the design of PICO, a C++ framework for implementing general parallel branch-and-bound algorithms. The PICO framework provides a mechanism for the efficient implementation of a wide range of branch-and-bound methods on an equally wide range of parallel computing platforms. We first discuss the basic architecture of PICO, including the application class hierarchy and the package’s serial and parallel layers. We next describe the design of the serial layer, and its central notion of manipulating subproblem states. Then, we discuss the design of the parallel layer, which includes flexible processor clustering levels and communication rates, various load balancing mechanisms, and a non-preemptive task scheduler running on each processor. We close by describing the application of the package to a simple branch-and-bound method for mixed integer programming, along with computational results on the ASCI Red massively parallel computer.

References in zbMATH (referenced in 21 articles , 1 standard article )

Showing results 1 to 20 of 21.
Sorted by year (citations)

1 2 next

  1. Eckstein, Jonathan; Hart, William E.; Phillips, Cynthia A.: PEBBL: an object-oriented framework for scalable parallel branch and bound (2015)
  2. Mason, Luke R.; Mak-Hau, Vicky H.; Ernst, Andreas T.: A parallel optimisation approach for the realisation problem in intensity modulated radiotherapy treatment planning (2015)
  3. Bendjoudi, A.; Melab, N.; Talbi, E-G.: An adaptive hierarchical master-worker (AHMW) framework for grids-application to B&B algorithms (2012)
  4. Dorta, I.; León, C.; Rodríguez, C.: Performance analysis of branch-and-bound skeletons (2010)
  5. Pinar, Ali; Meza, Juan; Donde, Vaibhav; Lesieutre, Bernard: Optimization strategies for the vulnerability analysis of the electric power grid (2010)
  6. Bussieck, Michael R.; Ferris, Michael C.; Meeraus, Alexander: Grid-enabled optimization with GAMS (2009)
  7. Xu, Yan; Ralphs, Ted K.; Ladányi, László; Saltzman, Matthew J.: Computational experience with a software framework for parallel integer programming (2009)
  8. Baravykaitė, M.; Čiegis, R.: An implementation of a parallel generalized branch and bound template (2007)
  9. Baravykaitė, M.; Žilinskas, J.: Implementation of parallel optimization algorithms using generalized branch and bound template (2006)
  10. Dolgov, D.A.; Durfee, E.H.: Resource allocation among agents with MDP-induced preferences (2006)
  11. Ravi, R.; Sinha, Amitabh: Hedging uncertainty: approximation algorithms for stochastic optimization problems (2006)
  12. Baravykaitė, M.; Čiegis, R.; Žilinskas, J.: Template realization of generalized branch and bound algorithm (2005)
  13. Van Hoai Tran: Solving large scale crew pairing problems. (2005)
  14. Dorta, Isabel; Leon, Coromoto; Rodriguez, Casiano: Parallel branch-and-bound skeletons: message passing and shared memory implementations (2004)
  15. Ralphs, T.K.; Ládanyi, L.; Saltzman, M.J.: A library hierarchy for implementing scalable parallel search algorithms (2004)
  16. Ralphs, T. K.; Ladányi, L.; Saltzman, M. J.: Parallel branch, cut, and price for large-scale discrete optimization (2003)
  17. Alba, E.; Almeida, F.; Blesa, M.; Cabeza, J.; Cotta, C.; Díaz, M.; Dorta, I.; Gabarró, J.; León, C.; Luna, J.; Moreno, L.; Pablos, C.; Petit, J.; Rojas, A.; Xhafa, F.: MALLBA: A library of skeletons for combinatorial optimisation (2002)
  18. Applegate, David; Cook, William; Dash, Sanjeeb; Rohe, André: Solution of a min-max vehicle routing problem (2002)
  19. Stam, Andries: A framework for coordinating parallel branch and bound algorithms (2002)
  20. Eckstein, Jonathan; Phillips, Cynthia A.; Hart, William E.: PICO: An object-oriented framework for parallel branch and bound (2001)

1 2 next