6
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ thanks a lot. As this is greedy heuristic, the optimal solution is not guaranteed. Choosing the second/third/fourth largest weight in the very first Step-2 may sometimes deliver higher objective, right? $\endgroup$ Aug 11 at 22:38
  • $\begingroup$ Yes, no guarantee. $\endgroup$
    – RobPratt
    Aug 11 at 23:04
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.