Optimization of a quadratic assignment problem on a lattice
A process for computing the optimal solution to the quadratic assignment problem (QAP) defined on lattices includes storing facility data as facilities in a facility grid with facility tiles. Location data are stored as locations in a location grid with location tiles. Each facility tile is associated with a location tile and each facility in each facility tile is associated with a location in an associated location tile. A flow function is identified as distances between the plurality of facilities in the facility grid, and a distance function is identified as distances between the plurality of locations in the location grid. An association function relating the facilities to the locations is identified such that a solution with a low-cost function depending on the flow function and the distance function is found.
1 . A process for optimizing instances of a quadratic assignment problem (QAP) on a given lattice comprising:
receiving into a computer processor facility data, the facility data comprising a given set of facilities on a finite lattice;
storing the facility data in the computer processor as a first set of a plurality of facilities in a facility grid, wherein the facility grid is partitioned into a plurality of facility tiles, the plurality of facility tiles comprising the facilities;
receiving into the computer processor location data, the location data comprising a given set of locations;
storing the location data in the computer processor as a second set of a plurality of locations in a location grid, wherein the location grid is partitioned into a plurality of location tiles, the plurality of location tiles comprising the locations;
associating each facility tile to a location tile;
associating each facility in each facility tile to a location in an associated location tile;
identifying a flow function as distances between the plurality of facilities in the facility grid;
identifying a distance function as distances between the plurality of locations in the location grid; and
identifying an association function relating the facilities to the locations such that a local minimum for a cost function depending on the flow function and the distance function is found;
wherein the flow function and the distance function satisfy one or more constraints;
wherein dimensions of the facility grid are equal to dimensions of the location grid, wherein a number of the facilities is equal to a number of the locations, and wherein a number of the facility tiles is equal to a number of the location tiles;
wherein the cost function comprises:
∑
a
,
b
∈
P
f
(
a
,
b
)
×
d
(
π
(
a
)
,
π
(
b
)
)
wherein P comprises a set of all the facilities such that a and b are the facilities;
wherein f comprises the flow function f: P×P→R;
wherein π: P→L comprises the association function such that (a) comprises a first location associated with a first facility and π(b) comprises a second location associated with a second facility:
wherein d comprises the distance function d: L×L→R;
wherein R comprises the set of real numbers;
wherein L comprises the set of all locations; and
wherein the facility tiles and the location tiles are generated using a heuristic approach, thereby enabling a selection and mapping of locations in the locations grid and facilities in the facility grid that result in a minimum computational cost.
2 . The process of claim 1 , wherein the flow function comprises an arbitrary norm between facilities in the facility grid.
3 . The process of claim 1 , wherein the distance function comprises an arbitrary norm between points in the locations grid.
4 . The process of claim 1 , wherein a cardinality of each facility tile and a cardinality of each location tile is 2{circumflex over ( )}k, where k is the dimension of the facility grid and the location grid.
5 . The process of claim 1 , comprising applying the minimized cost function to placing and routing connections on a circuit board; wherein the locations comprise sites in a backboard, the facilities comprise elements to a position in the backboard, the distance function comprises the Euclidian distance between the sites in the backboard and the flow function comprises a number of wires every two backboard elements share.
6 . The process of claim 1 , wherein the associating each facility in each facility tile to a location in the associated location tile is executed such that when two particular locations are close the corresponding facilities are distant.
7 . A non-transitory machine-readable medium comprising instructions that when executed by a processor execute a process comprising:
receiving into a computer processor facility data, the facility data comprising a given set of facilities on a finite lattice;
storing the facility data in the computer processor as a first set of a plurality of facilities in a facility grid, wherein the facility grid is partitioned into a plurality of facility tiles, the plurality of facility tiles comprising the facilities;
receiving into the computer processor location data, the location data comprising a given set of locations;
storing the location data in the computer processor as a second set of a plurality of locations in a location grid, wherein the location grid is partitioned into a plurality of location tiles, the plurality of location tiles comprising the locations;
associating each facility tile to a location tile;
associating each facility in each facility tile to a location in an associated location tile;
identifying a flow function as distances between the plurality of facilities in the facility grid;
identifying a distance function as distances between the plurality of locations in the location grid; and
identifying an association function relating the facilities to the locations such that a local minimum for a cost function depending on the flow function and the distance function is found;
wherein the flow function and the distance function satisfy one or more constraints; and
wherein dimensions of the facility grid are equal to dimensions of the location grid, wherein a number of the facilities is equal to a number of the locations, and wherein a number of the facility tiles is equal to a number of the location tiles;
wherein the cost function comprises:
∑
a
,
b
∈
P
f
(
a
,
b
)
×
d
(
π
(
a
)
,
π
(
b
)
)
wherein P comprises a set of all the facilities such that a and b are the facilities;
wherein f comprises the flow function f: P×P→R;
wherein π: P→L comprises the association function such that π(a) comprises a first location associated with a first facility and π(b) comprises a second location associated with a second facility;
wherein d comprises the distance function d: L×L→R;
wherein R comprises the set of real numbers;
wherein L comprises the set of all locations; and
wherein the facility tiles and the location tiles are generated using a heuristic approach, thereby enabling a selection and mapping of locations in the locations grid and facilities in the facility grid that result in a minimum computational cost.
8 . The non-transitory machine-readable medium of claim 7 , wherein the flow function comprises an arbitrary norm between facilities in the facility grid.
9 . The non-transitory machine-readable medium of claim 7 , wherein the distance function comprises an arbitrary norm between points in the locations grid.
10 . The non-transitory machine-readable medium of claim 7 , wherein a cardinality of each facility tile and a cardinality of each location tile is 2{circumflex over ( )}k, where k is the dimension of the facility grid and the location grid.
11 . The non-transitory machine-readable medium of claim 7 , comprising applying the minimized cost function to placing and routing connections on a circuit board; wherein the locations comprise sites in a backboard, the facilities comprise elements to a position in the backboard, the distance function comprises the Euclidian distance between the sites in the backboard and the flow function comprises a number of wires every two backboard elements share.
12 . The non-transitory machine-readable medium of claim 7 , wherein the associating each facility in each facility tile to a location in the associated location tile is executed such that when two particular locations are close the corresponding facilities are distant.
13 . A system comprising:
a computer processor; and
a memory coupled to the computer processor;
wherein the computer processor and the memory are operable for:
receiving into a computer processor facility data, the facility data comprising a given set of facilities on a finite lattice;
storing the facility data in the computer processor as a first set of a plurality of facilities in a facility grid, wherein the facility grid is partitioned into a plurality of facility tiles, the plurality of facility tiles comprising the facilities;
receiving into the computer processor location data, the location data comprising a given set of locations;
storing the location data in the computer processor as a second set of a plurality of locations in a location grid, wherein the location grid is partitioned into a plurality of location tiles, the plurality of location tiles comprising the locations;
associating each facility tile to a location tile;
associating each facility in each facility tile to a location in an associated location tile;
identifying a flow function as distances between the plurality of facilities in the facility grid;
identifying a distance function as distances between the plurality of locations in the location grid; and
identifying an association function relating the facilities to the locations such that a local minimum for a cost function depending on the flow function and the distance function is found;
wherein the flow function and the distance function satisfy one or more constraints;
wherein dimensions of the facility grid are equal to dimensions of the location grid, wherein a number of the facilities is equal to a number of the locations, and wherein a number of the facility tiles is equal to a number of the location tiles;
wherein the cost function comprises:
∑
a
,
b
∈
P
f
(
a
,
b
)
×
d
(
π
(
a
)
,
π
(
b
)
)
wherein P comprises a set of all the facilities such that a and b are the facilities;
wherein f comprises the flow function f: P×P→R;
wherein π: P→L comprises the association function such that π(a) comprises a first location associated with a first facility and π(b) comprises a second location associated with a second facility;
wherein d comprises the distance function d: L×L→R;
wherein R comprises the set of real numbers;
wherein L comprises the set of all locations; and
wherein the facility tiles and the location tiles are generated using a heuristic approach, thereby enabling a selection and mapping of locations in the locations grid and facilities in the facility grid that result in a minimum computational cost.
14 . The system of claim 13 , wherein the flow function comprises an arbitrary norm between facilities in the facility grid; wherein the distance function comprises an arbitrary norm between points in the locations grid; wherein the facility tiles and the location tiles are generated using a heuristic approach, thereby enabling a selection and mapping of locations in the locations grid and facilities in the facility grid that result in a minimum cost; and wherein the associating each facility in each facility tile to a location in the associated location tile is executed such that when two particular locations are close the corresponding facilities are distant.
15 . The system of claim 13 , wherein the computer processor and memory are operable for applying the minimized cost function to placing and routing connections on a circuit board; wherein the locations comprise sites in a backboard, the facilities comprise elements to a position in the backboard, the distance function comprises the Euclidian distance between the sites in the backboard and the flow function comprises a number of wires every two backboard elements share.