Multi-Stage Predict+Optimize for (Mixed Integer) Linear Programs
Authors: Xinyi HU
Jasper C.H. Lee
Jimmy H.M. Lee
Peter J. Stuckey
Venue: NeurIPS 2024 poster (2024)
Keywords: Constraint Optimization
Machine Learning
Predict+Optimize
Primary area: optimization

Abstract: The recently-proposed framework of Predict+Optimize tackles optimization problems with parameters that are unknown at solving time, in a supervised learning setting. Prior frameworks consider only the scenario where all unknown parameters are (eventually) revealed simultaneously. In this work, we propose Multi-Stage Predict+Optimize, a novel extension catering to applications where unknown parameters are revealed in sequential stages, with optimization decisions made in between. We further develop three training algorithms for neural networks (NNs) for our framework as proof of concept, both of which handle all mixed integer linear programs. The first baseline algorithm is a natural extension of prior work, training a single NN which makes a single prediction of unknown parameters. The second and third algorithms instead leverage the possibility of updating parameter predictions between stages, and trains one NN per stage. To handle the interdependency between the neural networks, we adopt sequential and parallelized versions of coordinate descent for training. Experimentation on three benchmarks demonstrates the superior learning performance of our methods over classical approaches.

Multi-Stage Predict+Optimize for (Mixed Integer) Linear Programs
Xinyi Hu', Jasper C.H. Lee", Jimmy H.M. Lee', Peter Stuckey Department of Computer Science and Engineering,
The Chinese University of Hong Kong, Shatin, N.T., Hong Kong Deppatmenn of Computer Science, University of California, Davis, USA Department of Data Science and AI, Monash University, Clayton, Australia (xyhu,jlee) www..ecc...... edu.hk, jasperlee @ uedavis. peter.stuckey monash. edu
Abstract
The recently-proposed framework of Predict+Optimize tackles optimization prob- lems with parameters that are unknown at solving time, in a supervised learning setting. Prior frameworks consider only the scenario where all unknown parameters are (eventually) revealed at the same time. In this work, we propose Multi-Stage Predict+ Optimize, novel extension catering to applications where unknown pa- rameters are instead revealed in sequential stages, with optimization decisions made in between. We further develop three training algorithms for neural networks (NNs) for our framework as proof of concept, all of which can handle mixed integer linear programs. The first baseline algorithm is a natural extension of prior work, training a single NN which makes single prediction of unknown parameters. The second and third algorithms instead leverage the possibility of updating parameter predic- tions between stages, and trains one NN per stage. To handle the interdependency between the NNs, we adopt sequential and parallelized versions of coordinate de- scent for training. Experimentation on three benchmarks demonstrates the superior learning performance of our methods over classical approaches.
Introduction
Constrained optimization problems can frequently model applications in everyday life, yet, the parameters of the problem are unknown at the time of solving. Consider, for example, real-world application where hospital administrators need schedule shifts for nurses, so as to minimize the total costs for hiring nurses while meeting the patient load. Here, the shifts need to be decided before the (real-time) patient demand known, which requires predicting the demand when scheduling.
In the present work, we focus on the supervised learning setting, where unknown parameters can be predicted using relevant features, and historical (features, parameters) pairs serve training data for the prediction model. The goal is to estimate the unknown parameters based on the related features, such that when solve the optimization problem using the estimated parameters, the resulting solution is good even under the later-revealed true parameters.
Classic approaches, for example by learning predictors using (regularized) lg loss, do not neces- sarily work well - low prediction error in parameter space does not guarantee good performance of the estimated solution according to the optimization objective. The influential framework of Predict+Optimizz proposed by Elmachtoub and Grigas (9] instead uses the more effective regrer loss, which incorporates information about the optimization problem. However, the framework limits the unknown parameters to appear only in the objective and not the constraints - if uncertainty in constraints is mis-predicted, the resulting estimated solution might not even be feasible under the true parameters. Recent works by Hu et al. 13 16 thus propose Two-Stage adaptation of
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Predict+Optimizz explicitly modelling 1) prediction stage and 2) recourse stage which corrects infeasible solutions into feasible ones. The new two-stage framework therefore applicable even when the optimization constraints contain uncertainty.
However, the two-stage framework essentially assumes that all the unknown parameters are revealed simultancously, excluding applications where such information is gradually released and new de- cisions need to be made across many stages (e.g. in a daily/weekly manner). Crucially, in these applications, predictions can also be updated between stages, in light of the new information and past committed actions. Consider again the example of scheduling shifts for nurses. typical facility might have an appointment system, with reservations closing the day before each working day. As opposed to a two-stage modelling, more practical approach would treat each day in work week as its own stage where new information (the precise appointments the next day) is learned, inducing both new optimization decisions and updated predictions.
The concrete contributions of this paper are three-fold.
Framework We propose and formalize the new framework of Multi-Stage Predict+ Optimize (Section where unknown parameters are revealed across multiple stages, inducing new optimization decisions and updated parameter predictions.
Training algorithms The flexibility to update (future) parameter predictions in each stage intro- duces intricate challenges to the training process, which should train a prediction model per stage. The challenges are both in predictive power and in computation time. The performance of predictors across stages are intertwined and interdependent: the "goodness" " of a prediction depends on actions in other stages, which in turn depends predictions of those other stages. Such dependency can also cause scrialization issues that could drastically lengthen training time.
In Section 4 we propose three neural network training algorithms for our framework, assuming that the optimization problems can be formulated as mixed integer linear programs (MILPs): 1) baseline algorithm that directly generalizes the two-stage algorithm of Hu et al. [16), training only a single neural network predictor, 2) a sequential coordinate descent training algorithm which trains a neural network model per stuge, and each stage is considered "coordinate" and 3) a parallel version of coordinate descent. These algorithms trade off between training time and predictive performance.
Empirical evaluation We apply these methods to three benchmarks (Section 5) to empirically demonstrate their superior learning performance over classical training methods, well as the computation//reeictioon tradeoff between the proposed methods.
We note that there are other lines of work tackling similar settings, where unknown parameters in optimizations are also revealed in a sequential fashion. Perhaps the most well-known is multi-stage stochastic optimization [14 30 The main difference between work and multi-stage stochastic optimization is supervised vs unsupervised learning. Our framework (and Predict+Optimize in general) has features that help making parameter predictions, whereas (non-contextual) stochastic optimization does not and requires different techniques to tackle. See Appendix (A.3 for detailed discussion on the connection and comparison between our framework and stochastic optimization.
Related Work We include brief literature review here in the main body. See Appendix A for detailed exposition.
Elmachtoub and Grigas proposed the influential framework of Predict+Optimize 19. with lots of followup work in the community on improving computational efficiency 23
24], predictive
accuracy 77] [8] 22), types of applicable optimization problems 112
17
36 and applying to
specific real-world scenarios [6] 34 33). More recently, Hu et al. [5 16 proposed adaptations of
the framework to handle uncertainty in optimization constraints, including the Two-Stage framework which our work is most related to.
Predict+ Optimize also sits in a broader line of work on decision-focused Jernsin including works that
learn prediction models for unknown parameters but with different goals/loss measures [25 28 as
well as other works that invent techniques for differentiating through optimization problems [| 2 36).

---

Outside of decision-focuset learning, our work is also somewhat related to (multi-stage) stochastic programming [4 30]. The main difference, again, is supervised vs unsupervised learning. See Appendix A.3 for more detailed comparison.
2 Background - Two-Stage Predict+Optimize
In this section, describe Two-Stage Predict+Optimize [6], which is prerequisite understanding our contributions. Without loss of generality, the framework is stated for minimization problems.
A parameterized optimization problem (Para-OP) P(0) is defined finding:
x (0) = arg min (bj s.t. C(x,0)
where z is a vector of decision variables, is a vector of parameters, obj function mapping decisions and parameters to real objective value that is to be minimized, and C' is a set of constraints that must be satisfied over under parameters 8. We call x (0) an optimal solution under parameters 0, and (bj(x (0), 0)) the optimal value under parameters 0. When the parameters are all known, Para-OP is just a classical optimization problem (OP).
In the Predict+Optimize setting (from the original framework [9] to the two-stage framework [16], and our multi-stage framework later on), each instantiation of the true parameter vector has an associated feature matrix A. These features are relevant information that can help model predict 6.
In the following, number the stages by 0 and 1 in Two-Stage Predict+Optimize [16 make the framework look more similar to the multi-stage framework we propose later Section
Stage The practitioner prediction model, which takes in feature matrix A, to compute vector of estimated parameters 0. The Stage O solution dgg is then computed
2(00) arg min (xj 0) s.t. C(x,
The Stage 0 solution (0)) should be interpreted as a form of soft commitment that can be modified in Stage subject to penalty.
Stage 1
The true parameters 0 are revealed, and the practitioner wishes to compute an updated
Stage solution a(1) from a(0), subject to a (problem-specifie) penalty function (en(E + _()),, ((),,) which depends on both the softly-commitedd Stage a(0), the final Stage solution a(1) and the true parameters More specifically, the Stage solution ((1) is computed as
(11) arg min obj(x, 0) Pen(s + xx s.t. C(x,0)
The Stage 1 solution (1)) should be interpreted as hard-committed final action, and note that it is guaranteed to be feasible under the true parameters 0.
The prediction á is evaluated using the post-hoc regret [66]. which is the sum of two terms: (a) the difference in objective between the true optimal solution x² (0) and the final Stage 1 solution .(1) under the true parameters 0, and (b) the penalty incurred by modifying ((0) a(1), Formally, the post-hoc regret function PReg(0, f) (for minimization problems) is:
PReg( 0 0) obj - (a)((="(0),,0 + Pen(x + 221)
The goal of a prediction model is to make predictions 0 so as to minimize the host-hoc regret. We emphasize again that the main difference between Predict+Optimize frameworks and stochastic prediction model has access to features
programming frameworks is that in Predict+Optimize relevant to the true parameters order to make a prediction. Stochastic programming. on the other hand, frequently operates solely the level of the distribution over the true parameters.

---

3 Multi-Stage Predict+Optimize
In this section, we present our new framework Multi-Stage Opetiiz which models applications where unknown parameters are revealed across T different stages. Consider again the Para-OP
x" (0) arg min obj 0) s.t. C(x, 0)
We view the true parameter vector 0 as (f...... released at Stage Similarly, we also view the vector decision variables x as (fn,..., FT), where each 24 is the sub-vector of decision variables that are hard-committed in Stage t (e.g. via concrete real-world action taken at Stage t) and soft-committed in prior stages (e.g. tentative nurse schedule).
rr), .t....,,r)))
where each 0, is the sub-vector of parameters
At a high level, the parameters 0g are revealed at Stage t, and a model makes a prediction ((t)
(0 t+1..... B()) of all the unrevealed parameters. Then, the practitioner solves the Stage optimization problem which we define later in the section. The decision variables Hy are newly hard-committed, whereas the decision variables Li+ly...,- JT are soft-committed with potential to be modified in
future stages (at the cost of a penalty). This process repeated until stages are completed.
In the rest of the section and paper, we will use the standard notation of 0lt ty] ......... 022) to
denote sub-vectors (treated arrays), and use the notation @ for vector concatenation.
3.1 Formal Framework Definition
Now we formally define Multi-Stage Predict+Optimii framework. In Appendix B we also present the hospital scenario from the Introduction as detailed example of applying this framework.
Stage 0 None of the parameters have been revealed. Modelo takes the feature matrix A and
predicts ((0) = (0 ) The practitioner then computes the Stage 0 solution ((() as
(:) arg arg min (bj (()) s.t. C(r, (())
The decision variables { are hard commitments, whereas the rest of the decision vector (0) ... 2T are soft commitments.
[0)
Stage (for S T) The true parameters 0I...., 0z-1 were previously revealed, and 0g is newly revealed. Model, makes prediction ((t) (0 (++1.... (()) using 1) the feature matrix A, 2) the previous stage solution f((-1) and 3) the revealed true parameters f1,... A.. For computational efficiency reasons, Model; may instead take any subset or derived functions of the above inputs. For example, Model, can choose whether or not incorporate the revealed true parameters f,,.... 9, as input. While these revealed parameters can serve as additional features, potentially guiding and correcting current predictions more effectively, they also increase training time (and inference time to smaller extent). The trade-off between prediction improvement and additional training time depends on the optimization problem, model structure, and training data. Therefore, whether to utilize the revealed true parameters can be considered hyperparameter that should be tuned for each application using the available training data. See Appendix H. for a more detailed discussion.
,,....,,--.
Afterwards, the practitioner computes the Stage f solution a(() using the following Stage t opti- mization problem, which crucially modifies the original Para-OP by: 1) introducing penalty term Pen,(# (2(+-1) > 2, 0[1 : t)) capturing the cost of changing the Stage - solution ((f- to the new Stage t solution x, and 2) introducing the constraint that xx1 : 1] = ((t-1)(1 : 1]. namely, hard commitments from prior stages cannot be modified in the current Stage t. This constraint is form of a non-anticipativity constraint the stochastic programming literature [4]
(t) arg min obj 0[1 0()) Pen, (ann((lt (t(t-1) + x, 0[1 t))
s.t. C(x, 01 0(0) and x|1 : t 1] = ((t-1)

---

The Stage solution, by construction, has 2 t - 1] being equal/compatible with the hard commitments from prior stages. The new hard commitments are a!!' and the rest the decision vector é [t [t+ + 1 7] are new soft commitments we make for the future stages.
At T, the prediction ( is length-O vector since all the true parameters will have been revealed.
For the rest of the paper, we make the assumption that these Stage t optimizations are always satisfiable, regardless of the prior stage solutions, prior+current predictions and revealed parameters. For practical applications, this assumption is both natural and essential. In real- world scenarios, encountering unsatisfiable condition the application, the domain expert should always have designed the underlying real-world system to have recourse actions mitigate bad prior commitments (at cost/penalty) and prevent catastrophe, and furthermore model such recourse actions in the (multi-stage) optimization problem. Any system and the corresponding formulation of multi-stage optimization problem lacking such recourse should not be used/executed. It is thus a reasonable assumption and practical responsibility our framework asks of the practitioner, that recourse actions are always designed into the underlying system and modelled, so that our feasibility assumption is satisfied.
lead to catastrophic outcomes. Therefore, before using
The sequence of predictions ((0), g(.,.... @(7), which along with the true parameters induces the sequence of solutions _:(0), ..... ((T), is evaluated using a generalized notion of post-hoc regret, defined as follows (for a minimization problem):
Evaluation:
PReg((0 ((T)), obj(a!
(()))=(00)))) Σ (en (1))
0n 4)
where x² (0) is again the optimal in-hindsight vector of decisions for the original Para-OP.
We note that if problem has only 2 stages (Stages 0 and 1), then framework of Multi-Stage Predict+Optimize indeed captures Two-Stage Predict+Optimize described in Section 2
4 End-to-End Training Algorithms on MILPs
In this section, we give 3 training algorithms for neural network models for the Multi-Stage Pre- dict+Optimize framework, under the assumption that all Stage t optimization problems can be formulated as (mixed integer) linear programs (MILPs).
The first training algorithm, our baseline (Section 4.1 is a straightforward generalization of the one proposed for the two-stage framework [16). This algorithm only trains single neural network and reuses the same parameter predictions across all stages. Although the approach is computationally efficient, it fails to fully exploit the power of the framework, which allows for predictions to be updated at each stage.
Our second and third algorithms (Sections 4.2 and instead train neural network per stage. each making new parameter predictions for the corresponding stage. As mentioned in Section [ it is delicate to train these neural networks. The quality of prediction in stage depends decisions in other stages, which in turn depends on predictions made in those other stages. To handle this dependency, we employ is coordinate. We present both a sequential version and a parallel version of this strategy as training algorithms, which trade off between training time (sequential being slower) and predictive performance.
coordinate-dsseen strategy, where each stage/neural network
We also point out that it is technically possible to train all networks simultancously, without using coordinate descent like in Sections 4.2 and 4.. To do so, we would instead use ground truth parameters in place of prior and future stage predictions. However, intuitively, this simpler approach should have worse predictive ability than the proposed two methods, given the interdependency of the predictors. We show experimental comparisons in Appendix H.2 confirming this intuition.
In Section 5| we show empirical results comparing these algorithms and classic learning algorithms (e.g. standard regression models), which demonstrate that even our baseline training approach outperforms classic rre-PeddtttOtimmizee algorithms. Also, our more sophisticated approaches yield even better learning performance, at the cost of additional training time.
5

---

4.1 Baseline: Extending the Two-Stage Approach to Train Single Neural Network
We first present a baseline Predict-Optimize training algorithm for our multi multi-stage setting, via natural extension of the two-stage approach [16].
This baseline algorithm trains a single neural network NN,, which takes feature matrix A and returns the prediction 0 (A). The same predictions then reused across all the stages, More specifically, in the language of Section we choose 0 O[ + T) for this basic approach.
We use standard gradient methods to train the neural network NN, with the goal of minimizing post-hoc regret as defined in Section
PReg = ob) 0) - obj (0), + Σ Pen +00, 01 :
Noting the second term is independent of (0) and hence NN, the gradient with respect an edge weight to in NN is
d PReg dobj(a(T),
T dPen(st + 6(1, 0[1:
dw
dw.
dw.
By the law of total derivative, we can expand this to
d PReg
dobj(a(T), 0) (T) de
Σ
a Pene
d
① Penu
do(t) db
dw.
dā(T) dÔ due
0z(t-1)
d0
1(t-1) d
dw
The term dws is calculated via standard backpropagation, while the terms
a da(?)
Pen
98(1-1)
aace
and
0 Pent
0210 ((--1) calculable when the objective and penalty functions smooth. The only
non-trivial calculation is for da(e) ab for all E [T].
Recall that a(() is computed from the Stage t optimization problem, deterministic function of a(t-1) and (() (which is a sub-vector of 0 here, since we reuse predictions), while ((t-1) itself also
depends on 0. We thus further decompose
dalt) into the following recursive computation
dø
(1)
(G-(-1)
(+((
(t-r)
d@
requires differentiating through MILP. So instead of directly using MILP formulations for the Stage optimization problems, we the convex relaxation by Hu et al. (16) which in turn adapts the approach of Mandi and Guns (22].
Calculating 88(()
1 and 1660
00 1ate-1
We also note that it is possible the MILP, for example using tools like CvxpyLayer [T]. We chose Hu et al.'s calculations because their experiments showed the computational efficiency of their approach over other tools.
other convex relaxations and approaches differentiate through
4.2 Sequential Coordinate Descent
Training only one neural network, the baseline algorithm is efficient but fails to fully harness the power of the framework in Section 3 Each stage / makes new decisions, and the "goodness" of future decisions depends on these previously committed decisions. Thus, new predictions should be made each stage for future parameters, based on prior-stage optimization decisions, so to yield current and future optimization decisions that work well with the commaty-committed ones. However, the baseline algorithm ignores this information and does not update the predictions accordingly.
We thus propose our second training algorithm, which trains one neural network per stage, from Stages 0 to 7 - 1. The neural network NN, for Stage takes the feature matrix A as input, as well as all the prior decision vector (((-1), and outputs the prediction ((t) for parameters 0 :7.. The astute reader might recall that the proposed framework in Section 3 allows N N,, to utilize the revealed parameters from stage t - 1 as additional features input. However, preliminary

---

Algorithm 1: Sequential and Parallel Coordinate Descent Approaches
PROCEDURE SeqCoordinnttDesceent
PROCEDURE ParCoordinateDescent
2 t ++0
7 While not terminating
While not terminating
Save copy NN; < NN, for all E [0, Parallel train+update NN, using NN-", (like
Train NN, using NN-r (Section 4.2
5 t - (t + 1) mod T
in Section 4.2
experiments in Appendix H.1 prediction quality, while merely increasing training time. Therefore, in our current implementation, NN, does include these revealed parameters. general, however, such choice should be treated as hyperparameter and made for each application.
indicated that including such parameters does not really enhance
To address the dependency between the neural networks, we employ coordinate descent ap- proach, where each stage/neural network is treated as a "coordinate". We train the neural networks NNo..... -N cyclic order, repeating until termination (e.g. convergence or timeout). See Algorithm for high-level pseudocode description of this sequential coordinate descent approach, as well as the parallelized version described in the next subsection.
Concretely, we train NN, by considering all the other neural networks as fixed. Here, we will focus on describing the forward pass, since the backward pass gradient computations follow essentially the same strategy described in Section
see Appendix C for details of the gradient computations.
Forward pass Consider a historical (feature, parameter) pair (A, We first iteratively generate the sequence of solutions $(0) ,'o),... (()) using O(1) NN, x(i=1)) for E [0, - 1]. Then, we compute the Stage t prediction ((() = NN, f(t-1)), and generate the remaining sequence of (((T) using ((1) 0 j 1: T] for i E [1.
solutions a(0)
Backward pass The goal is to compute the derivative of the post-hoc regret with respect to each edge weight w, of NN,, Similar to Section 4.1 instead of directly using the MILP formulation of all the Stage optimization problems in the forward pass, we use the convex relaxation of Hu et al. and Mandi and Guns. This allows regret with respect to each w, in NN,, As mentioned, the calculations are quite similar to those in Section and
differentiate the modified (due convex relaxations) post-hoc
defer them to Appendix C
Experimental results in deetioonddmmosttraa that the sequential coordinate descent training approach outperforms both the classic Son--rrdictt-ppimizze methods and the baseline Predict+Optimize approach from Section 4.1
We note that in the above description of the training implementation of NN,, there is lot of repeated computation that can pre-computed and reused. Since, during coordinate descent, the prior neural networks NNo..... ..,.-. are considered fixed, the solutions (f-(9) ..... (((11)) are also fixed for given (features, parameters) pair (A, 0) no matter how NN,, is updated during training. Thus, for each (A, 0) we always pre-compute and save the sequence of solutions (f:(0) ",("),..,,,(1 ((t-1)), and only recompute (#*,, (#",...,"")) as we update NN, through training gradient steps.
4.3 Parallel Coordinate Descent
While the sequential coordinate descent training approach yields accurate predictors, the compu- tational cost also high. Training single neural network already requires solving sequences of optimization problems over many iterations; the serialization from training the neural networks one at a time can make the resulting training time prohibitive for applications.
We thus propose to parallelize the coordinate descent approach, slightly sacrificing prediction quality for efficiency. In each coordinate descent step, we train all the neural networks parallel. When training a particular neural network NN,, we use copies of NN NN,-1. IN NNT-1 from the previous descent step, but otherwise the training implementation remain the same as in See also Algorithm
Section 4.2
7

---

This simple change drastically improves running time (Appendix G while only slightly decreases predictive accuracy: the post-hoc regret of models trained using parallel coordinate descent sits between that of the baseline training algorithm and the sequential coordinate descent approach.
5 Experimental Evaluation
We evaluate the proposed 3 training algorithms: Baseline, Sequential Coordinate Descent (SCD), and Parallel Coordinate Descent (PCD) on benchmarks described in Appendix D We compare these algorithms to classic Pr-PPredittOOtiiizze regression models [10]: ridge regression (Ridge), k-nearest neighbors (k-NN), classification and regression tree (CART), random forest (RF), and neural network (NN). The single predictions from these classical regression models are used in test time identically to our Baseline approach (Section 4.1). We tune all algorithm hyperparameters via vols-valicationn. Appendix E gives all the hyperparameter types and chosen values. In particular, the termination criteria for SCD and PCD in Algorithm[] are based on a threshold that measures the difference in training set post-hoc regrets between two (outermost) iterations of the training coordinate descent. This threshold is also treated as a hyperparameter that was tuned per each application; the experiments presented in this paper, used threshold of 0.1.
Due to space limitations, we present only the best results obtained among all standard regression methods (BAS) one column in the main paper. See Appendix [ for full results. Furthermore, we report mainly the prediction accuracy - see Appendix G for computational setup and detailed runtime comparisons.
Given the lack of datasets specific these benchmarks, we follow a standard Predict+Optimize experimental approach [16] [24] [Z] and use real data from different problems as numerical values in our experiment instances. We include details in the individual subsections. For each benchmark, we run 30 simulations, each simulation containing 70/30 training/test data split.
5.1 Production and Sales Problem
Our first benchmark is a linear programming (LP) problem. An oil company is developing a production and sales plan for the upcoming T quarters/months. The company aims to maximize profits - sales revenues minus production costs - under the constraint that the amount of oil sold each quarter/month cannot exceed the customer demands. The production cost and sales price for each quarter/month are known, but the demand is revealed only at the beginning of each quarter/month after the company receives the orders. See Appendix for the detailed description and LP model.
We generate production costs and sales prices following the method by Ardjmand et al. [3]. Production costs are randomly generated from [50. 100). Two groups of sales prices are considered: low-profit product prices are randomly generated from [50, 100]; high-profit product prices are from [120, 150). Customer demands are the unknown parameters and need prediction we use real data from knapsack benchmark (28 as demand parameters, where each parameter is related to 4096 features.
We conduct experiments on T' = {4, 12). corresponding to 4 quarters or 12 months. For NN, Baseline, SCD, and PCD, we use 5-layer fully connected networks with 512 neurons per hidden layer.
Table reports the mean post-hoc regrets and standard deviations across 30 simulations for the proposed 3 methods and BAS on the problem. Appendix[F]] [Fl gives full data table (Table (5) with all standard regression methods. We also report the mean and standard deviations of True Optimal Values (TOV) in the last column - optimal objective under parameters in hindsight for readers to use as (rough) normalization for relative errors. The results demonstrate the advantage of Predict+Optimize methods. All three proposed methods, even Baseline, beat all standard regression methods. SCD consistently achieves the best performance, followed closely by PCD. Baseline falls between the two coordinate descent methods.
In Appendix F.I Table 6 shows the percentage improvements the proposed methods against BAS. From that table, we observe that the advantage of our methods increases with the number of stages.
Considering the relatively large standard deviations in Table I to show the substantial performance improvements clearly, we provide "win rate" results in Figure I and related information in Table 7 in Appendix F.I Here, "win rate" refers to counting the number of simulations (out of 30) where

---

Table 1: Mean post-hoe regrets and standard deviations for the production and sales problem.
Price group
Stage num
SCD
PCD
Baseline
BAS
TOV
Low-profit
4
293.78499.21
297 197.34=107.44
305 26z 100.8
355,564103.66
1615,75=675.7
488.72=127.62
495.21=122.42
515.802137.67
637.77+199.25
7344.78+2290.04
Hlghh prufit
505.24189.55
520,76192.20
526.77a104.99
561.36496.49
09697.99
12
287.388250..55
905.61=255.99
935.03226347
997,44273991
21066.00:4199.5
Table 2: Mean post-hoc regrets and standard deviations for the investment problem when capital=50.
Stage num
Transaction factor
SCD
PCD
Baseline
BAS
TOV
0.01
47.48x6.99
47.67=6
48.24#7.13
48.9847.19
158.56+1 1.19
0.05
34.92+5.37
35 35.2245.00 98
35 15.6446..2 28
36,42+5,70
126. 22,8.228..
0.1
25.30=3388
25.63+3933
25.9644.64
26.62444077
59.83+
0.01
2846.20e4420.4
3869. 76192001-0
3941 091437.57
3999.701475.48
7365.333
12
0.055
1679.17#20550
3112224222
1736.599232. 15
25600
0.1
6-16.14275.52
652.37177.45
665.71276.40
680.94170.16
1259.99
method outperforms another. Table repoott win rate results among Baseline, SCD, PCD, and BAS, and Figure [ further compares the proposed methods against BAS across each individual simulation. Both the table and figure show that SCD outperforms BAS in all simulations, while PCD and Baseline outperform BAS in most simulations.
5.2 Investment Problem
Our second benchmark shows our framework on a MILP problem. The task create an investment plan for trading financial products over a year, under limited capital. The net profit consists of: I) dividends gained from holding products, 2) market price of products in the portfolio at the end of the year and 3) net profits from trading products (selling price minus buying price) minus trading transaction fees. For simplicity, we assume that transaction fees are linear in the products' market prices. We call the proportionality constant the transaction factor, which we vary across experiments.
The market price of (resp. dividends from owning) each product in each quarter/month is revealed only at the beginning (rexp. end) of the quarter/month, requiring predictions. As with the previous benchmark, we use real data from a knapsack benchmark (28 for parameters needing prediction. The detailed problem description and the MILP formulation are in Appendix [.2]
We conduct experiments five financial products, and 7 {4, 12), corresponding to 4 quarters 12 months. We consider two different initial capital values: 25 and 50, and three different transaction factors: 0.01, 0.05, or 0.1. For NN, Baseline, SCD and PCD, we again 5-layer fully connected network with 512 neurons per hidden layer.
Table reports the mean post-hoc regrets and standard deviations across 30 simulations for the proposed three methods and BAS on the problem when capital=50. We report full data tables F2 TOVs reported in the last column, again for reference. The results confirm the performance ordering of SCD > PCD > Bascline > classical regression methods.
(Tables and 9 in Appendix
Table Appendix F22 presents the percentage improvement of our proposed methods against BAS. Curiously, contrasting the previous benchmark, the advantage of our methods against BAS appears to be non- non-increasing with the number of stages. We hypothesize this is an LP versus MILP issue training for this benchmark required relaxing integrality constraints, introducing more approximations with more stages. It is interesting future work to study if the performance decay in the number of stages is a general phenomenon for MILPs and if can be mitigated.
For the investment problem benchmark, we again provide win rate results Table 1T in Appendix F2 The results show that the proposed 3 methods outperform BAS in more than 96.67% of the simula- tions.
5.3 Nurse Rostering Problem
Our last benchmark is the nurse rostering MILP problem described in Section T The task to minimize the costs of hiring nurses to meet the (unknown) patient demands. After each stage's patient

---

Table 3: Mean post-hoc regrets and standard deviations for the nurse rostering problem.
Extra nuns
payment
SCDD
PCD
Baseline
BAS
TOV
15
25
25
18845-2908
144.65550000
1089155- 1R5.37
30
1201
1290,10=371.8
1111071 154,15
demands revealed, the admin can modify future rosters cost, and hire extra temporary nurses at higher salary in case of understaffing. See Appendix [B] for a detailed description of the model.
Each problem instance consists of 10 regular nurses and 7 days (stages). Extra nurses come at cost of {15, 20, 25, 30} in different experiments. Due to the longer solving time for these MILPs, we use real data from the ICON scheduling competition 33 as the numerical values for patient demands, where each demand value is related features opposed 4096 features in previous benchmarks. Given far fewer features, for both NN, Baseline, SCD and PCD, we use a smaller network architecture: 5-layer fully-connected network with neurons per hidden layer.
Table reports the mean post-hoc regrets and standard deviations across 30 simulations for each approach, again corroborating the prediction performance order of SCD PCD Baseline > BAS. Appendix F.3 gives full experimental results.
Similarly the first two benchmarks, report win rate results in Table 14 and show comparisons between the proposed methods against BAS across each individual simulation in Figure 2 in Ap- pendix[F.3 Table 14 shows that SCD pretty consistently outperforms BAS, achieving win rates of 86.67% or higher in most scenarios. PCD also demonstrates competitive performance, with win rates ranging from 70% to 83.33%, making it viable alternative hypothesized.
5.4 Runtime Analysis
Appendix G gives the training times for each method. The training times follow the order of SCD > PCD Baseline > classic regression methods, which is the same for predictive accuracy in the benchmarks, indicating a tradeoff between training time and accuracy. Our methods take longer runtime than most other regression methods due to having to solve sequences of linear programs during training. Among our methods, the coordinate descent methods take longer time than Baseline due to having to train more neural networks, and the sequential version naturally takes longer than the parallelized version.
6 Conclusion and Future Work
We propose the first PredictOOttimize framework for scenarios where unknown parameters are revealed progressively over stages. Specifically, our proposal allows better predictions and (rr)miiimi at each stage as more parameters are made known. Algorithmically, we focus on MILPs-a large and widely-studied class of problems-an present three training methods for our novel framework. Empirical results three benchmarks demonstrate better predictions from our methods over classical ones. Our methods trade off between predictive accuracy and training time.
Our work establishes the feasibility of Multi-Stage Predict+Optimize, and furthermore shows that even our baseline algorithm of training a single predictor outperforms classical non-Pree non-Predict+Optimiii approaches. Looking into the future beyond the present work, there is ample space for algorithmic improvements. As we observed in Section 5] the current experimental results suggest that our multi-stage predict-optimize methods display rather different behaviors depending on whether the optimization is a linear program or a mixed integer program. In particular, for linear programs, the advantage our methods over classical methods increases with the number of stages, whereas the opposite happens for integer programs. We believe it is important to investigate whether this phenomenon holds more generally. If so, a prudent research direction to understand whether such decay is inevitable for MILPs, if there are algorithmic techniques to mitigate this effect.
10

---

Acknowledgments
We thank the anonymous reviewers for their constructive comments. In addition, Xinyi Hu and Jimmy H.M. Lee acknowledge the financial support of General Research Fund (RGC Ref. No. CUHK 14206321) by the Hong Kong University Grants Committee, and also Direct Grant (Ref. No. 4055231) by The Chinese University of Hong Kong. Jasper C.H. Lee's work was partially done while was at the University of Wisconsin-Madison. supported by a Croucher Fellowship for Postdoctoral Research and NSF Medium Award CCF-2107079, Peter Stukky's contribution was partially supported by the DARPA Assured Neuro Symbolic Learning and Reasoning (ANSR) program under award number FA8750-23-2-100 and by the Australian Research Council through the OPTIMA ITTC IC200100009.
References
[1] A. Agrawal, B. Amos, S. Barratt, S. Boyd, Diamond, and Z. Kolter. Differentiable convex optimization layers. Advances in neural information processing systems, 32, 2019.
[2] B. Amos and J. Z. Kolter. Optnet: Differentiable optimization layer in neural networks. In International Conference on Machine Learning, pages 136-145. PMLR, 2017.
[3] E. Ardjmand, G. R. Weckman, W. A. Young, O. Sanei Bajgiran, and B. Aminipour. A robust optimisation model for production planning and pricing under demand uncertainty. International Journal of Production Research, 54(1 3):3885-3900 2016.
[4] H. Bae, J. Lee, W. C. Kim, and Y. Lee. Deep value function networks for large-scale multistage stochastic programs. In International Conference on Artificial Intelligence and Statistics, pages 11267-11287. PMLR, 2023.
[5] M.-F. Balcan, T. Dick, T. Sandholm, and E. Vitercik. Learning to branch. In International conference on machine learning, pages 344-353 PMLR, 2018.
[6] H. Chu, W. Zhang, Bai, and Y. Chen. Data-driven optimization for last-mile delivery. Complex & Intelligent Systems, 933):2271-222 2023.
[7] E. Demirović, P. J. Stuckey, T. Guns, J. Bailey, C. Leckie, K. Ramamohanarao, and J. Chan. Dynamic programming for Predict+ptimise. In Proceedings of the Thirty- Thirty-Fourth AAAI Conference Artificial Intelligence, pages 1444-1451, 2020.
[8] P. Donti, B. Amos, and J. Z. Kolter. Task-based end-to-end model learning in stochastic optimization. Advances in neural information processing systems, 30, 2017.
[9] A. N. Elmachtoub and P. Grigas, Smart "Predict, then Optimize". Management Science, 68(1):9-26 2022.
[10] Friedman, Hastie, and R. Tibshirani. The elements of statistical learning. Springer series in statistics New York, 2001, Volume 1, Number 10.
[11] M. Gasse, D. Chételat, N. Ferroni, L. Charlin, and A. Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances in neural information processing systems, 32, 2019.
[12] A. U. Guler, E. Demirović. J. Chan, J. Bailey, C. Leckie, and P. J. Stuckey. A divide and conquer algorithm for Predict+Optimize with non-convex problems. In Proceedings of the Thirty-Sixh AAAI Conference on Artificial Intelligence, 2022.
[13] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023.
[14] J. L. Higle. Stochastic programming: optimization when uncertainty matters. In Emerging theory, methods, and applications, pages 53.53. Informs, 2005.
[15] X. Hu, J. C. H. Lee, and J. H. M. Lee. Predict+Optimize for packing and covering LPs with unknown parameters in constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022.
11

---

[16] X. Hu, C. H. Lee, and J. H. M. Lee. Two-Stage Predict+Opimmize for mixed integer linear programs with unknown parameters in constraints. In Advances in Neural Information Processing Systems, 2023.
[17] X. Hu, J. H. Lee, J. H. M. Lee, and A. Z. Zhong. Branch & Learn for recursively and iteratively solvable problems in Predict+Optimiz, In Advances in Neural Information Processing Systems, 2022.
[18] J. Jeong, P. Jaggi, A. Butler, and S. Sanner. An exact symbolic reduction of linear smart Predict+Opimize to mixed integer linear programming. In K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 10053-10067. PMLR, 17-23 Jul 2022.
[19] J.-H. Lange and P. Swoboda. Efficient message passing for 0-1 ilps with binary decision diagrams. In International Conference on Machine Learning, pages 6000-6010. PMLR, 2021.
[20] D. Liu, M. Fischetti, and A. Lodi. Learning to search in local branching, In Proceedings of the aaai conference on artificial intelligence, volume 36, pages 3796-3803, 2022.
[21] L. Lozano, D. Bergman, and J. C. Smith. On the consistent path problem. Operations Research, 6816):193311931 2020.
[22] J. Mandi and T. Guns. Interior point solving for LP-based prediction-optiiisstiinn Advances Neural Information Processing Systems, 33:7272-7282, 2020.
[23] Mandi, P. Stuckey, T. Guns, et al. Smart predict-and-optimize for hard combinatorial optimization problems. In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, volume 34, pages 1603-1610, 2020.
[24] M. Mulamba, J. Mandi, M. Diligenti, M. Lombardi, V. B. Lopez, and T. Guns. Contrastive losses and solution caching for predict-and-optimizz. In 30th International Joint Conference on Artificial Intelligence (IJCAI-21): IJCAI-21, pages 2833-2840. International Joint Conferences on Artificial Intelligence, 2021.
[25] Y. Nandwani, R. Ranjan, Singla, et al. A solver-free framework for scalable learning in neural ilp architectures. Advances in Neural Information Processing Systems, 35:7972-79986 2022.
[26] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, I.. Antiga, Desmaison, A. Kopf, Yang, De Vito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances Neural Information Processing Systems
32, pages 8024 8035. 2019.
[27] R. M. Patel, J. Dumouchelle, E. Khalil, and M. Bodur. Neur2sp: Neural two-stage stochastic programming. Advances in neural information processing systems, 35:23992-24005, 2022.
[28] A. Paulus, M. Rolínek, V. Musil, B. Amos, and G. Martius. Comboptnet: Fit the right NP-hard problem by learning integer programming constraints. In International Conference on Machine Learning, pages 8443-845 8453. PMLR, 2021.
[29] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
[30] G. C. Pfiug and A. Pichler. Multistage stochastic optimization, volume 1104. Springer, 2014.
[31] Y. Rychener, Kuhn, and T. Sutter. End-to-end learning for stochastic optimization: A bayesian perspective. In International Conference on Machine Learning, pages 29455-2941 PMLR, 2023.
[32] H. Simonis, B. O'Sullivan, D. Mehta, B. Hurley, and M. D. Cauwer. Energy-Cost Aware Scheduling/Forrcasting Competition, 2014.
12

---

[33] J. Song, Y. Yue, B. Dilkina, et al. A general large neighborhood search framework for solving integer linear programs. Advances in Neural Information Processing Systems, 33:20012-20023, 2020.
[34] A. Stratigakos, S. Camal, A. Michiorri, and G. Kariniotakis. Prescriptive trees for integrated forecasting and optimization applied in trading of renewable energy. IEEE Transactions on Power Systems, 37(6):4696-4700 2022.
[35] X. Tian, R. Yan, Y. Liu, and S. Wang. A smart predict-then-optmiie method for targeted and cost-effective maritime transportation. Transportation Research Part B: Methodological, 172:32-52, 2023.
[36] B. Wilder, B. Dilkina, and M. Tambe. Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization. In Proceedings of the Thirty-Thire AAAI Conference on Artificial Intelligence, pages 1658-1666 2019.
[37] G. Zarpellon, J. Jo, Lodi, and Y. Bengio. Parameterizing branch-and and-bound search trees to learn branching policies. In Proceedings of the aaai conference artificial intelligence. volume 35, pages 3931-3939, 2021.
13

---

A Detailed Literature Review
In this section, we first summarize the related works in Predict+Opiimze,, and then summarize other works related to learning unknowns in optimization problems, but outside of Predict+Optimize.
A.1 Predict+Optimize
As mentioned in Section 1 prior works all focus the case where all unknown parameters revealed simultaneously. Most of them have focused on the regime where the unknown parameters only appear in the objective and use the regret proposed by Elmachtoub al. ( as the loss function. Since the regret loss is usually not (sub-) differentiable, and gradient-based methods do not apply. they proposed ways overcome the non-differentiabiiiyy of the regret. Elmacchoub et al. [9] propose a differentiable surrogate function for the regret function, while Wilder et al. [36] relax the integral objective in constrained optimization and solve a regularized quadratic programming problem. Mandy and Guns [22] focus on mixed integer linear programs and propose an interior point based approach. In addition to computing the (approximate) gradients of the regret function or approximations of it, another way to deal with the non- con-dfferretiiabliiy of the regret is to exploit the structure of optimization problems train models without computing gradients. Demirovíć al. 7 investigate problems amenable to tabular dynamic programming and propose coordinate descent method to learn a linear prediction function. Hu et al. [17 extend their framework, to enable problems solvable with recursive or iterative algorithm to be tackled in Predict-Optimize. Guler et al. [12 proposes divide and conquer algorithm, extending the work of Demirović al. 7 in a different manner so that the algorithm can deal with problems with the linear objective function.
As for Predict+Optimize with unknown parameters also in constraints, Hu et post-hoc regret loss function and framework for packing and covering LPs with unknown parameters in both objectives and constraints. They [16] further advocate conceptually simpler framework, which enable solving MILPs with unknown constraints. Besides, there are also works applying PredictOOptimize to a wide range of real-world problems, including maritime transportation [35]. last-mile delivery (6 and trading in renewable energy (34]
first propose the
A.2 Decision-Focused Learning
Now we summarize other works related to learning unknowns in optimization problems, particularly those outside of Predict+Optimize. These works can placed into two categories.
One category considers learning unknown parameters but with very different goals and measures of loss. For example, CombOptNet (28) and Nandwani al. (25) focus on learning parameters so as to make the predicted optimal solution (Stage O estimated solution in the proposed framework) as close to the true optimal solution x² as possible in the solution space/metric. However, these works also assume that all unknown parameters are revealed simultaneously, and thus cannot be applied to applications where unknown parameters are revealed progressively over several stages. Furthermore, experiments in Two-Stage Predict+Optimizz [16] show that these other methods yield worse predictive performance when evaluated on the post-hoe regret.
Another category gives ways to differentiate through LPs or LPs with regularizations, as a technical component gradient-based training algorithm 2
33 M. While our proposed algorithms in Section 4.1 and Appendix C use the methods of Hu et al. [15] [6] and Mandi and Guns [22] to perform gradient computations, we could in principle use any of the aforementioned other works. However, we point out that our main contribution is not the gradient computation method but the two training algorithms of the set of NNs. Nonetheless, experiments in Two-Stage Predict+Optimize framework
[I6] demonstrate that the gradient calculation method they used (which we also use) performs least as well post-hoc regret performance as other gradient methods, while being (significantly) faster. This is the reason we follow Hu et al.'s method and implementation.
A.3 (Multi-Stage) Stochastic Programming
As mentioned in Section I while stochastic programming and Predict=Optimize are related frame- works, the technical challenges are very different. The most important difference is that Pre- dict+Optimize is supervised learning problem, whereas stochastic programming is unsupervised
14

---

learning. In Ppediet+Optimizz frameworks, the true parameters (which need prediction) are always associated with relevant features that help prediction. On the other hand, stochastic programming frameworks have no such features, and typically assume that the entire distribution over the unknown parameters is given to the algorithm - in practice, the distribution needs to be estimated from historical data over the unknown parameters, which is an unsupervised density estimation problem.
Due to the different starting assumptions, Predict+Optimzee and stochastic programming formulate optimization problems rather differently. In stochastic programming, since the assumption is that the full parameter distribution given, the optimization problem (or problems, across stages) would explicitly include the expectation operator in the objective the goal is to solve for optimization decisions so that the expected objective, with expectation taken over the parameter distribution, is Predict+Optimize frameworks approach this rather differently: while the goal is still to optimize the expected objective, the optimization problems themselves are phrased such that they take predicted parameters, and the problem asks for the optimal decisions assuming the predicted parameters.
maximized/minimiize
then becomes the goal of the learning algorithm to learn to make predictions from features, such that the expected objective is optimized overall. This is achieved via empirical risk minimization over training data, which we assume are samples from the underlying (eatureepaaramtee) joint distribution.
We also note the dimensionality of the objects being learnt in the different frameworks. In stochastic programming, the entire distribution over the unknown parameters needs to be learnt. On the other hand, Predict+Ottimzze, we learn mapping from features to predicted parameters, which, under smoothness assumptions or bounded model complexity assumptions (e.g. by restricting to using fixed neural network architecture), can effectively be regarded as a (much) lower dimensional object than learning an entire distribution over unknown parameters.
A.4 Integration of Machine Learning and Mixed-Integer Programming
The integration of machine learning and (discrete) optimization is an increasingly popular field. In this section, we mention some works on using machine learning to help solve rixed-integer programs and especially stochastic programs.
In the context of integrating machine learning with stochastic programming, several noteworthy contributions have emerged. Donti et al. [8] propose 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. Patel et al. (27] use neural network to approximate the expected value function in two-stage stochastic programming problems. enabling more efficient solution approaches compared to traditional methods. Bac et al. [4] propose a neural network -bsed stagewise decomposition algorithm that can effectively approximate value functions for large-scall multistage stochastic programming problems. Rychener et al. [3 develop 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.
The application of using ML to help mixed-integer programming (MIP) has also seen substantial progress: ML algorithms for exact solving of MIPs by branch-and-oo and-cut based algorithms 5 37]. ML algorithms for exact solving of MIPs by decomposition based algorithms [1] ML algorithms for approximate solving MIPs by large neighborhood search based algorithm 33 20 and so on.
B A Detailed Example for Multi-Stage Predict+Optimize Framework
In this section, we use the hospital scenario, i.e., the nurse rostering problem (NRP), mentioned in Section as a running example for the Multi-Stage Predict+Optimize framework described in Section 3.1
Here we describe the NRP in detail. A hospital needs to make nurses schedule for the whole week (7 days) two weeks beforehand so that the nurses can be well prepared for the work and also plan for their leisure activities. The goal of the hospital to minimize the total costs for hiring nurses and meet the patients' demands.
15

---

There are full-time nurses in the hospital. If there are too many patients and the hospital's 's nurses are understaffed, the hospital can temporarily hire some extra nurses at a higher salary. Since the number of patients that will come in each shift on each day is unknown two weeks beforehand, the hospital needs to predict the number of patients to make a schedule for the full-time nurses and plan to hire extra nurses. The hospital will learn the predictor based on historical hospital records, considering features such as time of year, day of the week and temperature.
To provide better service to patients, the hospital has an appointment system that requires patients to schedule an appointment in advance to receive medical care. Reservations for the next day close the night before. At this point, the hospital knows the precise number of patients for each shift of the current day. Therefore, at the night of day (t- 1). i.e., Stage (1 < t $ 7), the true numbers of patients for each shift of the current day are revealed.
Now show the running example for the Multi-Stage Predict+Optimize framework. Examples] T and are examples for Stage O and Stage t (for 1 S t S 7) respectively.
Example 1. Suppose there are n. full-itee murses, 7 days, and 3 working shifts per day. Full-time nurses are entitled to take a rest: day-off shift. The decision variables are: 1) a Boolean vector E {0, 1)nxTx3, where 24 j. represents that whether nurse i is assigned to shift k in day j. and 2) an integer vector E N7x3, where j.k represents the number of extra nurses hired in shift k day j. Let d5 denote the number of patients in shift day j. m, denote the number of patients that the murse i can serve per shift, C; denote the payment of the nurse i per shift, e, denote the number of patients that each extra nurse can serve per shift, and e, denote the payment of each extra nurse per shift. The unknown parameters are d E &N7x3.
Consider the time that the schedules need to be made as Stage O. The hospital learns the predictor and uses the estimated number of patients d to optimize for that week's 's schedule. The Stage 0 OP. the NRP using the estimations, can be formulated as:
3
7
(00) = arg min
Tighk + Co
(1)
2,5
j=1k=1
S.I.
Miliiik + CxTTj,k 2
j.k:
10)
(I..... E (1,2,3)
(2)
Σ Fijh =1 Vi (1, (l.....,, m), E (1, (1....,77 7}
(3)
Zij.3 + Fig+t111 11 vie (1......m).) m).j E (1....,6}
(4)
1 5 Σ JIJA 22 j=1
Vi (1,..,....
(5)
I ZE (0,11), o20
(6)
where Equation represents the objective, which is to minimize the total costs for hiring full-time nurses and extra nurses; Equation ) ensures that the schedule can satisfy the patient demand under each shift; Equation 33) ensures that each full-time nurse will be scheduled for exactly one shift each day; Equation (4) ensures that no full-time nurse will be scheduled to work a night shift followed immediately by a morning shift; and Equation 5 ensures that each fach-uul-tine full-time nurse gets one or two day-off shifts per week.
After Stage O, the schedules for day I are hard commitments and cannot be changed, i.e., To (Ki Vi E (1.....n) n), 1o E (1,,,3)) whereas the rest of the decisions are soft commitments.
(())
Example 2. (Continued) At the night of day 1. - 1, i.e., Stage I. (for 1 < 1 < 7), the reservations for the next day close, and the true numbers of patients for the three shifts of the next day O, (dr,1, dr,2, de,3) E N2 are revealed. By Stage t. all the true numbers of patients for the prior t - 1 days are also revealed. The number of patients for the later 7 days are still uncovered and are
estimated as g()) = (6(1) (6/ ((.)), where g = -d")), g(t) d. d E N33 represents the numbers of patients on day estimated on day
Hard commitments contain two parts: 1) the schedule for the day 1. and the prior I. 1 days, and 2) the number of extra nurses hired in the prior t - days, i.e., here x it represents {zigj Vi
16

---

(1,2,3)). The hospital may update the predictions and reschedule for the later (7 days. But such rescheduled leads to extra costs for hiring full-time nurses, which are recorded by the penalty function Pen Pen(i(t-1) - x. ..0 : The more temporarity the shift is rescheduled, the larger the increase in the costs. For simplicity, we assume that the extra cost is linear the original cost for hiring each full-time nurse. In this scenario, the penalty function can be formulated as Extra(a(t- + x)):
{I...,n nt.je M...
3
Extra (arra((/t11)) +x)=
Extra(s(t-1) + x)is.
==
where the (1, ky-th item the penalty functiin is:
a(t-1) (T - j+ tttpp Fij. > Fig.k
Extra( - +)).
alt-1) Jij.K I t.j.k
As mentioned in Section 3.1 the Stage i optimization problem modifies the original Para-OP by: 1) introducing the penalty term capturing the cost of changing the Stage solution ((t-1) to the new Stage t solution x to the objective:
gl(t) (()) arg min
EG
ΣΣ j.U
ΣΣΣ
Extra(E(t-1) + r)isk
Fisk
6e
k=
j=1k=1
and 2) introducing the constraint that hard commitments from prior stages cannot be modified the current Stage
Fijjk #iijk' Vi (1,-,,))) E ( (1....))kk (1,2,3)) (1,233))
((t-1)
Jjkk jjk
(t-1)
(1,, (1,2,3}
Besides, for the first constraint Equation (d1,1,...,dyy (1)
2p. the Stage 0 predicted parameters d are replaced by
141,1
m + e,0 2 di
miFijkk + 6G0 2 2d j,k0
() ,7, E (1,2,3}
The four constraints from Equation Equation (6) keep the same in the Stage (for $157
optimization.
C Gradient Computations in Sequential Coordinate Descent
The post-hoc regret used train NN, can be written as:
T
01 P
(())
(b) obb (0), Pen,(((i-1)) + +000), : (7)
1=
Noting the second term is independent of (()) and hence NN,, the gradient with respect to an edge weight we in NN, is
d PRgg dobj(a(T), 0)
T d Pen + +(() 0[1:
dwa
dw
dwa
By the law of total derivative, we can expand this to d dRReg
dob)( 0) (T) d
T
Pen;
1 (
θ Pens
(
+
dw,
d dgtr) dw
1
gat 13 d0())
dw,

---

Similar to the gradient computation in Section 4.1 the term d gation, while the terms
is calculated via standard backpropa-
date
8) Pen, and Pen, 020)
(a--1 are calculable when the objective
datry
aao
and penalty functions are smooth. The only non-trivial calculation is for dace for all E [T.
decej
Recall that ((() is computed from the Stage optimization problem, as deterministic function of a(i-1) and (0), while (((-1) itself also depends on ((), We thus further decompose da into the following recursive computation
d
d
aa0
dā (i-(1-)
Oa(()
do(
0-0-1)
00()) (at-1)
requires differentiating through a MILP. So instead of directly using MILP formulations for the Stage I optimization problems, we use the convex relaxation
Calculating 02t 6Cl)
Da and 0g(9)
80(3) gati 1)
by Hu et al. [16), which in turn adapts the approach of Mandi and Guns [22].
D Details for Case Studies
In this section, we give detailed description for the other two benchmarks used in Section 5
D.1 Production and Sales Problem
We first demonstrate, using the example of the production and sales problem, how our framework can tackle LPs. An oil company intends to develop production and sales plan for the upcoming T quarters/months. The goal is to maximize the profits, i.e., the sales revenues minus the production costs, under the constraints that the amount of oil product sold each quarter/month cannot exceed the customer demands. The production cost and sales price for each quarter/month are known, but the customer demand is revealed only at the beginning of each quarter/month after the company receives the orders. The company will estimate the customer demands based on historical sales records, considering features such oil type, oil consumption of different areas, and so on.
The decision variables are: 1) a real vector x E IRT, where z, represents the amount of product produced in month i, and 2) real vector y RT, where y represents the amount of product sold in month i. Let p. denote the unit profit of selling product month i, G denote the unit cost of producing product in month d, denote the customer demands in month i. The unknown parameters are d E ?
At Stage 0, i.e., the time that the production and sales plan needs to be made, there is no order yet and the customer demands are unknown. The company learns the predictor and uses the predicted demands (()) to make the plan. The Stage OP can be formulated as:
T
T
f((), gg(0) = arg max
V
PLy
C
(8)
z.9
im
im1
s.t. y. S 100
Vi E (I....,T}
(9)
i-1
{-1
y: -
23
Mj j=1
Vi (1...,
(10)
/=1
x 0,
y 0
(11)
where Equation represents the objective, for maximizing the profits, i.e.. the sales revenues minus the production costs; Equation (9) ensures that the amount of oil product sold each quarter/month will not exceed the customer demands; Equation (O)) ensures that the amount of oil product sold each quarter/month will not exceed the inventory at that quarter/month.
At the beginning of each quarter/month, the company receives orders, and the demand for that quarter/month is revealed. We assume that the beginning of each quarter/month one stage. Then, by Stage (1 < t < T), all the true demands for the prior (t 1) quarters/months as well as the t
18

---

quarter/month are revealed. The demands for the later (T' - t) quarters/months are still uncovered and
are estimated ((+) (0 :0........ 044), where 0 d represents the demand of quarter/month
estimated on quarter/month t. The production and sales for the quarter/month i and the prior (t - 1)
quarters/months have already happened and cannot be changed, which are committed variables. There is no penalty function in this scenario. Therefore, the Stage t OP can be formulated as:
T
arg max a.y
Pill
s.t. y1 di
E {1 (1......)
vi (t 1...., T
i-1
V/ 3 Σ Tj
Σ y! Vi .T.
j=1
24 = a (1-1)
81
9
(1-1)
viE (L...,,t 1}
x 2 0, 920
D.2 Investment Problem
In the second experiment, we showcase our framework on an MILP. The unknown parameters appear in both the objective and constraints. A person wants to make an investment plan for buying several types of financial products next year to maximize the investment profit, under limited capital. The investment profit contains 3 parts: 1) the interest gained from the products owned, 2) the market prices of the products owned at the end of the year, and 3) profits from selling products minus costs for buying products minus transaction fees. The capital for the whole year is given. However, the market price of each product in each quarter/month is revealed only at the beginning of the quarter/month, and the interest of owning each product in each quarter/month is revealed only at the end of the quarter/month. The person will estimate the market prices and interests based on past experiences, considering features such as the product type, the financial condition and operational capabilities of the company to which the product belongs, and so on.
Suppose there are T quarters/months, and N investment products. The decision variables are: 1) a natural vector x E NTxN, where Ti.j represents the number of product j on hand at the end of quarter/month i, 2) an integer vector y E 2(T-1)xN, where Vi., represents the number of product j bought or sold in quarter/month i, and 3) natural vector 2 E N where ži,j represents i. Let Pi.j denote the interest of product in month i, Wi. denote the market price of product in month i, C denote the capital for the whole year.
whether the transaction fee is paid for product j in month
We assume that the end of quarter/month i.e., the beginning of quarter/month (1+ 1), is Stage (. At Stage 0. i.e., the beginning of quarter/month 1, the person can buy some products without paying transaction fee. The market price of each product at this time is known, i.e., W1 = (W1,1.... (1.)
are given. The unknown parameters in this OP are p E T and w (w2,... wyy E (TT-1)x At the beginning of each subsequent quarter/month, the person can buy more products or sell the products owned but needs to pay transaction fee. For simplicity, we assume that the transaction fee for buying/selling product i in quarter/month j is linear in the market price of product i in quarter/month j. Here, the linearity factor is independent of the request. That is, if the person buys/sells k number of product in quarter/month j, the person has to spend kowsy, where 2 non-negative tunable scalar parameter, and we call it transaction factor.
19

---

At Stage O, i.e., the beginning of quarter/month 1, the person uses the predicted interests p() and market prices ()) to make the plan. The Stage 0 OP can be formulated as:
[0) (0) 20) arg max obj (p W1, (0) 2,
(12)
N
s.t.
W1,
S.
(13)
ΣØ=1 11,
N
+ 12 1= Tū Zij
(0)
SC, A [?
(14)
+ - 1= 2,=1 iij Vi.j
Fijj = ViJ + 1(j-
E (2.... T,, NJ
(15)
2. 2 Wisi
Vie f T..j E {1, (1...., N)}
(16)
2. 2 -bbt
Ei ( ,T,j (1,...,N)
(17)
where
obj(p" W1, v." zz v) 2)
N Σ I FTJ
N
T ΣΣ ow 21,j Wis +
NNN in Vi.z)
Σ Pi. Fi
(0)
(0)
represents the objective, which is to maximize the investment profit; Equations (13) and ensure that the money spent on buying products and transaction fees will not exceed the capital available; Equations [15). (16), and (17) formulate the relationships among three decision variables z, y. and 2.
At Stage t. i.c., the end of quarter/month t, the interest of owning each product in quarter/month I as well as the market price of each product revealed. Then, by Stage (1 < 1 7), all the true market prices for the prior quarters/months, as well as the (t + 1) quarter/month, are revealed. Besides, all the true interests for the prior f quarters/months are also revealed. But the market prices for the later (I' - f - 1) quarters/months and the interests for the later (T' - f) are still uncovered and estimated as (t) (w 2 ... (f and (()) (P .bf'), where wn(") and p!") represents the market price and the interest of quarter/month i estimated on quarter/month t. The investment decisions x. y, z for the prior quarters/months have already happened and cannot be changed, which are committed variables. There is no penalty function in this scenario.
a(0), g00) -(0)
arg max obj(p[1: : 1] + p() W1, w : + 1J + u (1) a. v,
2.y.2
s.t.
W1 CC
Σ WiJT
+ 2
-i= TWi SC Vk E (2,.....
+
j=1 Wi.jilij
Σ Wi WiJJ1j
+ +1
2 Σ aw. + d
2i=(+2 ΣN ani (1)
j= 5. 2g SC, Ak 1..,...,TT T}
+ DI E/=1 Wi + Li=t+2 Ej=1
Vi.
Zij ViJ + 1(j))) Vi {2, ..... ,,, [I,...,N]
21. 2 Wi
Vi {2, , TT.j E N]
21, 2 -iis
Vie ( [2,...T]). E (I,...,,N] N}
Eij = -115 (t-1)
Vi (l,...,thh E [I,
yi. = Mi.j zi.j = 2 [((-1) Vi
(1-1)
E (1,, (1,...,N)
20

---

where
obj(p[1: ( + 100 w1, w],
1+11111 1]
+
vú
N
T
N
N
N
T
Σ
Pijuia
W1j
awi.jFi.
OrW ;.j zi.s)
i=t+1 j=1
i=
++1 N
T
N
Σ
(t)
Wiglii
+
(i
+
T TTj
1=++2
E Hyperparameters for the Experiments
The methods of k-NN, RF, NN, Baseline, SCD and PCD have hyperparameters, which tune via cross-validation: for k-NN, we try & E (1. 11.3.77 5): for RF, we try different numbers trees in the forest {10, 50, 100); for NN, Baseline, and PCD, we treat the optimizer, learning rate, and epochs as hyperparameters, For Baseline, SCD and PCD, we treat the optimizer, learning rate, the early-cut-off value of log barrier regularization term (f), and epochs hyperparameters.
Table the final hyperparameter choices for the three problems: 1) production and sales problem, 2) investment problem, and 3) nurse rostering problem.
Table 4: Hyperparameters of the experiments on the three problems.
Hyperaprameters
Model
Production sales optimizer: optam.Adam;; learning rate: x 10-x;
Invesiment
Nurse rostering
optimizer: Aptim.Adam;
optimizer: Adlam: learning rate: x 10-";
Bascline
learning rate: 1 x 10-";
p 10 *; epochss=20
p 10 8; epochs=22
10 8; epochss22 20
optimizer: optam.Adam
optimizer: optim.Adamm
optimizer: Adaam:
SCD
learning rate: x 10-x;
learning rate: 1 x 10-";
learning rate: x 10-";
p 10-*; epochs=20
( 10 epochs=20
u 10-2; epochs=20 20
optimizer: optim. Adam;
optimizer: adai:
optimizer: optim. Adam:
PCD
learning rate: x 10 7
learning rate: 1 x 6;
learning rate: x
p 10-*; epochs=20
j 10 epochs=20
10-?; epochs=20
optimizer: optim. Adam;
optimizer: optim. Adam;
optimizer: optim. Adam:
NN
learning rate: x 10
learning rate: 1
6,
learning rate: x 10
epochs==0
epochs=20
epochs=20
K-NN
k=S
RF
n.estmator-100
Ridge, k-NN, CART and RF are implemented using scikit-learn (29.. The neural network is implemented using PyTorch (26). To compute the two stages of optimization at test time for our method, and to compute the optimal solution of an (MI)LP under the true parameters, we use the Gurobi MILP solver B
F Detailed Experiment Results
F1 Production and Sales Problem
Table reports the mean post-hoc regrets and standard deviations across 30 simulations for all training methods on the production and sales problem. Compared among standard regression models, NN performs well and achieves the best performance in all cases listed in Table 5 while Ridge and RF also have decent performances.
Table shows improvement ratios among the proposed 3 algorithms and BAS. "A vs B" refers to the improvement in the percentage of method A over method B. Take "Baseline BAS" as an example. the improvement percentage of the baseline over BAS is (355.56 50555563055000 (0.226) /355555556666 100% = 14.15% when 7 in the low-profit price group. Comparing numbers in "SCD VS BAS". "PCD VS BAS" and "Baseline VS BAS" when stage num = 4 and 12, we can see that the advantages of the proposed methods over BAS are more distinct when the number of stages larger. Additionally, comparing numbers in "SCD VS Baseline" and "PCD VS Baseline" when stage num 4 and 12, we also note that the advantages of SCD and PCD over the Baseline are more distinct when the number of stages is larger.
21

---

Table 5: Mean post-hoe regrets and standard deviations of all methods for the production and sales problem.
Price group
Low-profft
High-profit
Stage mum
12
SCD
293.78=99.21 21
488.724127.62
505.24289.55 55
887.384250.55
PCD
297.348107.44
520.76192.20
905.6112255 99
Baseline
305 115.262100.88
515.80113767
$26.774104.99
935.034:263.47
NN
355,562 103.78
637.774199:25
561.36196.49
997,448273.91
Ridge
390.885 114.8
6486604214.66
612.49 T09.62
1017.41227.00
Kan
168.20&111.38
663 26329666
591.4799788 867
1050.42:296.1
873.85227.668
76..88%
RF
175.18
644.634204.55
567.35494.16
10214142244,4
TOV
7616775677577
7344.784290004
5007
09:496665
21066
00+4159.56
Table 6: Improvement ratios among Baseline, SCD, PCD, and standard regression models for the production and sales problem.
Price group
Stage num
SCD VS BAS
PCD VS BAS
Baseline VS BAS
SCD VS Baseline
PCD VS Baseline
SCD VS FCD
Low-prolit
17.38%
16.37%
14.15%
3.76%
2.59%
1.20%
23.37%
22.35%
19.12%
5.25%
3.99%
1.31%
High-profit
4
10.00%
7.23%
6.16%
4.09%
1.14%
2.98%
11.03%
9.21%
6.26%
5.10%
3.15%
2.01%
Figure I shows post-hoc regret comparisons between BAS and the proposed methods (Baseline, SCD, and PCD) for each run. The x-axis refers to the number of each simulation, and the y-axis refers to the ratio of the post-hoc regret achieved by BAS and the proposed methods (Baseline, SCD, and PCD) corresponding to that simulation. To easily read the comparisons, we sorted all simulations by the increasing order of the post-hoc regret ratios of BAS/SCD. The red dashed line where the post-hoc regret ratio is 1.0 represents the boundary line where (Baseline, SCD, or PCD) performs better or worse than BAS. When the point representing the post-hoc regret ratio of BAS(BBasllne. SCD, or PCD) falls above the red dashed line, it means that (Baseline, SCD, or PCD) performs better than BAS. Conversely, when the point falls below the red dashed line, means BAS performs better than (Baseline, SCD, or PCD). Observing Figure [ SCD outperforms BAS across all simulations in all scenarios. While not as stable as SCD, PCD and Baseline also outperform BAS in most of the simulations. Compared with Figure [a there are more BAS/Baseline points that fall below the red dashed line in Figure Tb] while the number of BAS/SCD points and the number BAS/PCD points that fall below the red dashed line are similar in Figure Ta and Figure Tb The same phenomenon can be observed when comparing Figure Ic and Figure Id demonstrating the advantage of SCD and PCD over Baseline.
The win rate of method against other methods can be directly computed from Figure by counting the number of simulations with ratios > I, and we provide the win rates table as reference in Table Table 7 indiicates that in more than half of the simulations, SCD achieved the best performance. PCD followed closely, achieving the best performance in the remaining 20% to 50% of the simulations.
Table 7: Win rates for the production and sales problem.
Price group
Stage num
Baseline beats BAS SCD beats BAS
PCD beats BAS
BAS is best
Bascline is best
SCD is best
PCD best
Low-profit
12
93.33%
73.33%
100.00%
96.67%
86.67%
90.00%
0.00%
0.00%
0.02
3.35%
66.67%
50000%
46.67%
33.33%
High-profit
96.67%
0.00%
5000P%
26,64%
12
76.67%
100.00%
80000%
0.00%%
0.00%
63.33%
36.67%
F.2 Investment Problem
Table and Table the mean post-hoc regrets and standard deviations across 30 simulations for all training methods the investment problem. Compared among standard regression models, NN performs well and achieves the best performance in most cases, while Ridge and RF also have decent performances and obtain the smallest mean post-hoc regret in some cases.
Table 10 shows improvement ratios among the proposed algorithms and BAS. Comparing "SCD vs BAS "PCD vs BAS", and "Baseline vs BAS" performance under the same capital and the same stage number, we observe that the advantages of the proposed methods (SCD, PCD, and Baseline) over the standard regression approaches become more pronounced as the transaction factor increases.
22

---

24
BASiBaseline
BASHtasiinne
BASSCD
BASISCD
BASHPCD
BADIPCD
2.0
Pow-hoo Regiet Reelo
2.0
Poschos Regret
1.8
1.6
1.6
1.4
1.4
1.0
1.0
10
20
25
30
5
10
30
Smulation
Smulation
(a) Low-profit products and quarters.
(b) Low- Low-profit products and 12 months.
1.8
1.8
BAS/Beselire BAS/SCD DAS/PCD
BAS/Beseline
1.5
BASISCD
BASPCDD
Wost Heggne, Iallo
Poot-hur Wegret Hallo
1.3
1.3
1.2
6.1
1.0
1.0
0.8
0.8
(c) High-profit products and 4 quarters.
(d) High-profit products and 12 months.
Figure BAS/Bascline, BAS/SCD, and BAS/PCD for the production and sales problem.
Table 8: Mean post-hoc regrets and standard deviations of all methods for the investment problem when capital=25.
Stage num
12
Transaction
0.01
0.05
0.1
0.01
0.05
0.1
factor
SCD
19.8543.14
14.73&3.59
10.56+1.63
151..31+185.03
666.96291.54
260.274:34.32
PCD
20.00+3.24
14.9043.62
10.63+162
1524.69=191.U
675.27-95.1 10
263.97433.00 09
Baseline
20,20%3.68
13.1423.62
10.772104
1340:47=186300
086.84299.44
269.07434.47
20.51+3.43
15,4743.67
11,23+1.77
699.30+101
277.314:32.99
Ridge
20.8843.30
15.38+3.37
11,7042.00
1588 1 +1200448
703.74497.66 62
276.51+:2.11
K-NN
22,21#3.44
16.9624.18
11.5642.15
1643 (643 198.99
722.73=79.93
285.73441.28
CART
24.8144.30
19.68s4.58
13.4242.27
1045.40= 83
832.02 1290221122..0 22,30
333.71451. 1,311.1...44
21.88+3.56
16.9843.74
12.07+1.93
1563.94=
700.31+77.70
279. 84:3474
TOV
64.1144.91
51.5329.97
39.8742.67
2404.224264.88
1147.61=11454
502.051:46.67
Besides, comparing "SCD vs Baseline" and "PCD vs Baseline" under the same capital and the same transaction factor but different stage numbers, the advantages of SCD and PCD over Baseline amplified as the number of stages increases. This trend is consistent with the findings from the experiments on the production and sales problem. One interesting phenomenon is that under the same capital and the same transaction factor, the advantage of the proposed methods over BAS appears be similar or even less obvious when the number of stages 12 compared when is 4. This observation differs from the pattern seen in the production and sales problem experiments. We hypothesize that this divergence may be attributable to the fundamental differences between the problem settings. While the production and sales problem is pure LP, the investment problem is an IP with several integrality constraints. The proposed methods relax these integrality constraints and treat the problem an I.P for the purpose of forward and backward propagation. The gaps between the original and the relaxed I.P may accumulate as the number stages grows larger, potentially diminishing the advantages of the PredictOOptmiize approaches.
23

---

Table 9: Mean post-hoc regrets and standard deviations of all methods for the investment problem when capital=50.
Stage
12
Transaction
0.01
0.05
factor
SCD
47.4816.98
34.9245.57
25.50033888
3846, 20:42204422044
1663,824208.66
646,14475..
PCD
47.6746.64
35,2245 98
25,6343393
1699177225.01
652,57474,45
Bascline
48.2427.13
35.6426.28
25.9614..64
39410094437.37
1701 7701:51222,445
665.71276.40
48.9847.19
36.4245.70
26.6244.07
41146 7943390.52
1736.596222.15
680.94470.
Ridge
50.73+6.35
37.3844.66
27.6243.12
4019.04a454478
1743.964217955
682.24474.91
E-NN
53,4918.52
39.6947.22
28. 16.8823..6
4213.338434462
299.922206.99
702.48194.53
CART
62.35211.68
47.0559.14
31.8126.76
4723,274529.86
20N6.094325.70
835.966 137.08
RF
52,4926673
39.0746.50
27.7543.84
3999, 70:454447
1748.024201.6 1..66
696,46275.14
TOV
158.56
126.2248.86
99.83+7.02
6166.734573.51
2860.054288.85
1259.99
Table 10: Improvement ratios among Baseline, SCD, PCD, and standard regression models for the investment problem.
Capital
Stage
Transaction Factor
SCD VS BAS
PCD VS BAS
Baseline VS BAS
SCD Baseline
PCD VS Buseline
SCD VS PCD
0.01
3.25%
2.53%
1.33%
L.44%
1.01%
0.745
0.08
4.27%
3.15%
1.57%
2.70%
1.12%
1.99%
25
0.01
5.23%
2.50%
1.49%
1.76%
1.02%
0.78%
12
0108
4.07%
3.17%
1.78%
2.90%
1.8%
1,235
4.53%
3.27%
0.01
3,06%
2.85%
1.51%
1.38%
1.19%
0.39%
4
0.05
4.12%
3.2916
2.1495
2,027%
118%
0.83%
50
0.1
4.21%
3.25%
3.71%
2,46%
1,79%
1.27%
0.61%
0.52%
12
0.05
4.19%
3.31%
2,02%
2,2256
1.31%
0.91%
0.1
5.11%
4.17%
2.24%
2.94%
1.97%
0.99%
Table 11 presents the win rate results for Baseline, SCD, PCD, and BAS. We observe that SCD) outperforms BAS across most of the simulations, with win rates exceeding 80% in most scenarios. PCD also shows strong performance, particularly at higher transaction factors. Compared with BAS, PCD achieves win rates above 80% in many scenarios, closely following SCD.
Table 11: Win rates for the investment problem.
Captial
Stage
Transaction
Baseline
Buseline
PCD
0.01
31.339
86.87%
73.33%
3.33%
30.0F%
46.7%
X0002
1,05
0300%S
33.33%
43.33%
7000P9
93.33%
33.35%
46.6%%
X00056
96.67%
93,339
0.00%
6.67%
83.
10.00%
0.1
$3.23%
100002
56.07%
0.00%
0000%
50.6%%
13.35%
0.01
60003
80.075
66.675
3.35%
23.35%
43.33%
30,073
0,005
66,679
33.
33.338
3.33%
36.67%
4000P%
200073
90.00N
0000%S
26.67%
43.33%
1501
700099
83.33%
X3.339
3,338
130095
80T0PS
16.0%
0.1
76.67%
100.09%
90.009
0.00%
0.00%
93.33%
F.3 Nurse Rostering Problem
Table 12 reports the post-hoc regrets and standard deviations across 30 simulations for all training methods on the nurse rostering problem. Compared among standard regression models, NN always performs well and achieves the best performance, while Ridge and RF also have decent performances.
Table 13 shows improvement ratios among the proposed algorithms and BAS. Comparing "SCD vs BAS" "PCD vs BAS", and "Baseline vs BAS" performance with different extra nurse payments, we observe that the advantages of the proposed methods (SCD, PCD, and Baseline) over the standard regression approaches become more pronounced as the extra nurse payment increases.
Figure 2 shows post-hoc regret comparisons between BAS and the proposed methods (Baseline, SCD, and PCD) for each run. easily read the comparisons, we again sorted all simulations by the increasing order of the post-hoc regret ratios of BAS/SCD. Observing Figure 2 the proposed

---

Table 12: Mean post-hoc regrets and standard deviations of all methods for the nurse rostering problem.
Extra
25
30
payment
SCD
607.66=+12.119
789.65+2100.22
1038.294255.42
1207,50=319h
PCD
622.05+153.64
805.11
1048.08428..33
1240.48::332.3
Baseline
629.35x153.67
817 (.7,002299.44
1083,454259.68
1290. IO
NN
662.344119.11
863.024214 14,55
1144.633.305000
1369.81a:373.21
Ridge
663.574141.49
887.634206.35
1146.564297.33
1371.204320.37
K-NN
758.494135.75
1033.884 197.22
1309:924255.80
1562.984298. 14
CART
765.167277.67
1303.682280.1
1645.594
1957.
RF
080.472148.20
370,30#221.81
1145.32#293.18
1378.682233375
TOV
10671.14=1574.1
10732.32+1504
1504.12
10893.54x148.577
11110.73#1344.55
Table 13: Improvement ratios among Baseline, SCD, PCD, and standard regression models for the nurse rostering problem.
SCD BAS
PCD BAS
Baseline V$ BAS
SCD VS Buseline
PCD VS Baseline
SCD PCD
payment
15
8.26%
6.08%
4,98% 5.26%
3.45%
1.16%
2.31%
25
9,29%
8.44%
5,35%
4.17%
3.26%
0.93%
RAS/Boseline BAS/SCD
BAS/Boselire
BASISCD
1.8
BAS/PCD
1.8
BAS/PCD
Phst-hox Iegret Ital
Phatt Post-hos Iegget Itllo
1.6
1.6
1.0
0.8
0.8
30
15
20
25
10
15
30
Simulation
Simulattion
(a) Extra murse payment 15.
(h) Extra nurse payment 20.
2.0
2.0
BASrtaaseline
BASrtasseline
BASISCD
BAS/SCD
1.8
BASIPCD
BASIPCD
Pos coc Regret Itato
Pos--hoc tegret Hallo
1.4
1.2
1.2
1.0
1.0
0.8
0.8
Simulation
Simulation
(c) Extra nurse payment = 25.
(d) Extra nurse payment = 30.
Figure 2: BAS/Baseline, BAS/SCD, and BAS/PCD for the nurse rostering problem.
methods outperform BAS in most of the simulations. Since the nurse rostering problem is an IP with several integrality constraints, and the proposed methods just relax these constraints and treat the problem as an I.P for the purpose of forward and backward propagation. We hypothesize that the gap between the original and the relaxed I.P may diminish the advantages of the proposed methods, and thus, BAS sometimes performs slightly better than the proposed methods.
25

---

Table 14 presents the win rate results for Baseline, SCD, PCD, and BAS. Same as in the first two benchmarks. SCD demonstrates high win rates against BAS across all scenarios. SCD achieves win rates of 86.67% or higher in three out of four cases, peaking at 96.67% when the extra payment is 25. PCD also performs well, with win rates ranging from 70% to 83.33% against BAS. While not as consistently high as SCD, PCD's performance remains competitive, indicating its viability as an alternative approach.
Table 14: Win rates for the nurse rostering problem.
Extra murse payment
Baseline beats BAS
SCD beats BAS
PCD beats BAS
BAS is best
Baseline is best
SCD best
PCD is best
70.00%
70.00%
70.00%
10.00%
26.67%
40.00%
23.33%
20
73.33%
86.67%
80.00%
6.67%
10.00%
50.00%
33.33%
73.33%
96.67%
83,33%
3.33%
16.67%
43.33%
36.67%
30
73.33%
86.67%
76.67%
3.33%
6.67%
60.00%
30.00%
G Runtimes for the Experiments
Table 15: Average training time (in seconds) for the three benchmarks (in seconds).
Trining Line
Low grode
Figh profii
Law pooti
High profi
Capral 23
Cipral 30
Captil
Capital 30
R25, 69
700.682244.7
3287 09.509.7.
7329999
57455758000
535 18:885
78400=1198411
189601
20
137
19772-913
195 1755
08101-361
197
NXS
17.9171611
00.14 15.34
1eige
1.71
138.6.19
T.8N
03R
CART
0.7740.19
2/4610.30
5.7901
27.3022.19
RF
21XEETT
35K
In this paper, all models are trained with Intel(R) Xeon(R) CPU E5-2630 v2 @ 2.60GHz processors on Google Colab. Since the testing time of different approaches quite similar and close to being negligible, here, we only show the training time of each prediction model and do not include the testing time. At training time, the proposed Baseline, SCD, and PCD methods need to solve the LP. Training for the usual NN does not involve the LP at all, and so training is much faster (but gives much worse results).
There are two stopping criteria for SCD and PCD. We set the maximum iteration number of SCD and PCD as 5. Besides, if the difference between the post-hoe hoc regret of two consecutive iterations is less than 1, we consider that the algorithm has converged. This is the second stopping criterion.
Table 15 shows the average training time across 30 simulations for the three problems. For the investment problem, since the training times under different transaction fees are similar when the capital and the number of stages the same, we do not report them one by the average. For the nurse rostering problem, since the training times under different extra nurse payments are similar when the numbers of stages are the same, we also do not report them one by one but report only the average.
but report only
Since the proposed 3 methods require solving multiple LPs when training, their training times usually longer than standard methods. But since the production and sales problem is an LP, the solving time of which is not too long, the training time of Baseline is around double of NN. Table [5 also shows that SCD and PCD usually converge in 4 iterations in the production and sales problem.
In the investment problem, the training times of Baseline are better than that of RF. The solving time of the OP, i.c., the difficulty of solving the OP, can largely affect the training times of the proposed methods. When the number of stages grows larger, the investment problem is more difficult to solve. Therefore, the training times of Bascline when there are 4 stages are quite comparable with that of NN, but the training times of Baseline when there are 12 stages are much larger than that of NN. In addition, when the OP becomes more complex, the number of iterations required for SCD and PCD convergence also increases. SCD and PCD convergence usually in 2-3 iterations when there are stages, and usually in 3-4 iterations when there are 12 stages.
In the NRP, since the solving time of 1 NRP is large, the training times of the proposed methods are larger than standard regression methods, which indicates that one future research direction the seeed-vs-predicttnn accuracy tradeoff's on Multi-Stage Predict+Optimize.
26

---

H Other End-to-End Training Approaches on MILPs
As mentioned in Section 3 and Section other types of training algorithms be used within the proposed framework. Considering the performance in both post-hoc regret and training time, we proposed three training algorithms in Section 4 However, there additional possibilities, and will discuss two of them in this section.
H.1 Revealed Parameters as a Feature for Later Stage Predictions
As mentioned in Section 3 the proposed framework allows the training algorithm to choose whether to incorporate the revealed true parameters as additional features as input. In the current implementation of the proposed SCD and PCD methods, we did not include these revealed parameters because, in our preliminary experiments, including them does not really improve prediction quality while just increasing training time.
Table reprortss the results from the experiments on the production and sales problem by incorporating the revealed parameters from stage - 1 as inputs to the stage & networks. As Table shows, the performance using this expanded input did not improve over the results of the proposed three approaches.
Table 16: Mean post-hoe regrets and standard deviations of training SCD with revealed parameters, training PCD with revealed parameters, SCD, PCD, and Baseline for the production and sales problem..
Price group
Low-profit
High-profit profit
Stuge num
12
SCD with revealed
294, 294,44481.72
48K.934116.51
507.30e63.74
190148
PCD with revealed
299.73+82.91
498. 324.32+11 123.25
521. 22174282
911 04. .57
SCD
293.78199.21
488 1XX.72x127.00
505 24.39.55
887. 25.0.55
PCD
297.34+ 107.44
495.21+122.42
520. 520.76=92.00 20
605.611255.09
Baseline
305.264 100.88
515.80#137.67
526.77#104.99
935.033263.47
The reason that including revealed parameters does not lead to better predictive performance is due to a combination of the nature of the data and the neural network architecture. Consider one extreme: the true parameter vectors in every single stage are always equal. A neural network model (or other reasonable models) that takes in the prior-stage true parameters should be able to learn to pick up on that and use the information. Consider the other extreme: if the parameter vectors are completely independent across stages, then no model will be able to use prior-stage true parameter information, since no actual information exists. Reality (and our particular dataset) somewhere in between: there can be some correlation between stages, but, it really depends on whether such information is extractable by the neural network architecture (or whatever other prediction model one wants to use within our multi-stage framework).
For general applications, the decision whether another hyperparameter, to be tuned for that particular application using the available training data (though one can be safe and always include it, at the expense of training time).
the prior-stage true parameters is essentially
H.2 Training Different-Stage Neural Networks Simultancously (or, Necessity of Coordinate Descent Approach)
We propose two coordinate descent based methods in Section 4 but it is also possible to train all networks simultancously, without the use coordinate descent. In this section, we compare the proposed two methods against simultancous training method, to better motivate the necessity of coordinate descent.
A reasonable way (and the only way we can think of) to train all networks simultaneously is replace prior and future stage predictions in SCD and PCD by the ground truth parameters. However, intuitively, this is a worse approach than the proposed methods, given the interdependency of the predictors: the performance predictor depends on the predictions and choices made in past and future stages.
27

---

Table 17: Mean post-hoc regrets and standard deviations of simultaneous training method, SCD, PCD, and Baseline for the production and sales problem..
Price group
Low-profit
High-prooe
Stage num
12
12
SCD
293,78499 21
488. 488./24127.06
505.24489.55
887.382250.55
PCD
297.34 107.44
495.21#122.44
220962222.00
905.612255
Simultaneously training
523.38288.55
925.35a223.17
Baseline
305 26.10.888
515.80&137.67
526.77=104.99
935.03=263.47
We have explored this alternative training method and here are the preliminary results on the produc- tion and sales problem in Table 17 We observe that the solution quality achieved by the simultaneous training method was worse than the SCD and PCD methods.
The coordinate descent strategy in Section was needed to capture the complex interactions between the networks in different stages, and crucial for the strong performance.
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our abstract and introduction state our contributions, including the new framework and training algorithms. We state clearly that the algorithms applicable to MILPs.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Section 3 states the "total recourse" assumption that we assume all Stage optimization problems are always satisfiable. Section 4 states that we only work with MILP formulations. Section discusses the tradeoff between training time and predictive accuracy.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
29

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification: We make no substantial theoretical claims this paper, beyond basic gradient calculations which are provided.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide code and all hyperparameter choices, as well as how the data was generated sourced.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
30

---

reproducible, they 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
We provide data and code with the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
public/guides
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7/nips cc/ wtc/ppbliic// subbbic/guides /esocguuuus///oeuubbiiiiii
Codeeoomiiiieeee SanSSubbissss sebbbbisssiioi ssisnnoiccyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide all data splits, how the data was generated/sourced, and hyperpa- rameter choices.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: We give standard deviations our results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
31

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: A gives the computational setup.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't I make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
We have no human subjects nor do we use any private data in experiments.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is on fundamental research and does not have direct path to nefarious use cases.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
32

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work does not release any artifacts that can be easily misused.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cite relevant data sources in Section S
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
33

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We provide documentation for our implementations to run these experiments.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moddl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We do use any human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We do any human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "ZlShvXe17i", "reviewer": "Reviewer_GGkj", "summary": "The paper proposes a new framework called Multi-Stage Predict+Optimize for tackling optimization problems with parameters revealed in multiple stages, rather than simultaneously. The authors develop three training algorithms for neural networks within this framework, particularly for mixed integer linear programs (MILPs). These algorithms include a baseline extension of prior work and two novel algorithms leveraging sequential and parallel coordinate descent methods. The paper demonstrates the efficacy of these methods through experiments on three benchmarks, showing superior learning performance over classical approaches.", "questions": "Please see the weakness. As I am unfamiliar with this topic, I am unsure of my judgment and may need to discuss it with other reviewers.", "limitations": "NA", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces the Multi-Stage Predict+Optimize framework, which extends traditional two-stage optimization methods to handle parameters revealed in multiple stages. This approach addresses a more realistic scenario in many real-world problems where information becomes available progressively.\n\n2. The paper provides a detailed and rigorous development of the proposed methods. The theoretical foundations are well-explained, and the algorithms are clearly described, ensuring that the approach is both sound and replicable.\n\n3. The experiments conducted on three benchmark problems demonstrate the effectiveness of the proposed methods. The results are presented in a clear and structured manner, highlighting the strengths of the Multi-Stage Predict+Optimize approach compared to classical techniques.", "weaknesses": "1. The proposed Multi-Stage Predict+Optimize framework, while an extension of existing two-stage methods, may not significantly differentiate itself from prior frameworks in practical applications. The core idea of updating parameter predictions and decisions in multiple stages is not sufficiently innovative compared to existing work in multi-stage stochastic optimization. To improve, the authors could more clearly highlight unique aspects and potential new applications of their framework that are not covered by existing methods.\n\n2. Some sections of the paper, particularly those explaining the algorithms and theoretical foundations, may be dense and challenging for readers not deeply familiar with the subject. This can hinder the accessibility and broader understanding of the proposed methods. Simplifying the explanations and including more intuitive examples or visual aids can make the paper more accessible to a wider audience.\n\n3. The benchmarks used for experimentation, while useful, may not fully represent the diversity of real-world applications. Additionally, the performance metrics and evaluation scenarios could be more comprehensive to cover various practical constraints and conditions. Expanding the experimental evaluation to include a wider variety of benchmarks and more complex real-world scenarios would strengthen the paper's claims.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**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.\n\n**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.\n\nThe 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.\n\nThe 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.\n\nBy 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.\nOnce 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.\n\nIn summary, the two frameworks are in fact very different technically, even though they look similar on the surface.\n\n**Benchmarks**: Please see the overall response.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AyyWIgHUw4", "reviewer": "Reviewer_aupq", "summary": "The authors present an approach for learning hidden parameters for multi-stage optimization problems where parameters are gradually revealed at each stage. In this setting, latent parameters are predicted, then soft committed decisions are made based on those predictions, that stage’s parameters are revealed, and the practitioner can modify the soft committed solution to a hard committed solution for a penalty. Once that hard committed solution is fixed, the next stage begins with new predictions. After all stages are done, the post hoc regret is determined by the difference between the quality of decisions made and the optimal hindsight sequence of decisions, minus incurred solution modification penalties.\n\nThe goal is to train models that predict the next time step’s parameters, such that the overall regret is minimized. To solve this problem, the authors propose generalizing previous work on end-to-end training for the same post hoc regret developed for two stage problems. Here, the authors consider unrolling the multiple stages and propose three methods of training: baseline, coordinate descent, and parallel coordinate descent. The baseline approach considers the same model to be predicting at each stage. The other two approaches consider training independent networks for the different stages. Coordinate descent trains each network individually by fixing the other network weights and caching intermediate solutions if they don’t need to be recomputed. Parallel coordinate descent trains the different networks in parallel disregarding that the gradients for a given network may not be representative of the gradients obtained given the state of the other models.\n\nThe authors run experiments on three synthetic domains motivated by real world problems and show that their approaches outperform optimization-agnostic learning methods.", "questions": "1. Do the networks at stage t take in as input the revealed parameters from stage t-1 in addition to the features? Are those already considered as features? Are the standard baselines in BAS also given the previous step information as input?", "limitations": "The limitations are adequately addressed", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1 The authors tackle an interesting problem in multi-stage contextual optimization, generalizing previous work on two stages to multiple stages\n\n2 The authors present three approaches for training the predictive model, varying what model is considered and which network weights are frozen, with various tradeoffs in performance and training time\n\n3 the authors evaluate performance on three domains motivated by real world problems with nontrivial optimization formulations showing improved performance over standard optimization-agnostic approaches", "weaknesses": "1 the problem settings while well motivated are synthetic and seem to be pulling data from sources that are quite unrelated to the problem domain. For instance, the ICON challenge used for nurse scheduling represents energy data. Additionally, it is unclear what the knapsack data is supposed to represent and why it would be relevant for the oil shipment or investment settings. For the investment settings in particular, previous work [1,2,3,4] has used real world public stock data to evaluate performance. Given that the contribution is mostly empirical, it would be helpful to demonstrate performance on real-world settings with relevant data.\n\n2 The approaches themselves are somewhat incremental considering previous work. Mainly, the approaches consider unrolling the two-stage approach considered in previous work.\n\n4 It is unclear how substantial the performance improvements are given that the variability is quite large and induce overlapping confidence intervals. It might be helpful to give win rate results to determine how often a given approach is the top-performing approach.\n\n5 It is unclear why a coordinate descent approach is needed. Would it be possible to train all networks for all timesteps simultaneously? It would help to better motivate the necessity of coordinate descent by comparing against a simultaneous training approach.\n\nMinor comments\n\nFormal framework definition - it would be good to keep the revealed (and predicted) indices consistent. The off-by-one indices appear to be frequently mixed up. For instance, line 142, true parameters theta1,…, theta t-1 are revealed but then line 144 - theta t is revealed. Additionally, soft solutions \\hat{x} seem to start at 0 but are indexed from 1 to t-1 in line 152. It is fairly clear from the writing what the terms are supposed to represent, but making things more cohesive would improve the paper.\n\nAdditionally, in regards to notation it might be helpful to disambiguate the hard vs soft commitments with different variables, since it seems that \\hat{x} is considered as both a soft and hard committed solution which gets “overwritten”. Mainly, this just changes that the problem in 152 refers to \\hat{x} as a soft solution in the objective but hard solutions in the constraints.\n\n[1] Wang, Kai, et al. \"Automatically learning compact quality-aware surrogates for optimization problems.\" Advances in Neural Information Processing Systems 33 (2020): 9586-9596.\n\n[2] Ferber, Aaron, et al. \"Mipaal: Mixed integer program as a layer.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 02. 2020.\n\n[3] Shah, Sanket, et al. \"Decision-focused learning without decision-making: Learning locally optimized decision losses.\" Advances in Neural Information Processing Systems 35 (2022): 1320-1332.\n\n[4] Zharmagambetov, Arman, et al. \"Landscape surrogate: Learning decision losses for mathematical optimization under partial information.\" Advances in Neural Information Processing Systems 36 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review of our work. We respond to your concerns below.\n\n**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.\nWe will explicitly state this in the revised paper.\n\n**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.\n\n**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).\nWin rates can be directly computed from these plots by counting the number of simulations with ratios > 1.\nHere we present the win rate tables, showing that our methods outperform BAS in most simulations.\n\nWin rates for the production and sales problem.\n|Price group|Stage num|Baseline beats BAS|SCD beats BAS|PCD beats BAS|BAS is best|Baseline is best|SCD is best|PCD is best|\n|:-------------:|:---------:|:--------------------:|:-------------:|:-------------:|:-----------:|:----------------:|:-----------:|:-----------:|\n|Low-profit|4|93.33%|96.67%|86.67%|0.00%|3.33%|50.00%|46.67%|\n||12|73.33%|100.00%|90.00%|0.00%|0.00%|66.67%|33.33%|\n|High-profit|4|66.67%|96.67%|73.33%|0.00%|23.33%|50.00%|26.67%|\n||12|76.67%|100.00%|80.00%|0.00%|0.00%|63.33%|36.67%|\n\nWin rates for the 0-1 knapsack problem.\n|Capital|Stage_num|Trans_fee|Baseline beats BAS|SCD beats BAS|PCD beats BAS|BAS is best|Baseline is best|SCD is best|PCD is best|\n|:-------:|:---------:|:---------:|:--------------------:|:-------------:|:-------------:|:-----------:|:----------------:|:-----------:|:-----------:|\n|25|4|0.01|53.33%|86.67%|73.33%|3.33%|30.00%|46.67%|20.00%|\n|||0.1|70.00%|93.33%|90.00%|0.00%|33.33%|46.67%|20.00%|\n||12|0.01|66.67%|93.33%|83.33%|0.00%|3.33%|73.33%|23.33%|\n|||0.1|83.33%|100.00%|96.67%|0.00%|0.00%|86.67%|13.33%|\n|50|4|0.01|60.00%|80.00%|66.67%|3.33%|23.33%|43.33%|30.00%|\n|||0.1|70.00%|96.67%|90.00%|0.00%|26.67%|43.33%|30.00%|\n||12|0.01|70.00%|83.33%|83.33%|3.33%|0.00%|80.00%|16.67%|\n|||0.1|76.67%|100.00%|90.00%|0.00%|0.00%|93.33%|6.67%|\n\nWin rates for the nurse rostering problem.\n|Extra nurse payment|Baseline beats BAS|SCD beats BAS|PCD beats BAS|BAS is best |Baseline is best|SCD is best|PCD is best|PCD is best|\n|-----------------------|:--------------------:|:-------------:|:-------------:|:-----------:|:----------------:|:-----------:|:-----------:|:-----------:|\n|15|70.00%|70.00%|70.00%|10.00%|26.67%|40.00%|23.33%|46.67%|\n|20|73.33%|86.67%|80.00%|6.67%|10.00%|50.00%|33.33%|33.33%|\n|25|73.33%|96.67%|83.33%|3.33%|16.67%|43.33%|36.67%|26.67%|\n|30|73.33%|86.67%|76.67%|3.33%|6.67%|60.00%|30.00%|36.67%|\n\n**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.\nHowever, 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.\nWe did nonetheless explore this alternative training method before, with preliminary results, but the solution quality achieved was worse than the SCD and PCD methods.\n\nMean post-hoc regrets and standard deviations for different training methods in the production and sales problem.\n|Price group|Low-profit||High-profit||\n|:--------------------:|:-------------:|:-------------:|:-------------:|:-------------:|\n|Stage_num|4|12|4|12|\n|SCD|293.78±99.21|488.72±127.62|505.24±89.55|887.38±250.55|\n|PCD|297.34±107.44|495.21±122.42|520.76±92.20|905.61±255.99|\n|train_simultaneously|300.28±103.85|509.07±129.93|523.38±88.52|925.35±223.17|\n|Baseline|305.26±100.88|515.80±137.67|526.77±104.99|935.03±263.47|\n\nThe 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.\n\n**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.\n\nLine 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). \n\nLine 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).\n\n**Question**: Please see overall response.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qrLG5jmfB9", "reviewer": "Reviewer_Bz3V", "summary": "The paper proposes a Multi-Stage Predict+Optimize framework that addresses optimization problems where parameters are revealed in sequential stages. It introduces three neural network training algorithms tailored for mixed integer linear programs (MILPs) under this framework. The methodologies are empirically evaluated using three benchmarks, demonstrating enhanced predictive performance over classic methods.", "questions": "1. **Parameter Inclusion in Predictions**: Why aren't revealed parameters included in subsequent predictions? Would incorporating these parameters enhance prediction accuracy? I hope the author will share more of your thoughts on this with us.\n\n2. **Clarification on Terminology**: What does TOV stand for in the last columns of Tables 1 and 2? I could not find the full form of TOV in the main text.", "limitations": "1. **Applicability Concerns**: Despite listing applications like nurse scheduling, the practical applicability across diverse real-world scenarios remains uncertain. More concrete examples and a broader range of applications would strengthen the claims.\n\n2. **Innovativeness**: While the paper extends the two-stage predict+optimize framework to multi-stage, the core ideas closely resemble the existing models, which might diminish the perceived novelty.\n\n**Additional Note on Writing Corrections**:\n- Correct the notation for $\\hat{x}_0$ to $\\hat{x}^{(0)}$ where applicable in line 101.\n- Ensure consistency in table font sizes, especially noting that Table 3’s font size is noticeably smaller than that in Tables 1 and 2.\n\nThis is an interesting field, and if the authors can provide sufficiently detailed responses to the questions raised, I would be willing to consider revising my score.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. **Innovative Framework**: The proposed multi-stage framework is a significant extension of the existing two-stage predict+optimize models, effectively addressing scenarios where parameters are revealed progressively.\n2. **Robust Empirical Evaluation**: The paper provides a comprehensive experimental section that not only demonstrates the superiority of the proposed methods over traditional approaches but also discusses the trade-offs between them.", "weaknesses": "1. **Assumptions on Constraints**: The paper assumes that stage-wise optimizations are always feasible regardless of previous stages' outcomes and current parameter estimates. This assumption may not hold in practical scenarios, potentially limiting the framework's applicability.\n\n2. **Limited Benchmarks**: The choice of benchmarks does not include complex problems like the Alloy Production Problem or the 0-1 knapsack[1], which could benefit from a multi-stage approach. This omission raises questions about the framework's applicability to a broader range of problems.\n\n[1] X. Hu, J. C. H. Lee, and J. H. M. Lee. Two-Stage Predict+Optimize for mixed integer linear programs with unknown parameters in constraints. In Advances in Neural Information Processing Systems, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and your appreciation of the significance of our work. We address your concerns in this individual response.\n\n**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.\n\n**Benchmarks**: We want to point out that the benchmarks we consider are more complex than those in [1].\n \nThe 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.\n \nThe 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.\n\n**Parameter Inclusion in Predictions**: Please see overall response.\n\n**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.\n\n**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.\n\n**Innovativeness**: Please see our responses to Reviewers GGkj and aupq.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZBhkX2Bk1n", "reviewer": "Reviewer_fVWn", "summary": "This paper addresses optimization problems with parameter values unknown at solving time. Specifically, the work takes a supervised learning approach to predicting these parameters, which are revealed over multiple “stages.” The authors extend the Predict+Optimize framework, which uses an optimization-inspired loss function rather than typical mean squared error. This paper addresses multi-stage MILP problems, where unknown parameters of the optimization problem are revealed over several sequential stages. Three algorithms are proposed for training the prediction model, including the joint training of individual neural network predictors for each stage of the problem. Finally, experiments are conducted on three benchmark problems showing the advantage of the new framework over classical training methods.", "questions": "- Line 109: how common is the assumption that all the variables can be changed in Stage 1 (i.e., when does this occur)? This is what enables the guarantee of feasibility, unlike the hard commitments introduced later in the paper.\n- Line 157: likewise, what are the implications of the assumption that future decisions are always feasible given any choice of hard commitments? This should be discussed as a limitation.\n- Line 163: please check this. The two-stage framework in Section 2 includes no hard commitments.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The multi-stage framework is well motivated as an extension of Two-Stage Predict+Optimize, and the paper is well-written. The notation and presentation of the training methods is easy to follow.  \n- The authors perform extensive computational experiments, finding that the proposed coordinate descent training algorithms perform well in the benchmarks presented in the paper.\n- The trade-off between prediction accuracy and training times for the training algorithms is clearly shown.", "weaknesses": "- While this work is very interesting, the fit to this venue is questionable. Firstly, the value of this work to the ML community is unclear; it seems the main impact is in operations research. Secondly, many crucial aspects are moved to the appendices, e.g., all of the optimization problems and most of the computational results. For these reasons, perhaps a leading operations research journal would provide more space and be more appropriate.\n- While the integration of machine learning and optimization is an increasingly popular field, this paper does not reference many works. Adding references around using ML to help mixed-integer programming and especially stochastic programming, e.g., in Appendix A.3 or elsewhere, would better help readers place this work in the context. \n- The termination criteria for the algorithms in Algorithm 1 are omitted. They are also not discussed in Section 4.2-4.3, i.e., definition of convergence.\n- Training the neural networks for these problems requires differentiating through a MILP, which is approximated by differentiating its convex relaxation. The authors do not discuss the quality of this approximation, such as if the strength of the convex relaxation impacts the performance. Often, multiple MILP formulations are possible, with different convex relaxations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review of our work. We respond to your questions and comments below.\n\n**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.\n\n**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.\n\nSpecifically, 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.\n \nFurthermore, 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.\n\n\n**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.\n\n**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.\n\n**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.\n\n**Line 157, always-feasible assumption**: Please refer to our response to Reviewer Bz3V.\n\n[1] Jeong, Jihwan, et al. \"An exact symbolic reduction of linear smart predict+ optimize to mixed integer linear programming.\" ICML 2022.\n\n[2] Mandi, Jayanta, et al. \"Decision-focused learning: Through the lens of learning to rank.\" ICML 2022.\n\n[3] Hu, Xinyi, Jasper Lee, and Jimmy Lee. \"Two-Stage Predict+ Optimize for MILPs with Unknown Parameters in Constraints.\" NeurIPS 2023.\n\n[4] Donti, Priya, Brandon Amos, and J. Zico Kolter. \"Task-based end-to-end model learning in stochastic optimization.\" NeurIPS 2017.\n\n[5] Patel, Rahul Mihir, et al. \"Neur2SP: Neural two-stage stochastic programming.\" NeurIPS 2022.\n\n[6] Bae, Hyunglip, et al. \"Deep value function networks for large-scale multistage stochastic programs.\" AISTATS 2023.\n\n[7] Rychener, Yves, Daniel Kuhn, and Tobias Sutter. \"End-to-end learning for stochastic optimization: A bayesian perspective.\" ICML 2023.\n\n[8] Balcan, Maria-Florina, et al. \"Learning to branch.\" ICML 2018.\n\n[9] Gasse, Maxime, et al. \"Exact combinatorial optimization with graph convolutional neural networks.\" NeurIPS 2019.\n\n[10] Zarpellon, Giulia, et al. \"Parameterizing branch-and-bound search trees to learn branching policies.\" AAAI 2021.\n\n[11] Lange, Jan-Hendrik, and Paul Swoboda. \"Efficient message passing for 0–1 ILPs with binary decision diagrams.\" ICML 2021.\n\n[12] Lozano, Leonardo, David Bergman, and J. Cole Smith. \"On the consistent path problem.\" Operations Research, 68.6, 2020.\n\n[13] Song, Jialin, Yisong Yue, and Bistra Dilkina. \"A general large neighborhood search framework for solving integer linear programs.\" NeurIPS 2020.\n\n[14] Liu, Defeng, Matteo Fischetti, and Andrea Lodi. \"Learning to search in local branching.\" AAAI 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for the detailed, in-depth and constructive reviews. We are glad that reviewers recognize and appreciate that our work tackles an important problem, gives robust empirical evaluations, and that our paper is well-written.

In this overall response, we address some of the common reviewer concerns, and we also respond to individual comments in review-specific rebuttals. We hope to continue to engage with the reviewers in the author-reviewer discussion period -- we strongly believe in the value, importance and message of this work, and hope to convince you of the same.

**Benchmarks and datasets**: The benchmarks we used are more complex and sophisticated than the ones used by Hu et al.'s Two-Stage paper, not only due to the multi-stage nature, but also in other aspects of modelling (see our response to Reviewer Bz3V). In terms of datasets, we follow standard practice in the area that if we can't find directly relevant datasets, we use real datasets from an unrelated application domain in place. While one might reasonably question the choice somewhat, we point out that the Predict+Optimize field is very much still in its infancy, and our work is the *first* to propose a multi-stage framework in this supervised learning setting, also handling unknown parameters in constraints, which has been rarely studied in prior works. As such, for many application domains, there are simply no publicly available datasets suitable for evaluation in our problem setting (see our response to Reviewer aupq on why the cited stock market data is also unsuitable). We hope that our work, by contributing to the foundations of P+O, can serve as a "call to arms" along with prior works in the area, and encourage practitioners to start collecting/publishing data for other researchers to use for methodological research.

**Revealed parameters as a feature for later stage predictions**: In our current implementation, the network at stage $t$ in our proposed methods does not take the revealed parameters from stage $t-1$ as additional features as input, even though in principle we could write the framework to allow that. We did not include these revealed parameters because, in our preliminary experiments, including them does not really improve prediction quality while just increasing training time.
 
Here are the results from our preliminary experiments on the production and sales problem by incorporating the revealed parameters from stage $t-1$ as inputs to the stage $t$ networks:

Mean post-hoc regrets and standard deviations of training SCD with revealed parameters, training PCD with revealed parameters, SCD, PCD, and Baseline for the production and sales problem.
|     Price   group    |   Low-profit  |               |  High-profit  |               |
|:--------------------:|:-------------:|:-------------:|:-------------:|:-------------:|
|       Stage_num      |       4       |       12      |       4       |       12      |
| SCD_with_revealed_param    |  294.44±81.72 | 488.93±116.51 |  507.30±63.74 | 890.48±153.28 |
| PCD_with_revealed_param    |  299.73±82.91 | 498.32±123.25 |  521.82±74.86 | 911.04±185.57 |
|          SCD         |  293.78±99.21 | 488.72±127.62 |  505.24±89.55 | 887.38±250.55 |
|          PCD         | 297.34±107.44 | 495.21±122.42 |  520.76±92.20 | 905.61±255.99 |
|       Baseline       | 305.26±100.88 | 515.80±137.67 | 526.77±104.99 | 935.03±263.47 |
 
The table shows that the performance using this expanded input did not improve over the results of our proposed approaches. We will include these preliminary comparison results and discussion in the paper if accepted.

Meta-review: This paper considers the problem of learning unknown parameters for multi-stage optimization problems which are gradually known at each stage. The latent parameters are predicted to compute soft decisions; the stage's unknown parameters become known; practitioner can modify the soft decision to a hard decision for some penalty; and once the hard decision is fixed, the next stage begin. The post hoc regret is computed once all the stages are done. The overall goal is to train models to predict the latent parameters by minimizing the overall regret. The paper generalizes previous end-to-end training methods for two-stage problems. 

This is a borderline paper based on the reviews and discussion. One of the reviewer who gave a initial negative review could not participate in the discussion due to emergency situation (the author response seems to mostly address their critical comments). Here are strengths and weaknesses based on my reading and assessment. 

(++) Well-motivated new problem setting

(+) The proposed training approaches are reasonable but not particularly innovative

(-) The evaluation is on synthetic problems. It would have been nice to have at least one real-world problem to demonstrate the practical utility

I'm recommending accepting the paper with the hope that this new problem setting may inspire new research by both AI researchers and practitioners to expand the knowledge of decision-focused learning paradigm.
Decision: Accept (poster)