Continuous Parallel Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems

• URL: http://arxiv.org/abs/2402.02190v3
• Date: Thu, 14 Aug 2025 12:55:12 GMT
• Title: Continuous Parallel Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems
• Authors: Yuma Ichikawa, Hiroaki Iwashita,
• Abstract summary: Finding the optimal solution is often the primary goal in optimization (CO)<n>This study introduces Continual Parallel Relaxation Annealing (CPRA), a computationally efficient framework for unsupervised-learning (UL)-based CO solvers.
• Score: 0.6906005491572401
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding the optimal solution is often the primary goal in combinatorial optimization (CO). However, real-world applications frequently require diverse solutions rather than a single optimum, particularly in two key scenarios. The first scenario occurs in real-world applications where strictly enforcing every constraint is neither necessary nor desirable. Allowing minor constraint violations can often lead to more cost-effective solutions. This is typically achieved by incorporating the constraints as penalty terms in the objective function, which requires careful tuning of penalty parameters. The second scenario involves cases where CO formulations tend to oversimplify complex real-world factors, such as domain knowledge, implicit trade-offs, or ethical considerations. To address these challenges, generating (i) penalty-diversified solutions by varying penalty intensities and (ii) variation-diversified solutions with distinct structural characteristics provides valuable insights, enabling practitioners to post-select the most suitable solution for their specific needs. However, efficiently discovering these diverse solutions is more challenging than finding a single optimal one. This study introduces Continual Parallel Relaxation Annealing (CPRA), a computationally efficient framework for unsupervised-learning (UL)-based CO solvers that generates diverse solutions within a single training run. CPRA leverages representation learning and parallelization to automatically discover shared representations, substantially accelerating the search for these diverse solutions. Numerical experiments demonstrate that CPRA outperforms existing UL-based solvers in generating these diverse solutions while significantly reducing computational costs.

Related papers

• FSNet: Feasibility-Seeking Neural Network for Constrained Optimization with Guarantees [3.345575993695074]
  Traditional solvers are often computationally prohibitive for real-time use.<n>Machine learning-based approaches have emerged as an alternative, but they struggle to strictly enforce constraints.<n>We propose the Feasibility-Seeking-Integrated Network (FSNet) to ensure constraint satisfaction.
  arXiv  Detail & Related papers  (2025-05-31T03:05:29Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex.<n>Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs.<n>We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• Pareto Optimal Algorithmic Recourse in Multi-cost Function [0.44938884406455726]
  algorithmic recourse aims to identify minimal-cost actions to alter an individual features, thereby obtaining a desired outcome.<n>Most current recourse mechanisms use gradient-based methods that assume cost functions are differentiable, often not applicable in real-world scenarios.<n>This work proposes an algorithmic recourse framework that handles nondifferentiable and discrete multi-cost functions.
  arXiv  Detail & Related papers  (2025-02-11T03:16:08Z)
• 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)
• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  Sequentially solving similar optimization problems under strict runtime constraints is essential for many applications. We propose learning to predict emphmultiple diverse initial solutions given parameters that define the problem instance. We find significant and consistent improvement with our method across all evaluation settings and demonstrate that it efficiently scales with the number of initial solutions required.
  arXiv  Detail & Related papers  (2024-11-04T15:17:19Z)
• DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems [37.205311971072405]
  DISCO is an efficient DIffusion solver for large-scale Combinatorial Optimization problems. It constrains the sampling space to a more meaningful domain guided by solution residues, while preserving the multi-modal properties of the output distributions. It delivers strong performance on large-scale Traveling Salesman Problems and challenging Maximal Independent Set benchmarks, with inference time up to 5.28 times faster than other diffusion alternatives.
  arXiv  Detail & Related papers  (2024-06-28T07:36:31Z)
• An Efficient Approach for Solving Expensive Constrained Multiobjective Optimization Problems [0.0]
  An efficient probabilistic selection based constrained multi-objective EA is proposed, referred to as PSCMOEA. It comprises novel elements such as (a) an adaptive search bound identification scheme based on the feasibility and convergence status of evaluated solutions. Numerical experiments are conducted on an extensive range of challenging constrained problems using low evaluation budgets to simulate ECMOPs.
  arXiv  Detail & Related papers  (2024-05-22T02:32:58Z)
• Combinatorial Optimization with Policy Adaptation using Latent Space Search [44.12073954093942]
  We present a novel approach for designing performant algorithms to solve complex, typically NP-hard, problems. We show that our search strategy outperforms state-of-the-art approaches on 11 standard benchmarking tasks.
  arXiv  Detail & Related papers  (2023-11-13T12:24:54Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• 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)
• Multi-Objective Constrained Optimization for Energy Applications via Tree Ensembles [55.23285485923913]
  Energy systems optimization problems are complex due to strongly non-linear system behavior and multiple competing objectives. In some cases, proposed optimal solutions need to obey explicit input constraints related to physical properties or safety-critical operating conditions. This paper proposes a novel data-driven strategy using tree ensembles for constrained multi-objective optimization of black-box problems.
  arXiv  Detail & Related papers  (2021-11-04T20:18:55Z)
• 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.