Solver apparatus and computer program product

A solver apparatus that calculates a solution to a problem under a condition, the problem minimizing an objective function that is a function obtained by adding a non-convex quadratic function including I (I is an integer equal to or more than two) first decision variables that are each zero or one, and a continuous convex function including M (M is an integer equal to or more than two) second decision variables that are each a real number, and the condition satisfying J (J is an integer equal to or more than zero) simultaneous linear equations that each include at least one of the I first decision variables and the M second decision variables as a variable, and satisfying K (K is an integer equal to or more than one) simultaneous linear inequalities that each include at least one of the I first decision variables and the M second decision variables as a variable, the solver apparatus comprising:

• one or more hardware processors configured to function as:
• an acquisition unit that acquires the objective function, the J simultaneous linear equations, and the K simultaneous linear inequalities;
• an update unit that repeats first processing, second processing, and coefficient processing in predetermined order, the first processing acquiring candidate values of solutions of the I first decision variables that minimize a first function including the I first decision variables generated based on an augmented Lagrange function, the second processing acquiring candidate values of solutions of the M second decision variables and K dependent variables that minimize a second function including the M second decision variables and the K dependent variables generated based on the augmented Lagrange function, and the coefficient processing updating a coefficient included in the augmented Lagrange function;
• and
• an output unit that outputs the candidate values of the solutions of the I first decision variables as the solution to the problem when a preset end condition is reached by repeating the first processing, the second processing, and the coefficient processing, wherein
• the augmented Lagrange function includes an objective function term including the objective function, J first Lagrange terms corresponding to the J simultaneous linear equations, K second Lagrange terms corresponding to the K simultaneous linear inequalities, and a penalty term.

A computer program product having a non-transitory computer readable medium including programmed instructions for causing an information processing apparatus to function as a solver apparatus, wherein

• the solver apparatus calculates a solution to a problem under a condition, the problem minimizing an objective function that is a non-convex quadratic function including I (I is an integer equal to or more than two) decision variables that are each zero or one, and the condition satisfying J (J is an integer equal to or more than zero) simultaneous linear equations that each include at least one of the I decision variables as a variable and satisfying K (K is an integer equal to or more than one) simultaneous linear inequalities that each include at least one of the I decision variables as a variable, the program causing the information processing apparatus to function as:
• an acquisition unit that acquires the objective function, the J simultaneous linear equations, and the K simultaneous linear inequalities,
• an update unit that repeats first processing, second processing, and coefficient processing in predetermined order, the first processing acquiring candidate values of solutions of the I decision variables that minimize a first function including the I decision variables generated based on an augmented Lagrange function, the second processing acquiring candidate values of solutions of the K dependent variables that minimize a second function including K dependent variables generated based on the augmented Lagrange function, and the coefficient processing updating a coefficient included in the augmented Lagrange function, and
• an output unit that outputs the candidate values of the solutions of the I decision variables as the solution to the problem when a preset end condition is reached by repeating the first processing, the second processing, and the coefficient processing, wherein
• the augmented Lagrange function includes an objective function term including the objective function, J first Lagrange terms corresponding to the J simultaneous linear equations, K second Lagrange terms corresponding to the K simultaneous linear inequalities, and a penalty term.

A computer program product having a non-transitory computer readable medium including programmed instructions for causing an information processing apparatus to function as a solver apparatus, wherein

• the solver apparatus calculates a solution to a problem under a condition, the problem minimizing an objective function that is a function obtained by adding a non-convex quadratic function including I (I is an integer equal to or more than two) first decision variables that are each zero or one, and a continuous convex function including M (M is an integer equal to or more than two) second decision variables that are each a real number, and the condition satisfying J (J is an integer equal to or more than zero) simultaneous linear equations that each include at least one of the I first decision variables and the M second decision variables as a variable and satisfying K (K is an integer equal to or more than one) simultaneous linear inequalities that each include at least one of the I first decision variables and the M second decision variables as a variable, the program causing the information processing apparatus to function as:
• an acquisition unit that acquires the objective function, the J simultaneous linear equations, and the K simultaneous linear inequalities,
• an update unit that repeats first processing, second processing, and coefficient processing in predetermined order, the first processing acquiring candidate values of solutions of the I first decision variables that minimize a first function including the I first decision variables generated based on an augmented Lagrange function, the second processing acquiring candidate values of solutions of the M second decision variables and K dependent variables that minimize a second function including the M second decision variables and the K dependent variables generated based on the augmented Lagrange function, and the coefficient processing updating a coefficient included in the augmented Lagrange function, and
• an output unit that outputs the candidate values of the solutions of the I first decision variables as the solution to the problem when a preset end condition is reached by repeating the first processing, the second processing, and the coefficient processing, wherein
• the augmented Lagrange function includes an objective function term including the objective function, J first Lagrange terms corresponding to the J simultaneous linear equations, K second Lagrange terms corresponding to the K simultaneous linear inequalities, and a penalty term.