Heuristic solution to the graph partitioning problem

Question

I am working on a graph partitioning problem. A static column generation based solution was proposed in How to partition a graph with optimal number of groups?

But I need some MILP solver to solve this problem. I want a pure heuristic approach to solve this problem.

What would be an efficient heuristic approach to solve this problem, i.e., solving without the need of any solver?

Answer 1

A greedy heuristic is natural to try here:

1. Declare all groups to be admissible.
2. Find an admissible group $g$ with the largest weight.
3. Set $u_g=1$.
4. Declare all groups $h$ with $N_h \cap N_g \not= \emptyset$ inadmissible.
5. If some $i$ is still uncovered, go to step 2.

For your sample data in the linked question, this greedy heuristic returns groups $$\{11,12,15\}, \{8,10,13\}, \{4,5,6\}, \{7,9,14\}, \{1,2,3\}$$ (in that order), and this turns out to be an optimal solution.

Answer 2

A variant of Rob's answer would be a random key genetic algorithm. You can program a GA from scratch, although you're probably better off using an open-source library.

Each "chromosome" in the GA would be a permutation of the indices $1,\dots, \vert G \vert$ (or a vector of $\vert G \vert$ real values whose sort order would translate to such a permutation). To decode and evaluate a chromosome, sort $G$ using the permutation vector. Select the first group in permutation order. Go down the permuted list, selecting each eligible group until there are no eligible groups left. As in Rob's answer, selecting group renders ineligible any subsequent group that intersects it.