KR-102962324-B1 - NEURAL NETWORK DEVICE AND METHOD FOR RAPIDLY FINDING SOLUTION TO QUADRATIC ASSIGNMENT PROBLEM

KR102962324B1KR 102962324 B1KR102962324 B1KR 102962324B1KR-102962324-B1

Abstract

The present invention relates to a neural network device and method for searching for a solution to a quadratic allocation problem at high speed, and is characterized by comprising: a memory; and a processor that generates logits for locations and facilities based on quadratic allocation problem instances stored in the memory, generates an allocation matrix for locations and facilities through deep learning-based parallel processing using the generated logits as input, and calculates a cost based on the generated allocation matrix to search for a solution to the quadratic allocation problem.

Inventors

강현중
조성익
이연희
김영민
김태환
김현재
유태완
이호성
임완선
전종암

Assignees

한국전자통신연구원

Dates

Publication Date: 20260508
Application Date: 20240823

Claims (16)

Memory; and A processor that generates logits for locations and facilities based on instances of the quadratic allocation problem stored in the memory, generates an allocation matrix regarding the locations and facilities through deep learning-based parallel processing using the generated logits as input, and searches for a solution to the quadratic allocation problem by calculating costs based on the generated allocation matrix. A neural network device for searching for a solution to a quadratic assignment problem at high speed, characterized by including
In paragraph 1, The above processor A neural network device for rapidly searching for a solution to a quadratic assignment problem, characterized by updating the generated logits through gradient descent, and generating the assignment matrix through deep learning-based parallel processing when a local optimum is reached.
In paragraph 1, The above processor A neural network device for rapidly searching for a solution to a quadratic allocation problem, characterized by deriving a parallel masked softmax function that performs deep learning-based parallel processing while excluding constraints regarding the location and facility based on the softmax function, and generating the allocation matrix through the parallel masked softmax function.
In paragraph 3, The above constraints are A neural network device for rapidly searching for a solution to a quadratic allocation problem, characterized by including a first constraint set such that only one facility can be located at one location, and a second constraint set such that one facility can be placed at only one location.
In paragraph 1, The above processor A neural network device for searching for a solution to a quadratic assignment problem at high speed, characterized by generating a quadratic assignment problem instance by allocating the distance between each location stored in a database and the weight between each facility to the memory.
In paragraph 1, The above processor A neural network device for searching for a solution to a quadratic allocation problem at high speed, characterized by generating a plurality of allocation matrices within the capacity of a GPU (Graphics Processor Unit) equipped in the neural network device.
In paragraph 6, The above processor A neural network device for rapidly searching for a solution to a quadratic allocation problem, characterized by calculating costs for the aforementioned multiple allocation matrices, selecting the allocation matrix having the minimum cost, and searching for a solution to the quadratic allocation problem from the selected allocation matrix.
In Paragraph 7, The above processor A neural network device for rapidly searching for a solution to a quadratic allocation problem, characterized by updating the searched solution to the optimal solution when, as a result of comparing the cost of the selected allocation matrix with the existing cost, the cost of the selected allocation matrix is less than the existing cost.
A step in which a processor generates logits for locations and facilities based on secondary allocation problem instances stored in memory; The step of the processor generating an allocation matrix regarding the location and facility through deep learning-based parallel processing using the generated logit as input; and The step in which the processor calculates a cost based on the generated allocation matrix and searches for a solution to the secondary allocation problem A method for rapidly searching for a solution to a quadratic assignment problem, characterized by including
In Paragraph 9, The step of generating the above allocation matrix is A step of updating the generated logits using gradient descent, wherein when a local optimum is reached, the assignment matrix is generated through the deep learning-based parallel processing. A method for rapidly searching for a solution to a quadratic assignment problem, characterized by including
In Paragraph 9, The step of generating the above allocation matrix is A step of deriving a parallel masked softmax function that performs deep learning-based parallel processing while excluding constraints regarding the location and facility based on the softmax function; and The step of generating the assignment matrix through the parallel masked softmax function A method for rapidly searching for a solution to a quadratic assignment problem, characterized by including
In Paragraph 11, The above constraints are A method for rapidly searching for a solution to a secondary allocation problem, characterized by including a first constraint set such that only one facility can be located at one location, and a second constraint set such that one facility can be placed at only one location.
In Paragraph 9, The step of the processor creating the secondary allocation problem instance by allocating the distance between each location and the weight between each facility stored in the database to the memory. A method for rapidly searching for a solution to a quadratic assignment problem, characterized by further including
In Paragraph 9, The step of generating the above allocation matrix is A step of generating a plurality of the above allocation matrices within the capacity of the GPU equipped in the above processor A method for rapidly searching for a solution to a quadratic assignment problem, characterized by including
In Paragraph 14, The step of searching for a solution to the above second assignment problem is A step of calculating the cost for the plurality of allocation matrices above and selecting the allocation matrix having the minimum cost; and Step of searching for a solution to the quadratic assignment problem from the selected assignment matrix A method for rapidly searching for a solution to a quadratic assignment problem, characterized by including
In paragraph 15, The above processor compares the cost of the selected allocation matrix with the existing cost; and If the cost of the selected allocation matrix is less than the existing cost, the processor updates the searched solution to the optimal solution. A method for rapidly searching for a solution to a quadratic assignment problem, characterized by further including

