You saw this:
Now the problem: you want to minimize the total length of all cables, by reordering all units/devices in rack cabinets.
There are 16 devices in this examples. All permutations 16!=20922789888000, this is too much for bruteforce.
The solution using Python simanneal package:
from __future__ import print_function
import math
import random
from simanneal import Annealer
DEVICES=16
# each tuple - "source" device and "destination" device
wires=[(0, 13), (0, 3), (0, 5), (0, 6), (1, 11), (1, 3), (3, 14), (3, 1), (3, 7), (3, 9), (5, 4), (6, 1), (6, 14), (6, 8), (7, 12), (8, 0), (9, 6), (10, 4), (10, 7), (12, 13), (12, 14), (13, 8), (13, 8), (14, 15), (14, 3), (15, 9), (15, 0), (15, 10)]
def fitness(state):
# measure total length of all wires, for the given order of devices
total_len=0
for wire in wires:
src_device=wire[0]
dst_device=wire[1]
total_len=total_len+abs(state.index(src_device)-state.index(dst_device))
return total_len
class TestProblem(Annealer):
def __init__(self, state):
super(TestProblem, self).__init__(state) # important!
def move(self):
"""Swaps two (random) elements"""
a = random.randint(0, len(self.state) - 1)
b = random.randint(0, len(self.state) - 1)
self.state[a], self.state[b] = self.state[b], self.state[a]
def energy(self):
return fitness(self.state)
if __name__ == '__main__':
init_state = range(DEVICES)
test = TestProblem(init_state)
test.steps = 5000000
# since our state is just a list, slice is the fastest way to copy
test.copy_strategy = "slice"
state, e = test.anneal()
print()
print ("order =", state)
print ("total length of all wires =", fitness(state))
wire_drawn=[0]*len(wires)
for pos in range(DEVICES):
d=state[pos]
s="device %2d | " % d
for w in range(len(wires)):
src=wires[w][0]
dst=wires[w][1]
if d==src or d==dst:
s=s+" * "
wire_drawn[w]=wire_drawn[w]^1 # toggle
else:
if wire_drawn[w]==1:
s=s+" | "
else:
s=s+" "
print (s)
The total length fluctuates around 70 from run to run. This is not the minimal value, as SMT solver could give. But this solution may be good enough to be used in practice.
order = [4, 5, 10, 7, 12, 13, 8, 0, 15, 6, 14, 3, 9, 1, 11, 2] total length of all wires = 69 device 4 | * * device 5 | * * | device 10 | | * * * device 7 | | * * * | device 12 | | | * * * | device 13 | * | | * | * * | device 8 | | | | * * | * * | device 0 | * * * * | | * | * | device 15 | | | | | | * * * * device 6 | | * | * * * * | | | device 14 | | * | | * | * * * | device 3 | * * * * * * | | * | device 9 | | | * | * * device 1 | * * * * device 11 | * device 2 |
If, for some reason, or for fun, you'll want to get a solution with the total length maximized, negate fitness() function's result: "return -fitness(self.state)":
order = [3, 6, 13, 15, 5, 11, 10, 12, 2, 8, 4, 7, 9, 1, 14, 0] total length of all wires = 268 device 3 | * * * * * * * device 6 | | * | | | | | * * * * | device 13 | * | | | | | | | | | | | * * * | device 15 | | | | | | | | | | | | | | | | * | * * * device 5 | | | * | | | | | | * | | | | | | | | | | | | device 11 | | | | | * | | | | | | | | | | | | | | | | | | device 10 | | | | | | | | | | | | | | | | * * | | | | | | | * device 12 | | | | | | | | | | | | | | | * | | | * * | | | | | | device 2 | | | | | | | | | | | | | | | | | | | | | | | | | | device 8 | | | | | | | | | | | | | | * | * | | | | * * | | | | device 4 | | | | | | | | | | | * | | | | | * | | | | | | device 7 | | | | | | | | | * | | | * | | * | | | | | device 9 | | | | | | | | | * | | | * | | | * | device 1 | | | | | * * | * * | | | | | | device 14 | | | | | * * | * * * | device 0 | * * * * * *
→ [list of blog posts] Please drop me email about bug(s) and/or suggestion(s): my emails.