How to maximize distance between nodes on a graph?

Question

I have an undirected graph such as the one shown below. I can make up to 3 choices about the color of each node. The edge weights are equal to the difference between the nodes, given by the "distance" between the colors chosen for each node. What is an algorithm I can use to choose the colors for the nodes such that the total edge weight is maximized?

For example, say node 0 can be red, blue, or gray, and node 5 can be either blue or gold. If node 0 and node 5 were both blue, the edge between them would have low weight, which is not good.

I have considered a few possibilities:

Brute-force search. While feasible for this example, where there are only 3*2*2*1*1*2 = 24 total possible color combinations, my actual problem has well over 300 nodes, so this is not feasible.
Nonlinear optimization problem. I have written a formulation such that this small example can be solved in AMPL and Python's scipy, but this method also suffers from large complexity.
Maximum-cost network flow. I have tried to formulate this as a network flow problem, where each node represents a "choice" to be made about each actual node. However, I am unsure how to introduce appropriate constraints and/or dummy nodes such that I guarantee that the cost of the flow actually equals my objective function, and that the only feasible solutions in the flow problem "make sense" for my original problem.

There is also a chance that this problem is NP or otherwise can not be formulated as a linear program, but I would not know how to show that.

The actual use case of this problem is that I have a Voronoi diagram where each region corresponds to a different team. I can select one of up to 3 colors for each team to use for that team's region on the map, and I want to choose the colors such that the contrast between bordering regions is maximized.

user_3184950 · Answer

One way could be with Simulated Annealing, which has proven to work well for the Graph Coloring problem...

This is a example of a toy example, to show something basic. Not something optimal.

I use frigidum

!pip install frigidum

imports

import random
import frigidum

And define data/problem with

node_0 = { 'colors' : [0,1,2], 'edge_with' : [2,3,4,5]}
node_1 = { 'colors' : [2,3], 'edge_with' : [4,5]}
node_2 = { 'colors' : [1,2], 'edge_with' : [0,3]}
node_3 = { 'colors' : [0,2,3], 'edge_with' : [4,2]}
node_4 = { 'colors' : [0,2,3], 'edge_with' : [0,1,3]}
node_5 = { 'colors' : [1,3], 'edge_with' : [0,1]}

nodes = [node_0, node_1, node_2, node_3, node_4, node_5]

We define the necessary help functions

def random_start():
    random_solution = []
    for node in nodes:
        random_color = random.choice(node['colors'])
        random_solution.append(random_color)
    return random_solution


def obj(x):
    obj = 0
    for i, node in enumerate(nodes):
        own_color = x[i]
        for other_node in node['edge_with']:
            other_color = x[other_node]
            
            obj = obj + abs(own_color - other_color)
    return -1 * obj

def random_color_swap(x):
    random_edge = random.choice( range(len(nodes)))
    dx = x.copy()
    
    dx[random_edge] = random.choice( nodes[random_edge]['colors'])
    
    return dx

And start a annealing

local_opt = frigidum.sa(random_start=random_start, 
                        neighbours=[random_color_swap], 
                        objective_function=obj, 
                        T_start=10**5, 
                        T_stop=0.01, 
                        repeats=10**3, 
                        copy_state=frigidum.annealing.naked)

the best found solution will be

local_opt[0]

How to maximize distance between nodes on a graph?

1 Answers