- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This work studies anytime predict-then-optimize formulation for contextual combinatorial problems under operational deadlines. Such problems have unknown objective coefficients and limited online computation. Their approach called Soft-Primal-Prior, transfers cached solution information into objective preferences without restricting the feasible set or modifying the solver. They also derive a finite-budget regret bound that separates objective mismatch from residual optimization error at the deadline.
Critical strengths
- The theoretical concepts are presented cleanly, and the authors’ key idea behind SPP is easy to follow.
- I also find the problem-framing well motivated as using operational deadlines is practically relevant for real-time operations.
- Some of the experimental problems, especially Set Cover, are larger than the standard benchmarks used in many previous papers (e.g., shortest path or small knapsack), which makes the setting more practical.
- I also checked some of the supporting theory in the appendix, and the proofs look correct to me.
Critical weaknesses
-
I don’t quite understand the choice of benchmarks, and the paper does not explain it. Not sure how the chosen ones support the deadline setting. Also, in Table 1, the regret on both knapsack tasks and Energy barely changes across budgets, so only Set Cover shows a quality–time trade-off. Mandi et al. (2020), which the paper cites, already has hard energy-scheduling instances that take much longer to solve, but they are not used. Is there a reason why? I think it would also help to run the baselines on at least one standard benchmark, since several of them show regret above 1000% on Set Cover. As such, it becomes hard to attribute correctness.
-
I do not understand whether the improvement comes from the learned membership scores or just from a uniform bias. The paper’s own ablation shows that constant scores already give most of the gain on Set Cover and the same result on Energy.
-
It is also not clear whether the guidance weight, which controls how strongly the scores change the objective, was tuned for the constant scores as well? A tuned uniform bias and some evaluation of the membership head itself (e.g., AUC on test instances) would help show that the learned scores are what make the method work.
-
As I understand, the paper uses objective shaping so the membership scores can correct the predicted objective without restricting the feasible set. But another common way to use such scores is a trust region, which searches only near the predicted solution and can be faster under tight deadlines. I am not sure I understand why objective shaping the better choice here, and why is it not compared with a trust region using the same scores?
-
Proposition 2 is meant to show that training the membership head with BCE leads to good decisions. But it only bounds the error relative to the label memberships, not the true costs. The bound also seems to grow with the number of variables, is that practical?
-
The authors do not say under what conditions SPP should do better than standard predict-then-optimize (PTO).
Questions for authors
See above.
7 comments
Response to Reviewer ncm7 (2/5)
W2. Does the improvement come from learned membership scores or simply from a uniform bias?
Response: Thank you for raising this important question. Learned membership scores provide additional decision value on Synthetic MDKP, OR-Library, and Set Cover, while uniform bias also contributes substantially on Set Cover.
In the original ablation, constant scores worsen AURC relative to no guidance on both knapsack tasks, whereas learned scores improve it. On Set Cover, constant scores reduce AURC from 16.379% to 12.067%, and learned scores further reduce it to 11.200%. Thus, the observation that constant scores recover much of the Set Cover improvement is consistent with an additional contribution from learned, variable-specific information.
To further assess this contribution, we complemented the ablation in which Uniform and Learned independently select their guidance weight on the development set, with the selected values frozen before testing. Both variants share the same frozen coefficient head, coefficient-based initializer, solver settings, and strict deadline rule. The original and additional results are summarized below.
| Configuration | Synthetic MDKP | OR-Library | Set Cover | Energy |
|---|---|---|---|---|
| Original ablation (Table 2) | ||||
| No guidance () | 6.151 | 6.431 | 16.379 | 11.571 |
| Constant scores | 6.374 | 7.984 | 12.067 | 11.542 |
| Learned scores: full SPP () | 6.047 | 6.134 | 11.200 | 11.542 |
| Independently tuned comparison | ||||
| Uniform guidance | 18.50 | 19.06 | 15.71 | 11.54 |
| Learned guidance | 7.53 | 9.71 | 12.16 | 11.54 |
All values are E2E AURC (%); lower is better.
After tuning, Learned again achieves lower AURC than Uniform on all three of Synthetic MDKP, OR-Library, and Set Cover. On Set Cover, the paired analysis estimates an improvement of 3.54 percentage points. These results support an additional contribution from learned scores beyond a tuned uniform bias.
On Energy, all paired true costs and regrets are identical, so we observe no additional decision benefit from learned scores. A possible explanation concerns the distinction between reference-solution membership and scheduling cost. In the Energy formulation, cost depends on the aggregate load profile and electricity prices, and different feasible machine assignments can produce the same load profile and cost. Consequently, learned membership information may distinguish reference-solution assignments without improving the cost-relevant timing decisions under the evaluated setting.
Response to Reviewer ncm7 (3/5)
W3. Was the guidance weight tuned for constant scores, and does the membership head learn useful information?
Response: Thank you for these suggestions. The original constant-score control used the guidance weight of the learned-score configuration. We have now complemented that ablation with independent development-set selection of for both Uniform and Learned, freezing the selected values before testing. Both variants use the same frozen coefficient head, coefficient-based initializer, solver settings, and strict deadline rule. The resulting decision-quality comparison is reported in our preceding response to W2.
We also evaluated the membership head on the test instances using ROC-AUC and average precision (AP) against reference-solution membership labels. The selected guidance weights and membership-prediction results are reported below.
| Dataset | ROC-AUC (%) | AP (%) | Positive-label prevalence (%) | ||
|---|---|---|---|---|---|
| Synthetic MDKP | 0.20 | 0.50 | 78.17 | 78.67 | 50.64 |
| OR-Library | 0.30 | 0.50 | 84.76 | 82.75 | 49.59 |
| Set Cover | 0.05 | 0.10 | 97.52 | 68.60 | 5.06 |
| Energy | 0.490905 | 0.490905 | 66.54 | 6.71 | 1.69 |
For constant scores, ROC-AUC is 50% and AP equals the positive-label prevalence. The learned head exceeds both constant-score baselines on all four datasets, demonstrating that its scores contain information about reference-solution membership. The independently tuned decision comparison further shows that this information provides additional decision value on Synthetic MDKP, OR-Library, and Set Cover. On Energy, the scores are informative about membership, but we observe no additional decision benefit. We have added the independent guidance-weight selection procedure and membership-prediction evaluation to the revised experimental description and appendix.
W4. Why use objective shaping rather than a trust region based on the same membership scores?
Response: Thank you for suggesting this comparison. We chose objective shaping because it uses predicted memberships as soft preferences while preserving the full feasible set. Since membership predictions can be imperfect, restricting the search to a neighborhood around a predicted solution may exclude potentially better alternatives. Objective shaping instead allows the solver to explore the entire feasible set while using membership scores to guide its search. Nevertheless, trust-region guidance offers a complementary approach that may be advantageous under tight deadlines.
Additional comparison. We compared objective shaping with trust-region guidance using the same membership scores. The trust-region radius ratio was selected on the development set: for OR-Library, for Set Cover, and for Energy. Both approaches were evaluated under the same test cohorts and computation budgets.
The results are summarized below (AURC in percentage; lower is better).
| Dataset | Method | Node AURC | E2E AURC |
|---|---|---|---|
| OR-Library | Objective shaping | 6.19 | 12.96 |
| Trust region | 10.36 | 10.36 | |
| Set Cover | Objective shaping | 11.30 | 10.15 |
| Trust region | 11.67 | 11.67 | |
| Energy | Objective shaping | 11.54 | 11.63 |
| Trust region | 11.54 | 11.65 |
Node budgets are . E2E budgets in seconds are for OR-Library, for Set Cover, and for Energy.
Results under node budgets. Objective shaping achieves lower node AURC on OR-Library (6.19% versus 10.36%) and Set Cover (11.30% versus 11.67%), while both methods obtain identical results on Energy (11.54%). This suggests that preserving the full feasible set can be beneficial under fixed solver-node budgets.
Results under E2E deadlines. The relative performance depends on the problem structure. Trust-region guidance achieves lower E2E AURC on OR-Library (10.36% versus 12.96%). In contrast, objective shaping performs better on Set Cover (10.15% versus 11.67%) and Energy (11.63% versus 11.65%). These results indicate that restricting the search region does not consistently improve end-to-end decision quality, even under tight deadlines.
Response to Reviewer ncm7 (1/5)
W1. Benchmark selection and deadline relevance.
Response: Thank you for raising these concerns. Our benchmark selection was intended to cover complementary combinatorial structures, data sources, and application settings.
Specifically, we selected four tasks for different purposes. Synthetic MDKP provides a controlled multidimensional packing problem with 120 variables and 10 resource constraints, allowing us to examine learned decision preferences under multiple interacting constraints. OR-Library MDKP uses established public knapsack structures with 250 variables and 5 constraints, augmented with contextual objective coefficients. It allows us to evaluate generalization across different contextual realizations on known combinatorial structures (Chu and Beasley, 1998). Set Cover represents a structurally different covering problem with 1,500 variables and 750 constraints. Its overlapping coverage relationships require coordinated selection among multiple sets, making it particularly relevant for examining whether membership information learned from feasible solutions can improve combinatorial decisions (Balas and Ho, 1980; Prouvost et al., 2021). Finally, Energy scheduling provides an application-motivated evaluation using historical electricity-price data, with assignment, temporal, and resource constraints (Ifrim et al., 2012; Mandi et al., 2024). Together, these tasks cover packing, covering, and scheduling problems, combining controlled synthetic data, established public combinatorial structures, and historical application data.
Regarding deadline relevance, our objective is to evaluate the decision quality delivered by the complete prediction–optimization pipeline at different computation deadlines, rather than to require every benchmark to exhibit a pronounced quality–time trade-off. The task-specific budget grids measure the actual decisions available after accounting for feature processing, prediction, guidance, initialization, solver search, extraction, and verification.
We acknowledge that regret changes relatively little across budgets on the two knapsack tasks and the original retrospective Energy case. This indicates that additional search produces limited changes in decision quality under these particular configurations. However, these tasks remain useful for evaluating decision quality under different budgets and the overhead introduced by the complete pipeline. Set Cover provides a more pronounced quality–time trade-off, with SPP's regret decreasing from 11.53% at 2 seconds to 11.01% at 16 seconds. Energy illustrates a different deadline effect: SPP initially returns its registered fallback with 6.80% regret at 0.3 seconds, but achieves 2.39% at subsequent deadlines. This early penalty raises its E2E AURC to 3.10%, despite the substantially better later decisions. These contrasting profiles demonstrate why deadline-aware evaluation must account for both decision quality and decision availability.
Additional hard energy-scheduling benchmark. We agree that the hard energy-scheduling instances studied by Mandi et al. (2020) are particularly relevant to evaluating computationally constrained optimization. We have therefore added experiments on these instances and evaluated all methods under both node and strict E2E budgets.
The results are summarized below (AURC in percentage; lower is better).
Ours achieves the lowest E2E AURC of 2.96%, outperforming all compared methods, including SPO+ (3.08%) and A-PTO (3.49%). Although ConPaS achieves a slightly lower node AURC (2.46% versus 2.53%), its E2E AURC increases to 5.12%. This illustrates that better solver-side performance does not necessarily translate into better end-to-end decision quality. The additional results provide evidence that SPP is also effective on computationally challenging energy-scheduling instances.
References