Multi-Stage Predict+Optimize for (Mixed Integer) Linear Programs

Thank you for your positive review of our work. We respond to your questions and comments below.

Venue fit: While Predict+Optimize does have some operations research flavor, it is fundamentally a machine learning problem nonetheless. We also note that the NeurIPS+ICML community has shown interest in this line of work. This is evidenced by prior works that are specifically on the topic of Predict+Optimize that have been accepted in past ICML or NeurIPS ([1,2] in ICML 2022, and [3] in NeurIPS 2023). Additionally, papers that provide tools that we use, for example works studying differentiation through optimization layers, are widely accepted as part of the community. We hope that, by presenting a new use case, our work can inspire further development of such tools. In summary, we believe there is value in disseminating the current work at NeurIPS, and so we made the decision to submit here.

Additional literature: Thanks for the suggestion, we are happy to add these references in Appendix A.3 to situate our work in this broader context.

Specifically, we will include references to prior work on integrating machine learning with stochastic programming, such as [4] proposes an end-to-end learning framework that directly aligns the training of probabilistic machine learning models with the ultimate task-based objective in the context of stochastic programming. [5] uses a neural network to approximate the expected value function in two-stage stochastic programming problems, enabling more efficient solution approaches compared to traditional methods. [6] proposes a neural network-based stagewise decomposition algorithm that can effectively approximate value functions for large-scale multistage stochastic programming problems. [7] develops a principled end-to-end learning framework for training neural network decision maps that can effectively solve stochastic optimization problems, including empirical risk minimization and distributionally robust optimization formulations.

Furthermore, we will ensure to highlight relevant work on using ML to help mixed-integer programming (MIP): ML algorithms for exact solving MIP by branch-and-cut based algorithms [8,9,10], ML algorithms for exact solving MIP by decomposition-based algorithms [11,12], ML algorithms for approximate solving MIP by large neighborhood search based algorithm [13,14], and so on.

Termination criterion: Thanks for pointing out our accidental omission. Currently, we use a termination criterion which is to threshold by the difference in training set post-hoc regrets between two (outermost) iterations of the training coordinate-descent. The threshold we used is 0.1, but that is just another hyperparameter to be tuned per each application. We will add this info back into the paper.

Convex relaxation of integrality constraints: This is an excellent point that deserves further investigation, and we agree that it can be a fruitful direction for future work. As we pointed out in the Future Works section in lines 355-362, the experimental results suggest that our methods exhibit rather different behaviors depending on whether the underlying optimization problem is a linear program or a mixed integer program. We were wondering in a similar direction, as to how the relaxation might affect the prediction performance. Exploring the impact of the choice of convex relaxation on the overall performance of our framework is an important direction for future research.

Line 109, and Line 163: We would like to clarify that this is an assumption made by Hu et al. in their Two-Stage framework, and not an assumption we make in our new framework. Regardless, from our reading of Hu et al.'s work, they discussed how their framework can nonetheless model decision variables that cannot be changed in Stage 1 (i.e. hard commitments made in Stage 0), via choosing a penalty function that yields infinite penalty when changing hard commitments already made in Stage 0. They discuss the modelling approach/choice in Appendix A.1 in their paper.

Line 157, always-feasible assumption: Please refer to our response to Reviewer Bz3V.

[1] Jeong, Jihwan, et al. "An exact symbolic reduction of linear smart predict+ optimize to mixed integer linear programming." ICML 2022.

[2] Mandi, Jayanta, et al. "Decision-focused learning: Through the lens of learning to rank." ICML 2022.

[3] Hu, Xinyi, Jasper Lee, and Jimmy Lee. "Two-Stage Predict+ Optimize for MILPs with Unknown Parameters in Constraints." NeurIPS 2023.

[4] Donti, Priya, Brandon Amos, and J. Zico Kolter. "Task-based end-to-end model learning in stochastic optimization." NeurIPS 2017.

[5] Patel, Rahul Mihir, et al. "Neur2SP: Neural two-stage stochastic programming." NeurIPS 2022.

[6] Bae, Hyunglip, et al. "Deep value function networks for large-scale multistage stochastic programs." AISTATS 2023.

