Combinatorial optimization system and combinatorial optimization method
AssigneesDenso Corporation, Tohoku University
InventorsShuntaro Okada, Masayuki Ohzeki
Life of this patent
Estimating the term…
Abstract
A combinatorial optimization system includes an input unit to which a multivalued optimization problem is input, a halving unit configured to perform halving to select half of candidate solutions of the multivalued optimization problem, and an optimization control unit configured to obtain an optimal solution of the multivalued optimization problem by causing the halving unit to repeat the halving.
Claims8
A combinatorial optimization system comprising:
- a processor;
- a non-transitory computer-readable storage medium;
- and
- a set of computer-executable instructions stored on the non-transitory computer-readable storage medium that cause the processor to:
- receive a multivalued optimization problem;
- perform halving by
- selecting half of candidate solutions of the multivalued optimization problem,
- generating an evaluation function in which the multivalued optimization problem is represented with binary representation using a half-hot constraint, and
- performing the halving by optimizing the evaluation function using an Ising machine;
- control the generating of the evaluation function such that another evaluation function is generated for halving the half of the candidate solutions;
- and
- obtain an optimal solution of the multivalued optimization problem by repeating the halving,
- wherein
- the optimal solution of the multivalued optimization problem is used to select travel routes for multiple target vehicles so as not to cause traffic congestion.
A method of solving a multivalued optimization problem comprising:
- inputting the multivalued optimization problem;
- halving candidate solutions of the multivalued optimization problem by
- selecting half of the candidate solutions of the multivalued optimization problem,
- generating an evaluation function in which the multivalued optimization problem is represented with binary representation using a half-hot constraint, and
- performing the halving by optimizing the evaluation function using an Ising machine process;
- and
- controlling the generating of the evaluation function such that another evaluation function is generated for halving the half of the candidate solutions selected for halving;
- and
- repeating the halving to obtain an optimal solution of the multivalued optimization problem,
- wherein
- the optimal solution of the multivalued optimization problem is used to select travel routes for multiple target vehicles so as not to cause traffic congestion.
A combinatorial optimization system configured to solve a multivalued optimization problem and comprising at least one processor, the at least one processor configured to:
- halve candidate solutions of the multivalued optimization problem by
- selecting half of the candidate solutions,
- generating an evaluation function in which the multivalued optimization problem is represented with binary representation using a half-hot constraint, and
- performing the halving by optimizing the evaluation function using an Ising machine process;
- and
- control the generating of the evaluation function such that another evaluation function is generated for halving the half of the candidate solutions selected for halving;
- and
- obtain an optimal solution of the multivalued optimization problem by halving the candidate solutions repeatedly,
- wherein
- the optimal solution of the multivalued optimization problem is used to select travel routes for multiple target vehicles so as not to cause traffic congestion.
Dependencies are inferred from the claim text.