2
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

This is a discrete optimization problem. I think one possible approach would be to approximate the discrete elements with continuous, differentiable functions and then optimize the resulting substitute problem.

Consider the function $f(x)=1$ if $x\ge 0$, or $f(x)=0$ if $x<0$. This is a discrete function, which can be approximated by the sigmoid function $S_\alpha(x) = 1/(1+e^{-\alpha x})$. The sigmoid is effectively a "softened" version of $f$. The larger that $\alpha$ is, the better the approximation. And notice that the sigmoid function is continuous and differentiable and monotonic. Similarly, the function $f(x)=c$ if $x \ge t$, or $f(x)=0$ if $x<t$, can be approximated by $c/(1+e^{-\alpha (x-t)})$.

So, take your problem, and replace each of the discrete decisions with a softened version. For instance, you have a rule that says "if a pair of nodes is at distance $\le$ 25m, then multiply a factor of 1.04". I suggest you replace this with the rule "multiply a factor of $1.04/(1+e^{-\alpha(25-d)})$ where $d$ is the distance between those two nodes". In this way, each rule can be replaced with a "softened" version, where the parameter $\alpha$ determines how soft it is: the smaller $\alpha$ is, the smoother the function; the larger $\alpha$ is, the better an approximation it is to the discrete rule. Your requirement that the product be between 0.67 to 1.5 can be replaced with a version that applies a penalty if the product is below 0.67 or above 1.5, and then you compute a softened version of this penalty for each node. Finally, the objective function can be the sum of these penalties.

Once you've done that, you have a continuous, differentiable objective function, so you can minimize it using gradient descent. I suggest that you initially set $\alpha$ to be a fairly small value, and during gradient descent you gradually increase $\alpha$ until finally it is a very large value (i.e., slightly increasing $\alpha$ after each iteration of gradient descent).

As a side note, instead of working with the product of factors, I recommend you take the log of everything, so that work with the sum of log factors. Usually summations behave more nicely with gradient descent than products.

I suggest that you use gradient descent with random restarts. For instance, you might do 1000 trials, where in each trial you start with randomly chosen initial positions, and then do gradient descent from there until convergence; and you take the best result across all of these 1000 trials.

You could also try replacing gradient descent with any other iterative method, such as Newton's method.

I don't know whether this will work well for your particular problem, but it is one thing you could try that might work.

$\endgroup$
2
  • $\begingroup$ Quite interesting. I will try this. $\endgroup$
    – Reinderien
    Commented Jun 29, 2020 at 3:30
  • $\begingroup$ the sigmoid function is continuous and differentiable - it is also monotonic, which is very important in this case. $\endgroup$
    – Reinderien
    Commented Jun 30, 2020 at 4:13

Your Answer

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

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