[7] Rychener, Yves, Daniel Kuhn, and Tobias Sutter. "End-to-end learning for stochastic optimization: A bayesian perspective." ICML 2023.

[8] Balcan, Maria-Florina, et al. "Learning to branch." ICML 2018.

[9] Gasse, Maxime, et al. "Exact combinatorial optimization with graph convolutional neural networks." NeurIPS 2019.

[10] Zarpellon, Giulia, et al. "Parameterizing branch-and-bound search trees to learn branching policies." AAAI 2021.

[11] Lange, Jan-Hendrik, and Paul Swoboda. "Efficient message passing for 0–1 ILPs with binary decision diagrams." ICML 2021.

[12] Lozano, Leonardo, David Bergman, and J. Cole Smith. "On the consistent path problem." Operations Research, 68.6, 2020.

[13] Song, Jialin, Yisong Yue, and Bistra Dilkina. "A general large neighborhood search framework for solving integer linear programs." NeurIPS 2020.

[14] Liu, Defeng, Matteo Fischetti, and Andrea Lodi. "Learning to search in local branching." AAAI 2022.

I have read the authors responses and thank the authors for their answers. I maintain my score and overall positive impression of this work. Note that it would indeed make this work more comprehensive to investigate the effect of the tightness of the convex relaxation, as this can directly affect the accuracy of the trained surrogate models.

Thank you for your review and your appreciation of the significance of our work. We address your concerns in this individual response.

Assumption on constraints: As the reviewer pointed out, we make an assumption that the optimization problems are always feasible, which seems like a strong assumption on the surface. However, we argue that this is in fact natural, and essentially a necessary assumption in practice. In real-life applications, if we encounter an unsatisfiable scenario, this means something catastrophic is going to happen. Before actually using the application, the domain expert should always have designed the underlying real-world system to have recourse actions to mitigate bad prior actions (at cost/penalty) and to prevent catastrophe, and furthermore model such recourse actions in the (multi-stage) optimization problem. Any system and corresponding formulation of multi-stage optimization problem without such recourse should never be used/executed in the first place. It is thus a reasonable assumption and a practical responsibility we ask of the practitioner, that recourse actions are always designed into the underlying system and modelled, so that our feasibility assumption is satisfied.

Benchmarks: We want to point out that the benchmarks we consider are more complex than those in [1].

The production and sales problem we consider is not only a multi-stage extension of the alloy production problem in [1], but is more complex. The alloy production problem in [1] is a pure packing linear program, while our production and sales problem is a general (non-packing) linear program.

The investment problem we consider is also a more complex variant of the multi-stage 0-1 knapsack problem. In the 0-1 knapsack problem in [1], the objective function only considers maximizing profits. In our investment problem, the objective function considers profits from buying and selling, as well as interest gains. Additionally, the constraints in our investment problem are also more intricate.

Parameter Inclusion in Predictions: Please see overall response.

TOV: TOV stands for true optimal value (optimal objective value under true parameters in hindsight). Thanks for pointing out that we forgot to define this.

Applicability Concerns: The investment problem and the production and sales problem benchmarks are also applicable in real-life. As explained above, these benchmarks are more complex and realistic than the benchmarks considered by Hu et al. in their Two-Stage paper.

Innovativeness: Please see our responses to Reviewers GGkj and aupq.

Thank you for your review and your appreciation of the rigor in our work. Here, we address your concerns in the "Weaknesses" part of the review.

Comparison with existing Two-Stage framework: We want to emphasize that the multi-stage framework does cover a much wider range of applications. Take for example the nurse rostering problem from one of our benchmarks: we adapted the scenario from Hu et al.'s Two-Stage paper. We in fact argue that Hu et al.'s modelling into the Two-Stage framework can be somewhat unrealistic: they essentially assume that shift schedules are necessarily set a whole week at a time, with no changes possible during the week, and with appointments for the entire week closing, say, weekly on the Sunday night prior. This is rigid and does not offer the (common) flexibility of daily appointment scheduling. By contrast, our new multi-stage framework captures such flexibility --- a weekly schedule is released to nurses at the beginning of the week, but last minute (or medium-term) changes can be made at a cost/penalty, reflecting the possibility of such practice in real businesses.

