A library hierarchy for implementing scalable parallel search algorithms. 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 7 articles , 1 standard article )
Showing results 1 to 7 of 7.
- Shinano, Yuji; Heinz, Stefan; Vigerske, Stefan; Winkler, Michael: FiberSCIP -- a shared memory parallelization of SCIP (2018)
- Eckstein, Jonathan; Hart, William E.; Phillips, Cynthia A.: PEBBL: an object-oriented framework for scalable parallel branch and bound (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)
- Michel, Laurent; See, Andrew; van Hentenryck, Pascal: Parallel and distributed local search in COMET (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)
- Ralphs, T. K.; Ládanyi, L.; Saltzman, M. J.: A library hierarchy for implementing scalable parallel search algorithms (2004)