CAMBranch: Contrastive Learning with Augmented MILPs for Branching

• URL: http://arxiv.org/abs/2402.03647v1
• Date: Tue, 6 Feb 2024 02:47:16 GMT
• Title: CAMBranch: Contrastive Learning with Augmented MILPs for Branching
• Authors: Jiacheng Lin, Meng Xu, Zhihua Xiong, Huangang Wang
• Abstract summary: We propose a framework that generates Augmented MILPs (AMILPs) by applying variable shifting to limited expert data from their original MILPs. Results demonstrate that CAMBranch, trained with only 10% of the complete dataset, exhibits superior performance.
• Score: 5.216027167816416
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent advancements have introduced machine learning frameworks to enhance the Branch and Bound (B\&B) branching policies for solving Mixed Integer Linear Programming (MILP). These methods, primarily relying on imitation learning of Strong Branching, have shown superior performance. However, collecting expert samples for imitation learning, particularly for Strong Branching, is a time-consuming endeavor. To address this challenge, we propose \textbf{C}ontrastive Learning with \textbf{A}ugmented \textbf{M}ILPs for \textbf{Branch}ing (CAMBranch), a framework that generates Augmented MILPs (AMILPs) by applying variable shifting to limited expert data from their original MILPs. This approach enables the acquisition of a considerable number of labeled expert samples. CAMBranch leverages both MILPs and AMILPs for imitation learning and employs contrastive learning to enhance the model's ability to capture MILP features, thereby improving the quality of branching decisions. Experimental results demonstrate that CAMBranch, trained with only 10\% of the complete dataset, exhibits superior performance. Ablation studies further validate the effectiveness of our method.

Related papers

• Dynamic Prompt Adjustment for Multi-Label Class-Incremental Learning [0.13654846342364302]
  Visual language models such as CLIP have achieved good results in classification tasks. We integrate an improved data replay mechanism and prompt loss to curb knowledge forgetting. Our method has substantially improved the performance of MLCIL tasks across multiple benchmark datasets.
  arXiv  Detail & Related papers  (2024-12-31T08:23:45Z)
• SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch [33.90726769113883]
  Mixed Linear Program (MILP) solvers are mostly built upon a Branch sampling-and-Bound (B&B) algorithm, where the efficiency of traditional solvers heavily depends on hand-crafteds for branching. This paper proposes Sub-optimal-Demonstration-Reinforcement Learning (SORREL) for learning to branch.
  arXiv  Detail & Related papers  (2024-12-20T03:48:53Z)
• CLLMFS: A Contrastive Learning enhanced Large Language Model Framework for Few-Shot Named Entity Recognition [3.695767900907561]
  CLLMFS is a Contrastive Learning enhanced Large Language Model framework for Few-Shot Named Entity Recognition. It integrates Low-Rank Adaptation (LoRA) and contrastive learning mechanisms specifically tailored for few-shot NER. Our method has achieved state-of-the-art performance improvements on F1-score ranging from 2.58% to 97.74% over existing best-performing methods.
  arXiv  Detail & Related papers  (2024-08-23T04:44:05Z)
• Diversifying the Expert Knowledge for Task-Agnostic Pruning in Sparse Mixture-of-Experts [75.85448576746373]
  We propose a method of grouping and pruning similar experts to improve the model's parameter efficiency. We validate the effectiveness of our method by pruning three state-of-the-art MoE architectures. The evaluation shows that our method outperforms other model pruning methods on a range of natural language tasks.
  arXiv  Detail & Related papers  (2024-07-12T17:25:02Z)
• Representation Learning For Efficient Deep Multi-Agent Reinforcement Learning [10.186029242664931]
  We present MAPO-LSO which applies a form of comprehensive representation learning devised to supplement MARL training. Specifically, MAPO-LSO proposes a multi-agent extension of transition dynamics reconstruction and self-predictive learning. Empirical results demonstrate MAPO-LSO to show notable improvements in sample efficiency and learning performance compared to its vanilla MARL counterpart.
  arXiv  Detail & Related papers  (2024-06-05T03:11:44Z)
• Deep Boosting Learning: A Brand-new Cooperative Approach for Image-Text Matching [53.05954114863596]
  We propose a brand-new Deep Boosting Learning (DBL) algorithm for image-text matching. An anchor branch is first trained to provide insights into the data properties. A target branch is concurrently tasked with more adaptive margin constraints to further enlarge the relative distance between matched and unmatched samples.
  arXiv  Detail & Related papers  (2024-04-28T08:44:28Z)
• MA2CL:Masked Attentive Contrastive Learning for Multi-Agent Reinforcement Learning [128.19212716007794]
  We propose an effective framework called textbfMulti-textbfAgent textbfMasked textbfAttentive textbfContrastive textbfLearning (MA2CL) MA2CL encourages learning representation to be both temporal and agent-level predictive by reconstructing the masked agent observation in latent space. Our method significantly improves the performance and sample efficiency of different MARL algorithms and outperforms other methods in various vision-based and state-based scenarios.
  arXiv  Detail & Related papers  (2023-06-03T05:32:19Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  Machine learning has emerged as a promising paradigm for branching. We propose retro branching; a simple yet effective approach to RL for branching. We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables.
  arXiv  Detail & Related papers  (2022-05-28T06:08:07Z)
• Softmax with Regularization: Better Value Estimation in Multi-Agent Reinforcement Learning [72.28520951105207]
  Overestimation in $Q$-learning is an important problem that has been extensively studied in single-agent reinforcement learning. We propose a novel regularization-based update scheme that penalizes large joint action-values deviating from a baseline. We show that our method provides a consistent performance improvement on a set of challenging StarCraft II micromanagement tasks.
  arXiv  Detail & Related papers  (2021-03-22T14:18:39Z)
• Learning From Multiple Experts: Self-paced Knowledge Distillation for Long-tailed Classification [106.08067870620218]
  We propose a self-paced knowledge distillation framework, termed Learning From Multiple Experts (LFME) We refer to these models as 'Experts', and the proposed LFME framework aggregates the knowledge from multiple 'Experts' to learn a unified student model. We conduct extensive experiments and demonstrate that our method is able to achieve superior performances compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-01-06T12:57:36Z)

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.