Force-directed graph optimization with step-wise costs and constraints


Introduction

I have an optimization problem. There are up to 25 nodes. The connectivity between the nodes is far less important than the Cartesian placement of the nodes. Since all nodes can potentially affect each other in the optimization problem it is safe to model this as a complete, undirected graph.

In most modes of this optimization problem there are between 2-3 regions extending out infinitely from the origin separated by straight lines, i.e.

 A | B --------    C 

Each region exactly encompasses one or more Cartesian quadrants. Each imposes a fixed cost or benefit to each node, but this cost does not change the "farther into the region" a node gets.

Costs

This is the exhaustive list of costs and constraints on the nodes; all factors are cost multipliers (higher is worse). Distances are shown in metres but are really just discrete integers.

  • The distance between any two nodes must be at least 4m
  • For each node pair within 25m, there is a factor of 1.04
  • For each node, if there are three or fewer other nodes within 120m, there is a factor of 0.90
  • Depending on what region a node is in, the node has a factor between 0.90 and 1.10
  • For every node, there is an individual edge factor to every other node within 25m of between 0.90 and 1.10
  • The product of all of the above factors, for each node, will have a set minimum of 0.67 and a set maximum of 1.50

So none of the factors are continuous, and none are differentiable in space since they are all step-wise.

Search space

The 2D coordinates of each node are discrete and unbounded. Since there are 25 nodes, there are 50 integer variables (xy for each node) to optimize. The hope is that even though there are no bounds, there will be enough sub-1.0 factors to have the optimization converge rather than force the nodes to fly apart.

If I get this working well enough for a given region configuration, I might expand this to selection of a region configuration, for which there are currently 46 possibilities.

Optimization

Since none of the cost factors are space-differentiable, something like Gradient Descent would not be possible.

I have read about force-directed graph drawing; in particular this is interesting:

using the Kamada–Kawai algorithm to quickly generate a reasonable initial layout and then the Fruchterman–Reingold algorithm to improve the placement of neighbouring nodes.

Unfortunately, it seems that these methods have no notion of cost tied to absolute location, only distance of nodes relative to each other.

Implementation

I will probably end up implementing this in Python.

Any hints on how to approach this would be appreciated.