JP7461482B2 - Information processing system and method for supporting solving assignment problems - Google Patents

Description

The present invention generally relates to techniques that assist in solving assignment problems.

A resource allocation problem is one of the allocation problems in which multiple allocation targets are allocated to multiple allocation destinations. Patent Document 1 discloses a method of expressing and solving a resource allocation problem.

Japanese Patent Application Publication No. 2002-133052

It is possible to solve the mathematical model of the allocation problem using a general-purpose computer, i.e., to evaluate all possible allocations. However, depending on at least one of the factors of the number of allocation targets, the number of allocation destinations, and the capacity of the allocation destinations (the upper limit of the number of allocation targets that can be assigned to one destination), the amount of calculations becomes enormous, and as a result, it may not be possible to solve the allocation problem within a realistic amount of time.

Therefore, in order to avoid evaluating all assignments and obtain an optimal solution within a realistic time, the mathematical model of the assignment problem is converted into an interaction model (typically an annealing processing model such as the Ising model) for an annealing machine. ), and calculating the interaction model using an annealing machine is being considered. In order to obtain the optimal solution, it is necessary to optimize the interaction model for the annealing machine.

The system collects information such as information on the number of allocation targets α (α is a natural number), information on the number of allocation targets representing the number β (β is a natural number) of assignment targets, and information on the number of assignment targets that can be assigned to one assignment target. The allowable number L (L is a natural number) which is the upper limit of the number is accepted. The system performs a degree determination to determine whether M (M is a natural number), which corresponds to the degree of the mathematical model of the assignment problem of allocating the assignment target of α to the assignment target of β, and follows L (M is a natural number) is less than or equal to a predetermined value. The system determines an interaction model for the annealing machine, which is an accelerator for solving the assignment problem, by calculating the interaction model based on the result of the order determination and α and β. A system provides the determined interaction model.

According to the present invention, an interaction model for an annealing machine can be optimized.

1 illustrates an example of the configuration of an information processing system according to an embodiment. An example of the configuration of the processing support unit is shown. An example of information that can be included in the detailed information and represents the relationship between the assignment target and the assignment destination is shown. An example of information that can be included in the detailed information and represents the relationship between assignment targets is shown. 1 shows an example of a flow of processing performed by an information processing system. An example of an input UI is shown. An example of an output UI is shown.

In the following description, an "interface device" may be one or more interface devices. The one or more interface devices may be at least one of the following:
- One or more I/O (Input/Output) interface devices. The I/O (Input/Output) interface device is an interface device for at least one of an I/O device and a remote display computer. The I/O interface device for the display computer may be a communication interface device. The at least one I/O device may be a user interface device, eg, an input device such as a keyboard and pointing device, or an output device such as a display device.
- One or more communication interface devices. The one or more communication interface devices may be one or more of the same type of communication interface device (for example, one or more NICs (Network Interface Cards)) or two or more different types of communication interface devices (for example, one or more NICs (Network Interface Cards)). It may also be an HBA (Host Bus Adapter).

In the following description, "memory" refers to one or more memory devices, which are an example of one or more storage devices, and may typically be a primary storage device. At least one of the memory devices in the memory may be a volatile memory device or a non-volatile memory device.

Also, in the following description, "persistent storage" may be one or more persistent storage devices, which is an example of one or more storage devices. Persistent storage devices typically may be non-volatile storage devices (e.g. auxiliary storage devices), and specifically include, for example, HDDs (Hard Disk Drives), SSDs (Solid State Drives), NVMEs (Non-Volatile Memory Express) drive or SCM (Storage Class Memory).

Also, in the following description, "storage device" may be at least one of memory and persistent storage device.

Also, in the following description, a "processor" may be one or more processor devices. At least one processor device may typically be a microprocessor device such as a CPU (Central Processing Unit).

In the following description, functions are sometimes described using the expression "yyy part", but the functions may be realized by one or more computer programs being executed by a processor, or by one or more hardware circuits (e.g., FPGAs or ASICs), or by a combination thereof. When a function is realized by a program being executed by a processor, the function may be at least a part of the processor, since the specified processing is performed using a storage device and/or an interface device, etc., as appropriate. Processing described with a function as the subject may be processing performed by a processor or a device having the processor. A program may be installed from a program source. The program source may be, for example, a program distribution computer or a computer-readable recording medium (e.g., a non-transitory recording medium). The description of each function is an example, and multiple functions may be combined into one function, or one function may be divided into multiple functions.

