US 12,682,130 B2Granted

Optimization of a quadratic assignment problem on a lattice

AssigneeRaytheon Company

InventorsCecilia Tonelli, Tuhin Sahai

Life of this patent

Estimating the term…

Loading patent…

Abstract

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.

Claims15

Dependent claims

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.

51 more elements

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.

52 more elements

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.

55 more elements

Dependencies are inferred from the claim text.

Facts

Application: 17/987,399Filed 15 Nov 2022 · us provisional application
Priority: 16 Nov 2021
Published: US 2023/0153481 A118 May 2023
Granted: 14 Jul 2026
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06F 16/9024
Indexing; Data structures therefor; Storage structures: graphs; Linked lists
G06F 30/13
Geometric CAD: architectural design, e.g. computer-aided architectural design [CAAD] related to design of buildings, bridges, landscapes,…
G06Q 10/043
Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem":…
G06F 2101/08
Indexing scheme relating to the type of digital function generated: powers or roots