Dynamic Stratified Contrastive Learning with Upstream Augmentation for MILP Branching

• URL: http://arxiv.org/abs/2511.21107v1
• Date: Wed, 26 Nov 2025 06:47:11 GMT
• Title: Dynamic Stratified Contrastive Learning with Upstream Augmentation for MILP Branching
• Authors: Tongkai Lu, Shuai Ma, Chongyang Tao,
• Abstract summary: Branch-and-Bound (B&B) is the dominant approach for solving Mixed Linear Programming (MILP)<n>We propose ours, a underlinetextbfStratified underlinetextbfContrastive Training Framework for underlinetextbfMILP Branching.<n>It groups branch-and-bound nodes based on their feature distributions and trains a GCNN-based discriminative model to progressively separate nodes.
• Score: 28.92346104523666
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Mixed Integer Linear Programming (MILP) is a fundamental class of NP-hard problems that has garnered significant attention from both academia and industry. The Branch-and-Bound (B\&B) method is the dominant approach for solving MILPs and the branching plays an important role in B\&B methods. Neural-based learning frameworks have recently been developed to enhance branching policies and the efficiency of solving MILPs. However, these methods still struggle with semantic variation across depths, the scarcity of upstream nodes, and the costly collection of strong branching samples. To address these issues, we propose \ours, a Dynamic \underline{\textbf{S}}tratified \underline{\textbf{C}}ontrastive Training Framework for \underline{\textbf{MILP}} Branching. It groups branch-and-bound nodes based on their feature distributions and trains a GCNN-based discriminative model to progressively separate nodes across groups, learning finer-grained node representations throughout the tree. To address data scarcity and imbalance at upstream nodes, we introduce an upstream-augmented MILP derivation procedure that generates both theoretically equivalent and perturbed instances. \ours~effectively models subtle semantic differences between nodes, significantly enhancing branching accuracy and solving efficiency, particularly for upstream nodes. Extensive experiments on standard MILP benchmarks demonstrate that our method enhances branching accuracy, reduces solving time, and generalizes effectively to unseen instances.

Related papers

• Instance-Aware Robust Consistency Regularization for Semi-Supervised Nuclei Instance Segmentation [53.94176748542936]
  We propose an Instance-Aware Robust Consistency Regularization Network (IRCR-Net) for accurate instance-level nuclei segmentation.<n>We incorporate morphological prior knowledge of nuclei in pathological images and utilize these priors to assess the quality of pseudo-labels generated from unlabeled data.
  arXiv  Detail & Related papers  (2025-10-10T12:32:32Z)
• Deep Hierarchical Learning with Nested Subspace Networks [53.71337604556311]
  We propose Nested Subspace Networks (NSNs) for large neural networks.<n>NSNs enable a single model to be dynamically and granularly adjusted across a continuous spectrum of compute budgets.<n>We show that NSNs can be surgically applied to pre-trained LLMs and unlock a smooth and predictable compute-performance frontier.
  arXiv  Detail & Related papers  (2025-09-22T15:13:14Z)
• Limits of message passing for node classification: How class-bottlenecks restrict signal-to-noise ratio [0.6117371161379209]
  Message passing neural networks (MPNNs) are powerful models for node classification but suffer from performance limitations under heterophily and structural bottlenecks in the graph.<n>We provide a unifying statistical framework exposing the relationship between heterophily and bottlenecks through the signal-to-noise ratio (SNR) of MPNN representations.<n>We prove that optimal graph structures for maximising higher-order homophily are disjoint unions of single-class and two-class-bipartite clusters.<n>This yields BRIDGE, a graph ensemble-based rewiring algorithm that achieves near-perfect classification accuracy across all homophily
  arXiv  Detail & Related papers  (2025-08-25T09:25:14Z)
• Neural Bridge Processes [21.702709965353804]
  We propose a novel method for modeling functions where inputs x act as dynamic anchors for the entire diffusion trajectory.<n>We validate NBPs on synthetic data, EEG signal regression and image regression tasks, achieving substantial improvements over baselines.
  arXiv  Detail & Related papers  (2025-08-10T07:44:52Z)
