AU2020462915B2

AU2020462915B2 - Information processing system for assisting in solving allocation problems, and method

Info

Publication number: AU2020462915B2
Application number: AU2020462915A
Authority: AU
Inventors: Akiko Kato; Takuya OKUYAMA; Chihiro Yoshimura
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 2020-08-14
Filing date: 2020-08-14
Publication date: 2023-12-14
Anticipated expiration: 2040-08-14
Also published as: AU2020462915A1; JPWO2022034687A1; JP7461482B2; WO2022034687A1

Abstract

A system, according to the present invention, receives information-allocation target number information representing a number α (where α is a natural number) of allocation targets, allocation destination number information representing a number β (where β is a natural number) of allocation destinations, and an allowable number L (where L is a natural number) which is an upper limit for the number of allocation targets that can be allocated to one allocation destination. The system performs an order assessment which corresponds to a mathematical model order for allocation problems in which α allocation targets are allocated to β allocation destinations, and which is an assessment of whether or not M (where M is a natural number) according to L is a prescribed value or lower. The system calculates, based on the results of the order assessment and on α and β, an interaction model, and thereby determines an interaction model for an annealing machine which is an accelerator for solving allocation problems. The system provides the determined interaction model.

Description

TECHNICAL FIELD

[0001] The present invention generally relates to a technology for supporting solving an allocation problem.

BACKGROUND

[0002] There is a resource allocation problem as one of allocation problems which allocate a plurality of allocation objects to a plurality of allocation destinations. PTL 1 discloses a method for expressing the resource allocation problem and a method for solving the resource allocation problem.

PATENT LITERATURE

[0003] PTL 1: Japanese Patent Application Laid-Open (Kokai) Publication No. 2002-133052

[0004] It is assumed that a general purpose computer can be used to solve a mathematical model of an allocation problem, that is, to evaluate all patterns of allocations. However, a computation amount may become enormous due to at least one element of an allocation object quantity, an allocation destination quantity, and an allowable amount for an allocation destination (an upper limit of the allocation object quantity which can be allocated to one allocation destination) and, as a result, it sometimes become impossible to solve the allocation problem within a realistic time frame.

[0005] So, in order to avoid the evaluation of all patterns of allocations and obtain an optimum solution within the realistic time frame, it will be considered that it is to transform a mathematical model of an allocation problem into an interaction model designed for an annealing machine (typically, an annealing processing model like an Ising model); and to perform computation of that interaction model by using the annealing machine. In order to obtain the optimum solution, it is necessary to optimize the interaction model designed for the annealing machine.

[0005a] It is desired to address or ameliorate one or more disadvantages or limitations associated with the prior art, or to at least provide a useful alternative.

SUMMARY

[0006] In one embodiment, the present invention provides an information processing system comprising a first interface unit that accepts information allocation object quantity information indicating an allocation object quantity a (a: a natural number), allocation destination quantity information indicating an allocation destination quantity p(P: a natural number), and an allowable quantity L (L: a natural number) which is an upper limit of an allocation object quantity which can be allocated to one allocation destination. The system performs a degree judgment to judge whether or not M which corresponds to a degree of a mathematical model of an allocation problem to allocate a allocation object(s) to P allocation destination(s) and which satisfies L is equal to or less than a specified value. The system further comprises an input decision unit that decides an interaction model designed for an annealing machine, which is an accelerator to solve the allocation problem by computing the interaction model on the basis of a result of the degree judgment, a, and P, and a value set which is a set of values used to compute the interaction model. The system also comprises a second interface unit that provides the decided interaction model and the decided value set.

[0007] The interaction model designed for the annealing machine can be optimized according to at least some embodiments of the present invention.

BRIEF DESCRIPTION OF DRAWINGS

[0008] One or more embodiments of the present invention are hereinafter described, by way of example only, with reference to the accompanying drawings, in which: Fig. 1 illustrates a configuration example of an information processing system according to an embodiment; Fig. 2 illustrates a configuration example of a processing support unit;

Fig. 3 illustrates one example of information which can be included in detailed information and indicates the relation between allocation objects and allocation destinations; Fig. 4 illustrates one example of information which can be included in the detailed information and indicates the relation between the allocation objects; Fig. 5 illustrates one example of a flow of processing executed by the information processing system; Fig. 6 illustrates one example of an input UI; and Fig. 7 illustrates one example of an output UI.

DETAILED DESCRIPTION

[0009] In the description indicated below, an "interface apparatus" may be one or more interface devices. The one or more interface devices may be at least one of the following: - One or more 1/O (Input/Output) interface devices. The 1/O (Input/Output) interface device is an interface device for at least one of an 1/O device and a remote display computer. The 1/O interface device for the display computer may be a communication interface device. At least one 1/O device may be a user interface device, for example, either one of input devices such as a keyboard and a pointing device, and output devices such as a display device. - One or more communication interface devices. The one or more communication interface devices may be one or more communication interface devices of the same type (for example, one or more NICs [Network Interface Cards]) or two or more communication interface devices of different types (for example, an NIC and an HBA

[Host Bus Adapter]).

[0010] Furthermore, in the description indicated below, a "memory" is one or more memory devices, which are an example of one or more storage devices, and may typically be a main storage device. At least one memory device in the memory may be a volatile memory device or a nonvolatile memory device.

