Download the solvers for the k-cut problem
We have developed several heuristics for the k-cut problem. Each heuristic is available within an independent solver.
Gomory Hu Tree based Heuristic
Solver for the k-cut problem based on a Gomory Hu Tree construction
Download source codeSee documentation (compilation & usage)
Packing Heuristic
Solver for the k-cut problem based on the upper bound from this article (section 4.3)
Download source codeSee documentation (compilation & usage)
Hybrid Heuristic
A heuristic that uses the Gomory-Hu Tree heuristic within the Packing Heuristic
Download source codeSee documentation (compilation & usage)
Fast Heuristic
A fast and efficient heuristic for the k-cut problem.
Download source codeSee documentation (compilation & usage)
We also propose two exact solvers for the k-cut problem on graphs: a branch & bound method that relies on a custom lower bound, and a branch & cut method that requires CPLEX. The custom lower bound can also be used independently.
Exact Solver for Graphs
This is an exact solver for the k-cut problem on undirected weighted graphs. It supports lower bound computation, Branch & Bound, and Branch & Cut (using CPLEX). Usage and format details can be found in the README and documentation.
Download source codeSee documentation (compilation & usage)