FIG. 1 shows a configuration example of an information processing system according to an embodiment.

The information processing system 50 may be a computer system having one or more physical computers. The information processing system 50 includes an interface device 130, a storage device 140, an annealing machine 100, and a processor 150 connected thereto. Instead of a computer system having one or more physical computers, the information processing system 50 may be another type of system, for example, a system (e.g., a cloud computing system) realized on a group of physical computing resources (e.g., a cloud platform).

Information is input and output to and from the information processing system 50 via the interface device 130.

The annealing machine 100 is an example of a parallel processing device (a device capable of parallel processing), and is used to solve an assignment problem by calculating an interaction model (typically, an annealing processing model such as an Ising model). It is an accelerator. The annealing machine 100 may be realized by a CPU (Central Processing Unit) having multiple physical or virtual cores, but is typically implemented by an ASIC (Application Specific Integrated Circuit) or an FPGA (Field-Programmable Gate). It is a hardware circuit such as a GPU (Graphics Processing Unit) or a GPU (Graphics Processing Unit). The annealing machine 100 may be, for example, a semiconductor computer (for example, a CMOS annealing machine) that simulates the operation of the Ising model using a semiconductor circuit (for example, a CMOS (Complementary Metal Oxide Semiconductor) circuit).

The processing support unit 125 is realized by the processor 150 executing a computer program stored in the storage device 140.

In the information processing system 50, input and processing are performed, for example, as indicated by the illustrated white arrows. That is, the processing support unit 125 receives the assignment question input information 160 and stores it in the storage device 140. The assignment problem input information 160 includes information representing the number of assignment targets α (α is an integer of 2 or more) and information representing the number of assignment targets β (β is an integer of 2 or more). Based on the assignment problem input information 160, the processing support unit 125 converts the mathematical model of the assignment problem of assigning the assignment target of α to the assignment destination of β into an interaction model (for example, an Ising model) for the annealing machine 100. . The processing support unit 125 sets device input information 170, which is information including an interaction model and is input information to the annealing machine 100, in the annealing machine 100. Thereby, the annealing machine 100 performs parallel processing to obtain the optimal solution to the allocation problem based on the device input information 170. Note that setting the device input information 170 including the interaction model and value set in the annealing machine 100 may mean storing the device input information 170 in a storage area (for example, memory) that can be accessed by the annealing machine 100. . The annealing machine 100 updates the device input information 170 stored in the storage area by receiving an explicit notification from the processing support unit 125 or by periodically accessing the storage area. It can be loaded from.

The information processing system 50 performs output and processing as indicated by the illustrated gray arrows, for example. That is, the annealing machine 100 returns processing result information 180 representing the result of parallel processing (that is, the optimal solution to the assignment problem) to the processing support unit 125. The processing support unit 125 stores allocation solution output information 190 based on the processing result information 180 in the storage device 140. The processing support unit 125 outputs allocation solution output information 190.

Both the elements that can be the target of assignment and the elements that can be assigned to can be any element selected by the user.

Figure 2 shows an example configuration of the processing support unit 125.

The processing support unit 125 includes a first interface unit 201 for input/output to the outside of the information processing system 50, an order determination unit 202 that performs order determination, an input determination unit 203 that determines device input information 170, and annealing. It has a second interface unit 204 for inputting and outputting to the machine 100, and an output determining unit 205 that determines allocation solution output information 190. The input determining unit 203 includes a reduction unit 231 that performs reduction processing and a model compile unit 232 that performs model compilation. Various elements such as a server or a portable storage medium can be employed as external elements of the information processing system 50. In this embodiment, the person outside the information processing system 50 is a user.

The details of these functions will be explained below along with the flow of processing performed by the processing support unit 125. The i-th assignment target is expressed as "assignment target i" (for example, i = 1, 2, ..., and the maximum value of i is α), and the j-th assignment target is expressed as "assignment target j" (for example, j =1, 2, ..., and the maximum value of j can be expressed as β).

The first interface unit 201 provides an input UI (User Interface) for the assignment problem input information 160. The input UI is, for example, a GUI (Graphical User Interface). FIG. 6 illustrates an input UI 600. The assignment problem input information 160 is input via the input UI 600. The input of the assignment problem input information 160 may be another type of input (for example, input of a file (for example, a CSV file) containing at least a part of the assignment problem input information 160) instead of or in addition to the input via the input UI 600. The first interface unit 201 may also manage a mathematical model of the assignment problem in advance. The assignment problem mathematical model may be set in advance in the processing support unit 125 as in this embodiment (for example, information representing the assignment problem mathematical model may be stored in the storage device 140), or may be input to the processing support unit 125 in another manner. For example, information representing the assignment problem mathematical model may be included in the assignment problem input information 160.

