Controlling Continuous Relaxation for Combinatorial Optimization

• URL: http://arxiv.org/abs/2309.16965v4
• Date: Thu, 31 Oct 2024 12:21:32 GMT
• Title: Controlling Continuous Relaxation for Combinatorial Optimization
• Authors: Yuma Ichikawa,
• Abstract summary: Unsupervised learning solvers for optimization (CO) train a neural network that generates a soft solution using a continuous relaxation strategy. This study introduces a Continuous Relaxation Anneal (CRA) strategy, an effective-free learning method for UL-based solvers.
• Score: 0.0
• License:
• Abstract: Unsupervised learning (UL)-based solvers for combinatorial optimization (CO) train a neural network that generates a soft solution by directly optimizing the CO objective using a continuous relaxation strategy. These solvers offer several advantages over traditional methods and other learning-based methods, particularly for large-scale CO problems. However, UL-based solvers face two practical issues: (I) an optimization issue, where UL-based solvers are easily trapped at local optima, and (II) a rounding issue, where UL-based solvers require artificial post-learning rounding from the continuous space back to the original discrete space, undermining the robustness of the results. This study proposes a Continuous Relaxation Annealing (CRA) strategy, an effective rounding-free learning method for UL-based solvers. CRA introduces a penalty term that dynamically shifts from prioritizing continuous solutions, effectively smoothing the non-convexity of the objective function, to enforcing discreteness, eliminating artificial rounding. Experimental results demonstrate that CRA significantly enhances the performance of UL-based solvers, outperforming existing UL-based solvers and greedy algorithms in complex CO problems. Additionally, CRA effectively eliminates artificial rounding and accelerates the learning process.

Related papers

• Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
  This study proposes a different approach that integrates gradient-based update through continuous relaxation, combined with Quasi-Quantum Annealing (QQA) Numerical experiments demonstrate that our method is a competitive general-purpose solver, achieving performance comparable to iSCO and learning-based solvers.
  arXiv  Detail & Related papers  (2024-09-02T12:55:27Z)
• Adaptive Layer Splitting for Wireless LLM Inference in Edge Computing: A Model-Based Reinforcement Learning Approach [18.153641696306707]
  This study introduces a framework taking inspiration from model-based reinforcement learning (MBRL) to determine the optimal splitting point across the edge and user equipment (UE) By incorporating a reward surrogate model, our approach significantly reduces the computational cost of frequent performance evaluations.
  arXiv  Detail & Related papers  (2024-06-03T09:41:42Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  We introduce an NN-based solver to significantly narrow the gap with advanced metaheuristics. First, we propose direction-aware facilitating attention model (DaAM) to incorporate directionality into the embedding process. Second, we design a supervised reinforcement learning scheme that involves supervised pre-training to establish a robust initial policy.
  arXiv  Detail & Related papers  (2024-03-11T02:17:42Z)
• Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
  A machine learning (ML) model is trained to emulate a constrained optimization solver. This paper proposes an alternative approach, in which the ML model is trained to predict dual solution estimates directly. It enables an end-to-end training scheme is which the dual objective is as a loss function, and solution estimates toward primal feasibility, emulating a Dual Ascent method.
  arXiv  Detail & Related papers  (2024-03-06T04:43:22Z)
• Continuous Tensor Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems [0.6906005491572401]
  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.
  arXiv  Detail & Related papers  (2024-02-03T15:31:05Z)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  We introduce UnRolled Federated learning (SURF), a method that expands algorithm unrolling to federated learning. Our proposed method tackles two challenges of this expansion, namely the need to feed whole datasets to the unrolleds and the decentralized nature of federated learning.
  arXiv  Detail & Related papers  (2023-05-24T17:26:22Z)
• Federated Compositional Deep AUC Maximization [58.25078060952361]
  We develop a novel federated learning method for imbalanced data by directly optimizing the area under curve (AUC) score. To the best of our knowledge, this is the first work to achieve such favorable theoretical results.
  arXiv  Detail & Related papers  (2023-04-20T05:49:41Z)
• Accelerating Federated Edge Learning via Topology Optimization [41.830942005165625]
  Federated edge learning (FEEL) is envisioned as a promising paradigm to achieve privacy-preserving distributed learning. It consumes excessive learning time due to the existence of straggler devices. A novel topology-optimized federated edge learning (TOFEL) scheme is proposed to tackle the heterogeneity issue in federated learning.
  arXiv  Detail & Related papers  (2022-04-01T14:49:55Z)
• Learning for Robust Combinatorial Optimization: Algorithm and Application [26.990988571097827]
  Learning to optimize (L2O) has emerged as a promising approach to solving optimization problems by exploiting the strong prediction power of neural networks. In this paper, we propose a novel learning-based optimization, called LRCO, which quickly outputs a robust solution in the presence of uncertain context. Our results highlight that LRCO can greatly reduce the worst-case cost and runtime, while having a very low complexity.
  arXiv  Detail & Related papers  (2021-12-20T07:58:50Z)
• Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization [85.84019017587477]
  Distributionally robust supervised learning is emerging as a key paradigm for building reliable machine learning systems for real-world applications. Existing algorithms for solving Wasserstein DRSL involve solving complex subproblems or fail to make use of gradients. We revisit Wasserstein DRSL through the lens of min-max optimization and derive scalable and efficiently implementable extra-gradient algorithms.
  arXiv  Detail & Related papers  (2021-04-27T16:56:09Z)
• 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.