[0011] Furthermore, in the description indicated below, a "persistent storage apparatus" is one or more persistent storage devices which are an example of one or more storage devices. The persistent storage device is typically a nonvolatile storage device (such as an auxiliary storage device) and is specifically, for example, an HDD (Hard Disk Drive), an SSD (Solid State Drive), or an SCM (Storage Class Memory).

[0012] Furthermore, in the description indicated below, a "storage apparatus" may be a memory and at least a memory for the persistent storage apparatus.

[0013] Furthermore, in the description indicated below, a "processor" may be one or more processor devices. At least one processor device may typically be a microprocessor device like a CPU (Central Processing Unit).

[0014] Furthermore, in the description indicated below, a function may be sometimes described by an expression like "yyy unit"; however, the function may be implemented by execution of one or more computer programs by a processor, or may be implemented by one or more hardware circuits (such as FPGA or ASIC), or may be implemented by a combination of the above. If the function is implemented by the execution of a program by the processor, specified processing is performed by using, for example, storage apparatuses and/or interface apparatuses as appropriate and, therefore, the function may be considered as at least part of the processor. The processing explained by referring to the function as a subject may be the processing executed by the processor or an apparatus which has that processor. The 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 (such as a non-transitory recording medium). An explanation of each function is one example, and a plurality of functions may be gathered as one function or one function may be divided into a plurality of functions.

[0015] Fig. 1 illustrates a configuration example of an information processing system according to an embodiment.

[0016] An information processing system 50 may be a computer system equipped with one or more physical computers. The information processing system 50 includes an interface device 130, a storage apparatus 140, an annealing machine 100, and a processor 150 connected to those mentioned above. Incidentally, the information processing system

50 may be, instead of the computer system equipped with one or more physical computers, another type of system, for example, a system (for example, a cloud computing system) which is implemented in a physical calculation resource group (for example, a cloud platform).

[0017] Information is input to, or output from, the information processing system 50 via the interface device 130.

[0018] The annealing machine 100 is one example of a parallel processing device (a device capable of parallel processing) and is an accelerator for solving an allocation problem by computing an interaction model (typically, an annealing processing model like an Ising model). The annealing machine 100 may be implemented by a CPU (Central Processing Unit) which has a plurality of physical or virtual cores; however, the annealing machine 100 is typically a hardware circuit such as an ASIC (Application Specific Integrated Circuit), an FPGA (Field-Programmable Gate Array), or a GPU (Graphics Processing Unit). The annealing machine 100 may be, for example, a semiconductor computer (for example, a CMOS annealing machine) which has a semiconductor circuit (for example, a CMOS (Complementary Metal Oxide Semiconductor) circuit) perform simulated reproduction of operations of the Ising model.

[0019] A processing support unit 125 is implemented by the processor 150 by executing a computer program stored in the storage apparatus 140.

[0020] The information processing system 50 performs, for example, inputting and processing as indicated with white arrows in the drawing. Specifically speaking, the processing support unit 125 accepts allocation problem input information 160 and stores it in the storage apparatus 140. The allocation problem input information 160 includes: information indicating an allocation object quantity a (a: an integer equal to or more than 2); and information indicating an allocation destination quantity P(f: an integer equal to or more than 2). The processing support unit 125 transforms a mathematical model of an allocation problem, which allocates a allocation object(s) to P allocation destination(s), into an interaction model designed for the annealing machine 100 (for example, an Ising model) on the basis of the allocation problem input information 160. The processing support unit 125 sets device input information 170, which is information including the interaction model and is information to be input to the annealing machine 100, to the annealing machine 100. Consequently, the annealing machine 100 executes parallel processing for obtaining the optimum solution for the allocation problem on the basis of the device input information 170. Incidentally, to set the device input information 170, including the interaction model and a value set, to the annealing machine 100 may be for the annealing machine 100 to store the device input information 170 in an accessible storage area (for example, a memory). The annealing machine 100 can read the device input information 170, which is stored in the relevant storage area, from that storage area by receiving explicit notice from the processing support unit 125 or by regularly accessing the relevant storage area.

[0021] The information processing system 50 performs, for example, outputting and processing as indicated with gray arrows illustrated in the drawing. Specifically speaking, the annealing machine 100 returns processing result information 180, which indicates the result of the parallel processing (that is, the optimum solution for the allocation problem), to the processing support unit 125. The processing support unit 125 stores allocation solution output information 190, which is based on the processing result information 180, in the storage apparatus 140. The processing support unit 125 outputs allocation solution output information 190.

[0022] Each of an element(s) which can be an allocation object(s) and an element(s) which can be an allocation destination(s) can be an arbitrary element decided by a user.

[0023] Fig. 2 illustrates a configuration example of the processing support unit 125.

[0024] The processing support unit 125 includes: a first interface unit 201 for inputting/outputting information to/from the outside of the information processing system 50; a degree judgment unit 202 which performs a degree judgment; an input decision unit 203 which decides the device input information 170; a second interface unit 204 for inputting/outputting information to/from the annealing machine 100; and an output decision unit 205 which decides the allocation solution output information 190. The input decision unit 203 includes: a contraction unit 231which performs contraction processing; and a model compilation unit 232 which performs model compilation. Regarding the outside of the information processing system 50, various elements such as servers or portable storage media can be adopted. In this embodiment, the outside of the information processing system 50 is a user.

[0025] The details of these functions will be explained below along with a flow of processing executed by the processing support unit 125. An i-th allocation object can be expressed as an "allocation object i" (for example, i=1, 2, ... and so on and the maximum value of i is a) and a j-th allocation destination can be expressed as an "allocation destination j" (for example, j=1, 2, ... and so on and the maximum value of j is P).

