acceptodds
Under review as a conference paper at ICLR 2027

Anytime Predict-and-Optimize with Soft Primal Guidance

Abstract

In contextual combinatorial optimization, decision cost is a primary concern, but computation time can also be important, particularly in applications with operational deadlines. Conventional predict-and-optimize formulations focus on coefficient accuracy or terminal decision quality, but do not explicitly account for how prediction overhead and incomplete search jointly affect decisions before a deadline. We propose Soft Primal Prior (SPP), which combines coefficient regression with solution-membership supervision from cached feasible decisions. The predicted memberships define variable-level preferences that shape a linear surrogate objective and its feasible initialization, while an unmodified solver enforces the original constraints. This construction leaves every feasible decision admissible and uses one trained model across deadlines. After offline label construction, gradient updates require no optimizer calls. Our analysis relates budgeted regret to objective mismatch, membership-estimation error, and incomplete optimization, and identifies when later decision gains compensate for guidance latency. Across three contextual benchmarks and a retrospective energy-scheduling case, SPP achieves competitive budgeted decision quality and reduces end-to-end Area Under the Regret Curve (AURC) by up to approximately 19.3% relative to coefficient-only predict-then-optimize, while the energy case shows that early fallback costs can offset gains at later deadlines.

Primary area:
optimization
Keywords:
Contextual combinatorial optimization, Predict-and-optimize, Budgeted optimization, Primal supervision, Objective shaping

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_ncm7OpenReview ↗
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
  1. The theoretical concepts are presented cleanly, and the authors’ key idea behind SPP is easy to follow.
  2. I also find the problem-framing well motivated as using operational deadlines is practically relevant for real-time operations.
  3. 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.
  4. I also checked some of the supporting theory in the appendix, and the proofs look correct to me.
Critical weaknesses
  1. 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.

  2. 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.

  3. 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.

  4. 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?

  5. 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?

  6. 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
AuthorsOpenReview ↗

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).

MethodNode AURCE2E AURC
PTO3.273.56
SPO+2.733.08
PG2.943.23
LTR2.823.14
LANCER2.963.37
ConPaS2.465.12
A-PTO3.183.49
Ours2.532.96

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

  1. Mandi, J., Demirović, E., Stuckey, P. J., and Guns, T. (2020). Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 1603–1610. https://doi.org/10.1609/aaai.v34i02.5521
AuthorsOpenReview ↗

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.

ConfigurationSynthetic MDKPOR-LibrarySet CoverEnergy
Original ablation (Table 2)
No guidance (B0B_0)6.1516.43116.37911.571
Constant scores6.3747.98412.06711.542
Learned scores: full SPP (B3B_3)6.0476.13411.20011.542
Independently tuned comparison
Uniform guidance18.5019.0615.7111.54
Learned guidance7.539.7112.1611.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.

AuthorsOpenReview ↗

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 γ\gamma 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γUniform\gamma_{\mathrm{Uniform}}γLearned\gamma_{\mathrm{Learned}}ROC-AUC (%)AP (%)Positive-label prevalence (%)
Synthetic MDKP0.200.5078.1778.6750.64
OR-Library0.300.5084.7682.7549.59
Set Cover0.050.1097.5268.605.06
Energy0.4909050.49090566.546.711.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 ρ\rho was selected on the development set: 00 for OR-Library, 00 for Set Cover, and 0.10.1 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).

DatasetMethodNode AURCE2E AURC
OR-LibraryObjective shaping6.1912.96
Trust region10.3610.36
Set CoverObjective shaping11.3010.15
Trust region11.6711.67
EnergyObjective shaping11.5411.63
Trust region11.5411.65

Node budgets are {1,8,64,512}\{1,8,64,512\}. E2E budgets in seconds are (0.1,0.3,1,3)(0.1,0.3,1,3) for OR-Library, (2,4,8,16)(2,4,8,16) for Set Cover, and (0.3,0.9,3,9)(0.3,0.9,3,9) 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.

