US-20260126997-A1 - INFORMATION PROCESSING DEVICE, SIMULATED ANNEALING DEVICE, METHOD, AND PROGRAM

Abstract

A constraint simplification unit simplifies a plurality of constraints that are each expressed as a comparison between a weighted sum of binary variables with integer values and an integer value, by deleting one of the plurality of constraints or deleting a number of binary variables used in any of the plurality of constraints.

Inventors

• Takuya Araki

Assignees

• NEC CORPORATION

Dates

Publication Date

20260507

Application Date

20251014

Priority Date

20241107

Claims (9)

1. 1 . An information processing device comprising: a memory storing instructions; and one or more processors configured to execute the instructions to simplify a plurality of constraints that are each expressed as a comparison between a weighted sum of binary variables with integer values and an integer value, by deleting one of the plurality of constraints or deleting a number of binary variables used in any of the plurality of constraints.
2. 2 . The information processing device according to claim 1 , wherein the processor is configured to execute the instructions to simplify the plurality of constraints by determining a value of a binary variable included in any of the plurality of constraints.
3. 3 . The information processing device according to claim 2 , wherein the processor is configured to execute the instructions to determine the value of the binary variable to be 0 when the coefficient of the binary variable, which is an integer value, is greater than the integer value used in the comparison.
4. 4 . The information processing device according to claim 1 , wherein the processor is configured to execute the instructions to simplify the plurality of constraints by deleting one of the plurality of constraints that is satisfied.
5. 5 . The information processing device according to claim 4 , wherein the processor is configured to execute the instructions to delete one of the constraints that generated an expression in which the sum of the integer coefficients of the binary variables is less than or equal to the integer value used in the comparison.
6. 6 . The information processing device according to claim 1 , wherein the processor is configured to execute the instructions to simplify the plurality of constraints based on a plurality of constraints that indicate that a weighted sum of binary variables with positive integer values is less than or equal to a predetermined integer value.
7. 7 . The information processing device according to claim 1 , wherein the processor is configured to execute the instructions to convert a constraint expressed using binary variables into a weighted sum constraint, normalize the converted weighted sum constraint, and simplify the plurality of constraints based on the normalized weighted sum constraint.
8. 8 . A simulated annealing device comprising: a memory storing instructions; and one or more processors configured to execute the instructions to: execute simulated annealing based on an input constraint expressed as a comparison between a weighted sum of binary variables with integer values and an integer value; simplify a plurality of constraints by deleting one of the plurality of constraints or deleting a number of binary variables used in any of the plurality of constraints based on the plurality of constraints; and execute simulated annealing based on the simplified plurality of constraints.
9. 9 . A method comprising simplifying a plurality of constraints that are each expressed as a comparison between a weighted sum of binary variables with integer values and an integer value, by deleting one of the plurality of constraints or deleting a number of binary variables used in any of the plurality of constraints.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS This application is based upon and claims the benefit of priority from the prior Japanese Patent Application No. 2024-194796, filed Nov. 7, 2024, the entire contents of which are incorporated herein by reference. BACKGROUND OF THE INVENTION The present disclosure relates to an information processing device, a simulated annealing device, a method, and a program that perform processing for simplifying given constraints. Research is being conducted on quantum computers capable of rapidly solving combinatorial optimization problems using quantum annealing methods. For combinatorial optimization problems represented by an Ising model, a quantum computer uses quantum superposition to search for a state that minimizes an energy function corresponding to the objective function of the combinatorial optimization problem. However, at present, quantum computers of a sufficiently large scale to solve real-world combinatorial optimization problems have not yet been realized. However, with the advent of quantum computers, research into the application of combinatorial optimization technology is also underway. For example, in order to obtain solutions to various combinatorial optimization problems in a general-purpose manner, a simulated annealing method (also referred to as the SA method) that takes as input an energy function in an Ising model or QUBO (Quadratic Unconstrained Binary Optimization) is currently being used. By using the SA method, solutions to combinatorial optimization problems can be obtained even on classical computers. Patent Literature 1 discloses a simulated annealing device capable of easily obtaining candidate solutions that satisfy multiple constraints imposed on a combinatorial optimization problem. The simulated annealing device described in Patent Literature 1 uses a SAT (Boolean Satisfiability Testing) solver to search for combinations of spins (variables) that satisfy all constraints imposed on the combinatorial optimization problem. Non-Patent Literature 1 describes a type of constraint known as the weighted sum constraint. PRIOR ART DOCUMENTS Patent Documents [Patent Literature 1] International Publication WO2022/264414 Non-Patent Documents [Non-Patent Literature 1] Timo Berthold, Stefan Heinz, Marc Pfetsch, “Solving Pseudo-Boolean Problems with SCIP”, ZIB-Report 08-12, March 2008 SUMMARY OF THE INVENTION If an energy function in an Ising model or QUBO is applied to a simulated annealing method, solutions to various combinatorial optimization problems can be obtained in a general-purpose manner. However, when an original combinatorial optimization problem is converted into an Ising model or a QUBO format, there is a problem in that the problem space, which is the search range of the solution, increases. In addition, the simulated annealing device described in Patent Literature 1 requires the use of a SAT solver to obtain a neighboring solution. However, although the use of a SAT solver guarantees that a solution satisfying the constraints can be obtained, there is a problem in that it takes time to obtain the solution. Accordingly, an exemplary object of the present disclosure is to provide an information processing device, an optimization system, a method, and a program that are capable of simplifying the constraints themselves that are given. The information processing device according to the present disclosure includes a constraint simplification unit configured to simplify a plurality of constraints that are each expressed as a comparison between a weighted sum of binary variables with integer values and an integer value, by deleting one of the plurality of constraints or deleting a number of binary variables used in any of the plurality of constraints. The simulated annealing device according to the present disclosure includes: an optimization processing unit configured to execute simulated annealing based on an input constraint expressed as a comparison between a weighted sum of binary variables with integer values and an integer value; and a constraint simplification unit configured to simplify a plurality of constraints by deleting one of the plurality of constraints or deleting a number of binary variables used in any of the plurality of constraints based on the plurality of constraints, wherein the optimization processing unit executes simulated annealing based on the simplified plurality of constraints. The method according to the present disclosure includes simplifying a plurality of constraints that are each expressed as a comparison between a weighted sum of binary variables with integer values and an integer value, by deleting one of the plurality of constraints or deleting a number of binary variables used in any of the plurality of constraints. The program according to the present disclosure for causing a computer to execute constraint simplification processing, wherein the constraint simplification processing simplifies a plurality of