[0026] The first interface unit 201 provides an input UI (User Interface) for the allocation problem input information 160. The input UI is, for example, a GUI (Graphical User Interface). Fig. 6 illustrates an example of an input UI 600. The allocation problem input information 160 is input via the input UI 600. Incidentally, the input of the allocation problem input information 160 may be other types of inputs (for example, input of a file (for example, a CSV file) including at least part of the allocation problem input information 160) instead of or in addition to the input via the input UI 600. Furthermore, the first interface unit 201 may manage a mathematical model(s) of the allocation problem in advance. The mathematical model(s) of the allocation problem may be set to the processing support unit 125 in advance as in this embodiment (for example, information indicating the mathematical model(s) of the allocation problem may be stored in the storage apparatus 140), but it may be input to the processing support unit 125 by other means. For example, the information indicating the mathematical model(s) of the allocation problem may be included in the allocation problem input information 160.

[0027] The allocation problem input information 160 includes, from among basic information (one example of first information) and detailed information (one example of second information), at least the basic information.

[0028] The basic information is information including information (A) to (C) mentioned below (one example is as illustrated in Fig. 6). Regarding the following information (A) to (C), each of a and P is a natural number and may be typically an integer equal to or more than 2. L is also a natural number and may be an integer equal to or more than 2. Specifically speaking, in this embodiment, it is possible to solve a relatively easy allocation problem regarding which at least one of the values a, P and L is 1; and it is also useful in solving a relatively complicated allocation problem regarding which each one of the values a, P, and L is an integer equal to or more than 2. (A) Information indicating the allocation object quantity a. (B) Information indicating the allocation destination quantity. (C) Information indicating the allowable quantity L of an allocation destination.

[0029] The detailed information is information other than the basic information among the allocation problem input information 160. The user's input (input by the user) of information which is at least part of the detailed information may be optional. Default information may be adopted regarding information which is not input by the user among the detailed information. For example, if the detailed information includes, with respect to each pair of an allocation object and an allocation destination, information indicating the cost of allocation from the allocation object to the allocation destination and the information indicating the allocation cost with respect to 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 information (D) and (E) mentioned below (one example is as illustrated in Fig. 6). Incidentally, both the information (D) and (E) may possibly correspond to either coefficient impact information or coefficient non impact information, depending on which processing of (Processing A) through (Processing C) described later is adopted (i.e., what kind of contraction processing is performed). For example, if (Processing A) is adopted, each of the information (D) and (E) is adopted as a constraint term and, therefore, may become the coefficient impact information. On the other hand, if either one of (Processing B) and (Processing C) is adopted, both the information (D) and (E) may possibly become the coefficient non impact information. (D) Detailed allocation destination information indicating the details of the allocation destination(s) (for example, information indicating an allowable amount of an allocation destination m (m>0)). (E) Detailed allocation object information indicating the details of the allocation object(s) (for example, a resource amount of each allocation object).

[0030] According to the example illustrated in Fig. 6, the allocation problem input information 160 includes the basic information, the detailed allocation destination information, and the detailed allocation object information. The basic information is the aforementioned information (A) through (C). The detailed allocation destination information is the aforementioned information (D).

[0031] The allowable quantity L is an upper limit of the allocation object quantity which can be allocated to one allocation destination and is a degree M itself of an objective function term in the mathematical model of the allocation problem. The allowable amount m is a value of the type according to the type of the allocation destination and is a value related to an allocation constraint of the allocation object; and specifically, the allowable amount m is used as a constraint term of an M-th degree interaction model or a constraint condition for the model after reduction of the degree when input to the annealing machine by the processing described later. For example, as illustrated in Fig. 6, if allocation objects are virtual OS's (Operating Systems) and allocation destinations are servers, the allowable quantity L may be decided from a resource amount (for example, a memory capacity) of the relevant server. For example, the resource amount required for each virtual OS is m=30 and the resource amount of the relevant server (which is included in the detailed information) is 90, the allowable quantity may be L=3 (90+30) and L is equivalent to the degree M. Incidentally, in this embodiment, the allowable quantity L and the allowable amount m are in common with all the allocation destinations; however, the allowable quantity L and the allowable amount m do not have to be the same regarding all the allocation destinations. For example, the information indicating the allowable quantity 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 degree M.

[0032] The detailed information includes, for example, at least one of the following (dl) and (d2): (dl) coefficient impact information that is information which will impact one or more coefficient values (one or more coefficient values of one or more allocation status variables) in the interaction model; and (d2) coefficient non-impact information that is information which will not impact the coefficient value(s) in the interaction model.

[0033] The "allocation status variable(s)" exists for each pair of the allocation object i and the allocation destination j and is a variable indicating the allocation status of the allocation object i to the allocation destination j. For example, the value of the allocation status variable may be expressed as either a binary value or multiple values. If the binary value is adopted, the allocation status may indicate whether the allocation object i is allocated to the allocation destination j or not ("1" or "0"). If the multiple values are adopted, other types of statuses can be expressed as the allocation status in addition to whether the allocation object i is allocated to the allocation destination j or not.

