Efficient bit labeling in factorization machines with annealing for traveling salesman problem

Area of Science:

• Computational Mathematics
• Machine Learning
• Operations Research

Background:

• Efficiently solving large-scale optimization problems requires converting parameters into machine-readable variables.
• Quadratic unconstrained binary optimization (QUBO) is a key technique, often employing machine learning models like factorization machines with annealing.
• The choice of binary labeling method significantly impacts cost function shape and susceptibility to local minima.

Purpose of the Study:

• To investigate how different binary labeling methods affect the convergence speed and accuracy of optimization algorithms.
• To evaluate the performance of a novel labeling strategy, Gray labeling, in solving optimization problems.

Main Methods:

• The study focuses on quadratic unconstrained binary optimization (QUBO) problems.
• Numerical simulations were performed using the Traveling Salesman Problem (TSP) as a benchmark.
• Gray labeling was proposed and compared against natural labeling for binary variable conversion.

Main Results:

• Gray labeling demonstrated a reduced percentage of local minima compared to natural labeling.
• The proposed Gray labeling resulted in shorter traveling distances for the TSP instances simulated.
• Performance was evaluated within a limited number of iterations, highlighting efficiency gains.

Conclusions:

• Binary labeling methods critically influence the performance of QUBO solvers.
• Gray labeling offers a superior approach for TSP and potentially other optimization problems by minimizing local optima.
• This research provides a valuable method for enhancing machine learning-based optimization strategies.