A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs

• URL: http://arxiv.org/abs/2106.04927v1
• Date: Wed, 9 Jun 2021 09:18:18 GMT
• Title: A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs
• Authors: Runzhong Wang, Zhigang Hua, Gan Liu, Jiayi Zhang, Junchi Yan, Feng Qi, Shuang Yang, Jun Zhou, Xiaokang Yang
• Abstract summary: We propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity.
• Score: 91.07247251502564
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial Optimization (CO) has been a long-standing challenging research topic featured by its NP-hard nature. Traditionally such problems are approximately solved with heuristic algorithms which are usually fast but may sacrifice the solution quality. Currently, machine learning for combinatorial optimization (MLCO) has become a trending research topic, but most existing MLCO methods treat CO as a single-level optimization by directly learning the end-to-end solutions, which are hard to scale up and mostly limited by the capacity of ML models given the high complexity of CO. In this paper, we propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph (e.g. add, delete or modify edges in a graph), fused with a lower-level heuristic algorithm solving on the optimized graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity. The experiments and results on several popular CO problems like Directed Acyclic Graph scheduling, Graph Edit Distance and Hamiltonian Cycle Problem show its effectiveness over manually designed heuristics and single-level learning methods.

Related papers

• Learning to Optimize for Mixed-Integer Non-linear Programming [20.469394148261838]
  Mixed-integer non-NLP programs (MINLPs) arise in various domains, such as energy systems and transportation, but are notoriously difficult to solve. Recent advances in machine learning have led to remarkable successes in optimization, area broadly known as learning to optimize. We propose two differentiable correction layers that generate integer outputs while preserving gradient.
  arXiv  Detail & Related papers  (2024-10-14T20:14:39Z)
• An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem [5.092968949752308]
  This work proposes an unsupervised learning framework combined with Maximums for MMCP. A crucial observation is that each solution corresponds to at least one spanning tree. We conduct extensive experiments to evaluate our framework and give a specific application.
  arXiv  Detail & Related papers  (2024-08-16T02:07:34Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  An emerging strategy to tackle optimization problems involves the adoption of graph neural networks (GNNs) as an alternative to traditional algorithms. Despite the growing popularity of GNNs and traditional algorithm solvers in the realm of CO, there is limited research on their integrated use and the correlation between them within an end-to-end framework. We introduce a decision-focused framework that utilizes GNNs to address CO problems with auxiliary support.
  arXiv  Detail & Related papers  (2024-06-05T22:52:27Z)
• 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)
• Contextual Stochastic Bilevel Optimization [50.36775806399861]
  We introduce contextual bilevel optimization (CSBO) -- a bilevel optimization framework with the lower-level problem minimizing an expectation on some contextual information and the upper-level variable. It is important for applications such as meta-learning, personalized learning, end-to-end learning, and Wasserstein distributionally robustly optimization with side information (WDRO-SI)
  arXiv  Detail & Related papers  (2023-10-27T23:24:37Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Effective and efficient structure learning with pruning and model averaging strategies [9.023722579074734]
  This paper describes an approximate BN structure learning algorithm that combines two novel strategies with hill-climbing search. The algorithm starts by pruning the search space graphs, where the pruning strategy can be viewed as an aggressive version of the pruning strategies. It then performs model averaging in the hill-climbing search process and moves to the neighbouring graph that maximises the objective function.
  arXiv  Detail & Related papers  (2021-12-01T10:35:34Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  We introduce a Cogradient Descent algorithm (CoGD) to address the bilinear problem. We solve one variable by considering its coupling relationship with the other, leading to a synchronous gradient descent. Our algorithm is applied to solve problems with one variable under the sparsity constraint.
  arXiv  Detail & Related papers  (2020-06-16T13:41:54Z)
• Gumbel-softmax-based Optimization: A Simple General Framework for Optimization Problems on Graphs [5.486093983007419]
  We propose a simple, fast, and general algorithm framework based on advanced automatic differentiation technique empowered by deep learning frameworks. High-quality solutions can be obtained with much less time consuming compared to traditional approaches.
  arXiv  Detail & Related papers  (2020-04-14T14:11:00Z)

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.