This paper describes the design of the Abstract Library for Parallel Search (ALPS), a framework for implementing scalable, parallel algorithms based on tree search. ALPS is specifically designed to support data-intensive algorithms, in which large amounts of data are required to describe each node in the search tree. Implementing such algorithms in a scalable manner is challenging both because of data storage requirements and communication overhead. ALPS incorporates a number of new ideas to address this challenge. The paper also describes the design of two other libraries forming a hierarchy built on top of ALPS. The first is the Branch, Constrain, and Price Software (BiCePS) library, a framework that supports the implementation of parallel branch and bound algorithms in which the bounds are obtained by solving some sort of relaxation, usually Lagrangian. In this layer, the notion of global data objects associated with the variables and constraints is introduced. These global objects provide a connection between the various subproblems in the search tree, but they pose further difficulties for designing scalable algorithms. The other library is the BiCePS linear integer solver (BLIS), a concretization of BiCePS, in which linear programming is used to obtain bounds in each search tree node.
Keywords for this software
References in zbMATH (referenced in 10 articles , 1 standard article )
Showing results 1 to 10 of 10.
- Eckstein, Jonathan; Hart, William E.; Phillips, Cynthia A.: PEBBL: an object-oriented framework for scalable parallel branch and bound (2015)
- 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)
- Subramanian, A.; Drummond, L.M.A.; Bentes, C.; Ochi, L.S.; Farias, R.: A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery (2010)
- Linderoth, Jeff; Margot, François; Thain, Greg: Improving bounds on the football pool problem by integer programming and high-throughput computing (2009)
- Michel, Laurent; See, Andrew; van Hentenryck, Pascal: Parallel and distributed local search in COMET (2009)
- Vo, Khoa T.; Reinelt, Gerhard: Parallel computation for the bandwidth minimization problem (2009)
- Xu, Yan; Ralphs, Ted K.; Ladányi, László; Saltzman, Matthew J.: Computational experience with a software framework for parallel integer programming (2009)
- Crainic, Teodor Gabriel: Parallel solution methods for vehicle routing problems (2008)
- Linderoth, Jeffrey T.; Ralphs, Ted K.: Noncommercial software for mixed-integer linear programming (2006)
- Ralphs, T.K.; Ládanyi, L.; Saltzman, M.J.: A library hierarchy for implementing scalable parallel search algorithms (2004)