DOGE-Train: Discrete Optimization on GPU with End-to-end Training
- URL: http://arxiv.org/abs/2205.11638v2
- Date: Thu, 28 Dec 2023 20:55:19 GMT
- Title: DOGE-Train: Discrete Optimization on GPU with End-to-end Training
- Authors: Ahmed Abbas, Paul Swoboda
- Abstract summary: We present a fast, scalable, data-driven approach for solving relaxations of 0-1 integer linear programs.
We use a combination of graph neural networks (GNN) and the Lagrange decomposition based algorithm FastDOG.
- Score: 28.795080637690095
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a fast, scalable, data-driven approach for solving relaxations of
0-1 integer linear programs. We use a combination of graph neural networks
(GNN) and the Lagrange decomposition based algorithm FastDOG (Abbas and Swoboda
2022b). We make the latter differentiable for end-to-end training and use GNNs
to predict its algorithmic parameters. This allows to retain the algorithm's
theoretical properties including dual feasibility and guaranteed non-decrease
in the lower bound while improving it via training. We overcome suboptimal
fixed points of the basic solver by additional non-parametric GNN update steps
maintaining dual feasibility. For training we use an unsupervised loss. We
train on smaller problems and test on larger ones showing strong generalization
performance with a GNN comprising only around $10k$ parameters. Our solver
achieves significantly faster performance and better dual objectives than its
non-learned version, achieving close to optimal objective values of LP
relaxations of very large structured prediction problems and on selected
combinatorial ones. In particular, we achieve better objective values than
specialized approximate solvers for specific problem classes while retaining
their efficiency. Our solver has better any-time performance over a large time
period compared to a commercial solver. Code available at
https://github.com/LPMP/BDD
Related papers
- Newton Losses: Using Curvature Information for Learning with Differentiable Algorithms [80.37846867546517]
We show how to train eight different neural networks with custom objectives.
We exploit their second-order information via their empirical Fisherssian matrices.
We apply Loss Lossiable algorithms to achieve significant improvements for less differentiable algorithms.
arXiv Detail & Related papers (2024-10-24T18:02:11Z) - Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
We introduce a novel algorithm, denoted hereafter as QRF-GNN, leveraging the power of GNNs to efficiently solve Combinatorial optimization (CO) problems.
It relies on unsupervised learning by minimizing the loss function derived from QUBO relaxation.
Results of experiments show that QRF-GNN drastically surpasses existing learning-based approaches and is comparable to the state-of-the-art conventionals.
arXiv Detail & Related papers (2024-07-23T13:34:35Z) - T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining.
Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
arXiv Detail & Related papers (2023-10-05T02:58:29Z) - Searching Large Neighborhoods for Integer Linear Programs with
Contrastive Learning [39.40838358438744]
Linear Programs (ILPs) are powerful tools for modeling and solving a large number of optimization problems.
Large Neighborhood Search (LNS), as a algorithm, can find high quality solutions to ILPs faster than Branch and Bound.
We propose a novel approach, CL-LNS, that delivers state-of-the-art anytime performance on several ILP benchmarks measured by metrics.
arXiv Detail & Related papers (2023-02-03T07:15:37Z) - Learning To Dive In Branch And Bound [95.13209326119153]
We propose L2Dive to learn specific diving structurals with graph neural networks.
We train generative models to predict variable assignments and leverage the duality of linear programs to make diving decisions.
arXiv Detail & Related papers (2023-01-24T12:01:45Z) - On Representing Linear Programs by Graph Neural Networks [30.998508318941017]
Graph neural network (GNN) is considered a suitable machine learning model for optimization problems.
This paper establishes the theoretical foundation of applying GNNs to solving linear program (LP) problems.
We show that properly built GNNs can reliably predict feasibility, boundedness, and an optimal solution for each LP in a broad class.
arXiv Detail & Related papers (2022-09-25T18:27:33Z) - Fast Graph Learning with Unique Optimal Solutions [31.411988486916545]
We propose efficient GRL methods that optimize convexified objectives with known closed form solutions.
Our proposed method achieves competitive or state-of-the-art performance on popular GRL tasks.
arXiv Detail & Related papers (2021-02-17T02:00:07Z) - Hybrid Models for Learning to Branch [81.93868699246214]
We propose a new hybrid architecture for efficient branching on CPU machines.
The proposed architecture combines the expressive power of GNNs with computationally inexpensive multi-layer perceptrons (MLP) for branching.
arXiv Detail & Related papers (2020-06-26T21:03:45Z) - Learning to Optimize Non-Rigid Tracking [54.94145312763044]
We employ learnable optimizations to improve robustness and speed up solver convergence.
First, we upgrade the tracking objective by integrating an alignment data term on deep features which are learned end-to-end through CNN.
Second, we bridge the gap between the preconditioning technique and learning method by introducing a ConditionNet which is trained to generate a preconditioner.
arXiv Detail & Related papers (2020-03-27T04:40:57Z) - Self-Directed Online Machine Learning for Topology Optimization [58.920693413667216]
Self-directed Online Learning Optimization integrates Deep Neural Network (DNN) with Finite Element Method (FEM) calculations.
Our algorithm was tested by four types of problems including compliance minimization, fluid-structure optimization, heat transfer enhancement and truss optimization.
It reduced the computational time by 2 5 orders of magnitude compared with directly using methods, and outperformed all state-of-the-art algorithms tested in our experiments.
arXiv Detail & Related papers (2020-02-04T20:00:28Z)
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.