# 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.

## Requirements

We use `CUDA 11.2` and `GCC 10`. Other combinations might also work but not tested. `CMake` is required for compilation.

## Installation

### C++ solver:

``````mkdir build
cd build
cmake ..
make -j 4
``````

### Python bindings:

We also provide python bindings using pybind. Simply run the following command:

``````python -m pip install git+https://github.com/pawelswoboda/RAMA.git
``````

## Usage

### C++ solver:

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 `i` and `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>
``````

### Python solver:

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())
``````

### Parameters:

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
``````

Run  `./rama_text_input --help` for details about the parameters.