[0034] The coefficient impact information may be, for example, at least one of information (x) and (y) mentioned below. Incidentally, regarding (x) and (y) below, an arbitrary relation such as similarity or appropriateness can be adopted as the "relation." An example of the coefficient value of the allocation status variable is, for example, the value of an interaction coefficient (for example, C in C(aijxorj)) or the value of an external field coefficient (a coefficient in a primary formula or D in D(aijxaij)). Incidentally, "oij" is a variable indicating the allocation status of the allocation object i to the allocation destination j; "aijxai" means the product of allocation statuses of different groups of allocation objects and allocation destinations; and "aijxaij" means the product of allocation statuses of the same group of an allocation object and an allocation destination. (x) Information including a numerical value indicating the relation between an allocation object and an allocation destination (for example, the information illustrated in Fig. 3). For example, as one example of the numerical value indicating the relation between the allocation object i and the allocation destination j, it is possible to adopt probability of obtaining a given result when the allocation object i is allocated to the allocation destination j. (y) Information including a numerical value indicating the relation between an allocation object and an allocation object (for example, the information illustrated in Fig. 4). For example, as one example of the numerical value indicating the relation between the allocation object i and an allocation object (i+u) (u>), it is possible to adopt the difference between a feature value of one or more elements possessed by the allocation object i and a feature value of one or more elements possessed by the allocation object (i+u).

[0035] The coefficient non-impact information is information (for example, the number of auxiliary spins) which is required for contraction processing (processing for transforming a high-order mathematical model of the allocation problem into a low order mathematical model of the allocation problem); and specifically, for example, the coefficient non-impact information is information indicating a constraint condition(s) of the high-order (degree M) mathematical model of the allocation problem. The coefficient non-impact information may not be explicitly included in the interaction model after the contraction processing explained below, but it will be utilized as meta information used to decide a coefficient value(s) in the mathematical model of the allocation problem after the contraction processing. Incidentally, a constraint term(s) regarding the interaction model at the stage of being read to the annealing machine 100 (the interaction model on which the contraction processing has already been executed or which does not require the contraction processing) is information included in the coefficient impact information, so that it is different from (or distinguished from) the "constraint condition(s)" in this paragraph.

[0036] The first interface unit 201 inputs the information indicating a and P and the mathematical model of the allocation problem to the model compilation unit 232 and inputs the information indicating L to the degree judgment unit 202. If there is the detailed information (for example, information including the allowable amount m), the first interface unit 201 inputs the mathematical model of the allocation problem and the detailed information to the contraction unit 231.

[0037] The degree judgment unit 202 performs a degree judgment to judge whether the degree M which satisfies L indicated by the input information (the degree M of the objective function term in the mathematical model of the allocation problem) is equal to or less than a specified value or not. The processing by the processing support unit 125 varies depending on the result of the degree judgment. The "specified value" to be compared with the degree M may be, for example, a value which is set by the user via the first interface unit 201.

[0038] If the degree M is equal to or less than the specified value (that is, if the result of the degree judgment is true), the model compilation is performed without the contraction processing described later. Specifically speaking, the degree judgment unit 202 gives an instruction to the model compilation unit 232 to perform the model compilation. As a result, if the degree M is equal to or less than the specified value, the model compilation unit 232 receives the model compilation instruction from the degree judgment unit 202. When receiving the model compilation instruction from the degree judgment unit 202, the model compilation unit 232 transforms the mathematical model of the allocation problem into the interaction model. One example of the mathematical model of the allocation problem is Math. 1 to Math. 4 mentioned below and one example of the interaction model is Math. 5 mentioned below. Regarding the mathematical model of the allocation problem, Math. 1 is an objective function (minimization) and Math. 2 to Math. 4 are constraint conditions. In Math. 1 to Math. 5, oli represents a value indicating the allocation status of the allocation object i to the allocation destination j. In the mathematical model of the allocation problem (for example, Math. 1), it is assumed to minimize the product of allocated resources per allocation destination so that the load on the allocation destination will be reduced. In the case where the degree M is equal to or less than the specified value, the reduction of the degree M is unnecessary because the contraction processing will not be performed; and, therefore, it is unnecessary to transform the value of the allocation status variable from a binary value into multiple values in order to reduce the number of the allocation status variables for the purpose of reducing the degree.

[Math. 1]

ZR jEf€ HCYk kEM ikEa CikIik

[Math. 2]

iEa

[Math. 3]

[Math. 4]

