Continuous Tensor Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems

• URL: http://arxiv.org/abs/2402.02190v2
• Date: Sat, 25 May 2024 04:42:24 GMT
• Title: Continuous Tensor Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems
• Authors: Yuma Ichikawa, Hiroaki Iwashita,
• Abstract summary: This study introduces Continual Anne Relaxationing (CTRA) for unsupervised-learning (UL)-based CO solvers. CTRA is a computationally efficient framework for finding diverse solutions in a single training run. Numerical experiments show that CTRA enables UL-based solvers to find these diverse solutions much faster than repeatedly running existing solvers.
• Score: 0.6906005491572401
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding the best solution is a common objective in combinatorial optimization (CO). In practice, directly handling constraints is often challenging, incorporating them into the objective function as the penalties. However, balancing these penalties to achieve the desired solution is time-consuming. Additionally, formulated objective functions and constraints often only approximate real-world scenarios, where the optimal solution is not necessarily the best solution for the original real-world problem. One solution is to obtain (i) penalty-diversified solutions with varying penalty strengths for the former issue and (ii) variation-diversified solutions with different characteristics for the latter issue. Users can then post-select the desired solution from these diverse solutions. However, efficiently finding these diverse solutions is more difficult than identifying one. This study introduces Continual Tensor Relaxation Annealing (CTRA) for unsupervised-learning (UL)-based CO solvers, a computationally efficient framework for finding these diverse solutions in a single training run. The key idea is to leverage representation learning capability to automatically and efficiently learn common representations and parallelization. Numerical experiments show that CTRA enables UL-based solvers to find these diverse solutions much faster than repeatedly running existing UL-based solvers.

Related papers

• RL-MILP Solver: A Reinforcement Learning Approach for Solving Mixed-Integer Linear Programs with Graph Neural Networks [3.3894236476098185]
  Mixed-integer linear programming (MILP) is a widely used optimization technique across various fields. We propose a novel reinforcement learning (RL)-based solver that not only finds the first feasible solution but also incrementally discovers better feasible solutions.
  arXiv  Detail & Related papers  (2024-11-29T07:23:34Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  Combinatorial optimization (CO) problems are often NP-hard and out of reach for exact algorithms. GFlowNets have emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially. In this paper, we design Markov decision processes (MDPs) for different problems and propose to train conditional GFlowNets to sample from the solution space.
  arXiv  Detail & Related papers  (2023-05-26T15:13:09Z)
• Improved Training of Physics-Informed Neural Networks with Model Ensembles [81.38804205212425]
  We propose to expand the solution interval gradually to make the PINN converge to the correct solution. All ensemble members converge to the same solution in the vicinity of observed data. We show experimentally that the proposed method can improve the accuracy of the found solution.
  arXiv  Detail & Related papers  (2022-04-11T14:05:34Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• A Mutual Information Maximization Approach for the Spurious Solution Problem in Weakly Supervised Question Answering [60.768146126094955]
  Weakly supervised question answering usually has only the final answers as supervision signals. There may exist many spurious solutions that coincidentally derive the correct answer, but training on such solutions can hurt model performance. We propose to explicitly exploit such semantic correlations by maximizing the mutual information between question-answer pairs and predicted solutions.
  arXiv  Detail & Related papers  (2021-06-14T05:47:41Z)
• Discovering Diverse Solutions in Deep Reinforcement Learning [84.45686627019408]
  Reinforcement learning algorithms are typically limited to learning a single solution of a specified task. We propose an RL method that can learn infinitely many solutions by training a policy conditioned on a continuous or discrete low-dimensional latent variable.
  arXiv  Detail & Related papers  (2021-03-12T04:54:31Z)
• Reversible Action Design for Combinatorial Optimization with Reinforcement Learning [35.50454156611722]
  Reinforcement learning (RL) has recently emerged as a new framework to tackle these problems. We propose a general RL framework that not only exhibits state-of-the-art empirical performance but also generalizes to a variety class of COPs.
  arXiv  Detail & Related papers  (2021-02-14T18:05:42Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.