Weighted connected matchings branch-and-cut

Branch-and-cut algorithm for finding an optimal weighted connected matching: a subset M of edges in a graph inducing a matching, such that the vertices covered by M induce a connected subgraph.

Dependencies

• The LEMON library from the COIN-OR initiative
• The Gurobi Optimizer for our branch-and-cut framework

To get LEMON

Download lemon-1.3.1 source code at https://lemon.cs.elte.hu/trac/lemon

Unpack the file (e.g. on /opt) and open a terminal on that directory

mkdir build
cd build
cmake ../
make
make check
[optional] sudo make install

If LEMON is not installed (skipping the last step above), we need to add -I flags to the makefile indicating where to find the corresponding headers.

To get Gurobi

Download the Gurobi package, first creating a login if you don't have one yet. Follow the installation guide. In a nutshell, here's what we usually do:

• Unpack the file, e.g. on /opt
• Edit the .profile and/or .bashrc files under your home folder so that the path environment variables correctly point to your installation, for example

export GUROBI_HOME="/opt/gurobi1000/linux64"
export PATH="${PATH}:${GUROBI_HOME}/bin"
export LD_LIBRARY_PATH="${LD_LIBRARY_PATH}:${GUROBI_HOME}/lib"

• Register for a Gurobi license. Assuming you're in academia, you should visit the license page from your university network (or through their VPN), and run the grbgetkey tool to validate it. N.B. The specific command is indicated at the bottom of the License Detail page you get in the end of this step! Just copy and paste it on the terminal (after restarting your terminal so that the command is recognized).

To compile and run our software:

git clone https://github.com/phillippesamer/wcm-branch-and-cut.git
cd wcm-branch-and-cut

Edit the Makefile initial definition of variable GRB_PATH to reflect the root folder where Gurobi is installed. Finally, compile and run the solver:

make
./wcm [input file path]

The input parser reads .gcc (graphs with conflict constraints) and .stp (DIMACS steiner tree problem) formats automatically. See the five instances in input/ex* files for small examples. N.B. When using an .stp instance with edge weights (e.g. in the generalized maximum-weight connected subgraph benchmark), run the executable with an arbitrary additional argument:

./wcm [input file path] -e