BiCePS swMATH ID: 6321 Software Authors: Ralphs, T.K.; L'adanyi, L.; Saltzman, M.J. Description: 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. Homepage: http://coral.ie.lehigh.edu/~ted/software/ Source Code: https://github.com/coin-or/CHiPPS-BiCePS Keywords: parallel algorithm; parallel search; parallel branch and bound; optimization; integer programming Related Software: ALPS; CHiPPS; BLIS; SYMPHONY; PEBBL; PICO; CPLEX; MIPLIB; ParaSCIP; UG; SCIP; GitHub; ParaLEX; MIPLIB2003; FiberSCIP; MPI/MPICH; OpenMPI; MINTO; ABACUS; Concorde Cited in: 9 Documents Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year A library hierarchy for implementing scalable parallel search algorithms. Zbl 1062.90039Ralphs, T. K.; Ládanyi, L.; Saltzman, M. J. 2004 all top 5 Cited by 25 Authors 3 Ralphs, Ted K. 2 Ladanyi, Laszlo 2 Saltzman, Matthew J. 2 Shinano, Yuji 1 Bentes, Cristiana 1 Crainic, Teodor Gabriel 1 DeNegre, Scott T. 1 Drummond, Lúcia M. A. 1 Eckstein, Jonathan 1 Farias, Ricardo L. S. 1 Hart, William E. 1 Heinz, Stefan 1 Michel, Laurent 1 Munguía, Lluís-Miquel 1 Ochi, Luiz Satoru 1 Oxberry, Geoffrey M. 1 Phillips, Cynthia A. 1 Rajan, Deepak 1 See, Andrew 1 Subramanian, Anand Prabhu 1 Tahernejad, Sahar 1 Van Hentenryck, Pascal 1 Vigerske, Stefan 1 Winkler, Michael 1 Xu, Yan Cited in 5 Serials 2 Computers & Operations Research 2 INFORMS Journal on Computing 2 Mathematical Programming Computation 1 The Journal of Supercomputing 1 Computational Optimization and Applications Cited in 3 Fields 9 Operations research, mathematical programming (90-XX) 4 Computer science (68-XX) 1 Numerical analysis (65-XX) Citations by Year