RAMA: Rapid algorithm for multicut problem
Solves multicut (correlation clustering) problems orders of magnitude faster than CPU based solvers without compromising solution quality on NVIDIA GPU. It also gives lower bound guarantees. Paper available here.
CUDA 11.2 and
GCC 10. Other combinations might also work but not tested.
CMake is required for compilation.
mkdir build cd build cmake .. make -j 4
We also provide python bindings using pybind. Simply run the following command:
python -m pip install git+https://github.com/pawelswoboda/RAMA.git
We require multicut instance stored in a (.txt) file in the following format:
MULTICUT i_1, j_1, cost_1 i_2, j_2, cost_2 ... i_n, j_n, cost_n
which corresponds to a graph with
N edges. Where
j should be vertex indices and
cost is a floating point number. Positive costs implies that the nodes are similar and thus would prefer to be in same component and viceversa. Afterwards run:
./rama_text_input -f <PATH_TO_MULTICUT_INSTANCE>
For more details and downloading multicut instances see LPMP.
An example to compute multicut on a triangle graph:
import rama_py rama_py.rama_cuda([0, 1, 2], [1, 2, 0], [1.1, -2, 3], rama_py.multicut_solver_options())
The default set of parameters are defined here which correspond to algorithm
PD from the paper. This algorithm offers best compute time versus solution quality trade-off. Parameters for other variants are:
- Fast purely primal algorithm (P):
This algorithm can be slightly worse than sequential CPU heuristics but is 30 to 50 times faster.
./rama_text_input -f <PATH_TO_MULTICUT_INSTANCE> 0 0 0 0
- Best primal algorithm (PD+) :
This algorithm can even be better than CPU solvers in terms of solution quality as it uses dual information. Still, it is 5 to 10 faster than best CPU solver.
./rama_text_input -f <PATH_TO_MULTICUT_INSTANCE> 5 10 5 10
- Dual algorithm (D):
Use this algorithm for only computing the lower bound. Our lower bounds are slightly better than ICP and are computed up to 100 times faster.
./rama_text_input -f <PATH_TO_MULTICUT_INSTANCE> 5 10 0 0 5
./rama_text_input --help for details about the parameters.