The assignment problem input information 160 includes at least basic information (an example of first information) and detailed information (an example of second information).

The basic information is information including the following information (A) to (C) (an example is shown in FIG. 6). In the following information (A) to (C), α and β are all natural numbers, but typically may be an integer of 2 or more. L is also a natural number, but may be an integer of 2 or more. In other words, this embodiment can solve a relatively simple assignment problem in which at least one of α, β, and L has a value of 1, but is also useful for solving a relatively complicated assignment problem in which all of α, β, and L have an integer value of 2 or more.
(A) Information indicating the number α of allocation targets.
(B) Information indicating the number β of allocation destinations.
(C) Information indicating the allowable number L of allocation destinations.

The detailed information is information other than the basic information among the assignment problem input information 160. User input (input by the user) of at least some of the detailed information may be optional. For information not input by the user among the detailed information, default information may be adopted. For example, when the detailed information includes information representing the allocation cost from the allocation target to the allocation destination for each pair of the allocation target and the allocation destination, but the information representing the allocation cost for each pair is not input by the user, a default value (for example, "1") may be uniformly adopted as the allocation cost for each pair. The detailed information includes the following information (D) and (E) (an example is shown in FIG. 6). Note that both of the information (D) and (E) may correspond to either the coefficient influence information or the coefficient non-influence information depending on which of the processes (processing A) to (processing C) described later is adopted (depending on what kind of contraction process is performed). For example, when (processing A) is adopted, both of the information (D) and (E) may be adopted as constraint terms, and therefore may become coefficient influence information. On the other hand, when either (Process B) or (Process C) is adopted, both of the information (D) and (E) can be coefficient non-influencing information.
(D) Allottee detailed information indicating details regarding the allottee (for example, information indicating the allowable capacity m (m>0) of the allottee).
(E) Allocation target detailed information indicating details regarding the allocation target (for example, the amount of resources for each allocation target).

According to the example shown in FIG. 6, the assignment question input information 160 includes basic information, assignee detailed information, and assignment target detailed information. The basic information is the above information (A) to (C). The allocation destination detailed information is the above information (D).

The allowable number L is the upper limit of the number of assignment targets that can be assigned to one assignment destination, and is the order M of the objective function term of the assignment problem mathematical model itself. The allowable amount m is a type of value depending on the type of allocation destination, and is a value related to the allocation constraints of the allocation target. Specifically, it is a constraint term of the M-order interaction model, or an annealing machine It is used as a constraint condition for the model after order reduction when input to . For example, as illustrated in FIG. 6, when the assignment target is a virtual OS (Operating System) and the assignment destination is a server, the allowable number L may be determined from the resource amount (for example, memory capacity) of the server. For example, if the amount of resources required by each virtual OS is m = 30, and the amount of resources of the server (included in the detailed information) is 90, then L = 3 (90÷30) is sufficient, and L is equal to the degree M. . Note that in this embodiment, the allowable number L and the allowable amount m are common to all the allocation destinations, but the allowable number L and the allowable amount m do not need to be the same for all the allocation destinations. For example, information representing the allowable number L or the allowable amount m may exist for each allocation destination. In this case, the maximum value of the allowable amount L becomes the order M.

The detailed information includes, for example, at least one of the following (d1) and (d2).
(d1) Coefficient influence information, which is information that influences one or more coefficient values (one or more coefficient values of one or more assigned state variables) in the interaction model.
(d2) Coefficient non-influencing information, which is information that does not affect the coefficient values in the interaction model.

An "allocation state variable" exists for each pair of allocation target i and allocation destination j, and is a variable that represents the allocation state of allocation target i to allocation destination j. For example, the value of the allocation state variable may be expressed as either a binary value or multiple values. When a binary value is used, the allocation state may be whether or not allocation target i is assigned to allocation destination j ("1" or "0"). When a multiple value is used, the allocation state can represent other types of states in addition to whether or not allocation target i is assigned to allocation destination j.

