|
|
|
|
- ALPS is a framework for
implementing parallel graph search algorithms. It generalizes many of the
notions present in BCP, allowing the implementation of a wider range of
algorithms with a simplified interface. ALPS implements the search handling
methods required for implementing large-scale, data-intensive parallel search
algorithms, such as those used for solving discrete optimization problems. It
is the base layer of a planned hierarchy that will include a library for
solving mixed-integer linear programs.
|
|
-ALPS is still considered an experimental code, so use at your own
risk! There are also two examples of the use of ALPS in the COIN/Examples
subdirectory, a generic branch and cut code and a knapsack solver.
|
|
(More from Ted)
|
|
The goal of ALPS is to
|
|
(1) Achieve better parallel
scalability by improving on the simple master-worker scheme of SYMPHONY and
BCP.
|
|
(2) Provide a general C++
class library that supports the implementation of any algorithm based on tree
search (not just branch and bound).
|
|
(3) Provide support for the
generation, storage, and maintenance of huge amounts of data (called
"knowledge" in ALPS).
|
|
The applications we have in
mind are especially those that are "data-intensive," meaning that
the description of a node in the search
|
|
tree can be very large and
there is lots of information generated during the search that must be
maintained in various "knowledge pools" (think branch and cut).
|
|
|
|
The ALPS base layer is meant
to support building of the search tree in parallel and to provide a framework
to define various specialized search algorithms with associated customized
knowledge types (i.e., think cuts and columns in BCP). Additional layers
built on top of ALPS define knowledge types and knowledge management policies
for particular application. BiCePS is a layer built on top of ALPS that
provides
|
|
functionality for data
handling in any sort of relaxation-based branch and bound algorithm, i.e., it
defines the notion of cuts and variables,
|
|
etc. BLIS is a layer on top
of BiCePS that implements the usual LP-based scheme in BCP.
|
