SEARCH DEVICE, SEARCH METHOD, AND SEARCH PROGRAM

The search means 91 searches for an optimization problem matching a specified search condition from a database that stores search information that associates first data indicating an optimization problem including an objective function and a constraint with second data indicating a feature of the optimization problem. The input means 92 accepts input of the second data as search condition.

TECHNICAL FIELD

This invention relates to a search device, a search method, and a search program for searching registered information.

BACKGROUND ART

Patent Literature 1 describes a device for selecting one or more machine learning models from multiple machines learning models stored in a database in advance and providing them to a user device in response to a usage request obtained from the user device. In the method described in Patent Literature 1, the performance of each model is calculated by applying test data to each of multiple machine learning models stored in a database, and the machine learning model to be provided to the user-side device is selected based on the calculated performance.

CITATION LIST

Patent Literature

PL 1: International Publication 2018/142766

SUMMARY OF INVENTION

Technical Problem

The machine learning model described in Patent Literature 1 is assumed to be a predictive model generated by machine learning based on learning data and correct answer data, but it is not assumed that it will be used for decision making such as combinatorial optimization problem.

Therefore, it is an exemplary object of the present invention to provide a search device, a search method, and a search program capable of searching for desired an optimization problem.

Solution to Problem

A search device according to the present invention including: a search means which searches for an optimization problem matching a specified search condition from a database that stores search information that associates first data indicating an optimization problem including an objective function and a constraint with second data indicating a feature of the optimization problem; and an input means which accepts input of the second data as search condition, wherein the search means searches for the first data associated with the search information matching the input second data.

A search method according to the present invention including: accepting input of a feature of an optimization problem as a search condition, by a computer; and searching for an optimization problem associated with search information matching the input feature of the optimization problem from a database that stores search information that associates first data indicating an optimization problem including an objective function and a constraint with second data indicating a feature of the optimization problem, by the computer.

A search program according to the present invention for causing a computer to execute: search process for searching for an optimization problem matching a specified search condition from a database that stores search information that associates first data indicating an optimization problem including an objective function and a constraint with second data indicating a feature of the optimization problem; and input process for accepting input of the second data as search condition, wherein the first data associated with the search information matching the input second data is searched, in the search process.

Advantageous Effects of Invention

According to the present invention, it is possible to search for desired an optimization problem.

DESCRIPTION OF EMBODIMENTS

The following is a description of an exemplary embodiment of the present invention with reference to the drawings.

FIG.1is a block diagram illustrating a configuration example of one exemplary embodiment of an information distribution system according to the present invention. An information distribution system1in this exemplary embodiment includes an information generation device100, a search device200, and a storage server300. The information generation device100, the search device200, and the storage server300are mutually connected through communication lines.

The information generation device100is a device that generates information (hereinafter referred to as “search information”) used by the search device200, described below, to search for optimization problem. The optimization problem in this exemplary embodiment includes an objective function (more specifically, the structure of the objective function) and constraint conditions formulated for the problem to be solved. Therefore, it can be said that the optimization problem in this exemplary embodiment represents the type of decision-making by a user for the problem to be solved. The method of generating search information is described below.

FIG.2is an explanatory diagram showing an example of types of decision-making (i.e., the optimization problem). The example shown inFIG.2indicates that the type of problem to be solved is classified as a so-called “shift scheduling problem” and that the optimization problem includes an objective function specified by a linear sum of the degrees of violation (explanatory variables) of three conditions (conditions1,2, and3) and two constraint conditions (conditions4and5).

