Lifelong Learning for Neural powered Mixed Integer Programming

• URL: http://arxiv.org/abs/2208.12226v3
• Date: Fri, 30 Jun 2023 11:01:01 GMT
• Title: Lifelong Learning for Neural powered Mixed Integer Programming
• Authors: Sahil Manchanda, Sayan Ranu
• Abstract summary: Mixed programs (MIPs) are typically solved by the Branch-and-Bound algorithm. We propose LIMIP, which is powered by the idea of modeling an MIP instance in branching form of a bipartite graph. We evaluate LIMIP on a series of NP-hard problems and establish that in comparison to existing baselines, LIMIP is up to 50% better when confronted with lifelong learning.
• Score: 6.297356207581819
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Mixed Integer programs (MIPs) are typically solved by the Branch-and-Bound algorithm. Recently, Learning to imitate fast approximations of the expert strong branching heuristic has gained attention due to its success in reducing the running time for solving MIPs. However, existing learning-to-branch methods assume that the entire training data is available in a single session of training. This assumption is often not true, and if the training data is supplied in continual fashion over time, existing techniques suffer from catastrophic forgetting. In this work, we study the hitherto unexplored paradigm of Lifelong Learning to Branch on Mixed Integer Programs. To mitigate catastrophic forgetting, we propose LIMIP, which is powered by the idea of modeling an MIP instance in the form of a bipartite graph, which we map to an embedding space using a bipartite Graph Attention Network. This rich embedding space avoids catastrophic forgetting through the application of knowledge distillation and elastic weight consolidation, wherein we learn the parameters key towards retaining efficacy and are therefore protected from significant drift. We evaluate LIMIP on a series of NP-hard problems and establish that in comparison to existing baselines, LIMIP is up to 50% better when confronted with lifelong learning.

Related papers

• Patch-Based Contrastive Learning and Memory Consolidation for Online Unsupervised Continual Learning [6.042269506496206]
  We focus on a relatively unexplored learning paradigm known as em Online Unsupervised Continual Learning (O-UCL) Unlike prior work in unsupervised, continual, or online learning, O-UCL combines all three areas into a single challenging and realistic learning paradigm. In this setting, agents are frequently evaluated and must aim to maintain the best possible representation at any point of the data stream, rather than at the end of pre-specified offline tasks.
  arXiv  Detail & Related papers  (2024-09-24T18:46:32Z)
• Near-Optimal Learning and Planning in Separated Latent MDPs [70.88315649628251]
  We study computational and statistical aspects of learning Latent Markov Decision Processes (LMDPs) In this model, the learner interacts with an MDP drawn at the beginning of each epoch from an unknown mixture of MDPs.
  arXiv  Detail & Related papers  (2024-06-12T06:41:47Z)
• ECLIPSE: Efficient Continual Learning in Panoptic Segmentation with Visual Prompt Tuning [54.68180752416519]
  Panoptic segmentation is a cutting-edge computer vision task. We introduce a novel and efficient method for continual panoptic segmentation based on Visual Prompt Tuning, dubbed ECLIPSE. Our approach involves freezing the base model parameters and fine-tuning only a small set of prompt embeddings, addressing both catastrophic forgetting and plasticity.
  arXiv  Detail & Related papers  (2024-03-29T11:31:12Z)
• Scalable Federated Unlearning via Isolated and Coded Sharding [76.12847512410767]
  Federated unlearning has emerged as a promising paradigm to erase the client-level data effect. This paper proposes a scalable federated unlearning framework based on isolated sharding and coded computing.
  arXiv  Detail & Related papers  (2024-01-29T08:41:45Z)
• On the Soft-Subnetwork for Few-shot Class Incremental Learning [67.0373924836107]
  We propose a few-shot class incremental learning (FSCIL) method referred to as emphSoft-SubNetworks (SoftNet). Our objective is to learn a sequence of sessions incrementally, where each session only includes a few training instances per class while preserving the knowledge of the previously learned ones. We provide comprehensive empirical validations demonstrating that our SoftNet effectively tackles the few-shot incremental learning problem by surpassing the performance of state-of-the-art baselines over benchmark datasets.
  arXiv  Detail & Related papers  (2022-09-15T04:54:02Z)
• Branch Ranking for Efficient Mixed-Integer Programming via Offline Ranking-based Policy Learning [45.1011106869493]
  We formulate learning to branch as an offline reinforcement learning (RL) problem. We train a branching model named Branch Ranking via offline policy learning. Experiments on synthetic MIP benchmarks and real-world tasks demonstrate that Branch Rankink is more efficient and robust.
  arXiv  Detail & Related papers  (2022-07-26T15:34:10Z)
• Continual Learning with Guarantees via Weight Interval Constraints [18.791232422083265]
  We introduce a new training paradigm that enforces interval constraints on neural network parameter space to control forgetting. We show how to put bounds on forgetting by reformulating continual learning of a model as a continual contraction of its parameter space.
  arXiv  Detail & Related papers  (2022-06-16T08:28:37Z)
• Local Learning Matters: Rethinking Data Heterogeneity in Federated Learning [61.488646649045215]
  Federated learning (FL) is a promising strategy for performing privacy-preserving, distributed learning with a network of clients (i.e., edge devices)
  arXiv  Detail & Related papers  (2021-11-28T19:03:39Z)
• Learn-Prune-Share for Lifelong Learning [25.678753894026357]
  We propose a learn-prune-share (LPS) algorithm which addresses the challenges of catastrophic forgetting, parsimony, and knowledge reuse simultaneously. LPS splits the network into task-specific partitions via an ADMM-based pruning strategy. This leads to no forgetting, while maintaining parsimony.
  arXiv  Detail & Related papers  (2020-12-13T04:05:16Z)
• Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
  This work shows that these hardness barriers do not preclude efficient reinforcement learning for rich and interesting subclasses of Partially Observable Decision Processes (POMDPs) We present a sample-efficient algorithm, OOM-UCB, for episodic finite undercomplete POMDPs, where the number of observations is larger than the number of latent states and where exploration is essential for learning, thus distinguishing our results from prior works.
  arXiv  Detail & Related papers  (2020-06-22T17:58:54Z)

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.