E {Oij {,1}

[Math. 5]

H(tU)= CikiJ7j + (M J2 - j +y 1 - )2 jEI kEM ikEa jEf iEa jEf iCa

[0039] If the degree M exceeds the specified value (that is, if the result of the degree judgment is false), the contraction processing is executed and then the model compilation is performed. Specifically speaking, the degree judgment unit 202 issues an instruction to the contraction unit 231 to perform the contraction processing. Incidentally, the specified value to be compared with the degree M may be, for example, any one of the following. - A value which is decided at a designing stage of the annealing machine 1000 and is defined in the degree judgment unit 202. - A value which is input by the user (for example, input via the input UI 600). This value is a value whose upper limit is the maximum degree manageable by the annealing machine 100. For example, the input UI 600 may include a GUI component which accepts a value equal to or less than the maximum degree manageable by the annealing machine 100 as the specified value to be compared with the degree M. The first interface unit 201 notifies the degree judgment unit 202 of the input specified value. - A value identified by the degree judgment unit 202 by the following processing. Specifically speaking, the degree judgment unit 202 identifies the relevant specified value from information (for example, a table) indicating the relation between attributes of the annealing machine (for example, a model number and a vendor) and the specified value to be compared with the degree M by using the attributes of the annealing machine 100 (for example, the model number and the vendor) as keys.

[0040] When receiving the contraction processing instruction, the contraction unit 231 performs the contraction processing. The contraction processing is to reduce the degree M of the mathematical model of the allocation problem to a degree M'. The contraction unit 231 issues an instruction to the model compilation unit 232 to perform the model compilation and inputs the mathematical model after the contraction processing (the mathematical model after the degree reduction) to the model compilation unit 232. As a result, if the degree M exceeds the specified value, the model compilation unit 232 receives the model compilation instruction from the contraction unit 231. When receiving the model compilation instruction from the contraction unit 231, the model compilation unit 232 transforms the mathematical model after the contraction processing into the interaction model. Incidentally, the value of M' is the same value as (or smaller value than) the aforementioned specified value to be compared with the degree M. Specifically speaking, that specified value corresponds to the upper limit of the degree with regard to the mathematical model after the contraction processing and the degree M is reduced to that upper limit (or smaller value) by the contraction processing.

[0041] For example, the contraction processing includes at least one processing of the following (Processing A) through (Processing C). The degree M is reduced to the degree M' by at least one of (Processing A) through (Processing C). (Processing A) for transforming a mathematical model in a HOBO (Higher Order Binary Optimization) format into a mathematical model in a QUBO (Quadratic Unconstrained Binary Optimization) format. (Processing B) for deciding one or more coefficient values in the interaction model on the basis of the coefficient impact information (for example, at least one of the information illustrated in Fig. 3 and the information illustrated in Fig. 4) in the detailed information. (Processing C) for changing the expression of the value(s) of the allocation status variable(s) in the interaction model from a binary value to multiple values.

[0042] For example, the contraction processing may be as follows. S1: the contraction unit 231 selects any one of unselected processing among (Processing A) through (Processing C) and performs the selected processing in S1. S2: the contraction unit 231 judges if S1 results in M=M' or not. If the judgment result of S2 is true, the processing terminates. If the judgment result of S2 is false, the contraction unit 231 performs S1.

[0043] Incidentally, for example, if the annealing machine 100 has a sufficient memory, the priority order of the processing to be selected may be (Processing C) > (Processing A) > (Processing B). Specifically speaking, (Processing C) may be selected preferentially. Specifically speaking, the first processing to be selected in S1 may be (Processing C). Examples of the reasons may be as follows. - The reason why (Processing C) has the first priority order is, for example, as follows: (Processing C) has the highest hardware dependency of annealing machines (i.e., has high limitations on applicable machines) and it is thereby highly possible that (Processing C) may become inapplicable; however, it has the highest spin reduction effect. - The reason why (Processing A) has the second priority order is, for example, as follows: regarding a quartic or higher degree problem with a large number of spins before the transformation, the accuracy or the number of spins after the transformation may possibly suddenly turn to a bad direction, whether (Processing A) should be selected or not is decided based on the degree or the number of spins; however, (Processing A) is capable of transformation with a relatively low load. - The reason why (Processing B) has the third priority order is, for example, as follows: (Processing B) has relatively high versatility, but it requires preprocessing on a CPU, so that it may take much time for the processing.

[0044] Alternatively, the priority order of (Processing A) through (Processing C) to be selected may be in ascending order of the required number of spins (the number of spins of the model after the transformation, that is, memory usage of the annealing machine). Specifically speaking, the first processing to be selected in S1 from among (Processing A) through (Processing C) may be the processing with the smallest required number of spins.

[0045] One example of (Processing A) is as follows. Specifically speaking, a mathematical model in the HOBO format (for example, Math. 1 to Math. 4) is transformed into a mathematical model in the QUBO format (for example, Math. 6 to Math. 11) by using

that oli is the binary variable. For example, in a case of M4, (Processing A) is applied

(the value "4" to be compared with M is one example and the value to be compared may be a value close to "4" (a value with the difference from "4" may be equal to or less than a specified value)). Regarding the mathematical model in the QUBO format, Math. 6 is an objective function (minimization), Math. 7 is a first constraint condition, and Math. 8 to Math. 11 are second constraint conditions. According to Math. 6 to Math. 11, an auxiliary spin qij and a penalty factor v for the QUBO model to reproduce the original HOBO model are introduced. Incidentally, Math. 6 to Math. 11 are written in a common format and the number of auxiliary spins y and the penalty factor v after the QUBO transformation vary depending on a transformation method. The penalty factors v and v' are set so that no contradiction will occur when the first constraint condition is applied to in Math. 6 (the objective function). Since a method for deciding the penalty factor has arbitrariness, it can be arbitrarily set by the user according to the circumstances (for example, the input UI 600 may have a GUI component for accepting input of the penalty factors v and v'). Math. 6 to Math. 11 are input as mathematical models after the degree reduction and are transformed into an interaction model (Math. 13).

[Math. 6]

j]Ef kEM ikEa

[Math. 7]