• FMIP: Joint Continuous-Integer Flow For Mixed-Integer Linear Programming [52.52020895303244]
  Mixed-Integer Linear Programming (MILP) is a foundational tool for complex decision-making problems.<n>We propose Joint Continuous-Integer Flow for Mixed-Integer Linear Programming (FMIP), which is the first generative framework that models joint distribution of both integer and continuous variables for MILP solutions.<n>FMIP is fully compatible with arbitrary backbone networks and various downstream solvers, making it well-suited for a broad range of real-world MILP applications.
  arXiv  Detail & Related papers  (2025-07-31T10:03:30Z)
• Lattice-Based Pruning in Recurrent Neural Networks via Poset Modeling [0.0]
  Recurrent neural networks (RNNs) are central to sequence modeling tasks, yet their high computational complexity poses challenges for scalability and real-time deployment.<n>We introduce a novel framework that models RNNs as partially ordered sets (posets) and constructs corresponding dependency lattices.<n>By identifying meet irreducible neurons, our lattice-based pruning algorithm selectively retains critical connections while eliminating redundant ones.
  arXiv  Detail & Related papers  (2025-02-23T10:11:38Z)
• Modularity aided consistent attributed graph clustering via coarsening [6.522020196906943]
  Graph clustering is an important unsupervised learning technique for partitioning graphs with attributes and detecting communities. We propose a loss function incorporating log-determinant, smoothness, and modularity components using a block majorization-minimization technique. Our algorithm seamlessly integrates graph neural networks (GNNs) and variational graph autoencoders (VGAEs) to learn enhanced node features and deliver exceptional clustering performance.
  arXiv  Detail & Related papers  (2024-07-09T10:42:19Z)
• FedDIP: Federated Learning with Extreme Dynamic Pruning and Incremental Regularization [5.182014186927254]
  Federated Learning (FL) has been successfully adopted for distributed training and inference of large-scale Deep Neural Networks (DNNs) We contribute with a novel FL framework (coined FedDIP) which combines (i) dynamic model pruning with error feedback to eliminate redundant information exchange. We provide convergence analysis of FedDIP and report on a comprehensive performance and comparative assessment against state-of-the-art methods.
  arXiv  Detail & Related papers  (2023-09-13T08:51:19Z)
• Lookback for Learning to Branch [77.32867454769936]
  Bipartite Graph Neural Networks (GNNs) have been shown to be an important component of deep learning based Mixed-Integer Linear Program (MILP) solvers. Recent works have demonstrated the effectiveness of such GNNs in replacing the branching (variable selection) in branch-and-bound (B&B) solvers.
  arXiv  Detail & Related papers  (2022-06-30T02:33:32Z)
• Mixed Graph Contrastive Network for Semi-Supervised Node Classification [63.924129159538076]
  We propose a novel graph contrastive learning method, termed Mixed Graph Contrastive Network (MGCN)<n>In our method, we improve the discriminative capability of the latent embeddings by an unperturbed augmentation strategy and a correlation reduction mechanism.<n>By combining the two settings, we extract rich supervision information from both the abundant nodes and the rare yet valuable labeled nodes for discriminative representation learning.
  arXiv  Detail & Related papers  (2022-06-06T14:26:34Z)
• Self-Ensembling GAN for Cross-Domain Semantic Segmentation [107.27377745720243]
  This paper proposes a self-ensembling generative adversarial network (SE-GAN) exploiting cross-domain data for semantic segmentation. In SE-GAN, a teacher network and a student network constitute a self-ensembling model for generating semantic segmentation maps, which together with a discriminator, forms a GAN. Despite its simplicity, we find SE-GAN can significantly boost the performance of adversarial training and enhance the stability of the model.
  arXiv  Detail & Related papers  (2021-12-15T09:50:25Z)
• Dynamic Hierarchical Mimicking Towards Consistent Optimization Objectives [73.15276998621582]
  We propose a generic feature learning mechanism to advance CNN training with enhanced generalization ability. Partially inspired by DSN, we fork delicately designed side branches from the intermediate layers of a given neural network. Experiments on both category and instance recognition tasks demonstrate the substantial improvements of our proposed method.
  arXiv  Detail & Related papers  (2020-03-24T09:56:13Z)

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.