New answers tagged graphs
3
I hacked a random key genetic algorithm for the problem in Java, and ran it against a linearized version of Rob Pratt's MIP model (using CPLEX 20.1 with default parameter settings) on some small random test problems (five layers, three to nine nodes per layer, about 1/4 of all possible edges present). Because the GA stagnated very quickly, I did multiple ...
2
Treat nodes in 1st and 3nd layer as extra edges in the 2st layer to make a merged layer. Minimize bandwidth of 2nd layer. Repeat for the other layers.
layer 2: o o o
\ / \ /
layer 1: @ @
@ becomes an edge:
layer 2: o - o - o
```
3
Maybe this can work?
Numbering is same as sorting. Disregard the layers and treat the whole thing as a single graph. Use Cuthill-Mckee (if the bandwidth is low) or other heuristics for the graph bandwidth problem to find the big ordering of nodes. For each layer, filter out the nodes of other layers in the big ordering to get the ordering of nodes in that ...
6
I don't know whether this will be efficient enough for your real graph sizes, but with binary decision variables $x_{v,k}$ to indicate whether vertex $v$ is assigned label $k$, you can obtain a formulation that looks a lot like the quadratic assignment problem. Let $V_i$ be the set of vertices in layer $i$. The problem is to minimize $$\sum_{(v,w)\in E} \...
Top 50 recent answers are included
