Influence branching for learning to solve mixed-integer programs online

• URL: http://arxiv.org/abs/2510.04273v1
• Date: Sun, 05 Oct 2025 16:29:44 GMT
• Title: Influence branching for learning to solve mixed-integer programs online
• Authors: Paul Strang, Zacharie Alès, Côme Bissuel, Olivier Juan, Safia Kedad-Sidhoum, Emmanuel Rachelson,
• Abstract summary: This work introduces a new approach for learning to solve MIPs online.<n>Initiative branching, a new graph-oriented variable selection strategy, is applied throughout the first iterations of the branch and bound algorithm.<n>We achieve results comparable to state of the art online learning methods.
• Score: 4.802758600019421
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: On the occasion of the 20th Mixed Integer Program Workshop's computational competition, this work introduces a new approach for learning to solve MIPs online. Influence branching, a new graph-oriented variable selection strategy, is applied throughout the first iterations of the branch and bound algorithm. This branching heuristic is optimized online with Thompson sampling, which ranks the best graph representations of MIP's structure according to computational speed up over SCIP. We achieve results comparable to state of the art online learning methods. Moreover, our results indicate that our method generalizes well to more general online frameworks, where variations in constraint matrix, constraint vector and objective coefficients can all occur and where more samples are available.

Related papers

• Generalized Optimal Classification Trees: A Mixed-Integer Programming Approach [17.725629133949955]
  Mixed-integer programming (MIP) offers a high degree of modeling flexibility.<n>We propose a MIP-based framework for learning optimal classification trees under nonlinear performance metrics.<n>We evaluate the proposed approach on 50 benchmark datasets.
  arXiv  Detail & Related papers  (2026-02-02T14:46:01Z)
• Online Network Source Optimization with Graph-Kernel MAB [62.6067511147939]
  We propose Grab-UCB, a graph- kernel multi-arms bandit algorithm to learn online the optimal source placement in large scale networks. We describe the network processes with an adaptive graph dictionary model, which typically leads to sparse spectral representations. We derive the performance guarantees that depend on network parameters, which further influence the learning curve of the sequential decision strategy.
  arXiv  Detail & Related papers  (2023-07-07T15:03:42Z)
• 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)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Branch Ranking for Efficient Mixed-Integer Programming via Offline Ranking-based Policy Learning [45.1011106869493]
  We formulate learning to branch as an offline reinforcement learning (RL) problem. We train a branching model named Branch Ranking via offline policy learning. Experiments on synthetic MIP benchmarks and real-world tasks demonstrate that Branch Rankink is more efficient and robust.
  arXiv  Detail & Related papers  (2022-07-26T15:34:10Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  Bilevel optimization has been applied to a wide variety of machine learning models. Most existing algorithms restrict their single-machine setting so that they are incapable of handling distributed data. We develop novel decentralized bilevel optimization algorithms based on a gradient tracking communication mechanism and two different gradients.
  arXiv  Detail & Related papers  (2022-06-30T05:29:52Z)
• Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch [13.024115985194932]
  We propose a new approach for solving the data labeling and inference issues in optimization based on the use of the reinforcement learning (RL) paradigm. We use imitation learning to bootstrap an RL agent and then use Proximal Policy (PPO) to further explore global optimal actions.
  arXiv  Detail & Related papers  (2022-06-14T16:35:58Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  We propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity.
  arXiv  Detail & Related papers  (2021-06-09T09:18:18Z)
• Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm [0.10499611180329801]
  We leverage patterns in real-world instances to learn from scratch a new branching strategy optimised for a given problem. We propose FMSTS, a novel Reinforcement Learning approach specifically designed for this task.
  arXiv  Detail & Related papers  (2020-05-20T13:15:48Z)
• Optimization of Graph Total Variation via Active-Set-based Combinatorial Reconditioning [48.42916680063503]
  We propose a novel adaptive preconditioning strategy for proximal algorithms on this problem class. We show that nested-forest decomposition of the inactive edges yields a guaranteed local linear convergence rate. Our results suggest that local convergence analysis can serve as a guideline for selecting variable metrics in proximal algorithms.
  arXiv  Detail & Related papers  (2020-02-27T16:33:09Z)

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.