Reviewer_Ez8vOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates anytime predict-and-optimize for contextual combinatorial optimization, where both prediction and optimization must operate under limited end-to-end computation budgets. It proposes Soft Primal Prior (SPP), which jointly predicts objective coefficients and variable-selection preferences from cached feasible solutions, then uses these preferences to shape the solver objective and initialization without changing the feasible set. The analysis relates budgeted regret to objective mismatch, prediction error, and incomplete optimization. Experiments show that gains mainly arise from objective shaping, with up to a 19.3% reduction in end-to-end AURC over coefficient-only prediction, while an energy-scheduling case highlights how guidance latency can offset later improvements.

Critical strengths
  1. The paper evaluates decisions under deadlines that include prediction, initialization, search, and verification. The energy-scheduling case demonstrates that better late-budget decisions can be outweighed by early fallback costs. This provides useful insight into deployment trade-offs that terminal-quality evaluations overlook.
  2. SPP transfers historical solution information into a linear objective without modifying the solver or restricting the feasible set. It reduces end-to-end AURC from 13.93% to 11.24% relative to PTO on Set Cover, and deployment ablations identify objective shaping as the main contributor. These results support the practical potential of the approach.
Critical weaknesses
  1. I could not determine the actual OR-Library data split from the paper: Section 5.1 says that test episodes reuse all 30 base structures, while Appendix B.2 describes ten held-out structures. This changes whether the experiment tests generalization to unseen structures. Table 6 also leaves the Set Cover ablation constraint count unresolved and does not specify the retrospective Energy training/development split. These details are necessary to interpret and reproduce the reported results.
  2. Several established baselines exhibit regret above 1000% on Set Cover, but the paper provides limited explanation for these unusually large values. Table 8 lists baseline-specific configuration fields that should be reported rather than their actual settings, while the reduced or truncated variants shown in the appendix are not clearly linked to the corresponding results in the main table. Although these observations do not necessarily indicate unfair comparisons, they make it difficult to assess whether the baselines were adequately trained and tuned, weakening the evidence for SPP's superiority over existing methods.
Questions for authors

Section 5.1 states that OR-Library test episodes reuse all 30 base structures, whereas Appendix B.2 describes ten held-out structures. Which split produced Table 1, and were any test structures used during training or model selection? What actual training schedules and configurations produced the baseline results in Table 1, and how do they correspond to the reduced or truncated variants mentioned in the appendix? In particular, what explains the regret above 1000% on Set Cover?

4 comments
AuthorsOpenReview ↗

Response to Reviewer Ez8v (1/2)

W1. Data splits and problem dimensions.

Response: Thank you for pointing out these inconsistencies. We clarify the settings underlying the reported results below.

OR-Library. Table 1 uses 600 training, 200 development, and 100 test episodes constructed from the same 30 public base structures, with disjoint contextual seeds across splits. Thus, the test structures were also present in training, and model selection used development contexts on shared structures. This evaluates generalization to new contexts on known structures. The statement “ten held-out structures” in Appendix B.2 is incorrect, and we have corrected Appendix B.2 accordingly.

Set Cover ablations. The reported ablations use 1,500 binary variables and 750 covering constraints. We have replaced “Unresolved” in Table 6 with 750.

Retrospective Energy. The retrospective Energy case uses 394 training days, a 79-day validation pool, and 32 test dates evaluated across five model seeds. We have replaced “Train/dev not specified” in Table 6 with “394/79/32”.

AuthorsOpenReview ↗

Response to Reviewer Ez8v (2/2)

W2. Regret above 1000% and baseline configurations.

Response: Thank you for raising these concerns. We clarify the high regret values and the baseline training, configuration, and evaluation protocols below.

Regret above 1000%. Table 1 reports decision quality under the prescribed computation budgets. For Set Cover, finding a feasible cover does not imply that its cost is close to optimal, and finite budgets may limit further search and solution improvement. Under the reported training configurations and budgets, SPO+, PG, and LANCER returned feasible solutions whose true costs substantially exceeded those of the reference solutions, resulting in regret above 1000%. We have added this explanation to Section 5.2 of the main text.

