# Solve Smart, Not Often: Policy Learning for Costly MILP Re-solving

arXiv: https://arxiv.org/abs/2509.23470 · HTML: https://mlsanity.com/paper/2509.23470/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 30 of its 70 references that are in the map.
- First posted on arXiv 27 Sep 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 30)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [When to Trust Your Model: Model-Based Policy Optimization](https://mlsanity.com/paper/1906.08253/) (2019)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning](https://mlsanity.com/paper/2010.12367/) (2020)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Acting Less is Reasoning More! Teaching Model to Act Efficiently](https://mlsanity.com/paper/2504.14870/) (2025)
- [An Evaluation of Change Point Detection Algorithms](https://mlsanity.com/paper/2003.06222/) (2020)
- [A Survey of Reinforcement Learning Algorithms for Dynamically Varying Environments](https://mlsanity.com/paper/2005.10619/) (2020)
- [Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning](https://mlsanity.com/paper/2206.13414/) (2022)
- [Generalization Bounds in the Predict-then-Optimize Framework](https://mlsanity.com/paper/1905.11488/) (2019)
- [Learning to branch with Tree MDPs](https://mlsanity.com/paper/2205.11107/) (2022)
- [Fast Rates for Contextual Linear Optimization](https://mlsanity.com/paper/2011.03030/) (2020)
- [Reactive Soft Prototype Computing for Concept Drift Streams](https://mlsanity.com/paper/2007.05432/) (2020)
- [Towards Foundation Models for Mixed Integer Linear Programming](https://mlsanity.com/paper/2410.08288/) (2024)
- [Risk Bounds and Calibration for a Smart Predict-then-Optimize Method](https://mlsanity.com/paper/2108.08887/) (2021)
- [Can LLMs Serve As Time Series Anomaly Detectors?](https://mlsanity.com/paper/2408.03475/) (2024)
- [Warm Start of Mixed-Integer Programs for Model Predictive Control of Hybrid Systems](https://mlsanity.com/paper/1910.08251/) (2019)
- [Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Control](https://mlsanity.com/paper/2010.03161/) (2020)
- [Deep Reinforcement Learning for Event-Triggered Control](https://mlsanity.com/paper/1809.05152/) (2018)
- [On Abruptly-Changing and Slowly-Varying Multiarmed Bandit Problems](https://mlsanity.com/paper/1802.08380/) (2018)
- [Random Forests for Change Point Detection](https://mlsanity.com/paper/2205.04997/) (2022)
- [Automatic Change-Point Detection in Time Series via Deep Learning](https://mlsanity.com/paper/2211.03860/) (2022)
- [When to retrain a machine learning model](https://mlsanity.com/paper/2505.14903/) (2025)
- [Cost-Effective Retraining of Machine Learning Models](https://mlsanity.com/paper/2310.04216/) (2023)
- [Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Scheduling](https://mlsanity.com/paper/2502.15791/) (2025)
- [Some models are useful, but for how long?: A decision theoretic approach to choosing when to refit large-scale prediction models](https://mlsanity.com/paper/2405.13926/) (2024)

## Built on by (most cited first, 1 of 1)

- [Democratizing Large-Scale Re-Optimization with LLM-Guided Model Patches](https://mlsanity.com/paper/2605.18692/) (2026)

## Abstract (arXiv)

A common challenge in real-time operations is deciding whether to re-solve an optimization problem or continue using an existing solution. While modern data platforms may collect information at high frequencies, many real-time operations require repeatedly solving computationally intensive optimization problems formulated as Mixed-Integer Linear Programs (MILPs). Determining when to re-solve is, therefore, an economically important question. This problem poses several challenges: 1) How to characterize solution optimality and solving cost; 2) How to detect environmental changes and select beneficial samples for solving the MILP; 3) Given the large time horizon and non-MDP structure, vanilla reinforcement learning (RL) methods are not directly applicable and tend to suffer from value function explosion. Existing literature largely focuses on heuristics, low-data settings, and smooth objectives, with little focus on common NP-hard MILPs. We propose a framework called Proximal Policy Optimization with Change Point Detection (POC), which systematically offers a solution for balancing performance and cost when deciding appropriate re-solving times. Theoretically, we establish the relationship between the number of re-solves and the re-solving cost. To test our framework, we assemble eight synthetic and real-world datasets, and show that POC consistently outperforms existing baselines by 2%-17%. As a side benefit, our work fills the gap in the literature by introducing real-time MILP benchmarks and evaluation criteria.