I1 kEM =ii::::VlZ'ikI~aik.i +q, kEEM,kiEM k'kEM (aiki+ Uk

[Math. 8]

iea

[Math. 9]

[Math. 10] qf E {0,1}

[Math. 11]

eEij {0,1}

[Math. 12]

H ({f-}

I I CijCio 1 1 [voj 0 jj 1 +v'qi(aij + ailj)| jEfpi 1 EaioEalEy +A(M o +p 1Y - nio jegf iEa jEf3 iEa

[0046] One example of (Processing B) is as follows.

[0047] For example, if the information illustrated in Fig. 3 (the information indicating the relation between the allocation objects and the allocation destinations) is interaction coefficients in Math. 1 to Math. 4, the contraction unit 231 lists combinations of N patterns (N: a natural number) which always satisfy the constraint conditions in Math. 1 to Math. 4 among the values of the spins oi in Math. 1 to Math. 4. The contraction unit 231 transforms a mathematical model indicating which combination should be selected from among the N patterns of combinations, into a mathematical model of a "set partitioning problem or set covering problem" where the number of spins qt is a variable. Specifically, for example, Math. 1 to Math. 4 are transformed into Math. 13 to Math. 15. Math. 13 to Math. 15 are one example of the mathematical model(s) after the degree reduction. Math. 13 is an objective function (minimization) and Math. 14 to Math. 15 are constraint conditions. Although r't in Math. 13 to Math. 15 corresponds to the number of spins in its original models (Math. 1 to Math. 4), it is not a variable, but a constant. The variable in this model after the transformation is qt. The number N of the variable q is, among all combinations, the number of combinations that remain after eliminating those which have C smaller than a threshold value, or eliminating r indicating a combination(s) which does not satisfy the constraints. Accordingly, as a result, (Processing B) contributes to the degree reduction. Math. 13 to Math. 15 are input as models after the degree reduction to the model compilation unit 232 and are transformed into interaction models (Math. 16 to Math. 17). (Processing B) is also effective in a case of M>4. Furthermore, in the following examples, the auxiliary spin is a binary value; however, if hardware (the annealing machine 100) is compatible, the auxiliary spin(s) may be continuous values.

[Math. 13]

I[H7Cry'rit ]t tEN -riea

[Math. 14]

Y,~'rtItr=qt tEN

[Math. 15]

qt E{,1}

[Math. 16]

H = Ptqt + ''rtqt 1 t EN T Ea+l t EN )

[Math. 17]

Pt =7CrI'rrt r/Ea

[0048] Furthermore, for example, if the information illustrated in Fig. 4 (the information indicating the relation between the allocation objects) is the interaction coefficients in Math. 1 to Math. 4, the transformation into the "set partitioning problem or set covering problem" is performed in the same manner as with Math. 13 to Math. 15. For example, Math. 1 to Math. 4 are transformed into Math. 18 to Math. 20. Math. 18 to Math. 20 are one example of the mathematical model(s) after the degree reduction. Math. 18 is an objective function (minimization) and Math. 19 to Math. 20 are constraint conditions. A method for deriving Math. 18 to Math. 20 is similar to that for Math. 13 to Math. 15. Accordingly, as a result, (Processing B) contributes to the degree reduction. Math. 18 to Math. 20 are input as mathematical models after the degree reduction to the model compilation unit 232 and are transformed into interaction models (Math. 21 to Math. 22).

[Math. 18]

fICtu's~t qt tEN -riEa

[Math. 19]

Srtqt=1 tEN

[Math. 20]

qt E0,1

[Math. 21]

2

H ({})= Q + J'rtqt- )

tEN rEa+l \tEN/

[Math. 22]

Qt= Cta'rit rEa

[0049] Furthermore, for example, as the contraction unit 231 uses both the information illustrated in Fig. 3 and the information illustrated in Fig. 4, for example, Math. 1 to Math.

4 are transformed into Math. 23 to Math. 25. Math. 23 to Math. 25 are one example of the mathematical model(s) after the degree reduction. Math. 23 is an objective function (minimization) and Math. 24 to Math. 25 and constraint conditions. A method for deriving Math. 23 to Math. 25 is similar to that for Math. 13 to Math. 15. Accordingly, as a result, (Processing B) contributes to the degree reduction. Math. 23 to Math. 25 are input as mathematical models after the degree reduction to the model compilation unit 232 and are transformed into interaction models (Math. 26 to Math. 27).

[Math. 23]

CritJr'rrt qt tEN rrEa

[Math. 24]

1 -'Irtqt= tE N

[Math. 25]

qt E 0,1j

[Math. 26]

H ([o})= Rtqt + ( Irtqrt - 1 tEN rEa+/ tEN

[Math. 27]

Rt = Ctrlr'rrt rrEa

[0050] One example of (Processing C) is as follows. Specifically speaking, for example, Math. 1 to Math. 4 are transformed into Math. 28. Math. 28 is one example of an expression of the mathematical model after the degree reduction. Here, for example, spin addresses r and t of the objective function are made variables based on the mathematical models of Math. 23 to Math. 25. If a domain of the variables is set, the constraint conditions in Math. 23 to Math. 25 (that is, Math. 24 and Math. 25) will become no longer necessary. Accordingly, as a result, (Processing C) contributes to the degree reduction. Math. 28 is input as the mathematical model after the degree reduction to the model compilation unit 232 and is transformed into the interaction model (Math. 29). Incidentally, (Processing C) cannot be executed on hardware where the spin value can be only a binary value.

[Math. 28]

CrtU'rt t EN -r Ea+f

[Math. 29]

H (r, t) =Ctr 07'r t tEN rE a+f

[0051] Whether the contraction processing is executed or not is decided as described above depending on whether the result of the degree judgment is true or false. The model compilation is performed without or after executing the contraction processing. Specifically speaking, each mathematical model after the degree reduction like Math. 6 to Math. 11, Math. 13 to 15, Math. 18 to Math. 20, Math. 23 to Math. 25, or Math. 28 is transformed into the interaction model like Math. 12, Math. 16 to Math. 17, Math. 21 to Math. 22, Math. 26 to Math. 27, or Math. 29. At first glance, the interaction models seem to be respectively different expressions; however, once the mathematical model(s) is decided, all the interaction models can be found in the same procedure as the sum of the objective function and constraint terms expressed as quadratic formulas.

[0052] The detailed information may possibly include the coefficient non-impact information instead of or in addition to the coefficient impact information illustrated in Fig. 3 and Fig. 4. The coefficient non-impact information is used for the transformation into the interaction model which is contracted by the processing at the contraction unit 231.

[0053] For example, the coefficient non-impact information includes information indicating a constraint condition(s) in a model(s) before the contraction. The constraint condition(s) is reflected in the mathematical model of the allocation problem at the first interface unit 201 and the mathematical model of the allocation problem in which the constraint condition is reflected is output from the first interface unit 201.

[0054] Furthermore, for example, the coefficient non-impact information may include information indicating K (K: a natural number). K is the maximum number of allocation objects i-k (k: a natural number equal to or less than N) which can be allocated from one allocation object i. Specifically speaking, the maximum N number of the allocation objects i-k can be also allocated from one allocation object i to one or a plurality of allocation destinations. In this case, K is reflected as spins and a penalty term in a mathematical model in the QUBO format in the contraction processing.

[0055] The model compilation unit 232 outputs the device input information 170 including an interaction model(s) and a value set. The second interface unit 204 receives such device input information 170 and sets it to the annealing machine 100. The interaction model(s) is a model obtained by the model compilation. The value set is a set of values used to compute the interaction model and includes, for example, a coefficient value and an address value with respect to each allocation status variable in the interaction model. The coefficient value(s) in the value set is mapped to inside the annealing machine 100 (the address corresponding to the relevant coefficient value) by a control circuit, which is not illustrated in the drawing, in the annealing machine 100.

[0056] The annealing machine 100 calculates proposed allocation (the allocation status value for each pair of the allocation object i and the allocation destination j) by executing computation to find an energy ground state of the interaction model and outputs the processing result information 180, which is information indicating the proposed allocation, to the processing support unit 125. Incidentally, the processing support unit 125 can receive this output as a response to the setting of the interaction model and the value set to the annealing machine 100. The processing support unit 125 can find a final spin value from the processing result information 180.

[0057]

The second interface unit 204 accepts the processing result information 180 from the annealing machine 100 and outputs that processing result information 180 to the output decision unit 205. The output decision unit 205 generates the 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 (for example, the user's information processing terminal). For example, as illustrated in Fig. 7, an output UI 700 on which an allocation solution indicated by the allocation solution output information 190 is provided. The output UI 700 displays the allocation result indicated by the allocation solution output information 190 (the result of which allocation object is allocated to which allocation destination at what kind of allocation cost). The output of the allocation solution output information 190 may be other types of outputs (for example, output of a file (such as a CSV file) including at least part of the allocation solution output information 190) instead of or in addition to the output via the output UI 700.

[0058] Fig. 5 illustrates one example of a flow of processing executed by the information processing system.

[0059] In S501, the first interface unit 201 accepts input of the allocation problem input information 160. The first interface unit 201 stores the allocation problem input information 160 in the storage apparatus 140.

[0060] In S502, the degree judgment unit 202 identifies the degree M on the basis of the information required for the degree judgment (the information including the allowable quantity L), from among the allocation problem input information 160 in the storage apparatus 140, and judges whether the degree M is equal to or less than a specified value or not.

[0061] If the judgment result in S502 is false, the contraction unit 231 perform the aforementioned contraction processing in S503.

[0062] If the judgment result of S502 is true or after the contraction processing in S503, the model compilation unit 232 performs the model compilation in S504. A model before the model compilation is a mathematical model after the contraction processing (a mathematical model of the degree M') or a mathematical model on which the contraction processing has not been executed (a mathematical model of the degree M). The model after the model compilation is an interaction model. In the model compilation, the value of a (the allocation object quantity) and the value of P (the allocation destination quantity) in the allocation problem input information 160 are also used. Furthermore, in the model compilation, at least part of the detailed information in the allocation problem input information 160 may be used. The value set regarding the interaction model is also obtained by the model compilation.

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

[0064] In S506, the annealing machine 100 performs parallel processing (to perform parallel computation of the interaction model by using the value set) on the basis of the device input information 170.

[0065] In S507, the annealing machine 100 outputs the processing result information 180.

[0066] In S508, the second interface unit 204 accepts the processing result information 180 from the annealing machine 100 and outputs that processing result information 180 to the output decision unit 205. The output decision unit 205 generates the allocation solution output information 190 on the basis of 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, the user's information processing terminal).

[0067] One embodiment has been explained above; however, this is illustrative for the purpose of explaining the present invention and it is not intended to limit the scope of the present invention to only this embodiment. The present invention can be also implemented in various other forms.

[0068] For example, the annealing machine 100 does not have to be limited to a hardware circuit such as an ASIC, an FPGA, or a GPU.

[0069] Furthermore, for example, the interaction model may be a neural network or a Boltzmann machine.

[0070] Furthermore, the "constraint conditions" in Math. 1 to Math. 29 mentioned earlier may be the coefficient non-impact information among the detailed information of the allocation problem input information 160.

[0071] Furthermore, forexample, a pluralityof GUI components for accepting the user's inputs may exist in one input UI 600 or may be dispersed in a plurality of UI's (the GUI components are one example of the UI components). Furthermore, for example, the UI which indicates the allocation solution output information 190 may be one output UI 700 or a plurality of Ul's.

[0072] Furthermore, for example, the second interface unit 204 may provide the device input information 170, including the interaction model and the value set, to the outside of the information processing system 50 (for example, the user's information processing terminal) instead of or in addition to setting the device input information 170 to the annealing machine 100.

[0072a] Throughout this specification and the claims which follow, unless the context requires otherwise, the word "comprise", and variations such as "comprises" and "comprising", will be understood to imply the inclusion of a stated integer or step or group of integers or steps but not the exclusion of any other integer or step or group of integers or steps.

[0072b] The reference in this specification to any prior publication (or information derived from it), or to any matter which is known, is not, and should not be taken as an acknowledgment or admission or any form of suggestion that that prior publication (or information derived from it) or known matter forms part of the common general knowledge in the field of endeavour to which this specification relates.

REFERENCE SIGNS LIST

[0073] 50: information processing system

Claims

THE CLAIMS DEFINING THE INVENTION AREAS FOLLOWS:

[Claim 1] An information processing system comprising: a first interface unit that accepts information allocation object quantity information indicating an allocation object quantity a (a: a natural number), allocation destination quantity information indicating an allocation destination quantity P (P: a natural number), and an allowable quantity L (L: a natural number) which is an upper limit of an allocation object quantity which can be allocated to one allocation destination; a degree judgment unit that performs a degree judgment to judge whether or not M which corresponds to a degree of a mathematical model of an allocation problem to allocate a allocation object or objects to P allocation destination or destinations and which satisfies L is equal to or less than a specified value; an input decision unit that decides an interaction model designed for an annealing machine, which is an accelerator to solve the allocation problem by computing the interaction model on the basis of a result of the degree judgment, a, and P, and a value set which is a set of values used to compute the interaction model; and a second interface unit that provides the decided interaction model and the decided value set.
[Claim 2] The information processing system according to claim 1, wherein if the result of the degree judgment is false, the input decision unit performs contraction processing for deciding a degree M', which is lower than M, and decides the interaction model and the value set on the basis of a mathematical model of the degree M' decided by the contraction processing.
[Claim 3] The information processing system according to claim 2, wherein the first interface unit further accepts coefficient impact information that is information which impacts one or more coefficient values of one or more allocation status variables in the interaction model; and wherein the contraction processing includes deciding the one or more coefficient values on the basis of the coefficient impact information.
[Claim 4] The information processing system according to claim 3, wherein the coefficient impact information is information including a numerical value indicating a relation between an allocation object and an allocation destination.
[Claim 5] The information processing system according to claim 3, wherein the coefficient impact information is information including a numerical value indicating a relation between an allocation object and an allocation object.
[Claim 6] The information processing system according to claim 2, wherein the contraction processing includes at least one processing of (Processing A) through (Processing C) described below: (Processing A) for transforming a mathematical model in a HOBO (Higher Order Binary Optimization) format into a mathematical model in a QUBO (Quadratic Unconstrained Binary Optimization) format; (Processing B) for deciding one or more coefficient values in the interaction model on the basis of coefficient impact information that is information which impacts one or more coefficient values of one or more allocation status variables in the interaction model; and (Processing C) for changing an expression of a value of the allocation status variable in the interaction model from a binary value to multiple values; and wherein the input decision unit selects processing capable of reducing the degree M to the degree M'from among (Processing A) through (Processing C).
[Claim 7] The information processing system according to claim 6, wherein (Processing C), (Processing B), and (Processing A) are listed in descending order of a priority order to be selected.
[Claim 8] The information processing system according to claim 6, wherein a priority order of (Processing A) through (Processing C) to be selected becomes lower in ascending order of a required number of spins which is a number of spins of a model after transformation and is memory usage of the annealing machine.
[Claim 9] The information processing system according to claim 2, wherein the first interface unit further accepts coefficient non-impact information that is information which does not impact one or more coefficient values of one or more allocation status variables in the interaction model, and is information which is used in the contraction processing and indicates a constraint condition for the mathematical model of the degree M; and wherein the input decision unit performs the contraction processing by using the coefficient non-impact information.
[Claim 10] The information processing system according to claim 1, further comprising the annealing machine, wherein the annealing machine reads the interaction model and the value set, which are provided, solves the allocation problem by computing the interaction model by using the value set, and outputs processing result information which indicates an optimum solution of the allocation problem.
[Claim 11] An information processing method comprising: accepting, by a computer, information allocation object quantity information indicating an allocation object quantity a (a: a natural number), allocation destination quantity information indicating an allocation destination quantity P (P: a natural number), and an allowable quantity L (L: a natural number) which is an upper limit of an allocation object quantity which can be allocated to one allocation destination; performing, by the computer, a degree judgment to judge whether or not M which corresponds to a degree of a mathematical model of an allocation problem to allocate a allocation object or objects to P allocation destination or destinations and which satisfies L is equal to or less than a specified value; deciding, by the computer, an interaction model designed for an annealing machine, which is an accelerator to solve the allocation problem by computing the interaction model on the basis of a result of the degree judgment, a, and P, and a value set which is a set of values used to compute the interaction model; and providing, by the computer, the decided interaction model and the decided value set.