Compilation and usage of the heuristic-based solvers
for the k-cut problem

Each solver is compiled and executed in the same way:

Compilation

A makefile is provided:
  1. Download the source code
  2. Unzip it and open the directory
  3. Compile using the make command

Usage

The usage is illustrated with the Gomory-Hu Tree based solver; for the other solvers, simply change the name of the executable

The program takes 3 input parameters:

  • The name of the file to read (containing the hypergraph)
  • k (for the k-cut)
  • 0 or 1 (1 if you want to launch local search)

Example of usage:

./ght data/example2.txt 3 1
The program generates an output file named GHT_<fileName>.res containing the cost of the found solution and the associated partition.

Input File Format

Number of vertices (indexed from 0)

Number of hyperedges

List of hyperedges (one per line)

Weight of hyperedges (one per line)

Example:

Example of a hypergraph with 5 vertices and 4 hyperedges.

  • First hyperedge: 0,1,2 with weight 6;
  • Second hyperedge: 0,3 with weight 5;
  • Third hyperedge: 4,3,2 with weight 2;
  • Fourth hyperedge: 1,3,4 with weight 10;

The data file contains:


5
4
0 1 2
0 3
4 3 2
1 3 4
6
5
2
10

Exact Solver for Weighted Graphs

This exact solver handles the k-cut problem on undirected weighted graphs. It supports lower bound computation, Branch & Bound, and Branch & Cut using CPLEX. You can compile and run it using the following instructions.

Compilation

  1. Download the source code
  2. Unzip the archive and open the directory
  3. Edit the makefile and update the following lines to match your local CPLEX installation:
    • Line 12: set CPLEX_INCLUDE to the path to the CPLEX include directory
    • Line 13: set CPLEX_LIB to the path to the CPLEX library directory
  4. Compile the solver using the command: make

Usage

Command-line format:

./kcut <input_file> <k> [timelimit] [algoGeneral] [algoFlow]

Arguments:

  • input_file: file describing the graph
  • k: number of components
  • timelimit (optional): time limit in seconds (default 3600)
  • algoGeneral (optional):
    • 0: lower bound only
    • 1: Branch & Bound (default)
    • other: Branch & Cut (requires CPLEX)
  • algoFlow (optional):
    • 0:Push-Relabel (default)
    • other: Boykov-Kolmogorov

Example:

./kcut data/sample_graph.txt 3

Input File Format

The file must contain a graph described as:

n 
m
u1 v1
u2 v2
...
um vm
w1
w2
...
wm

Where:

  • n: number of vertices
  • m: number of edges
  • ui vi: edge between vertex ui and vi
  • wi: weight of edge i

Vertices are numbered starting from 0.

All edge weights must be positive.

Example (5 vertices, 5 edges):

5 
5
0 1
1 2
2 3
3 4
0 4
2
3
1
4
5