The coefficient influence information may be, for example, at least one of the following information (x) and (y). In the following (x) and (y), any relationship such as similarity or appropriateness may be adopted as the "relationship". The coefficient value of the allocation state variable may be, for example, the value of the interaction coefficient (e.g., C in C(σ _ij ×σ _i'j' )) or the value of the external field coefficient (coefficient in a linear expression, or D in D(σ _ij ×σ _ij )). Note that "σ _ij " is a variable that represents the allocation state of the allocation target i to the allocation destination j. "σ _ij ×σ _i'j' " means the product of the allocation states in which the pairs of the allocation target and the allocation destination are different. "σ _ij ×σ _ij " means the product of the allocation states in which the pairs of the allocation target and the allocation destination are the same.
(x) Information including a numerical value representing the relationship between an allocation target and an allocation destination (for example, information exemplified in FIG. 3). For example, as an example of a numerical value representing the relationship between an allocation target i and an allocation destination j, the probability that a given result will be obtained when the allocation target i is allocated to the allocation destination j can be used.
(y) Information including a numerical value representing the relationship between assignment targets (for example, information exemplified in FIG. 4). For example, as an example of a numerical value representing the relationship between assignment target i and assignment target (i+u) (u>0), the difference between the feature amount of one or more elements of assignment target i and the feature amount of one or more elements of assignment target (i+u) can be used.

The coefficient non-influence information is information (e.g., the number of auxiliary spins) required for the reduction process (the process of converting a high-order assignment problem mathematical model into a low-order assignment problem mathematical model), and specifically, for example, is information that represents the constraints of a high-order (order M) assignment problem mathematical model. Although the coefficient non-influence information is not explicitly included in the interaction model after the reduction process described below, it is utilized as meta-information used to determine the coefficient values in the assignment problem mathematical model after the reduction process. Note that the constraint terms for the interaction model (an interaction model that has been reduced or that did not require reduction) at the stage when it is loaded into the annealing machine 100 are information included in the coefficient influence information, and are therefore different (distinguished) from the "constraints" in this paragraph.

The first interface unit 201 inputs information representing α and β and the assignment problem mathematical model to the model compilation unit 232, and inputs information representing L to the degree determination unit 202. If there is detailed information (e.g., information including the tolerance m), the first interface unit 201 inputs the assignment problem mathematical model and the detailed information to the reduction unit 231.

The order determination unit 202 performs order determination, which is a determination as to whether or not the order M according to L represented by the input information (the order M of the objective function term of the assignment problem mathematical model) is less than or equal to a predetermined value. The processing in the processing support unit 125 differs depending on the result of the order determination. The “predetermined value” to be compared with the order M may be a value set by the user via the first interface unit 201, for example.

If the order M is less than or equal to a predetermined value (that is, if the result of the order determination is true), model compilation is performed without the reduction process described below. That is, the order determining unit 202 instructs the model compiling unit 232 to compile the model. As a result, if the order M is less than or equal to the predetermined value, the model compiling unit 232 receives an instruction to compile the model from the order determining unit 202. When receiving a model compilation instruction from the order determining unit 202, the model compiling unit 232 converts the assignment problem mathematical model into an interaction model. An example of an assignment problem mathematical model is Equation 1 to Equation 4 below, and an example of an interaction model is Equation 5 below. Regarding the assignment problem mathematical model, Equation 1 is an objective function (minimization), and Equations 2 to 4 are constraint conditions. In Equations 1 to 5, σ _ij is a value representing the allocation state of allocation target i to allocation destination j. In the allocation problem mathematical model (for example, Equation 1), it is assumed that the product of allocated resources per allocation destination is minimized so that the load on the allocation destination is reduced. In the case where the degree M is less than a predetermined value, the reduction process does not run, so there is no need to reduce the degree M. Therefore, in order to reduce the number of allocated state variables for the purpose of reducing the degree, the value of the allocated state variables is reduced by 2. There is no need to convert from value to multivalue.

If the order M exceeds a predetermined value (that is, if the result of order determination is false), model compilation is performed through reduction processing. That is, the order determination unit 202 instructs the reduction unit 231 to perform reduction processing. Note that the predetermined value to be compared with the order M may be, for example, any one of the following.
- A value determined at the design stage of the annealing machine 1000 and defined in the order determination unit 202.
- A value input by the user (for example, input via the input UI 600). This value is a value whose upper limit is the maximum order that the annealing machine 100 can handle. For example, the input UI 600 may include a GUI component that accepts a value less than or equal to the maximum degree that can be handled by the annealing machine 100 as a predetermined value to be compared with the degree M. The first interface unit 201 notifies the order determination unit 202 of the input predetermined value.
- A value specified by the order determination unit 202 through the following processing. That is, the order determining unit 202 uses the attributes (for example, model number and vendor) of the annealing machine 100 as a key to determine information ( For example, from a table), the corresponding predetermined value is specified.