Actual configurations. We have revised Table 8 to report the actual settings used for the reported results, and we now explicitly link each configuration to its corresponding dataset, method variant, and result row.

Training and tuning. The baseline experiments included substantive training and independent configuration selection. On Synthetic MDKP and OR-Library, the completed PTO, LTR, and ConPaS experiments used development-set hyperparameter searches, with the selected configurations subsequently frozen for evaluation. In the retrospective Energy experiment, SPO+ was initialized from a same-seed PTO model trained for 60 epochs and then underwent 30 additional epochs of LP-relaxed decision-focused fine-tuning. These procedures were insufficiently documented in the original configuration table. The revision now makes the training and selection process explicit.

Training budgets. For the computationally intensive baselines, the original “reduced” and “truncated” labels identified the specific training budgets used in the reported experiments. These methods repeatedly invoke optimization solvers during training, so their computational effort cannot be assessed from epoch counts alone. For example, the resource-bounded SPO+, PG, and LANCER runs on Synthetic MDKP, OR-Library, and Set Cover completed two epochs of MSE pretraining followed by two decision-focused epochs or alternating outer iterations. We now report both stages, together with the training subset sizes and training-oracle limits. For conciseness and consistency, we have removed “reduced” and “truncated” from the method labels in Table 1 and the figures. The simplified names refer to the same implementations and training configurations as the previously qualified labels. Their actual training budgets and procedures remain explicitly documented in Table 8 and the experimental description, with a clear correspondence to the reported results.

Configuration selection. Configuration selection is also documented separately from training duration. We identify which configurations were selected through development-set search and which were fixed, rather than leaving readers to infer the selection procedure from the method name. This allows the training and tuning effort behind each comparison to be assessed directly.

Q1. Table 1 splits, training configurations, variant labels, and high regret.

Response: Thank you for these questions and for highlighting the need for a clearer experimental description. Please see our response to Weakness 1 above for the OR-Library split used in Table 1 and the structural overlap during training and model selection. Our response to Weakness 2 provides the baseline training schedules and configurations, clarifies their correspondence to the appendix variants, and explains the Set Cover regret above 1000%1000\%.

Thank you for your response. However, I will maintain my original score.

AuthorsOpenReview ↗

Follow-up and appreciation

Thank you for considering our response and for taking the time to review our clarifications. We understand and respect your decision to maintain the original score. We appreciate your constructive feedback, which has helped us improve the clarity of our experimental protocols, baseline configurations, and evaluation results. We will incorporate these clarifications into the revised manuscript. Thank you again for your time and consideration.

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

The paper deals with the general area of predict then optimize, whereby a model is used to make predictions that reduce uncertainty and these estimates are used as part of an optimization task. The predict then optimize steps are performed in an overall joint fashion. The contribution of the paper is to consider an anytime scenario whereby there is an overall time budget for the predict the no optimize and so how how can the predict then optimize return effective solutions within a budget. It proposes a particular approach based on a soft primal prior and making use of cached solution information.

Critical strengths

Introduces a fresh problem

Defines metrics for assessing quality in terms of the fresh problem

Provides theoretical analysis of approach

Experiments indicate improvements over baselines

Critical weaknesses

Isn’t tested on a deployed real world problem case study where the argued benefits can be supported

Questions for authors

Why does set cover exhibit the largest improvements? What is it about the nature of that problem that makes it a good fit for the proposed approach?

As a baseline why not compare against decoupled predict then optimize each with separate anytime approaches? i.e. anytime predict for coefficients anytime optimize for the optimization [obviously separate time budgets will need to be specified for each]

3 comments
AuthorsOpenReview ↗

Response to Reviewer szkc (1/2)

We thank the reviewer for the constructive feedback. We address the concern about practical deployment and the two questions below.

W1. Lack of a deployed real-world case study.

