- 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
- 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.
- The empirical evaluation provides encouraging results across several settings.
Critical weaknesses
- 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.
- Assumption 3.3 requires clarification regarding the loss comparator. The assumption states that expected optimization loss against the realized-objective optimum decays as . 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
- 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?
- Weakness 2.