The reduction unit 231 receives the instruction for reduction processing and performs the reduction processing. The reduction process is to reduce the order M of the assignment problem mathematical model to the order M'. The reduction unit 231 instructs the model compilation unit 232 to compile the model, and inputs the mathematical model after reduction processing (the mathematical model after order reduction) to the model compilation unit 232. As a result, if the order M exceeds the predetermined value, the model compile unit 232 receives an instruction to compile the model from the reduction unit 231. When receiving a model compilation instruction from the reduction unit 231, the model compile unit 232 converts the reduced mathematical model into an interaction model. Note that the value of M' is the same value (or a smaller value) than the above-mentioned predetermined value with which the order M is compared. That is, the predetermined value corresponds to the upper limit of the degree of the mathematical model after the reduction process, and the degree M is reduced to the upper limit (or a smaller value) by the reduction process.

For example, the reduction process includes at least one of the following processes (process A) to (process C). The order M is reduced to the order M' by at least one of (processing A) to (processing C).
(Processing A) Converting a mathematical model in HOBO (Higher Order Binary Optimization) format to a mathematical model in QUBO (Quadratic Unconstrained Binary Optimization) format.
(Processing B) Determine one or more coefficient values in the interaction model based on the coefficient influence information in the detailed information (for example, at least one of the information illustrated in FIG. 3 and the information illustrated in FIG. 4) to do.
(Process C) Changing the representation of the value of the assigned state variable in the interaction model from binary to multivalued.

For example, the reduction process may be as follows.
S1: The reduction unit 231 selects any unselected process in S1 from among (processing A) to (processing C), and performs the selected process.
S2: The reduction unit 231 determines whether M=M' as a result of S1. If the determination result in S2 is true, the process ends. If the determination result in S2 is false, the reduction unit 231 performs S1.

The priority order of the processes to be adopted may be, for example, (Process C)>(Process A)>(Process B) if the annealing machine 100 has sufficient memory. In other words, (Process C) may be adopted preferentially. That is, the process selected first in S1 may be (Process C). One example of the reason is as follows.
The reason why (Process C) has the highest priority is, for example, as follows: (Process C) is highly dependent on the hardware of the annealing machine (there are high limitations on the machines to which it can be applied), so it is highly likely that it cannot be applied, but it has the highest spin reduction effect.
The reason why (Processing A) has the second highest priority is, for example, as follows: In problems with a fourth-order or higher order and a large number of spins before conversion, the accuracy and the number of spins after conversion can suddenly swing in a negative direction, so whether or not (Processing A) is adopted is determined based on the order and the number of spins, but (Processing A) can be converted with a relatively low load.
The reason why (Process B) has the third highest priority is, for example, as follows: (Process B) is relatively versatile, but requires preprocessing on the CPU, so that the processing may take a long time.

Alternatively, (processing A) to (processing C) may be prioritized in order of decreasing number of required spins (number of spins of the model after conversion, that is, memory usage of the annealing machine). That is, among (processing A) to (processing C), the process selected first in S1 may be the process that requires the least number of spins.

An example of (Process A) is as follows. That is, by utilizing the fact that σ _ij is a binary variable, a mathematical model in the HOBO format (for example, numbers 1 to 4) is converted into a mathematical model in the QUBO format (for example, numbers 6 to 11). For example, when M≦4, (Process A) is applied (the value "4" compared with M is an example, and the value to be compared may be a value close to "4" (a value whose difference from "4" is a predetermined value or less)). Regarding the mathematical model in the QUBO format, number 6 is the objective function (minimization), number 7 is the first constraint, and numbers 8 to 11 are the second constraint. According to numbers 6 to 11, auxiliary spins q _ij and a penalty coefficient ν for the QUBO model to reproduce the original HOBO model are introduced. Note that numbers 6 to 11 are written in a general format, and the auxiliary spin number γ and penalty coefficient ν after QUBO conversion differ depending on the conversion method. The penalty coefficients v and v' are set so that no contradiction occurs when the first constraint condition is substituted into the equation (6) (objective function). The method of determining the penalty coefficients is arbitrary, so that the user can set them arbitrarily depending on the situation (for example, the input UI 600 may have a GUI component that accepts the input of the penalty coefficients v and v'). The equations 6 to 11 are input to the model compiler 232 as a mathematical model after order reduction, and are converted into an interaction model (equation 13).

