Efficient partition of integer optimization problems with one-hot encoding

Area of Science:

• Quantum Computing
• Optimization Algorithms
• Computer Science

Background:

• Quantum annealing is a heuristic algorithm for solving combinatorial optimization problems.
• D-Wave Systems Inc. has developed hardware for quantum annealing.
• Current quantum annealers solve binary optimization problems but struggle with problems involving many integer variables.

Purpose of the Study:

• To address the challenge of solving large-scale optimization problems with integer variables using quantum annealers.
• To develop improved methods for partitioning binarized problems to enhance the efficiency of quantum annealing.

Main Methods:

• Integer variables are binarized using one-hot encoding.
• The binarized problem is partitioned into smaller subproblems.
• Two novel partitioning methods are proposed to maximize feasible solutions within subproblems.

Main Results:

• The proposed partitioning methods were demonstrated to be effective.
• These methods lead to improved solutions for large optimization problems compared to existing approaches.
• The partitioning strategies help manage the increased search space and infeasible solutions inherent in one-hot encoding.

Conclusions:

• The developed partitioning methods are crucial for efficiently solving large integer optimization problems with quantum annealers.
• This research advances the practical application of quantum annealing for complex real-world optimization tasks.
• Further research into partitioning strategies can unlock the full potential of quantum annealing for optimization.