Comparison to Multi-Stage Stochastic Optimization: Our work is very different from Multi-Stage Stochastic Optimization, with significantly disjoint challenges, as we detailed in Appendix A.3. Here, we highlight some of the main differences again.

The most important distinction is that MSSO does not make predictions based on features, but instead assumes knowledge of the distribution of the true parameters. On the other hand, the multi-stage Predict+Optimize framework is a supervised learning problem with predictions made from features.

The main challenge in MSSO, assuming that the distribution of true parameters we got is accurate, is primarily computational in the sense of the optimization problem -- how we can efficiently solve the complex, multi-stage optimization problem. The focus is on developing efficient algorithms and solution techniques to tackle the computational complexity of optimization.

By contrast, the key challenge in the multi-stage Predict+Optimize framework is in the learning aspect -- how we should train prediction models for estimated parameters (which has its own computational challenges), so that when applied to the optimization problem, we can obtain good solutions. Once we have a prediction model, we just solve a sequence of (relatively simple, non-multi-stage) optimization problems, without the computational challenge of solving a multi-stage stochastic programming problem.

In summary, the two frameworks are in fact very different technically, even though they look similar on the surface.

Benchmarks: Please see the overall response.

Thank you for your detailed review of our work. We respond to your concerns below.

Datasets: Please see overall response. Furthermore, thank you for your suggestion of stock data. However, the datasets from the cited works are not suitable for our purposes either. This is because the cited works only deal with unknowns in the objective, meaning that across each data set, the constraints are always the same, so there is nothing to predict in our setting. As we mentioned in our overall response, the field is still in its infancy. Application domain practitioners have yet to collect publicly available benchmarks and datasets in the multi-stage P+O setting (which is a supervised learning problem), given that there were no other works handling our proposed learning setting. We thus hope that our work, by laying the foundations for this new framework, will serve as a "call to arms" for practitioners and researchers to collect datasets for further work on training methods. We will explicitly state this in the revised paper.

Incrementality compared with two-stage work: We respectfully disagree with this assessment. Any multi-stage training approach, when restricted to $t=2$, will degenerate to a two-stage training method. In this sense, any multi-stage method will necessarily look like an unrolling of a two-stage method. Given that the problem setting itself is useful and enables a much wider class of applications, and the fact that we propose 3 concrete training methods, we believe that this line of work is valuable and actionable to disseminate to the community.

Substantial empirical improvement: In Appendices F.1 and F.3 (referenced in lines 294 and 337), we gave per-simulation comparisons between our methods against "best among all standard regression methods" (BAS). Win rates can be directly computed from these plots by counting the number of simulations with ratios > 1. Here we present the win rate tables, showing that our methods outperform BAS in most simulations.

Win rates for the production and sales problem.

Win rates for the 0-1 knapsack problem.

Win rates for the nurse rostering problem.

Necessity of coordinate-descent approach: Yes, it is possible to train all networks simultaneously, e.g. by using ground truth parameters in place of prior and future stage predictions. However, intuitively, this is a worse approach than our methods, given the interdependency of the predictors: the performance of a predictor depends on the predictions and choices made in past and future stages. We did nonetheless explore this alternative training method before, with preliminary results, but the solution quality achieved was worse than the SCD and PCD methods.

Mean post-hoc regrets and standard deviations for different training methods in the production and sales problem.

The coordinate descent strategy in the paper was needed to capture the complex interactions between the networks in different stages, and crucial for the strong performance. We will include the results and discussion in the revised paper.

Off-by-one indices: we double-checked, the indexing in the paper is correct, although we appreciate that the writing could be further clarified. Thank you for pointing this out and we will clean it up more in the paper.

Line 142 refers to what happened just prior to stage $t$, and line 144 refers to what is happening during stage $t$ (so $\theta_t$ has been revealed at that point).

Line 152: the soft solutions start at stage 0 in the sense that stage 0 generates a soft solution, but within the solution vector, the decision variables are between stages 1 to T (in the context of line 152 we only need to constrain the decisions in stages 1..t-1 for non-anticipativity).

Question: Please see overall response.