Description

Neural Network Device and Method for Rapidly Finding Solution to Quadratic Assignment Problem The present invention relates to a neural network device and method for searching for a solution to a quadratic assignment problem at high speed. The secondary allocation problem frequently occurs in various fields. First, regarding the government's budget allocation, for instance, each local government possesses a political and economic distance from the central government, and each local government also has a weight or flow of financial resources necessary to smoothly manage its local finances. Under these circumstances, the government may seek to efficiently allocate financial resources by considering the needs of each region and the distance from the central government's influence. Furthermore, when allocating public service facilities such as public medical facilities, the optimal placement can be considered by taking into account the distance between cities, the time required for patients to reach a hospital (Distance), and the estimated volume of patient flow heading from each city to the hospital (Flow). Furthermore, the secondary allocation problem frequently occurs in corporate resource management and business operations. For example, assume that an automobile manufacturer owns three parts factories and two assembly plants, each producing specific automotive parts. At times, the parts factories need to receive semi-finished parts from other parts factories. Ultimately, all parts must be delivered to the appropriate assembly plants. To minimize overall transportation costs, these factories must be carefully positioned (distance). Additionally, a weight may exist between the two factories. This weight 'ω' could be the number of trucks required for delivery or the weight of the cargo. In this case, 'ω*d' (where d is the distance between the two factories) becomes the final transportation cost. Intuitively, transportation costs may encourage the close placement of factories with high traffic flow. The background technology of the present invention is disclosed in Korean Published Patent Application No. 10-2021-0083661 (July 7, 2021). FIG. 1 is a diagram illustrating the network configuration of a neural network device for searching for a solution to a secondary assignment problem at high speed according to one embodiment of the present invention. Figure 2 is a diagram showing the system configuration of the neural network device of Figure 1. Figure 3 is a diagram showing the functional configuration of the neural network device of Figure 1. Figure 4 is an example of a two-dimensional pseudo-one-hot based assignment matrix. Figure 5 is a diagram illustrating a masked softmax and a parallel masked softmax. FIG. 6 is an example diagram illustrating the pseudo code of an optimal solution search algorithm according to an embodiment of the present invention. Figure 7 is a table showing the experimental results of the execution time required to find the solution. Figure 8 is a diagram showing experimental results regarding costs in a table format. Figure 9 is a table showing the experimental results regarding efficiency. FIG. 10 is a flowchart illustrating a method for searching for a solution to a quadratic assignment problem at high speed according to an embodiment of the present invention. Embodiments according to the present invention are described below. In this process, the thickness of lines or the size of components shown in the drawings may be exaggerated for clarity and convenience of explanation. Furthermore, the terms described below are defined considering their functions in the present invention, and these may vary depending on the intention or convention of the user or operator. Therefore, the definitions of these terms should be based on the content throughout this specification. Embodiments of the present invention are described below with reference to the attached drawings so that those skilled in the art can easily implement them. However, the present invention may be embodied in various different forms and is not limited to the embodiments described herein. Furthermore, in order to clearly explain the present invention in the drawings, parts unrelated to the explanation have been omitted, and similar parts throughout the specification are denoted by similar reference numerals. Throughout the specification, when a part is described as "including" a certain component, this means that, unless specifically stated otherwise, it does not exclude other components but may include additional components. The implementations described herein may be implemented, for example, as methods or processes, devices, software programs, data streams, or signals. Even if discussed only in the context of a single form of implementation (e.g., discussed only as a method), the implementation of the discussed features may also be implemented in other forms (e.g., devices or programs). Devices may be implemented in appropri