CLCR: Contrastive Learning-based Constraint Reordering for Efficient MILP Solving

• URL: http://arxiv.org/abs/2504.03688v1
• Date: Sun, 23 Mar 2025 05:01:43 GMT
• Title: CLCR: Contrastive Learning-based Constraint Reordering for Efficient MILP Solving
• Authors: Shuli Zeng, Mengjie Zhou, Sijia Zhang, Yixiang Hu, Feng Wu, Xiang-Yang Li,
• Abstract summary: Constraint ordering plays a critical role in the efficiency of Mixed-Integer Linear Programming (MILP) solvers.<n>This paper introduces CLCR (Contrastive Learning-based Constraint Reordering), a novel framework that systematically optimize constraint ordering to accelerate MILP solving.<n> Experiments on benchmarks show CLCR reduces solving time by 30% and LP iterations by 25% on average, without sacrificing solution accuracy.
• Score: 34.127805466651864
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Constraint ordering plays a critical role in the efficiency of Mixed-Integer Linear Programming (MILP) solvers, particularly for large-scale problems where poorly ordered constraints trigger increased LP iterations and suboptimal search trajectories. This paper introduces CLCR (Contrastive Learning-based Constraint Reordering), a novel framework that systematically optimizes constraint ordering to accelerate MILP solving. CLCR first clusters constraints based on their structural patterns and then employs contrastive learning with a pointer network to optimize their sequence, preserving problem equivalence while improving solver efficiency. Experiments on benchmarks show CLCR reduces solving time by 30% and LP iterations by 25% on average, without sacrificing solution accuracy. This work demonstrates the potential of data-driven constraint ordering to enhance optimization models, offering a new paradigm for bridging mathematical programming with machine learning.

Related papers

• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex. Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs. We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• Efficient Federated Split Learning for Large Language Models over Communication Networks [14.461758448289908]
  Fine-tuning pre-trained large language models (LLM) in a distributed manner poses significant challenges on resource-constrained edge devices. We propose FedsLLM, a novel framework that integrates split federated learning with parameter-efficient fine-tuning techniques.
  arXiv  Detail & Related papers  (2025-04-20T16:16:54Z)
• Towards Constraint-Based Adaptive Hypergraph Learning for Solving Vehicle Routing: An End-to-End Solution [4.965709007367529]
  Vehicle routing problems are characterized by vast solution spaces and intricate constraints.<n>This study introduces a novel end-to-end framework that combines constraint-oriented hypergraphs with reinforcement learning.
  arXiv  Detail & Related papers  (2025-03-13T14:42:44Z)
• Towards An Unsupervised Learning Scheme for Efficiently Solving Parameterized Mixed-Integer Programs [6.1860817947800655]
  We train an autoencoder for binary variables in an unsupervised learning fashion.<n>We present a strategy to construct a class of cutting plane constraints from the decoder parameters of an offline-trained AE.<n>Their integration into the primal MIP problem leads to a tightened MIP with the reduced feasible region.
  arXiv  Detail & Related papers  (2024-12-23T14:48:32Z)
• Attribute Controlled Fine-tuning for Large Language Models: A Case Study on Detoxification [76.14641982122696]
  We propose a constraint learning schema for fine-tuning Large Language Models (LLMs) with attribute control. We show that our approach leads to an LLM that produces fewer inappropriate responses while achieving competitive performance on benchmarks and a toxicity detection task.
  arXiv  Detail & Related papers  (2024-10-07T23:38:58Z)
• Enhancing Robustness of Vision-Language Models through Orthogonality Learning and Self-Regularization [77.62516752323207]
  We introduce an orthogonal fine-tuning method for efficiently fine-tuning pretrained weights and enabling enhanced robustness and generalization. A self-regularization strategy is further exploited to maintain the stability in terms of zero-shot generalization of VLMs, dubbed OrthSR. For the first time, we revisit the CLIP and CoOp with our method to effectively improve the model on few-shot image classficiation scenario.
  arXiv  Detail & Related papers  (2024-07-11T10:35:53Z)
• Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
  A machine learning (ML) model is trained to emulate a constrained optimization solver. This paper proposes an alternative approach, in which the ML model is trained to predict dual solution estimates directly. It enables an end-to-end training scheme is which the dual objective is as a loss function, and solution estimates toward primal feasibility, emulating a Dual Ascent method.
  arXiv  Detail & Related papers  (2024-03-06T04:43:22Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  We solve a weakly supervised regression problem. Under "weakly" we understand that for some training points the labels are known, for some unknown, and for others uncertain due to the presence of random noise or other reasons such as lack of resources. In the numerical section, we applied the suggested method to artificial and real datasets using Monte-Carlo modeling.
  arXiv  Detail & Related papers  (2021-04-13T23:21:01Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Constrained Combinatorial Optimization with Reinforcement Learning [0.30938904602244344]
  This paper presents a framework to tackle constrained optimization problems using deep Reinforcement Learning (RL) We extend the Neural Combinatorial Optimization (NCO) theory in order to deal with constraints in its formulation. In that context, the solution is iteratively constructed based on interactions with the environment.
  arXiv  Detail & Related papers  (2020-06-22T03:13:07Z)

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.