Continuous Tensor Relaxation for Finding Diverse Solutions in
  Combinatorial Optimization Problems
Yuma Ichikawa Hiroaki Iwashita
Finding the best solution is the most common objective in combinatorial
optimization (CO) problems. However, a single solution may not be suitable in
practical scenarios, as the objective functions and constraints are only
approximations of original real-world situations. To tackle this, finding (i)
"heterogeneous solutions", diverse solutions with distinct characteristics, and
(ii) "penalty-diversified solutions", variations in constraint severity, are
natural directions. This strategy provides the flexibility to select a suitable
solution during post-processing. However, discovering these diverse solutions
is more challenging than identifying a single solution. To overcome this
challenge, this study introduces Continual Tensor Relaxation Annealing (CTRA)
for unsupervised-learning-based CO solvers. CTRA addresses various problems
simultaneously by extending the continual relaxation approach, which transforms
discrete decision variables into continual tensors. This method finds
heterogeneous and penalty-diversified solutions through mutual interactions,
where the choice of one solution affects the other choices. Numerical
experiments show that CTRA enables UL-based solvers to find heterogeneous and
penalty-diversified solutions much faster than existing UL-based solvers.
Moreover, these experiments reveal that CTRA enhances the exploration ability.