An example of (Process B) is as follows.

For example, if the information illustrated in FIG. 3 (information representing the relationship between the allocation target and the allocation destination) is the interaction coefficient in Equation 1 to Equation 4, the contraction unit 231 enumerates N combinations (N is a natural number) of values of the spin σ _ij in Equation 1 to Equation 4 that necessarily satisfy the constraint conditions in Equation 1 to Equation 4. The contraction unit 231 converts a mathematical model that represents which combination is selected from the N combinations into a mathematical model of a "set partitioning problem or set covering problem" with the spin q _t as a variable. Specifically, for example, Equation 1 to Equation 4 are converted into Equation 13 to Equation 15. Equation 13 to Equation 15 are examples of the mathematical model after degree reduction. Equation 13 is an objective function (minimization), and Equation 14 to Equation 15 are constraint conditions. Although σ _r't in Equation 13 to Equation 15 corresponds to the spin of the original model (Equation 1 to Equation 4), it is a constant rather than a variable. The variable in this converted model is qt. The number N of variables q is the number of combinations remaining after eliminating combinations in which C is smaller than the threshold value and combinations r that violate the constraints among all combinations. As a result, (Process B) contributes to order reduction. Equations 13 to 15 are input to the model compiler 232 as a mathematical model after order reduction, and are converted into an interaction model (Equations 16 to 17). (Process B) is also effective when M>4. In the following example, the auxiliary spin is a binary value, but may be a continuous value if the hardware (annealing machine 100) supports it.

Also, for example, if the information illustrated in FIG. 4 (information representing the relationship between the allocation targets) is the interaction coefficient in numbers 1 to 4, then conversion to a mathematical model of the "set partitioning problem or set covering problem" is performed in the same manner as in numbers 13 to 15. For example, numbers 1 to 4 are converted to numbers 18 to 20. Numbers 18 to 20 are examples of expressions of a mathematical model after degree reduction. Number 18 is an objective function (minimization), and numbers 19 to 20 are constraint conditions. The method of deriving numbers 18 to 20 is the same as in numbers 13 to 15. As a result, (process B) contributes to degree reduction. Numbers 18 to 20 are input to the model compiling unit 232 as a mathematical model after degree reduction, and are converted to an interaction model (numbers 21 to 22).

Further, for example, by the reduction unit 231 using both the information illustrated in FIG. 3 and the information illustrated in FIG. 4, for example, Equations 1 to 4 are converted to Equations 23 to 25. Equations 23 to 25 are examples of equations of the mathematical model after order reduction. Equation 23 is an objective function (minimization), and Equations 24 and 25 are constraint conditions. The method for deriving Equations 23 to 25 is the same as Equations 13 to 15. Thus, as a result, (processing B) contributes to order reduction. Equations 23 to 25 are input to the model compiling unit 232 as a mathematical model after order reduction, and converted into an interaction model (Equations 26 to 27).

An example of (processing C) is as follows. That is, for example, Equations 1 to 4 are converted to Equation 28. Equation 28 is an example of a formula after the order of the mathematical model is reduced. Here, spin addresses r and t of the objective function are used as variables based on the mathematical model of Equations 23 to 25, for example. Once the domain of the variable is set, the constraints in Equations 23 to 25 (that is, Equations 24 and 25) become unnecessary. In this way, as a result, (processing C) contributes to order reduction. Equation 28 is input to the model compiling unit 232 as a mathematical model after order reduction, and is converted into an interaction model (Equation 29). Note that (processing C) cannot be executed on hardware where the spin value can only take binary values.

As described above, depending on whether the result of the order determination is true or false, it is determined whether the reduction process is executed or not. Model compilation is performed without or after reduction processing. In other words, the mathematical models after order reduction such as numbers 6 to 11, numbers 13 to 15, numbers 18 to 20, numbers 23 to 25, or numbers 28 are respectively It is converted into an interaction model such as Equation 21 to Equation 22, Equation 26 to Equation 27, or Equation 29. At first glance, each interaction model looks like a different formula, but once a mathematical model is determined, all can be calculated using the same procedure as the sum of an objective function and a constraint term expressed as a quadratic formula.

The detailed information may include coefficient non-affected information instead of or in addition to the coefficient affected information illustrated in Figures 3 and 4. The coefficient non-affected information is used for conversion to a reduced interaction model in the processing in the reduction unit 231.

