acceptodds
Under review as a conference paper at ICLR 2027

Learning When to Re-solve in Real-Time Optimization

Abstract

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.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Real-time operation, Policy learning, Mixed-Integer Linear Programming

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_RF4qOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper addresses when to re-solve an optimization problem whose objective coefficients change over time while its feasible region remains fixed. It minimizes cumulative optimization loss with a fixed cost to re-solve. The proposed framework combines change-point detection, features describing the incumbent solution and available observations, and a PPO-based policy deciding whether to re-solve. The paper also derives structural results regarding discounting and re-solving schedules. Experiments across eight optimization datasets report cumulative loss improvements of approximately 2% - 17% over the evaluated baselines.

Critical strengths
  1. The problem is clearly formulated and is practically motivated. Accounting for re-solve costs explicitly captures an important trade-off between retaining an outdated solution.and obtaining an updated one. The isolated components of scheduling re-solves and solving the underlying optimization problems makes the framework applicable across the different families.
  2. The empirical evaluation provides encouraging results across several settings.
Critical weaknesses
  1. The results do not isolate the contribution beyond the standard policy learning with suitable features. A matched PPO baseline and a simple cost-aware trigger using the same objective estimates would help determine whether the gains arise from policy learning, sample-size features, or data selection. EMA outperforms CPD on SPP while using fewer re-solves (Tab 10), making matched estimator comparisons important.
  2. Assumption 3.3 requires clarification regarding the loss comparator. The assumption states that expected optimization loss against the realized-objective optimum decays as θ(n−α)\theta(n^{-\alpha}). However, additional observations improve estimation of the mean objective without necessarily eliminating the gap to a clairvoyant decision. For example, suppose the feasible decisions are ((1,0)) and ((0,1)), and the objective independently equals ((1,2)) or ((2,1)) with equal probability. Any decision based on past observations has expected cost 1.5, whereas the clairvoyant optimum always costs 1, leaving a gap of 0.5 regardless of sample size. Do the authors instead intend Assumption 3.3 to describe excess loss relative to the mean-optimal decision?
Questions for authors
  1. For weakness 1, can the authors compare a validation-tuned objective drift trigger using the same objective estimator, with thresholds tuned separately for each re-solving cost?
  2. Weakness 2.
Reviewer_Lhn3OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper develops a framework that systematically learns when to re-solve optimization problems while balancing solution quality and computational cost. Theoretically, the authors establish a relationship between the number of re-solves and the associated re-solving cost. Experiments conducted on eight synthetic and real-world datasets demonstrate that the proposed POC framework outperforms existing baselines by 2%–17%.

Critical strengths
  1. The paper addresses an important and practically relevant problem encountered across various industries.
  2. The authors provide theoretical insights by establishing a relationship between the number of re-solves and the associated re-solving cost.
  3. The experimental results demonstrate that the proposed approach consistently outperforms existing baselines by 2%–17%.
Critical weaknesses
  1. The proposed loss function, (CL(\pi)), explicitly relies on the clairvoyant optimal solution. However, obtaining such a solution may be computationally prohibitive, particularly for large-scale problem instances.
  2. Given that the complete historical objective sequences are available during offline training, it would be valuable to compare the proposed PPO-based framework with simpler reinforcement learning alternatives, such as REINFORCE. Such comparisons would help clarify whether the additional complexity of PPO is justified by meaningful improvements in performance or training stability.
  3. The novelty of this work is not entirely clear. The paper presents learning when to re-solve computationally expensive optimization problems as a central contribution. However, closely related ideas have already been explored in the event-triggered model predictive control (MPC) literature. For example, [1] explicitly employs reinforcement learning to determine when an expensive MPC optimization problem should be re-solved, balancing computational cost against control performance. I encourage the authors to clarify the fundamental methodological novelty of POC relative to these existing approaches. In particular, what new learning or decision-making capabilities does POC introduce beyond adapting an established RL-based event-triggering framework to dynamic mixed-integer linear programs with change-point-based features?

[1] Eivind Bøhn, Sebastien Gros, Signe Moe, and Tor Arne Johansen. Optimization of the Model Predictive Control Update Interval Using Reinforcement Learning.

Questions for authors

See weakness section.

Reviewer_LDwyOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies when to re-solve mixed-integer linear programs (MILPs) in dynamic environments. Frequent re-solving improves decision quality but incurs computational costs. The authors formulate this tradeoff as a cumulative loss minimization problem and theoretically characterize properties of optimal re-solving schedules. They propose POC, a framework combining change-point detection, feature engineering, and proximal policy optimization (PPO) to learn when re-solving is worthwhile. Experiments across eight synthetic and real-world MILP benchmarks show 2–17% reductions in cumulative loss compared with existing baselines. Additional experiments examine sensitivity to re-solving costs, feature design, and generalization.

Critical strengths
  1. The paper addresses a practical and important problem in real-time optimization, with a clear formulation of the tradeoff between solution quality and re-solving cost.

  2. Consistent improvements across eight optimization benchmarks, including problems constructed from real-world data.

  3. Theoretical analysis provides useful insights into optimal re-solving frequency, supported by empirical results.

Critical weaknesses
  1. The baselines are primarily adapted from model retraining. A simpler cost-aware heuristic using the same change-point detection and engineered features would help establish the benefit of PPO.

  2. The theoretical results rely on assumptions about environmental changes, state representations, and estimation-error decay. They do not directly provide performance guarantees for the learned policy.

  3. The main synthetic experiments use true change points during training. Although Appendix D.5 examines estimated change points, a more comprehensive evaluation under realistic detection uncertainty would strengthen the results.

  4. Re-solving costs are represented by a fixed penalty rather than measured computational or operational costs. This limits conclusions about practical efficiency.

Questions for authors
  1. How much improvement comes specifically from PPO compared with a simpler cost-aware heuristic using the same features?

  2. Can the authors provide end-to-end runtime comparisons, including change-point detection, policy inference, and MILP solving?

  3. How well does POC generalize when trained entirely with estimated change points, particularly across the real-world benchmarks?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.