Constraint Matters: Multi-Modal Representation for Reducing Mixed-Integer Linear programming

• URL: http://arxiv.org/abs/2508.18742v2
• Date: Tue, 14 Oct 2025 09:36:10 GMT
• Title: Constraint Matters: Multi-Modal Representation for Reducing Mixed-Integer Linear programming
• Authors: Jiajun Li, Ran Hou, Yu Ding, Yixuan Li, Shisi Guan, Jiahui Duan, Xiongwei Han, Tao Zhong, Vincent Chau, Weiwei Wu, Wanyuan Wang,
• Abstract summary: This paper proposes a novel constraint-based model reduction approach for the MILP.<n>We show that our method improves the quality of the solution by over 50% and reduces the time by 17.47%.
• Score: 30.037594153262273
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Model reduction, which aims to learn a simpler model of the original mixed integer linear programming (MILP), can solve large-scale MILP problems much faster. Most existing model reduction methods are based on variable reduction, which predicts a solution value for a subset of variables. From a dual perspective, constraint reduction that transforms a subset of inequality constraints into equalities can also reduce the complexity of MILP, but has been largely ignored. Therefore, this paper proposes a novel constraint-based model reduction approach for the MILP. Constraint-based MILP reduction has two challenges: 1) which inequality constraints are critical such that reducing them can accelerate MILP solving while preserving feasibility, and 2) how to predict these critical constraints efficiently. To identify critical constraints, we first label these tight-constraints at the optimal solution as potential critical constraints and design a heuristic rule to select a subset of critical tight-constraints. To learn the critical tight-constraints, we propose a multi-modal representation technique that leverages information from both instance-level and abstract-level MILP formulations. The experimental results show that, compared to the state-of-the-art methods, our method improves the quality of the solution by over 50\% and reduces the computation time by 17.47\%.

Related papers

• Virtual Arc Consistency for Linear Constraints in Cost Function Networks [2.8675177318965037]
  We adapt an existing SAC algorithm to handle linear constraints.<n>We show that our algorithm significantly improves the lower bounds compared to the original algorithm on several benchmarks.
  arXiv  Detail & Related papers  (2025-09-22T12:44:52Z)
• Conformal Mixed-Integer Constraint Learning with Feasibility Guarantees [0.3058340744328236]
  Conformal Mixed-Integer Constraint Learning provides probabilistic feasibility guarantees for data-driven constraints in optimization problems.<n>We show that C-MICL consistently achieves target rates, maintains competitive objective performance, and significantly reduces computational cost compared to existing methods.
  arXiv  Detail & Related papers  (2025-06-04T03:26:31Z)
• 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.<n>Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs.<n>We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction [24.3088703166792]
  This paper aims to learn a reduced and equivalent model of the original MILP as an intermediate step.<n>The reduced model often corresponds to interpretable operations and is much simpler, enabling us to solve large-scale MILP problems much faster than existing commercial solvers.<n>We introduce an attention mechanism to capture and represent preference information, which helps improve the performance of model reduction learning tasks.
  arXiv  Detail & Related papers  (2024-12-31T06:50:42Z)
• Alternating Minimization Schemes for Computing Rate-Distortion-Perception Functions with $f$-Divergence Perception Constraints [10.564071872770146]
  We study the computation of the rate-distortion-perception function (RDPF) for discrete memoryless sources. We characterize the optimal parametric solutions. We provide sufficient conditions on the distortion and the perception constraints.
  arXiv  Detail & Related papers  (2024-08-27T12:50:12Z)
• 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)
• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  We study the Constrained Convex Decision Process (MDP), where the goal is to minimize a convex functional of the visitation measure. Design algorithms for a constrained convex MDP faces several challenges, including handling the large state space.
  arXiv  Detail & Related papers  (2024-02-16T16:35:18Z)
• Orthogonal Nonnegative Matrix Factorization with Sparsity Constraints [0.0]
  This article presents a novel approach to solving the sparsity-constrained Orthogonal Nonnegative Matrix Factorization (SCONMF) problem.<n>By reformulating SCONMF as a capacity-constrained facility-location problem, the proposed method naturally integrates non-negativity, orthogonality, and sparsity constraints.<n>Specifically, our approach integrates control-barrier function (CBF) based framework used for dynamic optimal control design problems with maximum-entropy-principle-based framework used for facility location problems to enforce these constraints while ensuring robust factorization.
  arXiv  Detail & Related papers  (2022-10-06T04:30:59Z)
• Tightening Discretization-based MILP Models for the Pooling Problem using Upper Bounds on Bilinear Terms [2.6253445491808307]
  Discretization-based methods have been proposed for solving non optimization problems with bi-linear terms. This paper shows that discretization-based MILP models can be used to solve the pooling problem.
  arXiv  Detail & Related papers  (2022-07-08T05:28:59Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs. A new dual approach is proposed with the integration of two ingredients: entropy regularized policy and Vaidya's dual. The proposed approach is shown to converge (with linear rate) to the global optimum.
  arXiv  Detail & Related papers  (2022-06-03T16:26:38Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)
• The empirical duality gap of constrained statistical learning [115.23598260228587]
  We study the study of constrained statistical learning problems, the unconstrained version of which are at the core of virtually all modern information processing. We propose to tackle the constrained statistical problem overcoming its infinite dimensionality, unknown distributions, and constraints by leveraging finite dimensional parameterizations, sample averages, and duality theory. We demonstrate the effectiveness and usefulness of this constrained formulation in a fair learning application.
  arXiv  Detail & Related papers  (2020-02-12T19:12:29Z)

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.