Information processing method, information processing system, and information processing program

Abstract

The information processing system includes: a processing unit that executes processing in cooperation with a memory; and a storage unit that stores a compression technology for a data volume to be applied to a Hamiltonian of the optimization problem, a compressible condition indicating whether the compression technology can be applied or not, and compression method judgment information associated with a compression format indicating a feature quantity of the Hamiltonian when the Hamiltonian is compressed by applying the compression technology. The processing unit: refers to the compression method judgment information and judges a part included in the Hamiltonian which satisfies the compressible condition; and extracts the feature quantity of the part, which is included in the Hamiltonian and judged as satisfying the compressible condition, by means of the compression technology corresponding to the compressible condition and compresses the extracted feature quantity into the compression format.

1 . An information processing method executed by an information processing system for executing an optimum solution search for an optimization problem,
 wherein the information processing system includes:   a processing unit that executes processing in cooperation with a memory; and a   storage unit that stores a compression technology for a data volume to be applied to a Hamiltonian of the optimization problem, a compressible condition indicating whether the compression technology can be applied or not, and compression method judgment information associated with a compression format indicating a feature quantity of the Hamiltonian when the Hamiltonian is compressed by applying the compression technology; and   wherein the processing unit:   refers to the compression method judgment information and judges a part included in the Hamiltonian which satisfies the compressible condition; and   extracts the feature quantity of the part, which is included in the Hamiltonian and judged as satisfying the compressible condition, by means of the compression technology corresponding to the compressible condition and compresses the extracted feature quantity into the compression format.   
     
     
         2 . The information processing method according to  claim 1 , 
 wherein the Hamiltonian is a quadratic constraint equation; and   wherein if a quadratic term included in the constraint equation satisfies the compressible condition, the processing unit compresses the quadratic term into the compression format by means of the compression technology corresponding to the compressible condition.   
     
     
         3 . The information processing method according to  claim 2 , 
 wherein if the constraint equation is of a cubic or higher order, the processing unit lowers a degree of the constraint equation to a quadratic degree and then generates a lowered-order constraint equation; and   if a quadratic term included in the lowered-degree constraint equation satisfies the compressible condition, the processing unit compresses the quadratic term into the compression format by means of the compression technology corresponding to the compressible condition.   
     
     
         4 . The information processing method according to  claim 1 , 
 wherein the Hamiltonian is a matrix; and   wherein if a block matric which is a part obtained by dividing the matrix satisfies the compressible condition, the processing unit compresses the block matrix into the compression format by means of the compression technology corresponding to the compressible condition.   
     
     
         5 . The information processing method according to  claim 4 , 
 wherein the processing unit:   divides the matrix into one or more block diagonal matrixes, each of which includes a maximum of diagonal components successively aligned in the matrix and satisfies the compressible condition, and a block matrix other than the block diagonal matrix or matrixes of the matrix divided along division lines used when dividing the matrix into the block diagonal matrix or matrixes; and   compresses the block diagonal matrix or matrixes and the block matrix which are obtained by dividing the matrix into the compression format by means of the compression technology corresponding to the compressible condition.   
     
     
         6 . The information processing method according to  claim 1 ,
 wherein the processing unit judges whether the part included in the Hamiltonian satisfies the compressible condition or not on the basis of whether or not the part can be applied to a specified formulation condition, or by a specified algorithm.   
     
     
         7 . The information processing method according to  claim 1 , 
 wherein the compression technology is a technology for replacing the part included in the Hamiltonian with any one of parameters, that is, an M-in-N-pieces selection problem for selecting M pieces from N pieces, an N-rook problem for placing N pieces of rooks in matrix squares in a state of mutually having no power of move, an N-cities traveling salesman problem for visiting N cities, each city only once, in a shortest distance, a zero matrix, a constant matrix, a sparse matrix, and a transposed matrix.   
     
     
         8 . The information processing method according to  claim 1 , 
 wherein the processing unit:   stores the compressed compression format in the memory; and   executes the optimum solution search for the optimization problem by processing the compression format, which is stored in the memory and obtained by means of the compression technology, by using an algorithm corresponding to the compression technology.   
     
     
         9 . An information processing system for executing an optimum solution search for an optimization problem, 
 the information processing system comprising:   a processing unit that executes processing in cooperation with a memory; and a   storage unit that stores a compression technology for a data volume to be applied to a Hamiltonian of the optimization problem, a compressible condition indicating whether the compression technology can be applied or not, and compression method judgment information  associated with a compression format indicating a feature quantity of the Hamiltonian when the Hamiltonian is compressed by applying the compression technology; and   wherein the processing unit:   refers to the compression method judgment information and judges a part included in the Hamiltonian which satisfies the compressible condition; and   extracts the feature quantity of the part, which is included in the Hamiltonian and judged as satisfying the compressible condition, by means of the compression technology corresponding to the compressible condition and compresses the extracted feature quantity into the compression format.   
     
     
         10 . The information processing system according to  claim 9 , 
 wherein the Hamiltonian is a quadratic constraint equation; and   wherein if a quadratic term included in the constraint equation satisfies the compressible condition, the processing unit compresses the quadratic term into the compression format by means of the compression technology corresponding to the compressible condition.   
     
     
         11 . The information processing system according to  claim 9 , 
 wherein the Hamiltonian is a matrix; and   wherein if a block matric which is a part obtained by dividing the matrix satisfies the compressible condition, the processing unit compresses the block matrix into the compression format by means of the compression technology corresponding to the compressible condition.   
     
     
         12 . The information processing system according to  claim 11 , 
 wherein the processing unit:   divides the matrix into one or more block diagonal matrixes, each of which includes a maximum of diagonal components successively aligned in the matrix and satisfies the compressible condition, and a block matrix other than the block diagonal matrix or matrixes of the matrix divided along division lines used when dividing the matrix into the block diagonal matrix or matrixes; and   compresses the block diagonal matrix or matrixes and the block matrix which are obtained by dividing the matrix into the compression format by means of the compression technology corresponding to the compressible condition.   
     
     
         13 . The information processing system according to  claim 9 , 
 wherein the processing unit judges whether the part included in the Hamiltonian satisfies the compressible condition or not on the basis of whether or not the part can be applied to a specified formulation condition, or by a specified algorithm.   
     
     
         14 . The information processing system according to  claim 9 , 
 wherein the compression technology is a technology for replacing the part included in the Hamiltonian with any one of parameters, that is, an M-in-N-pieces selection problem for selecting M pieces from N pieces, an N-rook problem for placing N pieces of rooks in matrix squares in a state of mutually having no power of move), an N-cities traveling salesman problem for visiting N cities, each city only once, in a shortest distance, a zero matrix, a constant matrix, a sparse matrix, and a transposed matrix.   
     
     
         15 .  An information processing program for causing a computer to function as the information processing system stated in  claim 9 .