Hybrid Models for Learning to Branch

• URL: http://arxiv.org/abs/2006.15212v3
• Date: Fri, 23 Oct 2020 14:01:14 GMT
• Title: Hybrid Models for Learning to Branch
• Authors: Prateek Gupta, Maxime Gasse, Elias B. Khalil, M. Pawan Kumar, Andrea Lodi, Yoshua Bengio
• Abstract summary: 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.
• Score: 81.93868699246214
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A recent Graph Neural Network (GNN) approach for learning to branch has been shown to successfully reduce the running time of branch-and-bound algorithms for Mixed Integer Linear Programming (MILP). While the GNN relies on a GPU for inference, MILP solvers are purely CPU-based. This severely limits its application as many practitioners may not have access to high-end GPUs. In this work, we ask two key questions. First, in a more realistic setting where only a CPU is available, is the GNN model still competitive? Second, can we devise an alternate computationally inexpensive model that retains the predictive power of the GNN architecture? We answer the first question in the negative, and address the second question by proposing 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. We evaluate our methods on four classes of MILP problems, and show that they lead to up to 26% reduction in solver running time compared to state-of-the-art methods without a GPU, while extrapolating to harder problems than it was trained on. The code for this project is publicly available at https://github.com/pg2455/Hybrid-learn2branch.

Related papers

• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  Large-scale graph training is a notoriously challenging problem for graph neural networks (GNNs) We present a new ensembling training manner, named EnGCN, to address the existing issues. Our proposed method has achieved new state-of-the-art (SOTA) performance on large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-14T03:43:05Z)
• MLPInit: Embarrassingly Simple GNN Training Acceleration with MLP Initialization [51.76758674012744]
  Training graph neural networks (GNNs) on large graphs is complex and extremely time consuming. We propose an embarrassingly simple, yet hugely effective method for GNN training acceleration, called PeerInit.
  arXiv  Detail & Related papers  (2022-09-30T21:33:51Z)
• An efficient and flexible inference system for serving heterogeneous ensembles of deep neural networks [0.0]
  Ensembles of Deep Neural Networks (DNNs) have achieved qualitative predictions but they are computing and memory intensive. We propose a new software layer to serve with flexibility and efficiency ensembles of DNNs.
  arXiv  Detail & Related papers  (2022-08-30T08:05:43Z)
• DOGE-Train: Discrete Optimization on GPU with End-to-end Training [28.795080637690095]
  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.
  arXiv  Detail & Related papers  (2022-05-23T21:09:41Z)
• A Unified Lottery Ticket Hypothesis for Graph Neural Networks [82.31087406264437]
  We present a unified GNN sparsification (UGS) framework that simultaneously prunes the graph adjacency matrix and the model weights. We further generalize the popular lottery ticket hypothesis to GNNs for the first time, by defining a graph lottery ticket (GLT) as a pair of core sub-dataset and sparse sub-network.
  arXiv  Detail & Related papers  (2021-02-12T21:52:43Z)
• PyTorch-Direct: Enabling GPU Centric Data Access for Very Large Graph Neural Network Training with Irregular Accesses [19.2129567657739]
  We introduce PyTorch-Direct, which enables a GPU-centric data accessing paradigm for graph neural networks (GNNs) training. Our microbenchmark and end-to-end GNN training results show that PyTorch-Direct reduces data transfer time by 47.1% on average and speeds up GNN training by up to 1.6x.
  arXiv  Detail & Related papers  (2021-01-20T04:24:39Z)
• Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
  We present the PPRGo model which utilizes an efficient approximation of information diffusion in GNNs. In addition to being faster, PPRGo is inherently scalable, and can be trivially parallelized for large datasets like those found in industry settings. We show that training PPRGo and predicting labels for all nodes in this graph takes under 2 minutes on a single machine, far outpacing other baselines on the same graph.
  arXiv  Detail & Related papers  (2020-07-03T09:30:07Z)
• MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models [96.1052289276254]
  This work introduces a new MAP-solver, based on the popular Dual Block-Coordinate Ascent principle. Surprisingly, by making a small change to the low-performing solver, we derive the new solver MPLP++ that significantly outperforms all existing solvers by a large margin.
  arXiv  Detail & Related papers  (2020-04-16T16:20:53Z)
• GLSearch: Maximum Common Subgraph Detection via Learning to Search [33.9052190473029]
  We propose GLSearch, a Graph Neural Network (GNN) based learning to search model. Our model is built upon the branch and bound bound, which selects one pair of nodes from the two input graphs to expand at a time. Our GLSearch can be potentially extended to solve many other problems with constraints on graphs.
  arXiv  Detail & Related papers  (2020-02-08T10:03:40Z)

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.