1
$\begingroup$

It is the same problem as posted at Coloring of nodes in a sensor networks.

Its about coloring a weighted graph.

@RobPratt suggested a very good solution that solves the problem directly.

However, we need to employ MIQP or MILP solver to solve this problem.

I am also looking for a greedy heuristic solution that would perform very close to what @RobPratt has suggested.

Or Any distributed (coloring) solution?

Improve this question
$\endgroup$
2
  • $\begingroup$ Do you have a specific objective function in mind. The previous question is a bit vague. You want nodes with high interference to have different colors, but that by itself does not adequately define the objective function. $\endgroup$
    – prubin ♦
    Apr 14 at 15:45
  • $\begingroup$ @prubin the edge weight quantifies the mutual damage done (interference) if the corresponding nodes have same colour. OI just want to minimize the total damage in the whole system by proper coloring of the nodes. $\endgroup$
    – KGM
    Apr 14 at 18:28

4 Answers 4

Reset to default
2
$\begingroup$

This is a variant of Rob's improvement heuristic. Assume the nodes are indexed $1,\dots,N.$

  1. Assign a color to each node randomly.
  2. Shuffle the list $1,\dots,N$ of node indices randomly.
  3. For each node in the shuffled list, compute the sum of edge weights to nodes in every color group and reassign the node to the "cheapest" color (which might be the current color of the node).
  4. After checking every node, repeat steps 2 and 3 until you make one full pass through the shuffled list without any nodes changing color.

Since this should be pretty fast computationally, you might want to do it multiple times and take the best solution.

For something more sophisticated, there are ways to attack the problem using genetic algorithms.

Addendum: I tried both the heuristic (with random restarts) and a GA on a 20 x 10 grid graph. Given equal run times, the heuristic seemed to outperform the GA. (I also tried solving the MIP model, with CPLEX, but gave up because the lower bound is too loose to reach proven optimality in the time I was willing to allocate.)

Improve this answer
$\endgroup$
13
  • $\begingroup$ can this solution be adapted to a system with multiple subsystems/clusters? one node belongs to only one clusters. There are edges between clusters. $\endgroup$
    – KGM
    Jul 1 at 23:24
  • $\begingroup$ If you intend to give every node in a cluster the same color, then you can treat each cluster as a node in a graph of reduced size, where an edge between clusters A and B in the cluster graph is the composite of all edges between any node in A and any node in B. $\endgroup$
    – prubin ♦
    Jul 2 at 2:44
  • $\begingroup$ no, that is not what I want. I also need to take care of intra-cluster coloring. But the system is big, so I go for clustering. Then we have inter-cluster nodes. $\endgroup$
    – KGM
    Jul 2 at 7:16
  • $\begingroup$ You can apply the heuristic to each cluster in isolation (ignoring edges between nodes in different clusters), but if you include those edges in the coloring decisions then I don't think clustering achieves any computational savings. $\endgroup$
    – prubin ♦
    Jul 2 at 15:58
  • 1
    $\begingroup$ If you are asking whether it is possible that an optimal solution is never found, yes. If you are asking whether you might never get a full pass without any changes, no (unless you cap the number of iterations or time limit too small). The objective function is monotonically decreasing, so the number of passes will be finite. $\endgroup$
    – prubin ♦
    Jul 28 at 2:45
2
$\begingroup$

Here are two heuristic approaches:

  1. A greedy construction heuristic could be to loop through the nodes and assign each node the color that increases the objective function the least. You could optionally process the nodes in some specified order, perhaps decreasing order of total sum of incident edge weights. Or run several times with random node ordering and keep the best.
  2. A local search improvement heuristic could be to try to improve a given coloring by two moves: change the color of a single node, or swap the colors of two (differently colored) nodes.
Improve this answer
$\endgroup$
4
  • $\begingroup$ For the first heuristic, by 'assign each node the color that increases the objective function the least', you mean the objective of minimizing the total sum edge-weight (as in the original problem, linked question), right? $\endgroup$
    – KGM
    Apr 14 at 18:19
  • $\begingroup$ Yes, but the same approach works for any objective: choose the color that hurts the objective the least. $\endgroup$
    – RobPratt
    Apr 14 at 19:15
  • $\begingroup$ for the local search improvement heuristic option 1 (change the color of a single node), what is a good way to select a node for color change? Also, for option 2 (swap the color of two nodes), how to select the pair? Should I give some pair higher priority? $\endgroup$
    – KGM
    Jul 14 at 10:16
  • $\begingroup$ For both options, here are four natural approaches to try: 1. Loop through all choices in any order, 2. Loop through the top several choices according to current contribution to the objective, 3. Choose repeatedly according to a random uniform distribution, 4. Choose repeatedly according to a random distribution based on current contribution to the objective. $\endgroup$
    – RobPratt
    Jul 14 at 13:19
2
$\begingroup$

You may try this:

  1. Sort out the edge weights in descending order. Initialize a counter for each of the colors.

Repeat until all nodes are exhausted
Repeat until colors are exhausted
2. Assign two separate colors with least counter to the nodes of first edge. Update the counter. 3. Move to the next edge.
If either of the nodes are same as any of the previous, choose color with least counter for the connected node.
Else you can choose the previous two colors.
4. Update counter of colors.

Improve this answer
$\endgroup$
2
$\begingroup$

The problem you are describing is strongly related to the Partial Directed Weighted Improper Coloring Problem which was studied for example in this paper, where the authors show how such a coloring problem can model channel assignment in a network, in order to maximize network use, while respecting interference constraints.

The authors have adapted the well known coloring algorithms (Welsh-Powell, DSATUR, RLF) to this problem with a limited number of colors, and weights. The heuristics are similar to what @prubin and @RobPratt have proposed, but with some theoretical results (mainly time complexity), some improvements, and some numerical results. You can also find a MIP for the problem.

References

  1. Constructive algorithms for the partial directed weighted improper coloring problem A Hertz, R Montagné, F Gagnon - Journal of Graph Algorithms and Applications, 2016
  2. A comparison of integer programming models for the partial directed weighted improper coloring problem A Hertz, R Montagné, F Gagnon - Discrete Applied Mathematics, 2019
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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