ID-PaS : Identity-Aware Predict-and-Search for General Mixed-Integer Linear Programs

• URL: http://arxiv.org/abs/2512.10211v1
• Date: Thu, 11 Dec 2025 01:58:28 GMT
• Title: ID-PaS : Identity-Aware Predict-and-Search for General Mixed-Integer Linear Programs
• Authors: Junyang Cai, El Mehdi Er Raqabi, Pascal Van Hentenryck, Bistra Dilkina,
• Abstract summary: This work extends the Predict-and-Search (PaS) framework to parametric MIPs.<n>It introduces ID-PaS, an identity-aware learning framework that enables the ML model to handle heterogeneous variables more effectively.
• Score: 21.379306770292136
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Mixed-Integer Linear Programs (MIPs) are powerful and flexible tools for modeling a wide range of real-world combinatorial optimization problems. Predict-and-Search methods operate by using a predictive model to estimate promising variable assignments and then guiding a search procedure toward high-quality solutions. Recent research has demonstrated that incorporating machine learning (ML) into the Predict-and-Search framework significantly enhances its performance. Still, it is restricted to binary problems and overlooks the presence of fixed variables that commonly arise in practical settings. This work extends the Predict-and-Search (PaS) framework to parametric MIPs and introduces ID-PaS, an identity-aware learning framework that enables the ML model to handle heterogeneous variables more effectively. Experiments on several real-world large-scale problems demonstrate that ID-PaS consistently achieves superior performance compared to the state-of-the-art solver Gurobi and PaS.

Related papers

• 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)
• EVA-MILP: Towards Standardized Evaluation of MILP Instance Generation [13.49043811341421]
  Mixed-Integer Linear Programming (MILP) is fundamental to solving complex decision-making problems.<n>The proliferation of MILP instance generation methods, driven by machine learning's demand for diverse datasets, has significantly outpaced standardized evaluation techniques.<n>This paper introduces a comprehensive benchmark framework designed for the systematic and objective evaluation of MILP instance generation methods.
  arXiv  Detail & Related papers  (2025-05-30T16:42:15Z)
• Multi-task Representation Learning for Mixed Integer Linear Programming [13.106799330951842]
  This paper introduces the first multi-task learning framework for ML-guided MILP solving.<n>We demonstrate that our multi-task learning model performs similarly to specialized models within the same distribution.<n>It significantly outperforms them in generalization across problem sizes and tasks.
  arXiv  Detail & Related papers  (2024-12-18T23:33:32Z)
• POGEMA: A Benchmark Platform for Cooperative Multi-Agent Pathfinding [76.67608003501479]
  We introduce POGEMA, a comprehensive set of tools that includes a fast environment for learning, a problem instance generator, and a visualization toolkit.<n>We also introduce and define an evaluation protocol that specifies a range of domain-related metrics, computed based on primary evaluation indicators.<n>The results of this comparison, which involves a variety of state-of-the-art MARL, search-based, and hybrid methods, are presented.
  arXiv  Detail & Related papers  (2024-07-20T16:37:21Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [51.00436121587591]
  In Multi-objective Reinforcement Learning (MORL) agents are tasked with optimising decision-making behaviours.<n>We focus on the case of linear utility functions parametrised by weight vectors w.<n>We introduce a method based on Upper Confidence Bound to efficiently search for the most promising weight vectors during different stages of the learning process.
  arXiv  Detail & Related papers  (2024-05-01T09:34:42Z)
• Sample Complexity Characterization for Linear Contextual MDPs [67.79455646673762]
  Contextual decision processes (CMDPs) describe a class of reinforcement learning problems in which the transition kernels and reward functions can change over time with different MDPs indexed by a context variable. CMDPs serve as an important framework to model many real-world applications with time-varying environments. We study CMDPs under two linear function approximation models: Model I with context-varying representations and common linear weights for all contexts; and Model II with common representations for all contexts and context-varying linear weights.
  arXiv  Detail & Related papers  (2024-02-05T03:25:04Z)
• Data-driven Mixed Integer Optimization through Probabilistic Multi-variable Branching [8.03915440701838]
  We propose a Pre-trained Mixed Optimization framework (PreMIO) that accelerates online mixed integer program (MIP) solving with offline datasets and machine learning models.<n>Our method is based on a data-driven multi-variable cardinality branching procedure that splits the feasible region using hyperplanes chosen by the concentration inequalities.
  arXiv  Detail & Related papers  (2023-05-21T05:11:30Z)
• Optimizing Hyperparameters with Conformal Quantile Regression [7.316604052864345]
  We propose to leverage conformalized quantile regression which makes minimal assumptions about the observation noise. This translates to quicker HPO convergence on empirical benchmarks.
  arXiv  Detail & Related papers  (2023-05-05T15:33:39Z)
• A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning [132.45959478064736]
  We propose a general framework that unifies model-based and model-free reinforcement learning. We propose a novel estimation function with decomposable structural properties for optimization-based exploration. Under our framework, a new sample-efficient algorithm namely OPtimization-based ExploRation with Approximation (OPERA) is proposed.
  arXiv  Detail & Related papers  (2022-09-30T17:59:16Z)
• A Simple Evolutionary Algorithm for Multi-modal Multi-objective Optimization [0.0]
  We introduce a steady-state evolutionary algorithm for solving multi-modal, multi-objective optimization problems (MMOPs) We report its performance on 21 MMOPs from various test suites that are widely used for benchmarking using a low computational budget of 1000 function evaluations.
  arXiv  Detail & Related papers  (2022-01-18T03:31:11Z)
• Conditional Generative Modeling via Learning the Latent Space [54.620761775441046]
  We propose a novel framework for conditional generation in multimodal spaces. It uses latent variables to model generalizable learning patterns. At inference, the latent variables are optimized to find optimal solutions corresponding to multiple output modes.
  arXiv  Detail & Related papers  (2020-10-07T03:11:34Z)
• StackGenVis: Alignment of Data, Algorithms, and Models for Stacking Ensemble Learning Using Performance Metrics [4.237343083490243]
  In machine learning (ML), ensemble methods such as bagging, boosting, and stacking are widely-established approaches. StackGenVis is a visual analytics system for stacked generalization.
  arXiv  Detail & Related papers  (2020-05-04T15:43:55Z)

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.