For example, the coefficient non-influence information includes information representing constraint conditions in the model before reduction. The constraint conditions are reflected in the assignment problem mathematical model in the first interface unit 201, and the assignment problem mathematical model reflecting the constraint conditions is output from the first interface unit 201.

Furthermore, for example, the coefficient non-influence information may include information representing K (K is a natural number). K is the maximum number of assignment targets i-k (k is a natural number equal to or less than N) that can be assigned from one assignment target i. In other words, up to N assignment targets i-k may be assignable from one assignment target i to one or more assignment destinations. In this case, K is reflected as a spin or penalty term in the QUBO format mathematical model in the contraction process.

The model compiler 232 outputs device input information 170 including an interaction model and a value set. The second interface unit 204 receives the device input information 170 and sets it to the annealing machine 100. The interaction model is a model obtained by model compilation. The value set is a set of values used for calculation of the interaction model, and includes, for example, a coefficient value and an address value for each assigned state variable in the interaction model. The coefficient values in the value set are mapped within the annealing machine 100 (addresses corresponding to the coefficient values) by a control circuit (not shown) in the annealing machine 100.

The annealing machine 100 executes a calculation to find the energy ground state of the interaction model, thereby calculating an allocation plan (allocation state value for each pair of allocation target i and allocation destination j), and outputs processing result information 180, which is information representing the allocation plan, to the processing support unit 125. Note that this output can be received by the processing support unit 125 as a response to setting the interaction model and value set in the annealing machine 100. From the processing result information 180, the processing support unit 125 can know the final spin value.