In addition, the objective function À illustrated inFIG.2is a value that indicates the degree to which the user attaches importance to the condition (sometimes also referred to as the user's intention), and is set to various values depending on the type of decision-making. By searching for combinations that minimize the value of this objective function, it becomes possible to derive appropriate actions.

The storage server300stores search information generated by the information generation device100. The storage server300may manage the search information using, for example, a general data base (database system). Furthermore, the storage server300may store search information generated by a device other than the information generation device100.

The search device200searches for optimization problem using the search information stored in the storage server300(more specifically, the database of the storage server300). The search device200also uses the searched optimization problem to derive the optimal action of the user.

Specific configuration examples of the information generation device100and the search device200will be described below.

FIG.3is a block diagram illustrating a configuration example of an information generation device100. The information generation device100of this exemplary embodiment includes a storage unit110, an input unit120, a feature generation unit130, a recommendation unit140, a learning unit150, a generation unit160, and a registration unit170.

The storage unit110stores various information used by the information generation device100to perform processing. The storage unit110may store training data, a parameter, learning result, and other information used in the learning process by the learning unit150described below. The storage unit110is realized by, for example, a magnetic disk.

The input unit120accepts input of various types of information used in generating search information. Specifically, the input unit120accepts input of information indicating an optimization problem that includes an objective function and a constraint (hereinafter referred to as “first data”), and information indicating a feature of the optimization problem (hereinafter referred to as “second data”).

The input unit120may accept input of the first data and the second data from the user. The input unit120may also accept input of an objective function generated by the learning unit150(more specifically, an objective function stored in the storage unit110), as described below. The input unit120may also accept input of the second data (i.e., information indicating a feature of the optimization problem) from the feature generation unit130described below.

In addition, the input unit120may accept input of an optimization solver (or information identifying the optimization solver) as a candidate for solving the optimization problem, along with the first data. Examples of optimization solvers include, for example, mathematical programming solver.

For example, a user inputting an optimization problem often understands the appropriate optimization solver to solve that optimization problem. Therefore, by accepting the input of such information along with the first data, it is possible for a user who searches for an optimization problem by using the search device200, described below, to understand the optimization solver to be used for that optimization problem.

The first data represents information that indicates the optimization problem, such as the structure of the objective function and conditions that indicate constraints, as described above. The form of the objective function is arbitrary. For example, as illustrated inFIG.2, it may be a function expressed as a linear sum of explanatory variable (condition). The form of the constraint is also arbitrary, and may be information that specifies whether the constraint is satisfied or not by a binary value, or may be information that indicates the degree to which the constraint is satisfied.

The second data can be any content that indicates the feature of the optimization problem. However, the second data need not be information that uniquely identifies the optimization problem. The feature of the optimization problem includes, for example, the type of the optimization problem, attribute information such as the explanatory variable (feature) included, optimization status indicating when, where, who, and what kind of decision is being made, and usage conditions such as the range of available (public) target person and dates.

The type of optimization problem may be a template type of optimization problem, for example, a schedule optimization problem or a knapsack problem, or the type of industry used (e.g., retail, manufacturing, travel, etc.).

The feature generation unit130generates feature for the optimization problem. Specifically, the feature generation unit130generates the second data described above from the first data. The method by which the feature generation unit130generates the second data is arbitrary. The feature generation unit130may, for example, automatically generate the second data based on a predetermined method, or may generate the second data based on a designation from the user.

For example, when the objective function is expressed as a linear sum of the explanatory variable described above, the feature generation unit130may generate the feature of the optimization problem according to the weight (i.e., the degree of emphasis) of the explanatory variable included in that objective function. For example, the feature generation unit130may generate the content of the explanatory variable with the largest weight as a feature of the optimization problem.

Further, for example, when an explanatory variable is explicitly specified by a user (e.g., a feature that is not used in other optimization problems), the feature generation unit130may generate the content of that specified explanatory variable as a feature of the optimization problem.

Further, the feature generation unit130may specify the type of optimization problem based on the explanatory variable (feature) included in the objective function, and generate the specified type of optimization problem as a feature. For example, it is assumed that the input unit120accepts input of an objective function that includes the explanatory variable called “employee work hours”. In this case, the type of optimization problem is more likely to be “shift scheduling” than “order quantity optimization”. This is because “shift scheduling” is more likely to include “employee work hours” as a feature. Therefore, the types of optimization problems according to the explanatory variables may be predetermined, and the feature generation unit130may generate the corresponding predetermined type of optimization problem as a feature based on the explanatory variables included in the objective function.

Note that all the features of the generated optimization problem may be included in the search information described below, or the features specified by the user by the recommendation unit140described below may be included in the search information described below.

The recommendation unit140recommends the feature generated by the feature generation unit130to the user. Specifically, the recommendation unit140presents the recommended feature to the user and allows the user to specify them. The method in which the recommendation unit140presents the feature is arbitrary. For example, the recommendation unit140may present content such as the second data illustrated inFIG.4. Further, the number of features that the recommendation unit140allows the user to specify is also not limited, and may be one or more.

The learning unit150generates an objective function by machine learning using the training data stored in the storage unit110. Specifically, the learning unit150generates the objective function of the optimization problem (more specifically, the first data) by inverse reinforcement learning using the historical data when the user made a decision (hereinafter referred to as decision-making history data) as training data.

Furthermore, when using a future prediction result, the learning unit150may accept input for a prediction model that derives a desired prediction result. The learning unit150may then generate the objective function using the prediction result of the accepted prediction model as an explanatory variable. Examples of the future prediction results include product demand prediction, road congestion prediction, and visitor count prediction. If the prediction model is stored in advance in the storage unit110, the learning unit150may acquire the prediction model stored in the storage unit110.

Here, the feature generation unit130may generate, as the second data, information indicating a user who is the basis for generating the training data used to learn the objective function. By using such information, it becomes possible to use the information about the user who made the decision that is the basis for generating the objective function as a feature of the optimization problem.

The learning unit150stores the generated objective function in the storage unit110. Note that if the optimization problem (more specifically, the objective function) has already been generated or if there is no need to learn the objective function, the information generation device100does not need to include the learning unit150.

The generation unit160generates search information that associates the first data and the second data. As a result, information for searching an optimization problem can be generated, so that the first data associated with the second data can be searched using that second data as a key.

Further, if the input unit120has accepted input of a candidate optimization solver for solving the optimization problem, the generation unit160may generate search information including information on the optimization solver. This makes it possible to grasp the optimization solver that can be used for the corresponding optimization problem.

Furthermore, when the recommendation unit140accepts a specification of the recommended feature from the user, the generation unit160may generate search information including the feature specified by the user in the second data.

The registration unit170registers the generated search information with the storage server300.

FIG.4is an explanatory diagram showing an example of search information stored in storage server300.FIG.4shows an example of search information that associates the first data with the second data. For example, the search information shown in the first line indicates that the optimization problem includes an objective function expressed as a linear sum of three conditions (explanatory variables) and two constraint conditions to be satisfied.

Furthermore, in the case of the search information shown in the first line, it indicates that the optimization problem corresponds to the type of so-called “schedule optimization” problem, which is intended to emphasize time efficiency but also emphasize action such as spending the night relaxing. Another optimization problem in the first line relates to the situation of a trip to Osaka by a man in his 20s, and indicates that all users are available for one month. Furthermore, it indicates that “Solver A” is specified as a candidate optimization solver for solving the optimization problem shown in the first line.

Note that the first data does not need to be associated with all of the assumed features as illustrated inFIG.4, and only some of the features may be associated with the first data. In addition, the classification and expression mode of the feature included in the second data are examples. These features may be expressed, for example, based on the index specifications prescribed in each database.

The input unit120, the feature generation unit130, the recommendation unit140, the learning unit150, the generation unit160, and the registration unit170are realized by a computer processor (e.g., CPU (Central Processing Unit), GPU (Graphics Processing Unit (GPU)) that operates according to a program (information generation program).

For example, the program may be stored in the storage unit110included by the information generation device100, and the processor may read the program and operate as the input unit120, the feature generation unit130, the recommendation unit140, the learning unit150, the generation unit160, and the registration unit170according to the program. The functions of the information generation device100may be provided in a Saas (Software as a Service) format.

The input unit120, the feature generation unit130, the recommendation unit140, the learning unit150, the generation unit160, and the registration unit170may each be realized by dedicated hardware. Also, some or all of the components of each device may be realized by general-purpose or dedicated circuits (circuitry), processors, etc., or a combination thereof. They may be configured by a single chip or by multiple chips connected via a bus. Part or all of each component of each device may be realized by a combination of the above-mentioned circuits, etc. and a program.

When some or all of the components of the information generation device100are realized by multiple information processing devices, circuits, etc., the multiple information processing devices, circuits, etc. may be centrally located or distributed. For example, the information processing devices and circuits may be realized as a client-server system, a cloud computing system, or the like, each of which is connected via a communication network.

FIG.5is a block diagram illustrating a configuration example of the search device200of this exemplary embodiment. The search device200in this exemplary embodiment includes a search condition input unit210, a search unit220, a model input unit230, a problem extraction unit240, a problem generation unit250, an optimization unit260, and an output unit270.

The search condition input unit210accepts input of a condition for searching optimization problem (hereinafter simply referred to as “search condition”). Specifically, the search condition input unit210accepts input of information indicating the feature of the optimization problem (specifically, the second data) as search condition.

The form of information to be input is arbitrary, and the search condition input unit210may extract the search condition based on the expected input. For example, the search condition input unit210may accept input of a string indicating the content to be solved as an optimization problem. In this case, the search condition input unit210may extract the feature of the optimization problem to be extracted from the input string based on known natural language processing. The extracted feature is used by the search unit220described below.

For example, if the string “I want to create the best plan for a man in his 20s to travel to Osaka,” is entered, the search condition input unit210may extract features such as “man in his 20s” and “travel to Osaka” from the entered string.

The search condition input unit210may also accept input of information indicating the optimization problem (specifically, information indicating the first data) as a search condition. For example, the search condition input unit210may display a list of candidates for the first data indicating the optimization problem and accept specification of the candidates from the user.

The search unit220searches for optimization problem from the storage server300(more specifically, a database that stores search information that associates the first data with the second data) that match the search condition specified by input to the search condition input unit210. More specifically, the search unit220searches for the first data (i.e., optimization problem) associated with the search information matching the input second data (i.e., feature of the optimization problem).

When information indicating the first data is input, the search unit220may search for the optimization problem that match the input information indicating the first data. If the search information includes a candidate for the optimization solver, the search unit220may also search for the corresponding optimization solver together.

The search unit220may also present the search result to the user and accept the user's desired specification of the optimization problem. For example, the search unit220may display the feature of the optimization problem (i.e., the second data) along with the first data as the search result, and accept the user's specification for the displayed first data.

The model input unit230accepts input of a model that has been learned based on the target user's decision-making history data (hereinafter sometimes referred to as a decision-making model). In other words, the model input unit230accepts input of a model that reflect the target user's past decision-making. The model input unit230may also accept input of constraints imposed on the model together with the model.

The method by which the model that accepts input is generated is arbitrary. The model input unit230may, for example, accept input of a model that has been learned in a similar way (e.g., inverse reinforcement learning) to the way the learning unit150of the information generation device100generates the objective function.

The accepted model is compared with the optimization problem searched by the search unit220. Therefore, the input model is preferably a model generated by a method similar to that of the optimization problem to be searched, or a model generated in a similar manner.

The problem extraction unit240compares the optimization problem searched by the search unit220with the decision-making model for which the model input unit230has accepted input, and extracts the optimization problem from the searched optimization problem (i.e., the first data) that satisfy a predetermined condition of similarity degree with the input decision-making model. The predetermined conditions include, for example, that the similarity degree must be greater than a predetermined threshold value.

Since the decision-making model is a model learned based on the decision-making history data of the target user, it can be said that the model reflects the intentions of the target user. The problem extraction unit240determines the similarity degree between such a model and an optimization problem, thereby making it possible to extract an optimization problem that reflects intentions similar to the target user.

The method by which the problem extraction unit240calculates the similarity degree is arbitrary. The problem extraction unit240may calculate the similarity degree of the features (explanatory variables) included in each of the decision-making model and optimization problem. For example, the problem extraction unit240may calculate the degree of overlap of feature types as the similarity degree. Otherwise, the problem extraction unit240may calculate the similarity by calculating the difference in the values of the weight coefficients of each of the overlapping feature, for example, by cosine similarity degree or RMSE (Root Mean Square Error).

Furthermore, if there is training data used in generating the decision-making model and optimization problem, the problem extraction unit240may calculate the degree of overlap of the range of possible value ranges in the same feature and the mean or variance of each feature as similarity degree.

The method by which the problem extraction unit240calculates similarity degree is not limited to the method based on the structure of the decision-making model and optimization problem, as described above. The problem extraction unit240may, for example, calculate similarity degree based on the difference in output values when the same data is input to each of the decision-making model and optimization problem. If the optimization problem and the decision-making model are each assigned sentences that indicate characteristics of the problem or model, the problem extraction unit240may calculate the similarity degree between each sentence as the similarity degree between the optimization problem and the decision-making model.

The search device200does not necessarily need to accept input of a decision-making model. If there is no decision-making model input, the search device200need not include the model input unit230and the problem extraction unit240.

In cases where multiple optimization problems are extracted, the problem generation unit250generates a new objective function from the extracted multiple optimization problems. Specifically, the problem generation unit250generates a new objective function by combining two or more objective functions selected from the multiple optimization problems. If one optimization problem is identified, the problem generation unit250does not need to generate a new objective function.

Here, combining two or more objective functions means that extracting some or all of the explanatory variables included in each objective function respectively based on predetermined rule, and formulating (functionalizing) them using the extracted explanatory variables. The rule is defined by the user, etc., according to the degree to which each objective function reflects the intention expressed. The predetermined rule includes, for example, multiplying the weights of the original explanatory variables by a predetermined percentage and then extracting all of them, and then calculating the sum of each of the extracted explanatory variables.

The following is a specific example of combining objective functions. For example, it is assumed that objective function A and objective function B include multiple overlapping features f1, f2, and f3as shown below.

Here, assume a situation where it is desired to generate an objective function that will indicates an intention intermediate between the intention indicated by objective function A and the intention indicated by objective function B (i.e., an intention that reflects both intentions equally). In this case, the problem generation unit250may generate objective function C as shown below by adding together the objective functions with each coefficient of each explanatory variable multiplied by 0.5 so that the combination ratio is 1:1.

Similarly, assume a situation where it is desired to generate an objective function that will reflect the intention indicated by objective function A more than the intention indicated by objective function B. In this case, the problem generation unit250may combine the objective variables so that the combination ratio is, for example, 4:1, and generate an objective function D as shown below.

The optimization unit260performs optimization processing based on the new objective function generated and derives an optimization result. Further, for example, if a candidate optimization solver is specified, the optimization unit260may derive the optimization result using the specified optimization solver.

The output unit270outputs the optimization result (e.g., optimal action) derived by the optimization unit260.

The search condition input unit210, the search unit220, the model input unit230, the problem extraction unit240, the problem generation unit250, the optimization unit260, and the output unit270are realized by a computer processor operating according to a program (search program).

For example, the program may be stored in a storage unit (not shown) included in the search device200, and the processor may read the program and operates as the search condition input unit210, the search unit220, the model input unit230, the problem extraction unit240, the problem generation unit250, the optimization unit260, and the output unit270according to the program. The function of the search device200may be provided in a Saas (Software as a Service) format.

Similar to the configuration of the information generation device100, the search condition input unit210, the search unit220, the model input unit230, the problem extraction unit240, the problem generation unit250, the optimization unit260, and the output unit270may each be realized in dedicated hardware.

Next, the operation of the information distribution system1of this exemplary embodiment will be described.FIG.6is a flowchart illustrating an operation example of the information generation device100of this exemplary embodiment. The input unit120accepts input of the first data indicating an optimization problem including an objective function and constraints, and the second data indicating a feature of the optimization problem (step S11). The generation unit160generates search information that associates the first data with the second data (step S12). The registration unit170registers the generated search information with the storage server300(step S13).

FIG.7is a flowchart illustrating an operation example of the search device200of this exemplary embodiment. The search condition input unit210accepts input of information (i.e., the second data) indicating the feature of the optimization problem (step S21). The search unit220searches from the storage server300for the optimization problem (i.e., the first data) associated with the search information matching the input information (i.e., the second data) (step S22). Thereafter, the optimization unit260performs optimization processing using the searched first data, and the output unit270outputs the optimization result.

As described above, in this exemplary embodiment, the input unit120accepts input of the first data and the second data, and the generation unit160generates search information that associates the first data with the second data. Thus, information for searching optimization problem can be generated.

In other words, as described above, the optimization problem is generally generated individually considering the user's point of view and various constraint conditions, so the technical concept of storing multiple optimization problems in a searchable manner in a database or the like did not exist. On the other hand, in this exemplary embodiment, the generation unit160generates search information that associates the first data with the second data, making it possible to manage the optimization problem using this search information.

Moreover, in this exemplary embodiment, the search condition input unit210accepts input of second data as a search condition, and the search unit220searches for the first data associated with the search information matching the input second data from the storage server300. Thus, the desired optimization problem can be searched.

In other words, as described above, due to the characteristic of the individually generated optimization problem, the technical concept of searching other optimization problem from the database did not exist. On the other hand, in this exemplary embodiment, the search unit220searches for the first data associated with the search information matching the input second data from the storage server300. Thus, it is possible to obtain the desired optimization problem.

Next, a specific example of a robot control system using the search device200of this exemplary embodiment will be described.FIG.8is a block diagram illustrating a configuration example of one exemplary embodiment of the robot control system. A robot control system2000illustrated inFIG.8includes a search device200and a robot2300.

The search device200illustrated inFIG.8is the same as the search device200in the above exemplary embodiment. The search device200stores the optimization result in a storage unit2310of the robot2300, which will be described later.

The robot2300is equipment that operates based on the optimization result. The robot here is not limited to device shaped to resemble human or animal, but also include devices that perform automatic tasks (automatic operation, automatic control, etc.). The robot2300includes the storage unit2310, an input unit2320, and a control unit2330.

The storage unit2310stores the optimization result derived by the search device200.

The input unit2320accepts input of various information used to operate the robot.

The control unit2330controls the operation of the robot2300based on the various information accepted and the optimization result stored in the storage unit2310. The method by which the control unit2330controls the operation of the robot2300based on the optimization result may be predetermined. In this exemplary embodiment, equipment that performs automatic tasks, such as the robot2300, can be controlled based on the derived optimization result.

The following is an overview of this invention.FIG.9is a block diagram illustrating the outline of a search device according to the present invention. A search device90(e.g., the search device200) according to the present invention includes a search means91(e.g., the search unit220) which searches for an optimization problem matching a specified search condition from a database (e.g., the storage server300) that stores search information that associates first data indicating an optimization problem including an objective function and a constraint with second data indicating a feature of the optimization problem, and an input means92(e.g., the search condition input unit210) which accepts input of the second data as search condition.

The search means91then searches for the first data associated with the search information matching the input second data.

Such a configuration can generate information for searching an optimization problem.

The input means92may accept input of information indicating the first data, and the search means91may search for the optimization problem matching the input information indicating the first data.

The search device90may include a model input means (e.g., the model input unit230) which accepts input of a decision-making model which is a model learned based on user's decision-making history data, and a problem extraction means (e.g., the problem extraction unit240) which extracts the first data that satisfy a predetermined condition of similarity degree with the input decision-making model from the searched first data.

The search device90may include a problem generation means (e.g., the problem generation unit250) which generates a new objective function by combining two or more objective functions selected from the multiple first data. The search means91may then search for multiple pieces of the first data.

The search device90may include an optimization means which performs optimization processing of the objective function.

The input means92may accept input of a string indicating the content to be solved as the optimization problem, and extract a feature of the optimization problem from the input string, and the search means91may search for the first data associated with the search information matching the extracted feature.

FIG.10is a schematic block diagram illustrating a configuration of a computer according to at least one of exemplary embodiments. A computer1000includes a processor1001, a main storage device1002, an auxiliary storage device1003, and an interface1004.

Each of the devices (the information generation device100and the search device200) of the information distribution system1described above is implemented in the computer1000. The operation of each processing unit described above is stored in the auxiliary storage device1003in the form of a program. The processor1001reads the program from the auxiliary storage device1003, expands it in the main storage device1002, and executes the above processing according to the program.

In at least one exemplary embodiment, the auxiliary storage device1003is an example of a non-temporary tangible medium. Other examples of non-transient tangible medium include a magnetic disk, a magneto-optical disk, a CD-ROM (Compact Disc Read-only memory), a DVD-ROM (Read Read-only memory), a semiconductor memory, etc., connected via interface1004. Furthermore, in a case where the program is distributed to the computer1000via a communication line, the computer1000that has received the program may develop the program in the main storage device1002and execute the above processing.

Furthermore, the program may be for implementing some of the functions described above. In addition, the program may be a program that implements the above-described functions in combination with another program already stored in the auxiliary storage device1003, a so-called difference file (difference program).

Although some or all of the above exemplary embodiments may also be described as in the following Supplementary notes, but not limited to the following.

(Supplementary note 1) A search device comprising:a search means which searches for an optimization problem matching a specified search condition from a database that stores search information that associates first data indicating an optimization problem including an objective function and a constraint with second data indicating a feature of the optimization problem; andan input means which accepts input of the second data as search condition,wherein the search means searches for the first data associated with the search information matching the input second data.

(Supplementary note 2) The search device according to Supplementary note 1, whereinthe input means accepts input of information indicating the first data, andthe search means searches for the optimization problem matching the input information indicating the first data.

(Supplementary note 3) The search device according to Supplementary note 1 or 2, further comprising:a model input means which accepts input of a decision-making model which is a model learned based on user's decision-making history data; anda problem extraction means which extracts the first data that satisfy a predetermined condition of similarity degree with the input decision-making model from the searched first data.

(Supplementary note 4) The search device according to any one of Supplementary notes 1 to 3, further comprising a problem generation means which generates a new objective function by combining two or more objective functions selected from the multiple first data,wherein the search means searches for multiple pieces of the first data.

(Supplementary note 5) The search device according to any one of Supplementary notes 1 to 4, further comprising an optimization means which performs optimization processing of the objective function.

(Supplementary note 6) The search device according to any one of Supplementary notes 1 to 5, whereinthe input means accepts input of a string indicating the content to be solved as the optimization problem, and extracts a feature of the optimization problem from the input string, andthe search means searches for the first data associated with the search information matching the extracted feature.

(Supplementary note 7) A search method comprising:accepting input of a feature of an optimization problem as a search condition, by a computer; andsearching for an optimization problem associated with search information matching the input feature of the optimization problem from a database that stores search information that associates first data indicating an optimization problem including an objective function and a constraint with second data indicating a feature of the optimization problem, by the computer.

(Supplementary note 8) The search method according to Supplementary note 7, further comprising:accepting input of information indicating the first data, by the computer, andsearching for the optimization problem matching the input information indicating the first data, by the computer.

(Supplementary note 9) A program storage medium for storing a search program for causing a computer to execute:search process for searching for an optimization problem matching a specified search condition from a database that stores search information that associates first data indicating an optimization problem including an objective function and a constraint with second data indicating a feature of the optimization problem; andinput process for accepting input of the second data as search condition,wherein the first data associated with the search information matching the input second data is searched, in the search process.

(Supplementary note 10) The program storage medium for storing the information generation program according to Supplementary note 9, for causing the computer to further execute:to accept input of information indicating the first data, in the input process, andto search for the optimization problem matching the input information indicating the first data, in the search process.

(Supplementary note 11) A search program for causing a computer to execute:search process for searching for an optimization problem matching a specified search condition from a database that stores search information that associates first data indicating an optimization problem including an objective function and a constraint with second data indicating a feature of the optimization problem; andinput process for accepting input of the second data as search condition,wherein the first data associated with the search information matching the input second data is searched, in the search process.

(Supplementary note 12) The information generation program according to Supplementary note 11, for causing the computer to further execute:to accept input of information indicating the first data, in the input process, andto search for the optimization problem matching the input information indicating the first data, in the search process.

REFERENCE SIGNS LIST