Problem solver apparatus, problem solving method, and computer program product
AssigneesKabushiki Kaisha Toshiba, Toshiba Digital Solutions Corporation
InventorMasaru SUZUKI
Life of this patent
Estimating the term…
Abstract
A problem solver apparatus includes a hardware processor serving to solve an integer optimization problem of minimizing an objective function under a linear constraint condition. The hardware processor calculates, for each of one or more penalty functions corresponding to one or more inequality constraint conditions, a first parameter to be multiplied on a target penalty function and a second parameter to be multiplied on a square of the target penalty function. The hardware processor generates a fast augmented Lagrange function. The hardware processor outputs, as a solution set for an integer optimization problem, a set of solutions satisfying the linear constraint condition among one or more solutions to the Lagrange function problem.
Claims14
A problem solver apparatus, comprising:
- a hardware processor connected to a memory, the hardware processor serving to solve an integer optimization problem of minimizing an objective function under a linear constraint condition, the linear constraint condition including one or more inequality constraint conditions and a target value constraint condition that makes the objective function equal to or more than or equal to or less than a target value, wherein
- the hardware processor is configured to
- acquire the integer optimization problem,
- calculate a first parameter to be multiplied on a target penalty function and a second parameter to be multiplied on a square of the target penalty function, the first parameter and the second parameter being calculated for each of one or more penalty functions corresponding to the one or more inequality constraint conditions,
- generate a fast augmented Lagrange function obtained by adding the objective function, one or more terms multiplied with the first parameter corresponding to each of the one or more penalty functions, and one or more terms multiplied with the second parameter corresponding to a square of each of the one or more penalty functions,
- acquire one or more solutions to a Lagrange function problem of minimizing the fast augmented Lagrange function, and
- output, as a solution set for the integer optimization problem, a set of solutions satisfying the linear constraint condition among the one or more solutions to the Lagrange function problem.
A problem solving method implemented by a computer, the method comprising:
- acquiring an integer optimization problem of minimizing an objective function under a linear constraint condition, the linear constraint condition including one or more inequality constraint conditions and a target value constraint condition that makes the objective function equal to or more than or equal to or less than a target value;
- calculating a first parameter to be multiplied on a target penalty function and a second parameter to be multiplied on a square of the target penalty function, the first parameter and the second parameter being calculated for each of one or more penalty functions corresponding to the one or more inequality constraint conditions;
- generating a fast augmented Lagrange function obtained by adding the objective function, one or more terms multiplied with the first parameter corresponding to each of the one or more penalty functions, and one or more terms multiplied with the second parameter corresponding to a square of each of the one or more penalty functions;
- acquiring one or more solutions to a Lagrange function problem of minimizing the fast augmented Lagrange function;
- and
- outputting, as a solution set for the integer optimization problem, a set of solutions satisfying the linear constraint condition among the one or more solutions to the Lagrange function problem.
A computer program product comprising a non-transitory computer readable recording medium on which a computer program executable by a computer is recorded, the computer program instructing the computer to perform:
- acquiring an integer optimization problem of minimizing an objective function under a linear constraint condition, the linear constraint condition including one or more inequality constraint conditions and a target value constraint condition that makes the objective function equal to or more than or equal to or less than a target value;
- calculating a first parameter to be multiplied on a target penalty function and a second parameter to be multiplied on a square of the target penalty function, the first parameter and the second parameter being calculated for each of one or more penalty functions corresponding to the one or more inequality constraint conditions;
- generating a fast augmented Lagrange function obtained by adding the objective function, one or more terms multiplied with the first parameter corresponding to each of the one or more penalty functions, and one or more terms multiplied with the second parameter corresponding to a square of each of the one or more penalty functions;
- acquiring one or more solutions to a Lagrange function problem of minimizing the fast augmented Lagrange function;
- and
- outputting, as a solution set for the integer optimization problem, a set of solutions satisfying the linear constraint condition among the one or more solutions to the Lagrange function problem.
Dependencies are inferred from the claim text.