The second interface unit 204 receives the processing result information 180 from the annealing machine 100 and outputs the processing result information 180 to the output determination unit 205. The output determination unit 205 generates allocation solution output information 190 based on the processing result information 180 and outputs the allocation solution output information 190 to the first interface unit 201. The first interface unit 201 provides the allocation solution output information 190 to the outside of the information processing system 50 (e.g., a user's information processing terminal). For example, as shown in FIG. 7, an output UI 700 is provided that displays the allocation solution represented by the allocation solution output information 190. The output UI 700 displays the allocation result represented by the allocation solution output information 190 (a result indicating which allocation target is allocated to which allocation destination and at what allocation cost). The output of the allocation solution output information 190 may be another type of output (e.g., output of a file (e.g., a CSV file) containing at least a portion of the allocation solution output information 190) instead of or in addition to output via the output UI 700.

FIG. 5 shows an example of the flow of processing performed by the information processing system.

In S501, the first interface unit 201 receives input of assignment question input information 160. The first interface unit 201 stores the assignment question input information 160 in the storage device 140.

In S502, the order determination unit 202 identifies the order M based on the information necessary for order determination (information including the allowable number L) among the assignment problem input information 160 in the storage device 140, and determines whether the order M is less than or equal to a predetermined value. Determine whether or not.

If the judgment result of S502 is false, in S503, the contraction unit 231 performs the above-mentioned contraction processing.

If the judgment result in S502 is true, or after the reduction process in S503, in S504, the model compilation unit 232 performs model compilation. The model before model compilation is a mathematical model after reduction process (mathematical model of order M'), or a mathematical model that has not been subjected to reduction process (mathematical model of order M). The model after model compilation is an interaction model. In model compilation, the values of α (number of allocation targets) and β (number of allocation destinations) in the assignment problem input information 160 are also used. In addition, in model compilation, at least a part of the detailed information in the assignment problem input information 160 may be used. A value set for the interaction model is also obtained by model compilation.

At S505, the model compilation unit 232 outputs device input information 170 including the interaction model and a value set, and the second interface unit 204 receives the device input information 170 and sets (writes) it to the annealing machine 100.

In S506, the annealing machine 100 performs parallel processing (computing the interaction model in parallel using the value set) based on the device input information 170.

At S507, the annealing machine 100 outputs processing result information 180.

In S<b>508 , the second interface unit 204 receives the processing result information 180 from the annealing machine 100 and outputs the processing result information 180 to the output determining unit 205 . The output determining unit 205 generates allocation solution output information 190 based on the processing result information 180 and outputs the allocation solution output information 190 to the first interface unit 201. The first interface unit 201 outputs the allocation solution output information 190 to the outside of the information processing system 50 (for example, to a user's information processing terminal).

Although one embodiment has been described above, this is an illustration for explaining the present invention, and is not intended to limit the scope of the present invention only to this embodiment. The invention can also be implemented in various other forms.

For example, annealing machine 100 may not be limited to hardware circuits such as ASICs, FPGAs, or GPUs.

Also, for example, the interaction model can be a neural network or a Boltzmann machine.

Further, the "constraint conditions" in Equations 1 to 29 above may be coefficient non-influence information among the detailed information in the assignment problem input information 160.

Further, for example, a plurality of GUI components for accepting user input may exist in one input UI 600 or may be distributed among a plurality of UIs (the GUI component is an example of a UI component). Further, for example, the UI representing the allocation solution output information 190 may be one output UI 700 or may be a plurality of UIs.

Further, for example, the second interface unit 204 may input device input information 170 including an interaction model and a value set to an external part of the information processing system 50 (for example, The information may be provided to the user's information processing terminal).

50: Information processing system

Claims (10)

Information on the number of assignment targets α (α is a natural number), information on the number of assignment targets representing the number of assignment targets β (β is a natural number), and information on the number of assignment targets that can be assigned to one assignment target. a first interface unit that accepts an upper limit of the allowable number L (L is a natural number);
an order determination unit that performs order determination to determine whether M (M is a natural number) that corresponds to the order of the mathematical model of the assignment problem of assigning the assignment target of α to the assignment destination of β and that follows L is less than or equal to a predetermined value;
If the result of the degree determination is false, perform a reduction process to determine a degree M' smaller than M, and based on the mathematical model at the degree M' determined in the reduction process and α and β, An interaction model for an annealing machine that is an accelerator for solving an assignment problem by calculating an interaction model, and an input determining unit that determines a value set that is a set of values used for calculating the interaction model. ,
and a second interface unit that provides the determined interaction model and value set. The first interface unit further receives coefficient influence information, which is information that influences one or more coefficient values of one or more assigned state variables in the interaction model;
the contraction process includes determining values of the one or more coefficients based on the coefficient influence information.
The information processing system according to claim 1 . The coefficient influence information includes information including a numerical value representing a relationship between an allocation target and an allocation destination.
The information processing system according to claim 2 . The coefficient influence information includes information including a numerical value representing a relationship between the allocation targets and the allocation targets.
The information processing system according to claim 2 . The contraction process includes at least one of the following processes (Process A) to (Process C):
(Process A) Converting a mathematical model in HOBO (Higher Order Binary Optimization) format into a mathematical model in QUBO (Quadratic Unconstrained Binary Optimization) format;
(Process B) determining one or more coefficient values in the interaction model based on coefficient influence information, which is information that influences one or more coefficient values of one or more assigned state variables in the interaction model;
(Process C) Changing the representation of the value of the assigned state variable in the interaction model from binary to multi-valued;
The input determination unit selects a process capable of reducing the order M to the order M' from among (processing A) to (processing C).
The information processing system according to claim 1 . The priority order of the processes A to C is as follows: process C, process B, and process A.
The information processing system according to claim 5 . The priority order of each of (Process A) to (Process C) is as follows: the number of spins required for the transformed model, which is the memory usage of the annealing machine, is smallest, and the number of required spins is smallest.
The information processing system according to claim 5 . The first interface unit further receives coefficient non-influence information, which is information that does not affect one or more coefficient values of one or more assigned state variables in an interaction model and is used in the reduction process and represents a constraint condition of a mathematical model of order M;
The input determination unit performs the contraction process by using the coefficient non-influence information.
The information processing system according to claim 1 . further comprising the annealing machine,
A process in which the annealing machine reads the provided interaction model and value set, calculates the interaction model using the value set, solves the assignment problem, and represents an optimal solution to the assignment problem. Output result information,
The information processing system according to claim 1. The computer receives allocation target number information indicating the number of allocation targets α (α is a natural number), allocation destination number information indicating the number of allocation recipients β (β is a natural number), and an allowable number L (L is a natural number) that is an upper limit of the number of allocation targets that can be allocated to one allocation recipient,
the computer performs an order determination to determine whether M (M is a natural number) which corresponds to the order of a mathematical model of an assignment problem for assigning the allocation targets of α to the allocation destinations of β and follows L is equal to or smaller than a predetermined value;
When the result of the degree determination is false, the computer performs a reduction process to determine an order M' smaller than M, and determines an interaction model for an annealing machine, which is an accelerator for solving the assignment problem by calculating an interaction model, based on a mathematical model at the order M' determined in the reduction process and α and β, and a value set, which is a set of values used in the calculation of the interaction model;
The computer provides the determined interaction model and value set.
Information processing methods.

Images