Response: Thank you for pointing out this limitation. Our Energy case study provides partial evidence of practical relevance: it evaluates the method on historical energy data in a constrained scheduling problem. In particular, it allows us to examine the decision-quality–computation trade-off under node and end-to-end time budgets in an application-motivated setting. However, we agree that this is a retrospective evaluation, not a deployment study. A meaningful deployment study would require collaboration with a system operator, integration with an operational data and scheduling pipeline, and prospective evaluation under the operator’s actual constraints and decision deadlines. It would also require observing the consequences of implemented decisions over a sufficiently long period. We currently have access to public data and a local experimental environment, but not to such an operational deployment setting. These requirements therefore cannot be met within the rebuttal period. We acknowledge this as a limitation of the present work. We will identify prospective deployment in real-world decision-making systems as future work, assessing the quality of implemented decisions, constraint satisfaction, and end-to-end latency under application-specific operational requirements and deadlines.

Q1. Why does Set Cover exhibit the largest improvements, and what properties make it a good fit for SPP?

Response: We attribute the larger gains on Set Cover primarily to SPP’s additional guidance for selecting sets. Baselines such as PTO rank feasible covers using predicted costs and can therefore favor poor combinations when those costs are inaccurate. SPP supplements this ranking with membership information learned from cached feasible solutions.

A key characteristic of Set Cover is that sets have overlapping and complementary coverage: an inexpensive set may largely duplicate coverage provided by other sets, whereas another set may cover critical elements that would otherwise remain uncovered. Consequently, a set’s individual cost does not fully describe its value within a complete cover. SPP’s membership labels are derived from complete feasible covers, providing supervision that reflects selection decisions made under the joint coverage requirements and cost trade-offs. Meanwhile, soft objective guidance preserves all feasible combinations, allowing the solver to handle the complementarity and substitution among sets. This alignment between Set Cover’s dependence on coordinated set selection and SPP’s combination of supervision from feasible solutions and soft objective guidance is our main explanation for the largest improvements observed on this benchmark.

AuthorsOpenReview ↗

Response to Reviewer szkc (2/2)

Q2. Why not compare with decoupled anytime coefficient prediction and anytime optimization, with separate budgets for the two stages?

Response: Thank you for this suggestion. We have evaluated A-PTO (Anytime Predict-then-Optimize), a decoupled baseline that explicitly combines anytime prediction of objective coefficients with anytime optimization, with computation allocated separately to the two stages. The prediction stage uses a multi-exit regressor to provide coefficient estimates at different inference depths, with its exits trained using AdaLoss-style adaptively weighted regression losses (Hu et al., 2019). The optimization stage uses Gurobi as an anytime solver: given the predicted coefficients, it maintains a feasible incumbent and searches for better solutions under the predicted objective within its allocated budget. The predictor is trained independently of the optimization solver. For each total E2E deadline, we select the prediction exit on the development set according to downstream decision regret under that deadline, and freeze this choice for testing. The selected exit determines the computation allocated to anytime prediction; the anytime optimizer receives the actual remaining time after inference, initialization, and model construction. Solution extraction and feasibility verification are also included in the E2E evaluation. This explicitly allocates computation between the two separate anytime stages. For node-budget evaluation, we use the final prediction exit and apply the prescribed node limit to the optimizer.

The results below show that SPP reduces E2E AURC relative to A-PTO by 69.6%69.6\%, 68.4%68.4\%, and 10.6%10.6\% on Synthetic MDKP, OR-Library, and Set Cover, respectively. A-PTO achieves lower E2E AURC on Energy (2.47%2.47\% versus 3.10%3.10\%), while SPP has lower regret at the three larger Energy deadlines. A-PTO also achieves lower node AURC on Set Cover (6.91%6.91\% versus 11.64%11.64\%), whereas SPP has lower E2E AURC on this task (11.24%11.24\% versus 12.57%12.57\%). These differences between node and E2E rankings reinforce the importance of evaluating the full decision pipeline under deadlines.

