Learning When to Re-solve in Real-Time Optimization

A common challenge in real-time operations is deciding whether to re-solve an optimization problem or use an existing solution. While modern data platforms collect information at high frequencies, many real-time applications require repeatedly solving computationally intensive optimization problems formulated as Mixed-Integer Linear Programs (MILPs). Determining when to re-solve is hence an economically important question. This problem poses several challenges: i) How to characterize the suboptimality–cost tradeoff in re-solving; ii) How to detect environmental changes and select beneficial samples at which re-solving the MILP is worthwhile; iii) How to develop principled learning-based re-solving policies when long horizons and non-Markovian dynamics make standard reinforcement learning ill-suited and prone to value-function explosion. Existing work mostly uses heuristics, short-horizon approximations, or smooth objectives, with limited attention to practical, large-scale, NP-hard MILPs. We hence propose Proximal Policy Optimization with Change Point Detection (POC), a framework that systematically learns when to re-solve while balancing performance and cost. Theoretically, we establish a relationship between the number of re-solves and the re-solving cost. Empirically, using eight synthetic and real-world datasets, we show that POC consistently outperforms existing baselines by 2%–17%. As a side benefit, our work helps fill a gap in the literature by introducing real-time MILP benchmarks and evaluation criteria.