We have added A-PTO to Table 1, described its implementation and budget allocation in Section 5.1, and updated the corresponding results analysis in Section 5.2.

Comparison with A-PTO.

(a) Node-budget evaluation

DatasetMethodN=1N=1N=8N=8N=64N=64N=512N=512AURC
Synthetic MDKPA-PTO6.146.146.136.156.14
Synthetic MDKPSPP6.046.056.056.046.05
OR-Library MDKPA-PTO6.346.346.336.326.33
OR-Library MDKPSPP6.196.196.166.166.17
Set CoverA-PTO7.137.146.896.246.91
Set CoverSPP11.7311.7311.6811.3111.64
Energy SchedulingA-PTO2.442.442.442.442.44
Energy SchedulingSPP2.392.392.392.392.39

(b) End-to-end time-budget evaluation

DatasetMethodT1T_1T2T_2T3T_3T4T_4AURC
Synthetic MDKPA-PTO21.1221.1120.4915.0419.87
Synthetic MDKPSPP6.136.076.005.976.04
OR-Library MDKPA-PTO19.5319.3919.4319.1919.39
OR-Library MDKPSPP6.166.176.106.106.13
Set CoverA-PTO13.1712.7312.3612.1012.57
Set CoverSPP11.5311.3211.1211.0111.24
Energy SchedulingA-PTO2.442.482.482.482.47
Energy SchedulingSPP6.802.392.392.393.10

Reference. H. Hu, D. Dey, M. Hebert, and J. A. Bagnell. Learning Anytime Predictions in Neural Networks via Adaptive Loss Balancing. Proceedings of the AAAI Conference on Artificial Intelligence, 33(1):3812–3821, 2019.

Thankyou, acknowledging your response.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Rebuttal Summary

Dear Area Chair,

We sincerely thank the reviewers for their thoughtful feedback. We have carefully addressed the concerns through detailed responses, additional experiments, and revisions to the manuscript.

1. Addressing the major concerns.

The main concerns involved experimental coverage, the contribution of learned membership scores, the choice of objective shaping, and the theoretical guarantees. In response, we have:

  • Expanded the experiments: Added a decoupled anytime predict-and-optimize baseline (A-PTO) and evaluated all baselines on the challenging energy-scheduling instances from Mandi et al. (2020). We also clarified benchmark selection, data splits, and baseline training configurations.
  • Clarified the contribution of learned scores: Conducted independently tuned comparisons between learned membership scores and uniform bias, together with membership-head ROC-AUC and AP evaluations.
  • Added a trust-region comparison: Evaluated objective shaping against trust-region guidance using the same membership scores, clarifying their complementary advantages.
  • Strengthened the theoretical discussion: Clarified the connection between Proposition 2 and true-cost regret, discussed the dimension dependence of the bound, and specified conditions under which SPP can outperform standard PTO.

2. Reviewers' feedback.

Reviewer szkc recommended weak acceptance, recognizing the novelty of the problem formulation, evaluation framework, and theoretical analysis. Reviewers Ez8v and ncm7 maintained their original scores after our responses. Notably, Reviewer ncm7 explicitly stated that they remain open to the views of the other reviewers and the Area Chair. We respect their assessments and hope our additional evidence helps inform the final decision.

3. Overall contribution.

We believe the main value of this work is the formulation of an important problem: delivering high-quality combinatorial decisions when prediction and optimization must share a limited end-to-end computation budget.

SPP offers a lightweight approach that transfers historical solution information into soft objective guidance while preserving the original feasible set and using an unmodified solver. Beyond the empirical results, our analysis provides insight into the interaction between objective mismatch, membership estimation, optimization progress, and decision availability.

We acknowledge that SPP does not uniformly outperform all alternatives across every task. Nevertheless, we believe the problem formulation, methodological contribution, theoretical analysis, and additional experimental evidence collectively make this work a meaningful contribution to anytime combinatorial optimization.

We respectfully ask the Area Chair to consider these contributions and the additional evidence when making the final decision.

Thank you for your time and consideration.

Sincerely, The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.