Two-Stage Predict+Optimize for MILPs with Unknown Parameters in Constraints
Authors: Xinyi HU
Jasper C.H. Lee
Jimmy H.M. Lee
Venue: NeurIPS 2023 poster (2023)
Keywords: Constraint optimization
Predict+Optimize

Abstract: Consider the setting of constrained optimization, with some parameters unknown at solving time and requiring prediction from relevant features. Predict+Optimize is a recent framework for end-to-end training supervised learning models for such predictions, incorporating information about the optimization problem in the training process in order to yield better predictions in terms of the quality of the predicted solution under the true parameters. Almost all prior works have focused on the special case where the unknowns appear only in the optimization objective and not the constraints. Hu et al. proposed the first adaptation of Predict+Optimize to handle unknowns appearing in constraints, but the framework has somewhat ad-hoc elements, and they provided a training algorithm only for covering and packing linear programs. In this work, we give a new simpler and more powerful framework called Two-Stage Predict+Optimize, which we believe should be the canonical framework for the Predict+Optimize setting. We also give a training algorithm usable for all mixed integer linear programs, vastly generalizing the applicability of the framework. Experimental results demonstrate the superior prediction performance of our training framework over all classical and state-of-the-art methods.

Two-Stage Predict-Optimize for Mixed Integer Linear Programs with Unknown Parameters in Constraints
Xinyi Hu', Jasper C.H. Lee", Jimmy H.M. Lee'
Department of Computer Science and Engineering
The Chinese University of Hong Kong, Shatin, N.T., Hong Kong
2 Department of Computer Sciences & Institute for Foundations of Data Science University of Wisconsin-Madises [xyhu,ilee| } wew..cchk.cec... edu..kk jasper.lee@wwi Sopper.le@wwiccedu
WI, USA
Abstract
Consider the setting of constrained optimization, with some parameters unknown at solving time and requiring prediction from relevant features. Predict+Optimize is a recent framework for end-to-end training supervised learning models for such predictions, incorporating information about the optimization problem in the training process in order to yield better predictions terms of the quality of the predicted solution under the true parameters. Almost all prior works have focused on the special case where the unknowns appear only in the optimization objective and not the constraints. Hu et al. proposed the first adaptation of Predict+Optimize to handle unknowns appearing in constraints, but the framework has somewha ad-hoc elements, and they provided training algorithm only for covering and packing linear programs. In this work, we give a new simpler and more powerful framework called Two-Stage Predict+Optimiie canonical framework for the Predict+Optimize setting. We also give a training algorithm usable for all mixed integer linear programs, vastly generalizing the applicability of the framework. Experimental results demonstrate the superior prediction performance of our training framework over all classical and state-of- the-art methods.
which we believe should be the
Introduction
Optimization problems are prevalent modern society, and yet the problem parameters are not always available at the time of solving, For example, consider the real-world application scenario of stocking store: as store managers, we need to place monthly orders for products to stock in the store. We want to stock products that sell fast and yield high profits, much of them as possible, subject to the hard constraint of limited storage space. However, orders need to placed two weeks in advance of the monthly delivery, and the customer demand next month cannot be known exactly at the time of order placement. In this paper, we consider the supervised learning setting, where be predicted from relevant features, and there sufficient historical
the unknown parameters (features, parameters) pairs as training data for a prediction model. The goal, then, is to learn a prediction model from the training data such that, if we plug in the estimated parameters into the optimization problem and solve for an estimated solution, the estimated solution remains a good solution even after the true parameters revealed.
The classic approach to the problem would be to train a simple regression model, based on standard losses such (regularized) l2 loss, to predict parameters from the features. It is shown, however, that having a small prediction error in the parameter space does not necessarily mean that the estimated solution performs well under the true parameters. The recent framework of Predict+Optimize, by
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Elmachtoub and Grigas 77), instead proposes the more effective regrer loss for training, which compares the solution qualities of the true optimal solution and the estimated solution under the have since appeared in the literature,
true parameters. Subsequent works [6 8 10 applying the framework to more and wider classes of optimization problems as well as focusing on speed-vs-predictin accuracy tradeoffs.
13
17
19 27
However, all these prior works focus only on the case where the unknown parameters appear in the optimization objective, and not in the constraints. The technical challenge for the generalization immediate: there were unknown parameters in the constraints, the estimated solution might not even be feasible under the true parameters revealed afterwards! Thus, in order to tackle the Predict+ Optiimze setting with unknowns in constraints, the recent work of Hu al. [22 presents the first such adaptation on the framework: they view the estimated solution as representing a soft commitment. Once the true parameters are revealed, corrective action can be taken to ensure feasibility, potentially at a penalty corresponding to the real-life cost of (partially) reneging on a soft commitment. Their framework captures application scenarios whenever such correction possible, and requires the practitioner to specify both the correction mechanism and the penalty function. These data can be determined and derived from the specific application scenario. As an example, in the product-stocking problem, additional unknown parameter is the storage space, because it depends on how the current products in the store sell before the new order arrives. We need to place orders know
two weeks ahead based on predicted storage space. The night before the order arrives, the precise available space, meaning that the unknown parameter is revealed. A possible correction mechanism then is to throw away excess products that the store cannot keep, while incurring the penalty that is the retail price of the products, as well as disposal fees.
While the Hu et al. 12 framework does capture many application scenarios, there are important shortcomings. In their framework, they require the practitioner to specify a correction function that amends infeasible solution into feasible solution. However, the derivation of correction function can be rather ad-hoc in nature. In particular, given an infeasible estimated solution, there may be many ways to transform the solution into feasible one, and yet their framework requires the practitioner to pick one particular way. This leads to the second downside: it is difficult to give a general algorithmic framework that applies to restrict their attention only to packing and covering linear programs, for which they could propose generic correction function. In this work, we aim to vastly generalize the kinds of optimization problems that Predict+Optimize can tackle under uncertainty in the constraints. In addition, the approach of Hu et al. fails to handle the interesting situation in which post-hoc correction is still desirable when the estimated solution is feasible but not good under the true parameters.
wide variety of optimization problems. Hu et al. had
Our contributions are three-fold:
To mitigate the shortcomings of the prior work, we propose and advocate a new framework. which we call Two-Stage Predict+ Optiimize that is both conceptually simpler and more expressive in terms of the class of optimization problems it can tackle. The key idea for the new framework is that the correction function is unnecessary. All that is required is penalty function that captures the cost of modifying one solution to another. A penalty function is sufficient for definnng a correction process: we formulate the correction process itself as "Stage 2" optimization problem, taking the originally estimated solution as well as the penalty function into account.
Under this framework, we further propose a general end-to-end training algorithm that applies not only to packing and covering linear programs, but also to all mixed integer linear programs (MILPs). We adapt the approach of Mandi and Guns [8] to give gradient method for training neural networks to predict parameters from features.
We apply the proposed method to three benchmarks to demonstrate the superior empirical perfor- mance over classical and oate-offthheart training methods.
2 Background
In this section, we give basic definitions for optimization problems and the Predict+Optimize setting 77. and describe the -tate-of-the-art framework [2] for Predict+Opimmie with unknown parameters
'The literature sometimes uses "two-stage" to mean approaches where the prediction is agnostic to the optimization problem. Here, "two-stage" refers to the soft commitment and the correction.

---

in constraints, The theory is stated in terms of minimization but applies of course also to maximization, upon uppropriate negation. Without loss of generality, an optimization problem (OP) can be defined as finding:
F arg min obj(z) s.t. C(x)
where x Rdd a vector of decision variables, obj IRd - is function mapping x to a real objective value that is to be minimized, and C is set of constraints that must be satisfied over z. We call x= an optimal solution and obj(x=) ) the optimal value. parameterized optimization problem (Para-OP) P(O) is extension of an OP P:
(0) arg min obj(2r, 0)
C(r, 0)
where 0 E IR' is a vector of parameters. The objective (bj 0) and constraints C(x, O) can both depend on 0. When the parameters are known, a Para-OP is just an OP.
In the Predict+ Optimize setting 771, the true parameters E I'' for a Para-OP are not known at solving time, and estimated parameters 0 are used instead. Suppose each parameter is estimated by m features. The estimation will rely on machine learning model trained over observations of training data set {(AA, , ).),... (A", 1,,,0 } where A' E R is a feature matrix for 0', in order to ......,(A,
yield prediction function f Rmm + R' predicting parameters 0 = f(A).
Solving the Para-OP using the estimated parameters, we obtain an estimated solution x² (0). When the unknown parameters appear in constraints, one major challenge is that the feasible region is only approximated at solving time, and hence the estimated solution may be infeasible under the true parameters. Fortunately, in certain applications, the estimated solution not a hard commitment, but only represents soft commitment that can be modified once the true parameters are revealed. Hu et al. 12 propose a Predict+Optimize framework for such applications. The framework is as follows: i) the unknown parameters are estimated as 0, and an estimated solution x (0) is solved using the estimated parameters, ii) the true parameters 0 are revealed, and if x (0) is infeasible under 6, it is amended into corrected solution (0, (0, 0) while potentially incurring some penalty, and finally iii) the solution Forre (0, 0) is evaluated according the of both the objective, under the true parameters 0, and the incurred penalty from correction.
More formally, a correction function takes an estimated solution x= =²) and true parameters 0 and returns a corrected solution (0,
(0, () that is feasible under 6. A penalty function Pen(x=(0) + Ftorr (Ó, 0)) takes an estimated solution x (0) and the corrected solution (0, (0, 0) and returns non- negative penalty. Both the correction function and the penalty function should be chosen according to the precise application scenario at hand. The final corrected solution (0, 0) is evaluated using the post-hoc regret, which is defined with respect to the corrected solution z'oor (6, 0) and the penalty function Pen(z" (z" (0) + (0,0)) The post-hoc regret is the sum of two terms: (a) the difference in objective between the true optimal solution x" (6) and the corrected solution 22orr (0, f) under the true parameters 8, and (b) the penalty that the correction process incurs. Mathematically, the post-hoc regret function P PReg(0,0) 0) TRC R' + Rzo (for minimization problems) is:
PReg Ô, 0) (1 (0.0), obj(>" (0),0) + Pen(æ" (0) - (0,
(1)
where obj(x tero 00,0),0 0),0) 0) is the corrected optimal value and obj (x* (0), is the true optimal value.
Given the post-hoc regret a loss function, the empirical risk minimization principle dictates that we choose the prediction function to be the function from the set of models J attaining the smallest average post-hoc regret over the training data:
1 7
12
fd arg min JEF
(R))
3 Two-stage Predict+Optimizz Framework
While the prior work by Hu et 12 is the first Predict#pptimize framework for unknowns in constraints, and is indeed applicable to good range of applications, it has several shortcomings.
3

---

First, the framework requires mathematically formalizing both penalty function and correction function from the application scenario, and essentially imposes differentiability assumptions on the correction function for the framework to be usable. The ad-hoc nature of writing down a correction function limits the practical applicability of the framework. Second, as a result of needing a single (differentiable) correction function, Hu et al. [12] needed to restrict their attention to only packing and covering linear programs, in order to derive a general correction function that is applicable to all the instances. This also significantly limits the immediate applicability of their framework. Third, their framework only corrects an estimated solution when it is infeasible under the true parameters. Yet, there are applications where corrections are possible even when the estimated solution were feasible, but just not very good under the true parameters.
In this paper, we advocate using simpler yet more powerful framework, which we call Two-Stage Predict+ Optimize, Predict+Optimize, addressing of the above shortcomings. The simplified perspective will allow us to discuss more easily how to handle the entire class of mixed integer linear programs (MILPs) instead of being restricted to just packing and covering linear programs. Since MILPs include all optimization problems in NP (under reasonable definition of NP for optimization problems), our framework is significantly more applicable in practice. We will describe the Two-Stage Predict+Optimize framework below, and discuss its application to MILPs in the next section.
Our framework is simple: we forgo the idea of a correction function and treat correction itself as an optimization problem, based on the penalty function, the estimated solution and the revealed true parameters. Recall the Hu et al. view of Predict+Optimize under uncertainties in constraints: the estimated solution is form of soft commitment, which can be modified at a cost once the true parameters are revealed. The penalty function describes the cost of changing from an estimated solution to a final solution. The main observation is that, given an estimated solution and the revealed parameters, we should in fact solve a new optimization problem, formed by applying the true parameters to the original optimization, and adding the penalty function to the objective. The final solution from this new optimization thus takes the penalty of correction into account. This approach yields three immediate advantages. First, the practitioner no longer needs to specify correction function, thus reducing the ad-hoc nature of the framework. Second, even feasible solutions are allowed to be modified after the true parameters Third, conditioned on the same penalty function, the solution quality from our two-stage optimization approach is always at least good that from using any correction function. The last advantage is presented as Proposition I
revealed if the penalty of doing so is not infinity.
Now we formally define the Two-Stage Predict+Optimize framework.
I. In Stage 1, the unknown parameters are estimated as 0 from features. The practitioner then solves the Stage 1 optimization, which is the Para-OP using the estimated parameters, obtain the Stage I solution z². The Stage 1 solution should be interpreted some form of soft commitment, that we get to modify Stage 2 at extra cost/penalty. Assuming the notation of the Para-OP in Section 2 the Stage 1 OP can be formulated as:
z = arg min (b) 0) s.t. C(x, 0)
II. At the beginning of Stage 2, the true parameters 0 are revealed. The Stage 2 optimization problem augments the original Stage problem by adding a penalty term Pen(x + zzz, 0) to the objective, which accounts for the penalty (modelled from the application scenario) for changing from the coftly-committer Stage solution of to the new Stage 2 and final solution z². The Stage OP can then be formulated as:
2 arg min obj(x, 0) + Pen(zī + x. 0) s.t. (xx,
Solving the Stage 2 problem yields the final Stage 2 "corrected" solution zzz
III. The Stage 2 solution z is evaluated according to the analogous post-hoe regret, as follows:
PReg(0, 0, 8) = obj 8) + Pen(æi - x²² 0) obj(x" ()).
where again, x= *0) is optimal solution of the Para-OP under the true parameters 6. Note that the post-hoc regret depends on all of a) the predicted parameters, b) the induced Stage solution, c) the true parameters and d) the final Stage 2 solution.
To see this new framework applies practice, the following example expands on the product-stocking problem in the introduction.

---

Example 1. Consider the product-stocken problem again, where regular orders have to be placed two weeks ahead of monthly deliveries. Since the available space at the time of delivery is unknown when we place the regular orders, depending a prediction on the available space to make a corresponding order. We learn the predictor using historical sales records from features such as time-of-year and price. Then, we use the predicted available space to optimize for the regular order we place. This is the Stage solution.
the sales over the next two weeks, we need to make
The night before the order arrives, the unknown constraint parameter, i.e. the precise available space, revealed. We can then check if we have over-ordered or under-orden ordered. the case of over- over-ondeinng we would have to call and ask the wholesale company to drop some items from the order. The company would perhaps allow taking the items off the final bill, but naturally they have a surcharge for fast-minute changes. Similarty. if we under-ordered. we might request the wholesale company to send us more products, again naturally with a surcharge for last-minute ordering. The updated order is the Stage 2 decision. The incurred wholesaler surcharges induce the penalty function.
A reader who is familiar with the literature on two-stage optimization problems may note that the above framework is phrased slightly differently from some other two-stage problem formulations. In particular, some two-stage frameworks phrase Stage 1 solutions as hard commitments, and include recourse variables in both stages of optimization to model what changes are made in Stage 2. We show in Appendix A how framework can capture this other perspective, and in general discuss how problem modelling can be done in our new framework.
The reader may also wonder: what about application scenarios where the (Stage 1) estimated solution a hard commitment, and there is absolutely no correction/recouree available? In Appendix A.2 we discuss how our framework is stil/ useful and applicable for learning in these situations.
We also give a more detailed comparison, in Appendix [A.3] between our new Two-Stage Pre- diet+Optimize framework and the prior Hu et al. framework. Technically, if we ignored differen- tiability issues, the two frameworks are mathematically equivalent in expressiveness. However, we stress that our new framework is both conceptually simpler and easier to apply to a far wider class of optimization problems. We show concretely in the next section how to end-to-end train a neural network for this framework for all MILPs, vastly generalizing the method of Hu et al. which is restricted to packing and covering (non-integer) linear programs. In addition, Appendix A..3 also states and proves Proposition I that if we fix an optimization problem, a prediction model and penalty function, then the solution quality from our two-stage approach is always at least as good as using the correction function approach.
4 Two-Stage Predict+ on MILPs
In this section, we describe how to give an end-to-end training method for neural networks predict unknown parameters from features, under the Two-Stage Predict+Optimize framework. The following algorithmic method is applicable whenever both stages of optimization are expressible as MILPs. Due to the page limit, the discussion in this section is high-level and brief, with all the calculation details deferred to Appendix B
The standard way to train a neural network is to use gradient-based method. In the Two-Stage Predict+Optimize framework, we use the post-hoc regret P PReg as the loss function. Therefore, for each edge weight w. in the neural network, we need to compute the derivative de Using the law of total derivative, get
dw.
dP dPReg((,0) OPReg(0,0) dw
0) i
dxy dxi ae @PReg(0,0) Oxi
da ab
(3)
dxi ob dw.
ab Dw.
22
As such, we wish to calculate each term on the right hand side.
ab The easiest term to handle is Dw. since 0 is the neural network output, and so the derivatives
can be directly calculated by standard backpropagation 25 As for the terms aPReg(0.9)
and
deg
@PReg(0.0) they are easily calculable whenever both the optimization objective and penalty d29 function are smooth, and in fact linear as in the case of MILPs. What remains are the terms
Ox
and
oz
5

---

Dzi The challenge is that x: is the solution of MILP optimization (Stage 2) that uses oj as its ad
parameters, i.e., differentiate through MILP. Similarly, zi depends on ô through MILP (Stage 1). Since MII.P optima may not change under minor parameter perturbations, the gradients can be either O or non-existent, which are uninformative. We thus need to compute some approximation in order to get useful training signals.
Our approach, inspired by the work of Mandi and Guns [8] is to define a new surrogate loss function PReg that is differentiable and produces informative gradients. Prior works related to learning unknowns in constraints [ 2 [77] give ways of differentiating through LPs or LPs with regularizations. These works can be used in place of the proposed approach. However, experiments in Appendix E demonstrate that the proposed approach performs at least as well in post-hoc regret performance as the others, while being faster. We show the construction of the proposed approach below, and note that it does not have simple closed form. Nonetheless, can compute its gradients.
The rest of the section assumes that both stages of optimization are expressible as MILP in the following standard form:
arg min Ta s.t. Ax = b, Ga 2 h, x 2 0, ag E
with decision variables Rd and problem parameters c E Rd, A Roxd, be E RD, E Rexd E R2, The subset of indices S denotes the set of variables that are under integrality constraints. Since the unknown parameters may appear in any combination of c, A, G and h in the Stage I optimization for zj. the surrogate loss function construction needs computable and informative
gradients for all of Ox" Oz" Ox' Oz'
de aA 8b aG and Ox"
8h
We follow the interior-point based approach of Mandi and Guns [18], used also by Hu al. [12]
Consider the following convex relaxation of (4), for a fixed value of μ 2 O:
arg min TT x 1b > In(x;) 1 Σ In(s)) S.t. Ar b, Ga - 8 s=
(5)
This is a relaxation of (4) by i) dropping all integrality constraints, ii) introducing slack variables 2 0 turn Gx 2 h into Gr with the logarithm barrier terms in the objective, with multiplier 2 0. The observation is that the dr Oz Or Øz gradients 0e* 9A 06 + aG and dr for (5) are all well-defined, computable and informative for a fixed ah
h and iii) replacing both the x 2 0 and s 2 constraints
value of μ #2 0: Slater's condition holds for (5). and so the KKT conditions must be satisfied the optimum (x* s²) of (5). We can thus compute all the relevant gradients via differentiating the KKT conditions, using the implicit function theorem. We give all the calculation details in Appendix B
Given the above observation, we then aim to construct the surrogate loss function by replacing the zt and z²z which are supposed to solved using MILP { with a) ž1 that is solved from program (5) relaxation of the Stage 1 optimization problem, using the predicted parameters Ô and b) TP that is solved from the program (5) relaxed version of Stage optimization, using J1 and the true parameters 0. The only remaining question then, is. which values of μ do we use for the two relaxed problems?
Given a MILP in the form of 4.. the interior- point based solver of Mandi and Guns [8] generates and solves 5 for sequence of decreasing non-negative μ., with termination condition that μ cannot be smaller than some cutoff value. Thus, we simply choose the cutoff value to use as "v" in (5).
which then completes the definition of the surrogate loss PReg.
Algorithmically, we train the neural network on the surrogate loss PReg as follows: given predicted parameters, we the Mandi and Guns solver to get the optimal solution (x", s'") for the final value of μ.. We can then compute the gradient of the output solution with respect to any of the problem
parameters using the calculations in Appendix B combined with backpropagation, to yield de dw.
according to Equation
In Appendix C we give three example application scenarios, along with their penalty functions, that our training approach can handle. These problems are: a) an alloy production problem, for factory trying to source ores under uncertainty in chemical compositions in the raw materials, b) variant of the classic 0-1 knapsack with unknown weights and rewards, and c) a nurse roster scheduling problem with unknown patient load. We show explicitly in Appendix C how both stages of optimization

---

Table 1: Relevant problem sizes of the three benchmarks.
Problem nume
Brass alloy production
Tianiuu- alloy production
Knapsack
Nurse scheduling problem
Dimension
Number of constraints
12
14
21
846
Number of unknown parameiers
40
Namber of features (por parameter)
4096
4096
4096
can be formulated as MILPs for these applications, and apply the Appendix calculations to yield gradient computation formulas for the surrogate loss P PReg for these problems.
A limitation of our approach is the requirement that both stages must be expressible as MILPs, constraining the optimization objectives be linear in the MILP decision variables. This contrasts the Hu et al. framework [2] which handles non-linear penalties. We point out that even MILPs can handle some non-linearity by using extra decision variables: for example, the absolute-valuc function. Moreover, the Appendix B gradient calculations can be adapted to handle general differentiable non-linear objectives. We present only MILPs as main overarching application for this paper because of their widespread use in discrete optimization, with readily available solvers.
5 Experimental Evaluation
We evaluate the proposed method on three benchmarks described in Section and Appendix C Table reports the relevant benchmark problem sizes. We compare our method (2S) with the state of the art Predict+Optimize method, IntOpt-C (12). and 5 classical regression methods M ridge regression (Ridge), k-nearest neighbors (k-NN), classification and regression tree (CART), random forest (RF), and neural network (NN). All of these methods use their classic loss function to train the prediction models. At test time, to ensure the feasibility of the solutions when computing the post-hoc regret, we perform Stage 2 optimization on the estimated solutions for these classical regression methods before evaluating the final solution. Additionally. CombOptNet [4] is differrnnt method focusing on learning unknowns in constraints, but with a different goal and loss function. We experimentally compare our proposed method with CombOptNet on the 0-1 knapsack benchmark the only with available CombOptNet code. We also present a qualitative comparison in Section
In the following experiments, we will need to take care to distinguish two-stage optimization training technique (Section 4) and as an evaluation framework (Section 3). We will denote our training method as "2S" in the experiments, and when we say "Two-Stage Predict+Optinin we always mean as an evaluation framework. 2S is always evaluated according to the Two-Stage Predict+Optimize framework. As explained above, will also evaluate all the classical training methods using the Staget Predict+Optimize framework. For our comparison with the prior work of Hu et al. [12), will also distinguish their training method and evaluation framework. The name "IntOpt-C" always refers to their training method using their correction function. We will simply call their evaluation framework the "Hu et al. framework" or with similar phrasing (see Section 2 to recall details). IntOpt-C will sometimes be evaluated using our new Two-Stage Predict+Optimize framework, and sometimes the prior framework of Hu et al. [12] using their correction function.
framework,
The methods of k-NN, RF, NN, and IntOpt-C as well as 2S have hyperparameters, which we tune via cross coossvalidation We include the hyperparameter types and chosen values in Appendix D In the main paper we only report the prediction performances. See Appendix H for runtime comparisons.
Alloy Production Problem The alloy production problem is covering LP, see Appendix C.I for the practical motivation and LP model. Since Hu et al. [12] also experimented on this problem, we use it to compare our 2S method with IntOpt-C [12, using the same dataset and experimental setting.
We conduct experiments on the production of two real alloys: brass and an alloy blend for strength- ening Titanium. For brass, 2 kinds of metal materials, Cu and Zn. are required (14) The blend of
alloy, 4 kinds of metal materials, C, AI, V. and Fe, are required [15] The blend of the four materials are proportional to req [0.8, 60, 40, 2.5). We use the same real data as that used in IntOpt-C [22 as numerical values in our experiment instances. In this dataset 23 each unknown metal concentration
the two materials are, proportionally, reg- = [627.54, 777,544,.777 369.72). For the Sraniuum-strengtheme
Our implementation is available at http:://gghbb.oomm///ieeeettst/s
Swo__ttaee_ Predict-Optimize

---

Table 2: Comparison of the Two-Stage Predict+Optimize framework and the Hu et al. framework on the alloy production problem.
Phig
Pan-Stage Pretict #Oplimiee Francwook
Hu
Alloy
Panally Eactor
Frunswookk
0:25.0.015
48.87
66. 16m6, 26
0.540.015
68.71
82.91-5545
Bross
2
1e0,015
123.90:6.84
88.75+5.00 91
150 150.67=12.99
107 (17.54466.33
460.015
161 8648-49
17%, 69.00.00.0
$.0.015
194/66 13,09
206 84-12.51
0225g00013
4.52230.47
6.4529781
0.560.115
6.83291.22
7. 7.90g0.35 56
Tlaaium alloy
280.015
Le0,015
12.17a1.24
8,58g0.74
10.73:0.81 81
14.17=1.3)
4e0.015
16.10s11000
17.48-0.90 90
$+0.015
19.69-8.91
21.06-1.91
Table 3: Mean post-hoc regrets and standard deviations for the alloy production problem using the Two-Stage Predict+Optimize framework.
Allay
FRaz
Pemalty Batter
28
IntOpe C
Ridge
A-NN
CART
RF
NN
TOV
B:33500115
41.872273
45.2763.35
M12012.55
61.1244 T9
17,8006 V7
64:661355
0.5eCLO15
65.71=4.81
67 49+425
71:12+348
74.36+5.0)
98.67-7.01
70.36+3.20
74 14.92+2.50
BeIsa
2:0.015
1:0.015
123.90a6.84
88.75s5.99 91
125 16196619.20
89 59.8314779
(33,184122 2.98
01.8215.41
16.77211602
96.5218.90
189, 12..
125. 5049 49
131 12 2.48
90.9716. 14
13066210052
03.12:4:24
312,02+6 94
4110.015
.6..898
164.94:10.33
21507422655
229.22430.74
316.31
40125
205 763.76224.33 33
810.015
191,06:13,09
200-4248.51
304330553375
406.19250.42
570,75.61442
372.01
355 263.9555222
0:25200015
6.03:6.62
7.7120.45
7,27.0.01
6.7660.55
7.38:0.67
alloy
12.17=1.24
8.58=88.4
12.31+1.31
15:3741.08
10.26411222
14.11:084
9.55e0.52
17.57
11.57H0.52
12.7841.11
8.70
12.38a1
30.27=0.54
16.10:1.06
16.92+1.70
25.60+1
23.24ml1
18.05e2000
8+0.015
19.69=0.91
20.80el.74
46.0443.55
41.49=3.05
53.57e3.10
36.8833.6
related 4096 features. For experiments both alloys, 350 instances used for training and 150 instances for testing the model performance. For NN, IntOpt-C,, and 2S, we use a 5-layer fully connected network with 512 neurons per hidden layer.
In the penalty function described in Appendix C.I we need to choose a penalty factor//mlltiplier for each supplier. We conduct experiments on 6 types of penalty factor (a) settings: 6 vectors where each entry is i.i.d. uniformly sampled from [0.25 + 0.015], 0 = 0.015), [2.0 0.015), [4.0 + 0.015), and [8.0 + 0.015) respectively. This random sampling of ensures that the penalty factor for each supplier is different, but remains roughly on the same scale.
The first experiment we run compares See-Tw--Stag Predict+Optimize framework with IntOpt-C+Hi C-u et al. framework. Specifically, we compare a) using 2S for training and evaluating using the Two-Stage Predict+Optimize framework in Section 3 versus b) using IntOpt-C for training and evaluating using the same correction function from training, according to the Hu et al. framework described Section 2 Table compares the mean post-hoe regret and standard deviations for the alloy production problem for the two different frameworks. The table shows that wwo-Stage Predict+Optimize framework always achieves smaller mean post-hoc regret than the Hu et al. framework. Compared with the Hu et al. framework, our framework obtains 6. 5.18%%355 55.63% smaller mean post-hoc regret brass production, and 6.59% 55.9-99.%%% smaller mean post-hoc regret in titanium-alloy production.
We present further comparison in Appendix F with variant of the Hu et al. framework the l2 projection idea in 13. which performs even worse than the Hu et al. framework.
The second experiment compares various training approaches all evaluated under the Two-Stage Predict-Optimize framework. That is, the models are trained differently, but at test time, we always use Stage 2 optimization give final solution and evaluate post-hoc regret on it. Table reports the mean post-hoc regrets and standard deviations across 10 runs for each training method on the alloy production problem. The table shows that our method, 2S, achieves the best performance, compared with IntOpt-C achieving the second best performance, beating all the classical training approaches. Compared with IntOpt-C, 2S obtains 1.20%-3.18% smaller mean post-hoe regrets in brass production, and 1.18%-5.334 93.33% smaller mean post-hoc regret in titanium-alle classical approaches, the improvements are much more significant. 2S obtains at least 2.44%-45.448 smaller mean post-hoc regrets in brass production, and at least 1.39%-38.785 smaller mean post-hoc regret in titanium-alloy production. The average True Optimal Values (TOV) are reported in the last column of Table 3 for reference, although the reader should take care to not over-interpret the ratio
production. Compared with the
8

---

Table 4: Mean post-hoc regrets and standard deviations for 0-1 knapsack problem using the Two-Stage Predict+Opimize framework.
Penaliy factor
PReg
25
CombOptNet
Ridge
K-NN
CART
RF
NN
TOV
0.21
1.610.01
9,4520.19
9.4620.19
9.38g0.11
8.6750.13
9.50200.26
9.8120
0.25
6.28+0005
9.60=0.22
9.77+0.19
9.70=0.10 19
9.19-0.12
9.82+0.27
10.11140.00
29.68=0.14
0.3
9.22:0.10
10.45:0.344 34
10.16:0.19
10.1020.10 18
9.85=0.11
10.23:0.28
10.49:0.21
0.21
0.73+0.01
8.90-8.97
9.12+0.22
8:91-0.20
8.46-0.18
9.20+0.27
9.6640.47
150
0.25
3.64:0.04
9.11:9.41
9.4020.21
9.19:0.20
8.88:0.17
9,4720.26
9,92:0045
40.23a0.19
0.3
7.27:0.06
9,34g9.38
9.7620.22
9.53=0.11
9.41=0.17
9.81=0.24
10.23:0.30 0338
0.33:10.1
15.
6.5710.21
6.3820.29
6.26210.21
6.5920.23
7.08:00. 9.5
200
0.25
1.67:0.03
15.20=0.22
6. 6.80200200
6,62=0,20 29
6.57=0.19
6.82=0.21
7.2740.88
48. 48.13
0.3
3.33+0006
15.25:0.:22
7.09
6.9120.28
6.9520.19
7.1024018
7.5240.80
0,07:0.00
20:42:0:25
2.3930.22
2.18:0.20
2.4520.20
2.34200:32
2.70z1
250
0.25
0.34+0.02
20.47a0.13
2.53g0.21
2.34
2.60=0.19
2.4920.30
2.82&1.26
53.4340.26
0.3
0.69:0.04
20.5440.33
2,71+0,200
2.54=0.18
2.79=0.18
2.67=0.28
2,97+1.16
Table 5: Mean post-hoc regrets and standard deviations for the NSP using the Two-Stage Pre- dict+Optimize framework.
Penalty factor
Ridge
L-NN
CART
NN
TOV
0.25=50815
3.94+1.91
6.45 68
15.20=5.76
26 2018 96
19.47=7.19
4.2762.22
0,5+0.01
6.92=2.26
12.68-9.33
30.29-11.55
$2.47+17.9
38.93-14.22
8.2014444
2.0.0.155
1.000015
25.0419.29
13.12+3.15
15.12-18.71
49.95.37.339
120.62e46.08
60.43=23.07
210.02472.06
005.01436.00
155.64258.06
77,86+28.99
31.51+17.40
16.00=8.78
190.21426.17
4,8+0011
33,2949.53
99.61=74.78
241.01+92,14
420 044144444 18
311.19-116.23
62,52+34 64
8.0+00155
46.72s14.80
198.91#149.54
481.79e184.27
840. 10+288.44
622.32+252.56
124.54x60.14
between the post-hoc regret and the true optimal value, since the post-hoc regret also includes the penalty term which increases with the penalty factors.
0-1 knapsack In the second example, we showcase our framework on a packing integer program- ming problem, variant of the 0-1 knapsack problem, with unknown item prices p; and sizes st. See Appendix C.2 for details of an application in running "proxy buyer" business. Here, the unknown parameters appear in both the objective and constraints. The proposed 2S method can handle this MILP straightforwarddy, but the IntOpt-C method cannot be applied. Thus, we only experiment with the Two-Stage Predict+Optimize framework for evaluation, and compare the proposed 2S method with classical approaches and CombOptNet. Again, all approaches are evaluated at test time using the Stage 2 optimization to yield the final solution, on which the post-hoe regret is computed.
The MILP formulation of the two stages and the penalty function are described in Appendix C.2 We use the dataset of Paulus et al. [23]. in which each 0-1 knapsack instance consists of 10 items and each item has 4096 features related to its price and size. For both NN and our method, we use a 5-layer fully-connected network with 512 neurons per hidden layer. We conduct experiments different knapsack capacities: 100, 150, 200, and 250. We use 700 instances for training and 300 instances for testing the model performance. Considering the real- setting, use 3 scales of the penalty factor for the penalty function in Appendix C.2 σ 0.05, 0.25, or 0.5.
4
Table 4 reports the mean post-hoc regrets and standard deviations across 10 runs for each approach on this 0-1 knapsack problem. Due to the space limitation and the fact that larger penalty factors unrealistic in this problem setting, present penalty factors > 1 in Appendix G The average True Optimal Values (TOV) are reported in the last column, again for reference. As shown in the table, our proposed 2S method has significantly better results. In addition, we observe that across all approaches, the post-hoe regrets decrease as the knapsack capacity increases: this is due to the fact that as the capacity increases, more and more items can be selected, and minor inaceuracies in predicted values/weights do not affect the selected set of items as much. On the other hand, the advantage of our 28 method over other approaches actually becomes more significant as the capacity increases, demonstrating the superior accuracy of our approach.
Nurse Scheduling Problem Our last experiment is on the nurse scheduling problem (NSP) with
unknown patients needs, with the goal of scheduling a nurse roster satisfying unknown patient load demands while minimizing mismatched nurse-shift preferences the objective. See Appendix C.3 for a description of the application scenario, the MILP formulations of the two stages, as well as the associated penalty function. Given that NSP is not an LP, IntOpt-C again does not apply, and

---

only compare the proposed 2S training method with the classical approaches, using the Two-Stage Predict+Optimize framework for evaluation. Each NSP instance consists of 15 nurses, 7 days, and shifts per day. The nurse preferences are obtained from the NSPLib dataset (26). which is widely used for NSP [66] 20] The number of patients that each nurse can serve in one shift is randomly generated from [10,20], representing the fact that each nurse has different capabilities. Given that we are unable to find datasets specifically for the patient load demands and relevant prediction features, we follow the experimental approach of Demirovic et al. 4 5 6 and use real data from different problem (the ICON scheduling competition) as the numerical values required for our experiment instances. In this dataset, the unknown number of patients per shift is predicted by 8 features.
Since there are far fewer features than the previous experiments. for both NN and 2S we use a smaller network structure: 4-layer connecco network with 16 neurons per hidden layer. We use 210 instances for training and 90 instances for testing. Just like the first experiment, we use scales of penalty factors (see Appendix C.3 for the penalty function): with i.i.d. entries drawn uniformly from [0.25 + 0.015), [0.5 + 0.015). [1.0 + 0.015), [2.0 + 0.015), [4.0 0.015), and [8.0 + 0.015].
Table T reports the mean post-hoe regrets and standard deviations across 10 runs for each approach on the NSP. The table shows that the proposed 2S method again has the best performance among all the training approaches. Our 2S method obtains at least 7.61%, 6,1, 15.65%, 17.99%, 20.51 %, 46. 76%, and 62.49% smaller post-hoc regret than other classical methods when the penalty factor is [0. 0.015,, [0.5 00.01),, 0.055) 0.015), 0.015) and =.0050005) respectively.
Runtime Analysis Appendix ErpendxxHliiver gives the training times for each method. Most classical approaches faster than our 2S method, although as shown their post-hoc regrets are much worse. In alloy production, the only setting where IntOpt-C applies, its running time is shorter but comparable with 2S. In 0-1 knapsack, the only problem with public CombOptNet code, the 2S method is much faster.
Literature Review
Section aalread summarized prior works in Predict+Optimize, most of which focus on learning unknowns only in the objective. Only the Hu et al. [12] framework considers unknowns in constraints.
Here we summarize other works related to learning unknowns in optimization problem constraints, particularly those outside of Predict+Optimize. These works can be placed into two categories.
One category also considers learning unknowns in constraints, but with very different goals and mea- sures of loss. For example, CombOptNet (23] and Nandwani et al. [2] focus on learning parameters so to make the predicted optimal solution (first-stage solution in our proposed framework) as close to the true optimal solution x: as possible in the solution space/metric. By contrast, our proposed framework explicitly formulates the two-stage framework and post-hoc regret in order directly capture rewards and costs in application scenarios. Experiments on 0-1 knapsack in Section shoo that these other methods yield worse predictive performance when evaluated the post-hoe regret, under the proposed two-stage framework.
Another category gives ways to differentiate through LPs or LPs with regularizations, technical component in a gradient-based training algorithm. As mentioned in Section 4 these works can indeed be used in place of our proposed approach in Section 4Appendix However, we point out that: (i) these other technical tools are essentially orthogonal to our primary contribution, which is the two-stage framework (Section 3). and (ii) nonetheless, experiments on the 0-1 knapsack in Appendix
[ demonstrate that our gradient calculation approach performs at least as well in post-hoc regret performance as other works, while being faster.
Summary
We proposed Two-Stage Predict+Optimie:: a new, conceptually simpler and more powerful framework for the Predict+Optiiize setting where unknown parameters can appear both in the objective and in constraints. We showed how the simpler perspective offered by the framework allows us to give a general training framework for all MILPs, contrasting prior work which apply only to covering and packing L.ss. Experimental results demonstrate that our training method offers significantly better prediction performance over other classical and state-of-the-ar approaches.
10

---

Acknowledgments
We thank the anonymous referees 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 University Grants Committee, Hong Kong. Jasper C.H. Lee was supported in part by the generous funding of Croucher Fellowship for Postdoctoral Research, NSF award DMS-2023239, NSF Medium Award CCF-2107079 and NSF AiTF Award CCF-2006206.
References
[1] A. Agrawal, B. Amos, S. Barratt, S. Boyd, S. 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 145-145. PMLR, 2017.
[3] B. Chen, L. Donti, K. Baker, 7., Kolter, and M. Bergés. Enforeing policy feasibility constraints through differentiable projection for energy optimization. In Proceedings of the Twelfth ACM International Conference on Future Energy Systems, pages 199-210, 2021.
[4] E. Demirović, P. J. Stuckey, J. Bailey, J. Chan, C. Leckie, K. Ramamohanarao, and T. Guns. An investigation into PeddictionOOpiimisatoon for the knapsack problem. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 241-257. Springer, 2019.
[5] E. Demirović, P. J. Stuckey, J. Bailey, J. Chan, C. Leckie, K. Ramamohanarao, and T. Guns. Predict+Optimise with ranking objectives: Exhaustively learning linear functions. Proceedings of the Twenty-Eightn International Joint Conference on Artificial Intelligence, pages 1078-1085, 2019.
[6] E. Demirović, P. J. Stuckey, T. Guns, J. Bailey, C. Leckie, K. Ramamohanarao, and J. Chan. Dynamic programming for Predict+Optimise. In Proceedings of the Fourth AAAI Conference Artificial Intelligence, pages 1444-1451, 2020.
[7] A. N. Elmachtoub and P. Grigas. Smart "Predict, then Optimize". Management Science, 68(1):9-22 260 2022.
[8] A. N. Elmachtoub, J. C. N. Liang, and R. McNellis. Decision trees for decision decision-making under the predict-then-optinie framework. In Proceedings of the 37th International Conference Machine Learning, pages 2858-2867, 2020.
[9] J. Friedman, T. Hastie, and R. Tibshirani. The elements of statistical learning. Springer series in statistics New York, 2001. Volume 1, Number 10.
[10] A. U. Guler, F. Demirović, J. Chan, J. Bailey, Leckie, and J. Stuckey, divide and conquer algorithm for Pradictt+ptiminz with non-convex problems. In Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022.
[11] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023.
[12] 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 Artificial Intelligence, 2022.
[13] X. J. H. Lee, J. H. Lee, and A. Z. Zhong. Branch & Learn for recursively and iteratively solvable problems in Predict+pttimize. In Advances in Neural Information Processing Systems, 2022.
[14] K. B. Kabir and I. Mahmud. Study of erosion-corrosion of stainless steel, brass and aluminum by open circuit potential measurements. Journal of Chemical Engineering. pages 13-17, 2010.
[15] N. Kahraman, B. Gülenç, and F. Findik. Joining of titanium/stainless steel by explosive welding and effeet interface. Journal of Materials Processing Technology, 169(2):127-133, 2005.

---

[16] B. Maenhout and M. Vanhoucke. Branching strategies in a Branch-andd-Prg approach for multiple objective nurse scheduling problem. Journal of scheduling, 13(1):77-93, 2010.
[17] J. Mandi, V. Bucarey, M. M. K. Tchomba, and Guns. Decision-focused learning: Through the lens of learning to rank. In International Conference on Machine Learning, pages 14935-14947. PMLR, 2022.
[18] J. Mandi and T. Guns. Interior point solving for LP-based Prediction-OOpimisationn Advances in Neural Information Processing Systems, 33:7272-722 2-822 2020.
[19] M. Mulamba, J. Mandi, M. Diligenti, M. Lombardi, V. Bucarey, and T. Guns. Contrastive losses and solution caching for Predict-and-Opimmize arXiv preprint arXiv:201 2.003544 2020.
[20] R. Muniyan, R. Ramalingam, S. S. Alshamrani, D. Gangodkar, A. Dumka, R. Singh, A. Gehlot, and M. Rashid. Artificial bee colony algorithm with Nelder-Mead method to solve nurse scheduling problem. Mathematics, 10(15)22576, 2022.
[21] Y. Nandwani, R. Ranjan, P. Singla, et al. A solver-free framework for scalable learning in neural ilp architectures. Advances in Neural Information Processing Systems, 35:7972-7986, 2022.
[22] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf. E. Yang. Z. Vetito, 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 in Neural Information Processing Systems
32, pages 8024-8035. 2019.
[23] A. Paulus, M. Rolínek, V. Musil, B. Amos, and G. Martius. Comboptnet: Fit the right NP-hard problem by learning integer programming constraints. International Conference on Machine Learning, pages 8443-8453. PMLR, 2021.
[24] 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.
[25] D. E. Rumelhart, G. E. Hinton, and R. J. Williams. Learning representations by back mack-propagating errors. nature, 363(688))5333-536 1986.
[26] M. Vanhoucke and B. Maenhout. Nsplib-a nurse scheduling problem library: A tool to evaluate (meta-) heuristic procedures. In Operational research for health policy: making better decisions, proceedings of the 31st annual meeting of the working group on operations research applied to health services, pages 151-165, 2007.
[27] B. Wilder, B. Dilkina, and M. Tambe. Melding the data-decisions pipeline: Decision-focusee learning for combinatorial optimization. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, pages 1658-1665, 2019.
12

---

A Detailed discussion on the Two-Stage Predict+Optimize framework
A.1 Problem modelling using the framework
As mentioned in Section B the proposed Two-Stage Prediction-Optimize framework is phrased differently from some other two-stage problem formulations. The proposed framework phrases Stage solutions as seft commitments, and corrects Stage 1 solutions with penalty in Stage 2. On the other hand, some two-stage frameworks phrase Stage solutions as hard commitments, and include explicit recourse variables in both stages of OP to model the correction in Stage 2. Some optimization problems are more natural to express according to one perspective than the other, while some problems might be straightforward to express in either. This section aims to show that our framework, while explicitly stated and motivated according to the first perspective, is in fact general enough to also easily model the second perspective of hard commitments and recourse actions. In what follows, we first describe different types of variables and how our framework can capture them. Then, give two example problems that respectively use the softhhard commitment perspectives, and we detail how the problem can be modelled.
Soft commitment variables:
These are variables which represent decisions that correspond soft commitments made in Stage I in an application, namely decisions that may be modified once the true parameters are revealed, but a cost or penalty. The discussion in Section tailored for this kind of variables- simply define such a variable in Stage and use finite penalty function to model the cost of changing this soft commitment in Stage
Hard commitment variables:
These are variables Hhard which represent hard commitments made in Stage 1, meaning that after commitment, they absolutely cannot change in Stage 2. To model these variables in our framework, simply write penalty function that is infinite whenever Stage and Stage 2 solutions for these variables are different. Explicitly, add a term oo haahdd1 * 2. This way, no Stage 2 solution will change these variables from what they were committed in Stage 1.
Recourse/other variables: These are variables which represent explicit actions/decisions taken only in Stage 2, once the true parameters are revealed. These variables are necessary, for example, when Stage I actions are all hard commitment variables, to ensure that we have mechanism for corrective action if the hard Stage decisions are in any way "incompatible" with the revealed parameters. These corrective actions also typically come at cost. Thus, to model these variables, simply include them in both Stages and 2, and incorporate their cost into the objective of the optimization problem. There should also be 0 penalty for modifying these variables between the stages.
To summarize, Stage actions can be classified as either soft or hard commitments, depending on whether they can be changed in Stage 2 (at a finite penalty). Stage 2 actions are classified as "recourse" " variables, which are simply variables that have no penalty from changing between Stage 1 to Stage 2. The above discussion shows how our framework captures all these possibilities. We now give two example applications: the first one is more naturally expressed via the soft commitment perspective, and the second one is more natural to phrase using hard commitments+recourse We give also their explicit formulations to demonstrate how the modelling is done in our framework.
We first show an example problem which is naturally modelled using soft commitment variables and penalty functions. Consider the product-stocking problem in Example | again, where regular orders have to he placed two weeks ahead of monthly deliveries. We aim to maximize the net profit by selling stocked products, under the constraint that the available storage space is limited. Each product has a purchase price p," (the price of purchasing the product from the wholesale company) and selling price p (the price of selling the product to customers), and needs s; space to be stocked. Let z; denote whether the product i is ordered. In Stage 1, i.e., two weeks before the delivery, the available storage space Sp the time of delivery is unknown, and we place the order x based on estimated space. In Stage 2, i.e., the night before the delivery, the precise available space is revealed, and we ask the wholesale company to change the order but need to pay a surcharge for last-minute changes. Assume the surcharge for the last-minute change in the order of product i is q, In this example, x; is thus a soft commitment variable, and we model the surcharge e; using the penalty function of the framework.
13

---

The proposed framework can naturally model this problem. The Stage OP can be formulated as:
ri = arg max E(p
(pf pa)
S.t. Esat S Sp, x xE (0,1)
In Stage 2, the order 2 can be changed with surcharges, which can be modelled as a penalty function:
(æn xx = Σ c/at x.l
Then the Stage 2 OP can be formulated
E (pi - -pp) p.) E -
222
arg max
x
s.t. Σ
8,04 S Sp, x [0
Next, we give an example problem which more naturally modelled using hard commitment variables and recourse variables. Consider a production-plamning problem: a company owns a set of facilities of customers. Each facility can provide fixed amount services m, and has fixed operating cost Si in the standard working mode. The company aims to meet customer demands at the minimum operating costs. In Stage I, the company decides which facilities to open for production based on the estimated demands d. This is a binary decision variable 2; for each facility i. In Stage 2, the orders from customers arrive and the demands d are revealed. If the services provided by the operating facilities the standard mode cannot meet demands, the company will ask some facilities that already operating (i.e. F; 1) to work overtime, but naturally need to pay high overtime fees. Let o, denote the unit overtime fee for producing service facility i, and a; denote the amount of service provided by overtime working in facility
and provides services
This example naturally modelled using hard commitment variables and recourse variables. Which facilities to operate, z, is vector of 0/1 hard commitment variables. The amount of service, provided by the overtime working mode of operating facilities can be modeled by recourse variables. and the recourse costs are the overtime fees Using hard commitment variables and recourse variables, the Stage I OP can be formulated as:
o = arg min
Σ Jia:: + Σ Σoior o:0
s.t. Σ (m+ +0,0;
x (0,1), o a20
In Stage 2, we include a term oo 1 [ * x] in the penalty function part of the Stage 2 objective to make sure that cannot be changed, while the penalty for changing is zero since it is recourse variable, The Stage 2 OP is formulated as:
222 02 = arg min
Ebar Σ + 00. 1|21 +
2,0
s.t. [im+ 2 d, x x (0,1), a 0
In summary, we discussed how to model in our framework soft and hard commitment actions in Stage 1, as well as recourse/other actions in Stage 2. We gave two concrete examples to demonstrate how such modelling can be done.
A.2 What if correction/reccourse is not possible in the application?
The motivating premise of this paper that the application scenario hand allows for some post- hoc corrective action once the true parameters are revealed. One natural question is: what if such
14

---

corrective action (Stage 2 actions) is not actually possible in the application? For example, in our running example of the product-stocking problem, we considered wholesale company that allows for order changes the night before. Other wholesalers may not allow such correction/modificati framework can essentially still model these scenarios: just set the penalty of modification to infinity (or at least, very large numbers for practice). Concretely, use the penalty function so 1 [x] * xi] (or replace oo with a very large number). This penalty function encourages the learning algorithm to learn conservative predictions that maximize the chances of yielding Stage 1 decisions that remain feasible Stage 2.
Our
To show this, we ran another quick experiment, using the 0-1 knapsack problem setting in the paper (with knapsack capacity 100). This time, as we varied the magnitude of the penalty function, we measure at test time the empirical fraction of Stage solutions that remain feasible under the true parameters. The results in Table demonstrate our claim that as the penalty term increases, the predictions get more and more likely to remain feasible, making it a reasonable way to train predictor even when Stage 2 correction mechanisms do not actually exist in the application.
Table 6: Mean and standard deviation of empirical fraction of Stage 1 solutions that remain feasible in Stage 2, for the 0-1 knapsack problem when capacity is 100 using the Two-Stage Predict+Optimize framework.
Penalty Factor
Feasibility
0.05
0.00%
0,25
0.00%:40.005%
0.5
1.73%:20.52%%
I
50.93%:+1.92%
2
51.63%:#1 2.2%
4
99.07%:=0..15
A.3 Two-Stage Predict+Optinize vs Prior Hu et al. Framework
As mentioned earlier in Section B] Two-Star Stage Predict+Optimize is technically mathematically equiva- lent to the prior framework of Hu et al. [12], in the sense of expressiveness, ignoring differentiability issues. On the one hand, we can regard the Stage 2 optimization and hence Two-Stage Predict+Optimize can be considered as special case of the Hu et al. [12] framework. On the other hand, given a correction function as in the Hu et al. [12] framework, we can simply modify the penalty function such that we keep the penalty value of the corrected solution, and make the penalty value infinite for all other potential Stage 2 solutions. This forces the Stage optimization to always emulate the correction function. In this sense, our Two-Stage Predict+Optimize framework can also emulate the Hu et al. [2] framework, meaning that the two frameworks are technically equivalent.
form of correction function,
Nevertheless, the Two-Stage Predict+Optimize framework is both conceptually simpler and easier to apply. In the main paper, we showed how to perform end-to-end neural network training within this new framework whenever both stages of optimization can be phrased as MILPs, and also give empirical experimental results. Together, they demonstrate the much more general applicability of the Two-Stage Predict+Optmmiee framework.
We end this appendix with the statement and short proof that, conditioned on the same penalty function and prediction model, Two-Stage PredictOOpimize always outputs at least as good a final solution as the prior framework using any correction function.
Proposition A.1. Consider an arbitrary minimization Para-OP P. penalty function Pen, correction function Yorrrs estimated parameters O and true parameters 0. Let Let (0) and (0) both denote the estimated solution from the estimated parameters 0, 17, f) be the output final solution from the Two-Stage Predict+ Optimize framework, and v'urr (0, B) be the output corrected solution from the prior framework of Hu et al. Then.
(bj (0, 0) + (0) + (0,00) I ob (0.0).0) + Pen(x" (0) -0) zoor (0,0)
Proof. Observe that both sides of the inequality are the objective of the Stage 2 optimization problem, evaluated at x. and atory respectively. Since xz the optimal solution to the minimization problem, the inequality follows directly.
15

---

B Gradient Calculations for Problem (5)
Approximating daj In the context of the MILP, the unknown parameter è may either be c, 6, b, G. a6
or h. Using the solution x and the barrier weight I returned from solving Problem ( we can
compute the relevant derivatives of Uzij de The case of has already been derived by Mandi and can be rewritten as:
Guns [18] (see Appendix A.1 and A.2 their paper). Problem (5)
d+g
x² = arg min cT Tx' x''-' p. Σ In(1))
(6)
x²
2m1
s.t. A'x' = bb
where
d'
0] Rd+t
x'
x S Rd+4
A' =
A
E (R((+t))((+g))
b
12Pt
h
Fact B.1. Consider the LP relaxation (6), defining x' as a function of d, A' and b. Then, according Mandi and Guns [8],
under this definition of x²,
-X-11
T
ATT
Ox'
r
A'
0
=
0
TT
T
R
qe!
x
86
where X' = diag(z'),t= diagl()) y' is the lagrangian multiplier of Problem (6) and
and are additional variables added by Mandi and Guns [18] to represent the duality gap. The can be obtained by solving this system of equalities.
âz;
gradient 05
Define the notation fxx c, G,h) = TTx. Di In(a,) 11 -E In[ h.). Then, Problem 5 can be expressed as finding:
arg Sxx G,h, s.t. Ar=
Using this notation, we write down the following four lemmas on computing approximately.
Or" Ox" Or
and
On" 8b
80 0h 8A
Lemma B.2. Consider the LP relaxation 7 defining x" a function of c, A, G and h. Then, under this definition of x²,
Ox" 3G
G,h)
where H = (x c, G.h) denotes the matrix of second derivatives of f with respect to different coordinates of x, and similarly for other subscripts, and explicitly:
{ pag + E G2. x -- h1)2 j j=b
SE (x,
(8)
1 DE GifGit/ -1)²², j
and
IGea, Ne,,G,G,, = [GGeaz x h2) p\/ u/(TT x he)
r r=
(uGeja./ x h2)
r r+1
Note that when there are equality constraints, iee, A = 0, we have
Or
- (c,, G.G
0G
which is the same the Lemma in (12].
16

---

Proof. Using the Lagrangian multiplier the Lagrangian relaxation of Problem can be written as L(x Lx, G, h) = f(z, c, G.h) + (bb
(9) Since x² arg min, f(z, c. G. s.t. Ar = b is optimum, x² must obey the Karush- Kuhn- Tucker (KKT) conditions, obtained by setting the partial derivative of Equation ( with respect to and to O. Let f2 c, G, h) denotes the vector of first derivatives of f with respect to different coordinates of æ. Jaz (I, e, G, h) denotes the matrix of second derivatives of / with respect to different coordinates of v, we obtain:
(a e, G, - A 0
(10)
-r
The implicit differentiation of these KKT conditions with respect to G allows us to get the following system of equalities:
C,, (
-A
][
Ba
0
(11)
0
By
8G
By solving this system of equalities, can obtain
Ox
(11 - (cc,
11
8G
Since f(z, c, h) = c. -- -PE In(,;) - r E In x h1)) we have
f2 e, G,h) = 1r - 11 11 1=| G hi)
C,, {
μ2g + > Gy h,)? j= k
(12)
E G.
(G j jik
and
fera, (2, = pueez | h₂) u/(GT x -he)
r r=
(uGeja,/ -- 2 h₂)²
r #
Lemma B.3. Consider the LP relaxation 7 defining x* as a function of c, A, b, and h. Then, under this definition ofx" x",
Ox
AH-IAA A AH- H (h,
0h
where = S2x is defined as in Lemma
B.2 and
fhez, (z, c, G,h) = HGGee//eGG he)² Note that when there are no equality constraints, i.e,, A = 0, we have
Ox
- - -h c,,
0h
which is the same as the Lemma in [22
Proof. As stated in the proof of Lemma
B.2, using the Lagrangian relaxation and the Karush-Kuhn
Tucker (KKT) conditions, we obtain:
CI - A y
(13)
Ar-b=0
The implicit differentiation of these KKT conditions with respect to h allows us to get the following system of equalities:
[
[
Jiz (r, e, G,
] + (x, G,h)
-AT
dz
gh
= 0
(14)
0
0
By solving this system of equalities,
obtain
Or = (H-IAT
- -h G.h)
0h
17

---

where H = far is defined as in Lemma B.2 E In(G,r h4), we have
Since G, = c' 1e =E In(2))
Thizg (z) -u
Lemma B.4. Consider the LP relaxation under this definition of x²
defining x² as a function of c, A,b, G and h. Then,
dx
H (AH
AH + 113)
DAi
where 11
BAT BA.
12
8A "A,''
and H Saz is defined as in Lemma B.2
Proof. As stated in the proof of Lemma B.2 using the Lagrangian relaxation and the Karush-Kuhn-
Tucker (KKT) conditions, we obtain:
f A y Ar -r
(15)
Since A E Roxd, fix E ......,P:.J (I....,d}. the implicit differentiation of these KKT conditions with respect to Ai allows to get the following system of equalities:
0A
8Ay V
8AT
(a A
-AT 0
JA
by
0
(16)
8A,,
JA..,
Let 1,
BAT BAs,"
I2
8A
By solving this system of equalities, we can obtain
BA
dx
H 1-A
'12r + AH (1y) Iiy)
AAij
where faz is defined as Lemma B.2
Lemma B.5. Consider the LP relaxation 7 under this definition of x²,
defining x² as a function of e, A,b, G and h. Then,
Ox
H AT ATAAAAAHA AAH-1
Ob
where = faz is defined as in Lemma
B.2
Proof. As stated in the proof of Lemma
B.2
using the Lagrangian relaxation and the Karush-Kuhn-
Tucker (KKT) conditions, we obtain:
(, A
(17)
Ar-b=0
The implicit differentiation of these KKT conditions with respect to b allows us to get the following system of equalities:
[
0
Sax (
-AT
-1
25
(18)
A
dy
7b
By solving this system of equalities, can obtain
Oz
H AT
(AH AAAAA
-
ab
where = Saz is defined as Lemma B.2
18

---

C Details for Case Studies
Since the penalty function partly solely affects the terms
@P dag
0 RPReg and
Oz
d=i
we give three case studies for our framework to show how to design the penalty function and compute gradients using the corresponding penalty function.
C.1 Alloy Production Problem
We first demonstrate, using the example of the alloy production problem, how our framework can tackle problems solvable by the prior work of Hu et al. [[2]. An alloy production factory needs to produce certain amount of particular alloy, requiring a mixture of M kinds of metals. To that end, it must acquire at least reqm tons of each of the E [M] metals. The raw materials are to obtained from K suppliers, each supplying a different type of ore. The factory plans to buy ores from sites and then extract the metals themselves. The ore supplied by site k E [K] contains conte E [0, 1] fraction of material m at a price of cost, per ton. The goal of the factory is to meet its requirements for each metal at the minimum cost. However, the precise metal concentrations (averaged a batch) are unknown before the factory actually completes metal extraction. The factory will estimate metal concentrations based historical buying records, considering features such as the ore type, ore origin, site-reported preliminary samples and so on. Then the factory will decide how much to order from each site. This is the Stage 1 solution. The Stage 1 OP is the alloy production problem using the estimated metal concentrations con, and can be formulated as follows:
Fj = arg min cost T x
S.t. cón x 2 req, x 2
After the factory obtains the ores and completes metal extraction, i.e., in Stage 2, the precise metal concentrations//mounts are known. Since the purchased ores are already processed, the factory cannot return ores even if it has bought too much. However, if the obtained metals do not satisfy the requirements, the factory can post-hoc decide to last-minute order more ores at higher price, for example, (1 + a coosls per ton from the site k, where o 2 a non-negative tunable scalar parameter. In this scenario, the penalty function is:
Pen(x + x) = (a o cost) T (x - -r²))
(19)
where o is the Hadamard/entrywise product.
With respect the above penalty function, are now ready to define the Stage 2 OP:
2 arg min cost." T + (ar o cost) (x > s.t. con J 2 reg, x 2 xi
(20)
x
Note that since the precise metal concentrations the problem parameters instead of the estimated concentrations. The final amount of ores bought from each site, including the ores bought in both Stage and Stage 2, is the Stage 2 solution.
revealed, the true concentrations used as
The above formulation is based on the "soft commitment" modelling approach discussed Ap- pendix A.I
The post-hoc regret for the alloy production problem can be explicitly written as:
( 0) cost x (a cost)
(z) - 21) cost x= (con)
(21)
where x= (con) an optimal solution of the alloy production problem under the true concentrations
con. We now show how to compute the relevant gradients as discussed in Section 4 and Appendix B
Using Equation (1). is straightforward to compute that the i-th item vector @PReg(000) dug
and
)
the i-th item in vector
OPRee(00.0
@PRea((..) 8x
(1 o.) cost,,
a aPRee 8x
8a
costt
Now we show how to compute the approximation of the remaining term, Øz.
19

---

Approximation dz. We use the same interior-point LP solver to help compute the relevant -e.
derivatives. First, the estimated parameters are fed into the LP solver to solve the Stage I OP to obtain the Stage 1 optimal solution z and the corresponding μa, which are used to compute the term dzi 80
Then the Stage I optimal solution zं and the true parameters are fed into the LP solver to solve the Stage 2 OP to obtain the Stage 2 optimal solution z and the corresponding 14, which are used to dzz Consider the Stage 2 OP in program (20). It is clear that the Stage 2 OP is MILP, with z2 in the objective and af in of the constraints. Applying Lemma B.3 we can compute term.
compute the term āzū"
an approximate gradient of the dug
dx?
C.2 Variant of 0-1 Knapsack
The second example, which we call the proxy buyer problem, is variant of the 0-1 knapsack problem. The unknown parameters appear in both the objective and constraints. This problem, as we shall see, can be handled by our framework, but not by the prior approach by Hu et al. [12] since the problem inherently discrete and cannot be formulated as L.s..
A proxy buyer is a person who purchases goods for others possibly for a profit. Consider a proxy buyer who from City A, with very high cost of living, who regularly travels to City B with a much lower cost of living. Given her regular travels, her friends in City A have asked her to help purchase everyday-life products, which are significantly cheaper in City B, yet the time and transportation cost from City A to City B makes it prohibitive for most people to just go to City B themselves. The traveller commutes between City A and City B once every three months, and has a known and limited capacity cap of goods she could carry and bring back. Before each trip, her friends would make requests for things to buy. For simplicity, one request contains one item. If the buyer brings back the item as requested, her friends will pay her 20% of the price-tag ps: of each item as courtesy- carttss-thhankyu. We denote this "profit" by St. i.e. fa = 20%p:-
The buyer is popular, and many friends ask her for favours. One day before the buyer leaves for City B, the buyer needs decide which of her friends' requests accept, given the limited capacity, and inform them accordingly. The buyer wants to maximize the total amount of courtesy-thanky money she gets, subject to the hard constraint of the limited suitcase capacity cap. However, the precise price p; of each item is unknown, due to the uncertainty of the price itself, the volatility of the exchange rate, and the uncertainty of the discount activities of the items. Thus, the "profit" f: of buying item is unknown. In addition, the exact size s; of each item i is also estimated. The buyer will estimate the profit, i.e., the prices, and the sizes based on past experiences, considering features such as time-of-year, holiday-or-not, brand and so on. The buyer will decide which requests to accept based on the estimation. This is the Stage I solution. The Stage 1 OP is the proxy buyer problem using the estimated sizes á and estimated profits f:
क arg max f I
s.t. ST. x <cp.. x E {0,
After the buyer arrives at City B, the buyer knows the precise price and size of each item. If she cannot carry all the accepted requests, for example, if the packaging for certain items have changed since she last bought them, the buyer will necessarily need to drop some of these requests. The buyer usually feels bad about reneging apology the request cannot be fulfilled after she promised. For simplicity, we assume that the price of the apology- meal is linear in the profit of the dropped request, since more expensive items considered "more important" requests. Here, the linearity factor is independent of the request. That is, if she drops item i, she has to spend ft amount of money, where o 2 0 is non-negative tunable scalar parameter. In this scenario, the penalty function is:
promise to her friends, and treats her friends to a meal as an
Pen(xi - x) = a f (xi - x)
(22)
We are now ready to define the Stage 2 OP with respect to the above penalty function:
x arg max IT of (af x),,
s.t. T x S cap, x S x1, x E (0,
(23)
The requests that were finally filled, namely the items that were actually bought by the buyer and brought home to City A, forms the Stage 2 solution.
20

---

Then the simplified form of the post-hoc regret for the proxy buyer problem can be written as:
PReg(0000) 0) - 1"= - I
of [2] -
(24)
where (f, 3) is an optimal solution of the proxy buyer problem under the true proxy fees f and true sizes
Using Equation (2).. it is straightforward to compute that the i-th item in vector
2PRe
and
si
the i-th item in vector
Reg
0x1
27 =
=(-1- fs.
@PReg( 0xi
o
25
Approximation deg duf
Similar to the computation in Section 1 we obtain the Stage optimal
solution zi. the Stage 2 optimal solution z=2. and the corresponding j from the interior-point LP
ax Consider the Stage 2 OP in program (23) it is clear that the Stage OP is
compute the term Ux
MILP, with 2 in the objective and æ in h of the constraints. Applying Lemma B.3
we compute
an approximate gradient of the term.
8ag dm,
C.3 Nurse Scheduling Problem
Our last example is the nurse scheduling problem (NSP), which can be handled by framework but not by the prior work of Hu et al. [[2] since it is neither a packing LP nor a covering LP.
Consider a large optometry center that needs to assign nurses to shifts per day to meet patients' needs. Every Monday morning, the center collects the nurses' preferences for each shift of the following week. Since nurses may have their own activities and errands during unscheduled shifts, they want to be informed of their schedules as early as possible. After the preferences are collected, on Monday night, the center sets preliminary shift schedule for the upcoming week based on the estimated number of patients for each shift. Suppose there are n nurses, h days, and 8 shifts per day, then the number of the total shifts is 1 x We formulate the decision variables as Boolean vector x E {0, ]dd where d = n x x 8. Let P E 21,2, 3, 4] represent the value of each nurse's s preferences for a particular shift (the higher the number the better), and H E N' represents the number of patients in each shift, which are unknown and need to be predicted. Each nurse can serve my patients in one shift. The objective is maximize the nurses' preferences under set of constraints: (1) the schedule must satisfy the patient demand, under each shift (2) each nurse must be scheduled for exactly one shift each day (3) no nurse may be scheduled to work a night shift followed immediately by a morning shift. The Stage OP is the NSP using the estimated number of patients H:
1 = arg max P
mcs+4 2 HI Vj (0,.... t 1}
S.L.
Vi = {0, n - 1}. j = (0, (0...... ., 1}
Σ
Ta+astt =1
0=
Littajts-1 + Iit- $ Vi (0.. ...., 1}: j = (0...., 2}
10
To provide better service patients, the optometry center has implemented an appointment system that requires patients to schedule an appointment in advance to receive medical care. Reservations for the upcoming week, from Monday to Sunday, close every Sunday evening. At this point, the center knows the precise number of patients for each shift of the next week. The center might adjust the shift schedule to satisfy the actual patient demand or to improve the overall nurse preferences. However, due to the late notice for schedule changes, the nurse's 's preference may become lower. For example, if a nurse is rescheduled shift may become 4 due to the late notice. Besides, a nurse may be more unhappy to be changed to
shift for which her original preference 5, now her preference for this
21

---

a low-preference shift. In this scenario, since the nurses' preferences are in 11,2,3,44 the penalty function can be formulated as:
Pen(a] + x) Pen(æi + x)
(25)
where the i-th item in the penalty function is:
7:(5 P:)) - 27.e)
Pen(æi - x)); - 10
24 < zii
We are now ready to define the Stage 2 OP with respect to the above penalty function:
22 = arg max PT I
(e + x);
s.t.
m&Zu+s 2 Hy
Vj {0, 1}
Vi f0. n 1}.
Tit+sfta
= 10. k -11 1}
Bittatt--1 + Fit-sjte S {0, ................................ 11 1}
{0 2}
E {0.1}
Then the simplified form of the post-hoc regret for the NSP can be written as:
PReg(0,0) PT (H) PT PT Pen(aï - +x))
(26)
Using Equation (26). is straightforward to compute that the i-th item vector (eg
and
dag
the i-th item in vector aPge (0.0)
aPReg(O,0)
P.+
P.)
2 2 3 < Fi
Oxg
P.
@PReg(0.0)
-2 P.)
22 2 21 241 21
On
0
22
Approximation duf Similar to the computation in Section C. we obtain the Stage optimal
dug
solution zi. the Stage 2 optimal solution æ and the corresponding μ from the interior-point LP
compute the term
0z
Using the penalty function in Equation 25 the Stage 2 OP can be formulated
22

---

as MILP by adding new variables and one more constraint:
22 arg max P
7:(5 P.)
1=0
M43+s 2 H2
Vj E {0, (0,.../. 1-.,,,-11 1}
Vi = (0. n 1),
Fit+s+t7
j = (0.
8-11 1]
Vi (0, 1
Tittsjto-1 + Pitej+s S
j (0, ,
0.2 - +is I 6 {0,1}
vi {0,
1}
E {0,1}
Suppose the Stage 2 OP of the NSP can be written as:
2 arg min -P x (5 P
s.t. G5 H
Az = b
G2 2 -1
x 2 -
0 E {0,1}
Then the standard form of the Stage OP is:
2 = arg min T x'
s.t. A'a' =
Gr 2 h
x' E {0,1}
where
=
P
7o
(5 PP)
E 2d
I' = |r ol E Rdd
G
0
G
G2
0
E <)(+
h =
1
E Bltnk-nnd
-I
1
x
A'
A 0
]
E Rnkx2d
and E Ra an all-ones vector.
It is clear that z is in the objective and x; is in h of the constraints. Applying Lemma compute an approximate gradient of the dz term.
B.3
we can
0x
23

---

D Hyperparameters for the Experiments
The methods of k-NN, RF, NN, and IntOpt-C as well 2S have hyperparameters, which we tune via cross-vale voss-vaaiittion: for k-NN, we try & E {1, 3, 5] ; for RF, we try different numbers of trees in the forest {10, 50, 100); for NN, IntOpt-C, and 2S, we treat the learning rate, epochs and weight decay as hyperparameters.
Tables 7 [ and show the final hyperparameter choices for the three problems: 1) alloy production problem, 2) the classic 0-1 knapsack problem, and 3) a nurse roster scheduling problem.
Table 7: Hyperparameters of the experiments on the alloy production problem.
Model
Hyperparameters
Proposed
optimizer: optim, Adam; leamming rate: 5 "y j 10 epochs=20
KNN
RF
n
KN
optmiizrr: aptm..ddmm, Adaa;; leaminng 10 epochs-20
Table 8: Hyperparameters of the experiments on the 0-1 knapsack problem.
Model
Hyperparameters
Proposed
optimizr:: oplim.Adam: learning rate: 1 epachu112
NNN
k=5
n. estimators
NN
optimizer: optim.Adam; learning 10 epochs=12
Table 9: Hyperparameters of the experiments on the nurse scheduling problem.
Model
Hyperparanntees
Proposed
optimizer: optim.Adum; learning rate: 10 epochss8
E-NN
k=5
n. eeestiaatr=100 100
optimizer: optim.Adam; learning rate: 10 epochs
Ridge, k-NN, CART and RF are implemented using scikit-learn 124] The neural network is implemented using PyTorch [22]. To compute the two stages of optimization at time for our method, and to compute the optimal solution of an (MI)LP under the true parameters, we use the MILP solver from Gurobi II]
E
Comparisons of the 2S Method and the Prior Differentiation Methods
In this section, compare the proposed method with prior works 2 27 that provide ways of differentiating through LPs or LPs with regularization.
conduct comparisons with CvxpyLayer [ but not OptNet [ QPTL 227. The reason is that the calculation method proposed in QPTL is LP+quadratic regularization using OptNet, and CvxpyLayer is just a conic extension to OptNet. We compared Layer ( with a) regularization, b) quadratic regularization and c) log- barrier (like our Section Appendix B) The key indicator of its predictive performance the type of regularization used, with the log- log-barrier version performing the best, but still slightly worse than method. We applied CvxpyLayer ① to the 0-1 knapsack benchmark to compare with our 2S method.
The
Table 10 reports the mean post-hoc regrets and standard deviations across 10 runs and Table []] reports the average training times. More precisely, we use it with various regularizations (a. LP with no regularization, b. with quadratic regularization, c. with log barrbarrier in our paper) to replace the Section SiciionAAppa Appendix B ggradient calculations. We find that CaxpyLayer [[] never gives better solution quality while 2S is 30%-50% faster.
24

---

Table 10: Mean post-hoe regrets and standard deviations of the 2S method and CvxpyLayer with different regularization on the 0-1 knapsack problem.
Penalty factor
PReg
CvspyLayertlog
CvapyLayersqual.gg
CrapyLayer-no_rg
0005
126=0..01
L26=:1.01
1.2700001
7.70=0.39
cup=100
0.25
6.2820.05
6.2820.05
6.3420.03
8.8720.92
9.22+0.10
9.47=0.31
9.9620.54
10.13=0.46 46
0.055
0.7320.01
0.7420.01
0.7520.03
6.7420.58
cap=150
0.25
3.64:0.04
3.64:0.04
3.70=0.03
7.18=0.77
0.5
7.27+0.06
7.28+0.08
7,39=0.06
8.43+00.58
Table 11: Average runtime (in seconds) of the 2S method and CvxpyLayer with different regularization on the 0-1 knapsack problem.
Runtime
CyspyLayertlog
Cyxpyl Layer+quad reg
Cvxpy reg
cap=100 100
204.76
438.24
571.38
344.50
cap=150
245.61
467.65
662.30
366.83
F Frameworks Comparisons on the Alloy Production Problem
In this section, we further compared the proposed framework with the framework using the differ- entiable projection idea in [3] on the alloy production benchmark. The idea B] is to use the l2 projection, and we implemented it using CvxpyLayer. The experiment set-up follows that of Table 2 both training and testing use la projection in the second stage, as opposed to solving the second stage optimization problem defined in Section 3 Table 12 shows both the post-hoc regret and training time for le projection. We find that not only is le projection slow, but it has even worse post-hoc regret than the Hu et al. correction [12]. We suspect that this is due the Hu et al. correction function 12 preserving the direction of the solution vector whereas l2 projection can change the direction, and that this makes difference for Alloy Production. In any case, this experiment confirms again that our Two-Stage framework has better post-hoc regret than a framework based on differentiable projections, reinforcing the main message of our paper.
Table 12: Comparison of three frameworks on the alloy production problem.
PReg
Average runtime
Penalty factor
0.25+0.015
0.520.015
1s0.015
2=0.015
420.015
$20.015
Two-Stage Predict
Optimize Framework
43.87=2.73
65.7124.81
88.75a5.91
123.90=6.84
161.8618849
194.06:13.09
268.22
Hu Framework
16416662
82.91+5.45
107.6446.85
150.47412.99
178.
106.5
228.00
projection
103,2844.87
118.9001699
150.15211.45
212.62420.58
337.59223.24
562,41134.29
442.97
G Experiments on the 0-1 Knapsack Problem with Large Penalty Factors
Table 13 reports the mean post-hoc regrets and standard deviations across 10 runs for each approach on the 0-- knapsack problem with large penalty factors (penalty factors 2 1). With more data, we make further analysis of the performance of the proposed 2S method. Observing Tables Taoles/aadd [3] we can see that the trend, in terms of the difference between 2S and other methods, first decreases, then increases, as the penalty factor increases. The trend in Tables 4 and 13 is identical to the trend in Table We can explain this phenomenon as follows.
First, when the penalty factor is small, the rational behavior for the buyer is to just take every order, and only decide which orders to drop when the true parameters are revealed (at close to no cost). 2S identifies and exploits this behavior for small penalties, while classic regression methods are agnostic to this possible tactic. Thus, the advantage of 2S compared to classic regression methods is large in the small penalty case.
Second, when the penalty factor is large, 2S will analogously learn be conservative, such that the first stage solution likely remains feasible under the true parameters, in order to avoid the necessary (and high) penalty due having to change to a feasible solution. Again, classic regression methods will be agnostic to this possible tactic, leading to large advantage of 2S over the classic methods.
25

---

Table 5 only has the increasing trend from the large penalty, since it is neither a covering nor packing program, and so there no analogous tactic/exploitation for the small penalty.
Table 13: Mean post-hoe regrets and standard deviations for 0-1 knapsack problem with large penalty factors using the Two-Stage Predict+Optimizz framework.
PRog
Penalty factor
CombOpeNNct
Ridge
i-NN
CART
TOV
15
10.9150177
109340 19
11.1T0017
11,16-1114
I1D1=0.31
11. 11.2640.22
cap-100
12.31:0.16
12.48+0.20
12.49:0.21
13.77=0.26
12.60=0.39
12.78+0.30 30
19.6840.14
14.5420.15
15.6620.47
15,5740.25 25
15.6840.39
19.01
15.7720.62
15.8440.500
10.22400.12
10:27=0:18
10,404122 23
10:00:018
10.46=01199
10.49=0.21
10300e00.20 70
cap-150
11.1840.15
11.74a0.34
11,8840.30 30
11,6340.20
12.56.0.31
11.83=0.19
12.12:0.17
40.2340.
13.20=00166
14.33+0-4
14.7140.49
16.25-0.63
14.53+0.29
14/65+2.41
6.77:10.36
15.3090028
7.57 18
7.3120127
1,7150.20
7.6780.16
8.0080.65
cxp=200)
8.19+0.12
15.39e0.16
8.8400.22 22
8.69 26
9.24=0.30
8 8,80e0.20
8 8.97=+0.37
48. 13+0.34
9.71+0035
15.46+0.22
11.1740.44
11,06+0.32
12.29-0.59 59
11 11005-0.46
10.91+0.53
1_37:00.88
20.0920.20
3,0890
2.9220.16
3.17=0.17
cop=250
3.34:0.15
20.78=0.20
80H0 20
3.73+0.11 15
3,94 20
3.79H41.26
3 3.89H03S5
53.45+0.26
4.46:20.09
20.93e0.20
5.2540.35
5.32+0.27
5,47=0.35
5.20+00.4
5.11+0.39
H Runtimes for the Experiments
In this paper, all models are trained with Intel(R) Xeon(R) CPU E5-2630 v2 @ 2.60GHz processors. Table [14] shows the average runtime across 10 simulations for different optimization problems. Since the testing time of different approaches is quite similar, here, the runtime refers to only the training time of the prediction model and does not include the testing time. At training time, only the proposed 2S method and IntOpt-C solve the LP. Training for the usual NN does not involve the LP at all, and so training is much faster (but gives worse results).
Since IntOpt-C cannot handle the variant of the 0-1 knapsack problem and the NSP, we only report the runtime of IntOpt-C for the alloy production problem.
Since the provided code of CombOptNet is only available for the 0-1 knapsack problem, we only report the runtime of CombOptNet for the 0-1 knapsack problem. As Table [4ssows, CombOptNet drastically slower than the proposed 2S method.
In the alloy production problem, the runtimes of the proposed 2S method are a little larger than that of IntOpt-C. The reason is that 2S needs to solve two LPs when training while IntOpt-C only needs to solve one. But in the alloy production problem, the unknown parameters are on the left hand side of the inequality constraints and the gradient computation includes matrix computation, which is also cime-consuming. Thus, the runtimes of the 2S method are larger but not twice as large as that of the IntOpt-C method.
In both the alloy production problem and the variant of the 0-1 knapsack problem, the runtimes of the 2S method are much better than RF.
The runtime of the 2S method is large in the NSP. This is because we use the formulation where each decision variable corresponds to whether a specific nurse is assigned to a specific day and a specific shift. Thus, the number of the decision variable of the relaxed LP is large and the LP takes more time to solve.
Table 14: Average runtime (in seconds) for the alloy production, 0-1 knapsack, and nurse scheduling problems.
Runtime(s)
Brass
Alloy production
Tilunium- alloy
Capacity= 204.76
Capacity= 245.61
(-1 knspsack
Capacity=200 202.65
Capacity=250 193.46
Nurse scheduling
28
268.22
394.53
$37.32
IntOpe-C
228.00
331.38
NIA
CompOptNct
NTA
2341.40
2940.256
2394,05
2383,39
NC
Ridge
20.22
$6.89
22.33
<]
K-NN
25.14
70,22
26.
<1
CART
30.33
94.89
34.83
<]
RF
2551.25
1034.07
2.11
'NNN
212.22
321.11
135.80
11.39
26


Reviews:
[{"review_id": "YsFXwuPfh8", "reviewer": "Reviewer_FnYQ", "summary": "The authors develop a two-stage predict-and-optimize approach. There is a recent paper of Hu et al. [9] that extends the predict-and-optimize framework to having unknown parameters in the constraints. The authors argue that the Hu et al. approach, which requires defining both a \"correction function\" and a \"penalty function\", could be simplified by solving a single optimization problem. The authors show how to run the Mandi and Guns [15] solver to get the answer to this optimization problem. They then demonstrate a wide range of examples for their approach, including some real-world examples.", "questions": "I've tried to be pretty specific as to what are the weaknesses of the paper so that the authors can correct as relevant. Please take the \"Weaknesses\" section as a set of questions where I'm happy to be corrected.", "limitations": "This part of the paper is fine.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The authors have written a clear and easy-to-understand paper. I have not checked the proofs with great detail, but the mathematics looks very reasonable. The authors are getting impressive results on the examples that they explore.\n\nThe novelty is that the authors are combining the work of Hu et al. with the work of Mandi and Guns.\n\nThis is a fairly important problem within the Predict+Optimize framework and getting good solutions to these problems is important, so the significance is that this approach could hopefully be used. For the examples that the authors are demonstrating, their approach is clearly better to Hu et al.", "weaknesses": "As a point of order, it's frustrating that papers sometimes cite references so narrowly. I understand this a bit better when a paper is very mathematical, for instance building a proof based on another proof. But in this paper, the proofs are fairly algorithmic/arithmetic and involve well-known components. I haven't tried to discover who the authors are, but I notice that that 7 of the 23 references [1, 2, 3, 7, 14, 15, 16] are to the same group of close collaborators. Then, another 11 of the 23 references [6, 8, 11, 12, 13, 17, 18, 19, 20, 21, 22] are to software packages, test problems and text books. This leaves only 5 of 23 references which are to papers that are somehow intellectually related but not from a single group of collaborators (of these 5 remaining papers, two are to Elmachtoub and co-workers, two are to Hu and co-workers, and one is to Wilder et al.).\n\nI am anxious about how many of the papers (7) refer to one closely-related group when only 5 of the cited papers are to work outside the group (I discard the 11 software packages / textbooks / test instances because these don't require the same work in linking ideas). Work that singularly focuses on just a single small group of collaborators sometimes neglects to take the broad perspective that often characterizes good science.\n\nThe reason that I'm marking \"Fair\" in the \"Presentation\" tick mark is this very limited interaction with the literature. Other than this problem, the paper is quite clear.\n\n****\n\nAt least as the paper is worded, there is a Hu et al. [9] framework that has been introduced that matches the authors setting, but everything would be better if only we would \"adapt the approach of Mandi and Guns [15]\" [Section 1, line 79]. For example, most of Section 4 (lines 211 - 268) discuss an adaptation of Mandi and Guns [15]. The point of the paper often seems to be that if only Hu et al. had read Mandi and Guns a bit more carefully, Hu et al. would have done things differently.\n\nOverall, the current paper reads like a \"letter to the Editor\" objecting to elements of the work of Hu et al. [9] and trying to correct it. The Hu et al. framework is described in detail (lines 40-82 in the introduction and also Section 3 seem dedicated to Hu et al. and why what they're doing is wrong). Then, Section 4 proposes fixes for the Hu et al. framework using the Mandi and Guns framework.\n\nThe impression this leaves is that the authors' work is a bit incremental. As the authors acknowledge, their framework and the framework of Hu et al. are \"mathematically equivalent in expressiveness\". So the only difference is that the Hu et al. [9] paper develops a \"correction function\" and a \"penalty function\" whereas these authors solve an additional optimization problem (this optimization problem seems very similar to the one already proposed in Mandi and Guns).\n\nThe reason that I'm marking the \"Contribution\" as \"Fair\" is that I can't see anything except modifying Hu et al. to work more like Mandi and Guns.\n\n****\n\nI disagree with the authors that their approach \"should be the canonical framework for the Predict+Optimize setting\". The authors have a lot of impressive results, especially in comparison to Hu et al., but there are times where solving an optimization problem may take too long and it may be better to have a function that is quick-to-evaluate. \n\nThis small note (that the authors are claiming that it's always better to solve an optimization problem) is the only reason that I'm marking the \"Soundness\" as \"Good\" rather than \"Excellent\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and detailed review of our work. Below, we address the points you raise in \"weaknesses\".\n\n**Significance**: We believe there might be a misunderstanding of the main message of our work. Our point is not \"everything is better if we do it the way of Mandi and Guns\". In fact, Hu et al. also use the work of Mandi and Guns as a technical component for differentiating through LPs. As we argue, however, their high-level view of Predict+Optimize with unknowns in constraints, by imposing a correction function, is sub-optimal. As a result, they're using Mandi and Guns's work not in the best way possible. We give a simple change in perspective, which enables better algorithmic use of differentiating through LPs.\nPlease also refer to \"main message\" in our overall response for more details.\nWe also point out that, at least in our opinion (and a view that seems shared also by reviewers Pw5Y and Jj2a), a simple idea that leads to much better performance is valuable, instead of a downside on the quality of the work.\nThe fact that we presented a detailed comparison with the Hu et al. framework should also be a plus and not a minus.\n\n**Canonicity** of the framework: we agree that there is a tradeoff in runtime and learning capabilities/solution quality. We will tone down the claim in the paper by remarking *up front* the tradeoffs. Thank you for pointing out this nuance that we forgot to address. Please also see our overall response concerning the training times of these different approaches.\n\n**Literature**: While we have cited all the works that directly inspire our paper, we understand that we have indeed missed some related references. We are happy to incorporate and cite other missing works, and welcome additional suggestions. We additionally wish to point out that, as far as we understand, the Stuckey group and the Guns group are two distinct research groups on Predict+Optimize, despite Guns occasionally collaborating with the Stuckey group. The focuses on the groups also seem somewhat different: the Stuckey group seems to work more directly on combinatorial optimization whereas the Guns group works more on \"continuous\" optimization techniques as far as we can tell."}, {"review_id": "FRBBwo6x7y", "reviewer": "Reviewer_Xm8w", "summary": "The authors propose a framework for learning latent variables in optimization problems that appear both in the constraints and objective. In this setting, the user is given features and asked to provide a solution to an optimization problem where the objective and constraints of the optimization problem are partially observed and related to the features. Additionally, the user can optimally modify the solution once the true parameters are known at a cost based on the change. The overall goal is to ensure that the total regret is low where the regret is the total value of the final solution after fixing minus the fixing cost and minus the objective value of the optimal solution in hindsight. The authors propose that the second stage solution should be considered the output of an optimization problem which is given the first stage solution as input and then backpropagates through both optimization problems to update the weights of the predictive model predicting parameters for the first stage optimization problem. The authors propose differentiating through continuous relaxations of these optimization problems using previous work that differentiates through iterates of an interior point method.\n\nThe authors evaluate their approach on several settings to demonstrate improved predictive performance over the investigates baselines.\n", "questions": "Are there any specific reasons that previous work that learns constraints for LP or comboptnet are not applicable to the investigated settings?\n\nAre there any specific components of this method which are specialized to handle integrality that cannot be handled by simply applying previous approaches for differentiating through continuous problems?\n\nIt might be helpful to compare the gradients of this approach on a subjective level as well. In equation (3) are the gradients from one component relatively large compared to gradients from the other? How do they differ overall from previous work?\n", "limitations": "Relevant limitations are addressed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main strength of the work is that it considers penalizing the recourse using a flexible optimization problem rather than having a domain-dependent method of doing so as was done in previous work for packing and covering. Additionally, the paper itself is easy to read and ", "weaknesses": "Given that the main contribution of this work is that the framework has good empirical performance, it would be good to strengthen the experiments by evaluating against relevant baselines.\n\nThe work does not compare against relevant baselines and claiming generality to MILP to discount several differentiable continuous optimization baselines when in practice, the proposed approach simply relaxes the integrality constraints to consider differentiating through a continuous LP. Given that this approach considers differentiation of MILP with respect to the constraints as simply differentiating the constraints of the LP relaxation, the authors should evaluate against methods which can differentiate through constraints of an LP which includes cvxpylayers [1], and OptNet with quadratic regularization to differentiate through LP [2,3].\n\nAdditionally, the previous CombOptNet work [19 in the paper] which is formulated explicitly for learning constraints in combinatorial settings, and whose datasets are used for two of the three settings, is not compared against.\n\n\n[1] Agrawal, Akshay, et al. \"Differentiable convex optimization layers.\" Advances in neural information processing systems 32 (2019).\n[2] Amos, Brandon, and J. Zico Kolter. \"Optnet: Differentiable optimization as a layer in neural networks.\" International Conference on Machine Learning. PMLR, 2017.\n[3] Wilder, Bryan, Bistra Dilkina, and Milind Tambe. \"Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 33. No. 01. 2019.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for pushing us on running more experiments and comparing with more baseline methods, which strengthens the paper. We believe we have adequately addressed your concerns through the additional experiments presented in the overall response, along with the following discussion.\nWe are happy to answer any additional questions you may have.\n\n-----\n\nResponse to \"weaknesses\": originally, we didn't compare with cvxpylayers because cvxpylayers is a conic generalization of OptNet, and Mandi and Guns had already given empirical evidence that their approach is better than QPTL (which uses OptNet for differentiating through programs). However, after you pointed out the lack of comparison, we ran additional experiments comparing 2S with using cvxpylayers (without regularization, with quadratic regularization and with log-barrier regularization) in place of our Section 4 gradient computation approach. We find that (see Tables 1 and 2 in new pdf) 2S offers at least as good solution quality while being around 30-50\\% faster. Please see the overall response for more details and the precise description of the experiments.\n\nWe also added comparisons to CombOptNet, which is not designed to learn solutions to have good post-hoc regret, but rather, to learn $\\hat{x}$ that is close to the optimal $x^*$. Our additional experiments find that CombOptNet both has far inferior solution quality in post-hoc regret, takes far longer to train, and needs more data to have reasonable generalization. Please again see the overall response for more details.\n\n-----\n\n**Q1**:\nThey are applicable and we now have further experiments, see above and overall response.\n\n**Q2**: No, and we added experiments comparing 2S (using the Section 4 gradient computations) with using cvxpylayers (with different regularizations). Please see the above.\n\n**Q3**: This is a very interesting question. We re-ran the experiments for 2S to investigate. First note that in Equation 3, the terms correspond to gradients coming from the second and first stages of optimization respectively, and they have common factors that we will ignore. We find the following pattern: the gradients due to the second stage optimization is small compared to the first stage analogue. Furthermore, as the training continues, the gap widens. The effect is especially pronounced when the penalty factor is large. This can be explained by the fact that, if the penalty factor is large, then the model has incentive to give predictions that yield an $x^\\ast_1$ that will change minimally to $x^\\ast_2$ in the second stage optimization. Thus, as we train more and more, we can expect the $\\frac{\\partial x^\\ast_2}{\\partial x^\\ast_1}$ term to decrease in magnitude. The same effect persists, but in a less pronounced way, even when the penalty factor is smaller."}, {"review_id": "Zb1mx0tjSw", "reviewer": "Reviewer_Pw5Y", "summary": "The paper presents a novel '2-stage' framework for Predict+Optimize with uncertain parameters in the constraints. In the first \"stage\" a soft commitment is made based on the predictions, and in the second, the commitment is updated based on updated information in such a way that the objective value plus a penalty for deviating from the commitment is minimized. This generalizes the framework of Hu et al. [9] ", "questions": "1. In Table 3, the difference between 2S and the other methods *decreases* as the penalty factor increases. Why is that? I would have expected the opposite (as in Tables 2 and 4).\n1. On line 355 the paper says, \"On the other hand, the advantage of our 2S method over other approaches actually becomes more significant as the capacity increases, demonstrating the superior accuracy of our approach.\" However, the difference between 2S and other approaches for the lowest penalty factor actually decreases in absolute value?", "limitations": "The limitations are not described, despite having responded 'yes'. The fact that the paper does not acknowledge any of these limitations highlighted in the `weaknesses' section is worrying.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Great idea: I find the new framework simple and sensible, I think this is the right framework for Predict+Optimize with unknown constraints. The biggest plus is that it allows for improving soft commitments in which constraints aren't violated, which is not something that Hu et al. allow for, but makes a lot of practical sense. It also removes the need to create a differentiable projection.\n1. Clarity: The paper is well written and covers most bases (the tables could be bigger, though!)", "weaknesses": "1. Requires linear penalties: The penalties have to be linear in the decision variables. Hu et al. [9] doesn't require that.\n1. Is slower than Hu et al.: Because Hu et al. only require running a differentiable projection, which can be quite cheap, it is cheaper than 2S (Appendix E confirms this).\n1. Generalization of Hu et al.'s framework: While Hu et al. propose a specific projection that is limited to packing and constraint problems, there has been work in the literature about differential projections for enforcing feasibility constraints generally [A] and efficiently [B] that could be used instead. It would have been great to compare against those in the experiments.\n1. I understand that the space is limited, but a lot of important information, like the description of the experiments and runtimes are in the Appendix. It would have been useful to have summaries in the main text...\n\n_References:_\n\n[A] Chen, Bingqing, et al. \"Enforcing policy feasibility constraints through differentiable projection for energy optimization.\" Proceedings of the Twelfth ACM International Conference on Future Energy Systems. 2021.\n\n[B] Sanket, Shah, et al. \"Solving online threat screening games using constrained action space reinforcement learning.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 02. 2020.", "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.\nWe also appreciate the points you raised in the weaknesses section.\nPlease see our response below.\nThe paper is also further strengthened now by our additional experiments in the overall response.\nWe hope to further convince you of the merits of our work; please let us know if you have any additional questions.\n\n---\nResponse to \"weaknesses\":\n\n1. Linear penalties: thanks for pointing out that Hu et al. can handle non-linear penalties; we will add a comment to clarify in the paper. We also want to point out that our framework, as stated, can already handle special cases of non-linearity: for example, one can (in many cases) express the absolute-value function in linear programs. In addition, the Section 4/Appendix B gradient calculations can in fact be adapted to handle general differentiable non-linear objectives just like Hu et al., though of course the caveat that the second-stage optimization problem needs to be solvable efficiently for the framework to be useful. We chose to present only MILPs as a main overarching application for this paper mainly because of their widespread use in discrete optimization, with readily available solvers.\n\n2. Yes, training for 2S is slower than IntOpt-C, but as we pointed out in the overall response, the runtimes are quite comparable.\n\n3. The projection of [B] is identical to the correction function proposed by Hu et al. The projection of [A] on the other hand is $\\ell_2$ projection, which we hadn't compared against. For this rebuttal, we ran an experiment analogous to Table 1 in the main paper, for the alloy production problem (a covering LP) and the $\\ell_2$ projection. We find that the $\\ell_2$ projection performs even worse than the [B]/Hu et al. correction, for the linear penalty function used in the alloy production problem. Please see the overall response for more details.\n\n4. We did struggle with the page limit. If accepted, we will move more information to the main body of the paper, given the extra page available.\n\n---\n**Q1**: In Table 3, we omitted to present penalty factors $\\ge 1$ for space reasons. Additionally, in that problem setting (proxy buyer knapsack), large penalty factors are unrealistic anyway. We now include the corresponding rows here.\n\n| PReg    | Penalty factor |     2S     |    Ridge   |    k-NN    |    CART    |     RF     |     NN     |     TOV    |\n|---------|:--------------:|:----------:|:----------:|:----------:|:----------:|:----------:|:----------:|:----------:|\n|         |        1       | 10.90±0.15 | 10.93±0.19 | 11.11±0.17 | 11.16±0.14 | 11.01±0.31 | 11.26±0.23 |            |\n| cap=100 |        2       | 12.31±0.16 | 12.48±0.20 | 12.49±0.21 | 13.77±0.26 | 12.60±0.39 | 12.78±0.30 | 29.68±0.14 |\n|         |        4       | 14.54±0.15 | 15.57±0.25 | 15.68±0.39 | 19.01±0.56 | 15.77±0.62 | 15.84±0.50 |            |\n|         |        1       | 10.23±0.12 | 10.46±0.23 | 10.40±0.18 | 10.46±0.19 | 10.49±0.21 | 10.86±0.30 |            |\n| cap=150 |        2       | 11.18±0.15 | 11.88±0.30 | 11.63±0.20 | 12.56±0.31 | 11.83±0.19 | 12.12±0.17 | 40.23±0.19 |\n|         |        4       | 13.20±0.16 | 14.71±0.49 | 14.43±0.33 | 16.75±0.63 | 14.53±0.29 | 14.65±0.41 |            |\n|         |        1       |  6.77±0.36 |  7.67±0.18 |  7.51±0.27 |  7.71±0.20 |  7.67±0.16 |  8.00±0.65 |            |\n| cap=200 |        2       |  8.19±0.12 |  8.84±0.22 |  8.69±0.26 |  9.24±0.30 |  8.80±0.20 |  8.97±0.37 | 48.13±0.24 |\n|         |        4       |  9.71±0.35 | 11.17±0.40 | 11.06±0.32 | 12.29±0.59 | 11.05±0.46 | 10.91±0.53 |            |\n|         |        1       |  1.37±0.08 |  3.08±0.19 |  2.94±0.16 |  3.17±0.17 |  3.05±0.25 |  3.28±0.96 |            |\n| cap=250 |        2       |  3.34±0.15 |  3.80±0.20 |  3.73±0.15 |  3.94±0.20 |  3.79±0.26 |  3.89±0.58 | 53.43±0.26 |\n|         |        4       |  4.46±0.09 |  5.25±0.35 |  5.32±0.27 |  5.47±0.35 |  5.29±0.48 |  5.11±0.39 |            |\n\nAlong with these extra rows, we can see that the trend of Table 3, in terms of the difference between 2S and other methods, is in fact identical to the trend in Table 2. The difference first decreases, then increases, as the penalty factor increases. We can explain this phenomenon as follows.\n\nFirst, when the penalty factor is small, the rational behavior for the buyer is to just take every order, and only decide which orders to drop when the true parameters are revealed (at close to no cost). 2S identifies and exploits this behavior for small penalty, while classic regression methods are agnostic to this possible tactic. Thus, the advantage of 2S compared to classic regression methods is large in the small penalty case.\n\nSecond, when the penalty factor is large, 2S will analogously learn to be conservative, such that the first stage solution likely remains feasible under the true parameters, in order to avoid the necessary (and high) penalty due to having to change to a feasible solution. Again, classic regression methods will be agnostic to this possible tactic, leading to a large advantage of 2S over the classic methods.\n\nTable 4 only has the increasing trend from the large penalty, since it is neither a covering nor a packing program, and so there is no analogous tactic/exploitation for small penalty.\n\n**Q2**: Here, \"advantage\" refers to the improvement in *percentage* of our method over other approaches.\nTake penalty factor = 0.05 as an example, the improvement percentage is (8.67 - 1.26)\\%/8.67\\% = 85.47\\% when capacity is 100, 91.37\\% when capacity is 200, 94.73\\% when capacity is 300, and 96.79\\% when capacity is 400.\nWe will clarify in the paper.\n\n---\nLimitations: as discussed above, we will clarify the points you raised in the paper. Thank you for pointing them out."}, {"review_id": "wlV5sT7hEC", "reviewer": "Reviewer_Jj2a", "summary": "Predict+Optimize is an emerging paradigm that lies in the intersection of classical optimization (particularly mixed integer programming) and machine learning. Specifically, it considers the setting where a parameterized optimization problem:\n$$ x^{\\star}(\\theta) = \\operatorname*{argmin}_{x} f(x;\\theta) \\text{ subject to } C(x;\\theta) $$\nmust be solved yet the parameters $\\theta$ are unknown. Here $C(x;\\theta)$ represents constraints that must be respected, which could be equality, inequality, or inclusion. In the last 4--5 years this topic has seen heightened interest. Most approaches, including the one proposed in this paper, assume access to observed features $A$ that correlate with $\\theta$, and aim to learn a predictor $f(A)$ so that $\\hat{\\theta} := f(A) \\approx \\theta$. Then, a problem of the form above is solved with $\\hat{\\theta}$ in place of $\\theta$ to yield a predicted minimizer $x^{\\star}(\\hat{\\theta})$. Hopefully,  $x^{\\star}(\\hat{\\theta}) \\approx x^{\\star}(\\theta)$.\n\n\nThe paper in question is one of the first to actively consider the setting where the constraints depend on $\\theta$; prior work mostly considered constraints of the form $C(x)$. The method proposed is interesting, intuitive and general. They start from the observation that any scheme handling parametrized constraints must be allowed to make post-hoc adjustments to $x^{\\star}(\\hat{\\theta})$  after the true parameters $\\theta$ are revealed, as $x^{\\star}(\\hat{\\theta})$ might not be feasible. Thus, they propose to solve a second, penalized problem:\n\n$$ x_2^{\\star} = \\operatorname{argmin}_x f(x;\\theta) + r(x^{\\star}(\\hat{\\theta}), x) \\text{ subject to } C(x;\\theta) $$\n\nwhere $r(\\bullet, \\bullet)$ penalizes the discrepancy between the stage 1 solution $x^{\\star}(\\hat{\\theta})$ and the stage 2 solution $x_2^{\\star}$.  \n\nThe bulk of the paper is devoted to motivating, introducing and implementing this proposed new method. Numerical experiments illustrate that this new method performs well. Finally, there is a little bit of theory (contained in the appendix) relating this new approach to older approaches to predict+optimize with parametrized constraint sets.\n\n\n ", "questions": "- The two-stage nature of your proposed approach reminds me a lot of Model-agnostic Meta-Learning (MAML) [2]. Moreover, I think there is an interesting analogy between the connection between your work and that of Hu et al [3] and the connection between MAML and later implicit MAML (I-MAML) works [4]. I think the appeal of your work could be broadened by adding a discussion of this connection.\n\n- An interesting variant of predict+optimize is the setting where at train time the true cost vectors ($c$ in the notation of your equation (4)) are never revealed, rather only the true solutions $x^{\\star}$ are accessible (see [1] for a discussion on this). Do you have any thoughts on how to extend your approach to this setting?\n\n[1]  _Faster predict-and-optimize using three-operator splitting_ McKenzie _et al_, 2023\n\n[2] _Model-agnostic meta-learning for fast adaptation of deep networks_ Finn _et al_, 2017\n\n[3] _Predict+Optimize for packing and covering LPs with unknown parameters in constraints_ Hu _et al_ 2022\n\n[4] _Meta-learning with implicit gradients_ Rajeswaran _et al_, 2019.\n\n-----\n\nAfter discussion with the authors I've raised my score 6--> 7\n\n-------", "limitations": "As mentioned above, I think the computational complexity of the proposed approach could be a limitation. This should be discussed.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- I agree with the assertion in the appendix that the proposed approach is _simple and powerful_. I think this is an elegant solution to an important problem.\n- The paper is well-written; I did not find any typos or unclear sentences. The running example of stocking a store is useful.\n- I appreciated the choice of experiments---they are closer to \"real-world\" problems than many experiments I have encountered in Neurips papers.\n- The Appendices are thoughtfully written, addressing many potential reader's questions and providing several nice extensions of the model at hand.\n- The framework proposed is indeed original, but I think some additional comparisons with existing literature is needed, see \"weaknesses\".\n\n\n", "weaknesses": "- With regard to novelty, I think the authors should compare their work to various differentiable quadratic program (QP) solvers. For example, in [1] formulas for the derivatives of $x^{\\star}$ with respect to constraint (_e.g._ $\\partial x^{\\star}/\\partial A$, to reference the notation of your equation (5)) are given. Note that the MILP in (4) can be turned into a QP by using a quadratic regularizer (as done in [2]) instead of the logarithmic regularizer of Mandi & Guns.\n\n - I found the use of the name \"Two-stage Predict+Optimize\" for your proposed framework a bit confusing. In much of the Predict+Optimize literature, the two-stage approach refers to the approach of training a predictor $f(A)$ to minimize the mean square error $\\|f(A) - \\theta\\|^2$ (see for example [3]) I strongly suggest you add a remark  discussing this towards the beginning of your paper.\n\n- I think the benchmarks considered are a little weak. For example, all 5 classical regression methods are slight variations on the \"two-stage approach\" mentioned above. You should include some SOTA approaches for (one-stage) predict+optimize, e.g. training with the SPO+ loss, Perturbed Optimization [7], blackbox backpropagation [8] etc or justify why such approaches are incompatible with the proposed Two-Stage Predict+Optimize framework. The PyEPO benchmarking suite [4] could be useful.\n\n- I'd like to see more discussion on the computational cost of your proposed approach. Given that it is a tri-level (!) problem, I think this is something to address. For the experiments, could you indicate the dimension of $x$ and the number of constraints, as well as the time required to train using the 2S and IntOpt-C approaches? It might be nice to add a remark about possible approaches to scaling your proposed framework, see [5,6].\n\n[1] _Optnet: Differentiable optimization as a layer in neural networks_ Amos & Kolter, 2017.\n\n[2] _Melding the data-decisions pipeline: Decision focused learning for combinatorial optimization_ Wilder _et al_, 2019\n\n[3] _Interior point solving for LP-based prediction+optimization_ Mandi & Guns, 2020\n\n[4] _PyEPO: A PyTorch-based end-to-end predict-then-optimize library for linear and integer programming_ Tang & Khalil 2022\n\n[5] _Faster predict-and-optimize using three-operator splitting_ McKenzie _et al_, 2023\n\n[6] _Backpropagation through combinatorial solvers: Identity with projection works_, Sahoo _et al_, 2022\n\n[7] _Learning with differentiable perturbed optimizers_ Berthet _et al_, 2020\n\n[8] _Differentiation of blackbox combinatorial solvers_ Vlastelica _et al_, 2019\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your positive review of our paper, concrete suggestions and also your questions. We respond to your points below to address your remaining reservations about our work. Hopefully you are more convinced by our contributions. Please let us know if you have any additional questions.\n\n-----\n\nResponse to \"weaknesses\":\n\n1. We added comparisons to cvxpylayers using quadratic regularization (and no regularization and log-barrier regularization). Please see the overall response and our response to reviewer Xm8w.\n\n2. We will clarify in the paper, thank you for pointing this out.\n\n3. One-stage Predict+Optimize methods referenced in the review, by definition, cannot handle unknown parameters in constraints (since Hu et al. was the first Predict+Optimize framework for unknowns in constraints), and therefore they do not apply and are incompatible with our new Two-Stage Predict+Optimize framework. See also Table 1 in the PyEPO paper for reference. Moreover, we added additional comparisons with cvxpylayers.\n\n4. For the experiments in the paper, see the following table for the number of decision variables (dimension of $x$), constraints, unknown parameters and features. Training times are reported in Appendix E, and as discussed in the overall response, 2S has rather comparable training time compared with IntOpt-C. In the rebuttal experiments, our training times are also faster than using cvxpylayers instantiated using various regularizations.\nWe agree that it is an interesting future work direction to speed up training and further improve the training-time scalability; the main focus of our work is on getting good learning performance.\n\n| Problem name                 | Brass alloy production | Titanium-alloy production | 0-1 knapsack | Nurse scheduling problem |\n|------------------------------|:----------------------|:-------------------------|:--------------|:--------------------------|\n| Dimension of $x$        | 10           |             10            |      10      |            315           |\n| Number of constraints  |   12           |             14            |      21      |            846           |\n| Number of unknown parameters | 20           |             40            |      10      |            21            |\n| Number of features (per parameter) |4096          |            4096           |     4096     |             8            |\n\n------\n\n**Q1**: Thank you for pointing out the high-level similarities between our framework and that of MAML. Here is a brief comparison between the two.\n\n*Similarities*: In both MAML and our setting, the prediction isn't evaluated/used directly. Instead, after prediction happens, new information is revealed by the environment that allows us to adapt the model. In our framework, this is the second stage optimization after the true parameters are revealed. In the meta-learning setting, it is the true task being revealed, and the model can be fine-tuned. Training needs to be aware of this adaptation, in order to perform well.\n\n*Differences*: The most important difference of course is that the adaptations are quite different: second stage optimization (our setting) vs fine-tuning (meta-learning). Also, in MAML, there are no features for the future task, and the future task is drawn purely distributionally (and we assume that the training algorithm has access to samples). On the other hand, in Two-Stage Predict+Optimize, we have features for predicting the true parameters. In this sense, MAML is closer to traditional stochastic programming, and our framework in a sense is a *contextual* variant. Though of course, one could plausibly also formulate a contextual version of MAML to bring it closer to our setting.\n\n**Q2**: This is a really interesting question, and we believe it is enough scope for another paper. Here we present our initial thoughts on the problem, with basic theory. It remains to empirically test whether this approach would actually work.\n\nWe'll consider the same two-stage setting as in our paper, where we get features in the first stage, need to make a soft commitment using predictions, and then once the true parameters are revealed we solve for a second stage solution.\nThe difference is that, now, for training, we get feature-solution pairs $(A, x^\\ast)$, where $x^\\ast$ is the optimal solution under the true parameters $\\theta$, instead of feature-(true parameter) $(A,\\theta)$ pairs.\n\nAssuming the penalty is non-negative and that the penalty for no solution modification is 0, we train a predictor $\\hat{\\theta}(A)$ so as to minimize\n$Pen(x_1 \\to x^\\ast,\\hat{\\theta}(A))$\nwhere $x_1 = \\mathrm{argmin}\\text{ } obj(x, \\hat{\\theta}(A))$ s.t. $C(x, \\hat{\\theta}(A))$ holds.\n\nThis is somewhat similar to what McKenzie et al. already does, except that our first stage optimization also has unknowns in constraints, and that we use the problem-specific penalty function as opposed to a generic l2 loss.\n\nNote the following two basic lemmas justifying this training loss, which are straightforward to prove:\n\n1. It is minimized at $\\hat{\\theta}(A)$ that induces $x_1 = x^\\ast$, yielding a training loss of 0. So for example, $\\hat{\\theta}(A) = \\theta$ is a minimizer.\n\n2. Suppose further that the penalty function has no explicit dependence on the unknown parameters, and only depends on the first and second stage solutions. Then, for every $\\hat{\\theta}(A)$, we have $\\text{training loss} + obj(x^\\ast,\\theta) = Pen(x_1 \\to x^\\ast) + obj(x^\\ast, \\theta) \\ge Pen(x_1 \\to x_2) + obj(x_2, \\theta) = \\text{test loss}$, where $x_2$ is the second stage solution induced by the predicted parameters $\\hat{\\theta}(A)$ and the true parameters $\\theta$.\nSince $obj(x^\\ast,\\theta)$ does not depend on the predictions $\\hat{\\theta}(A)$, it does make sense to train to minimize the training loss, in order to minimize the test loss.\n\nWe believe that this is a reasonable starting point for this different Predict+Optimize problem, but this is out of the scope of the current paper."}]

Author rebuttal:
Thank you for your constructive and in-depth feedback for improving the paper.
We are encouraged by the reviewers recognizing that our paper 1) tackles an important problem (reviewers FnYQ, Jj2a) in Predict+Optimize, 2) presents a simple/sensible, elegant and flexible solution (reviewers Pw5Y, Jj2a, Xm8w), and 3) gives experiments that are close to real-life (reviewers FnYQ, Jj2a).
We are also grateful for the constructive criticisms which can improve our paper.
In this overall response, we wish to emphasize again the main conceptual contribution of this paper, as well as address the criticisms on our experiments and citations.
We will additionally respond to remarks and questions separately for each individual review.

We believe that our rebuttals below have adequately addressed your criticisms, and hope that you will improve your evaluation of our work based on these responses. Please let us know if you have remaining concerns. We will address them.

**Main message**: While Hu et al. gave the first Predict+Optimize framework to handle unknowns in constraints, their framework required specifying an ad-hoc correction/recourse/differentiable projection. In this work, we provide a *simple* change of perspective (Section 3), viewing the recourse action itself *naturally* as the solution of an optimization problem. This simple change (a) yields much better test-time performance (see e.g. experiments in Table 1 in the paper), (b) allows for post-hoc correction even when the stage 1 solution (a soft commitment) doesn't violate constraints under the true parameters (as was recognized by reviewer Pw5Y), and (c) enables the algorithmic training methodology for generalizing to handle MILPs in Section 4. We emphasize that, especially in the context of frameworks, simplicity and the associated flexibility is a virtue and not a downside (as was recognized by reviewers Pw5Y, Jj2a, Xm8w).

**Experiments**: Thank you for pushing us on additional experiments, which strengthen the empirical part of our paper. Based on reviewer feedback, we ran two new experiments comparing with the suggested methods.

1. We applied cvxpylayers and CombOptNet to the 0-1 knapsack benchmark to compare with our 2S method. See Table 1 in the new pdf for post-hoc regrets and Table 2 for the training times. More precisely, for cvxpylayers, we use it with various regularizations (a. LP with no regularization, b. with quadratic regularization, c. with log-barrier as in our paper) to replace the Section 4/Appendix B gradient calculations. For CombOptNet, we just run it as is, since it is a method for learning unknowns in constraints. These methods are evaluated at test-time using the Two-Stage framework, as we did in the paper.\
We find that cvxpylayers never gives better solution quality while 2S is 30\%--50\% faster. For CompOptNet, the solution quality is very bad, since it was designed to learn a first-stage solution $\hat{x}$ close to $x^\ast$ and not learning for small post-hoc regret. CompOptNet is also drastically slower. We further observe that, using only 700 training samples (as in the experiments in the paper and rebuttal), CompOptNet does not have good generalization. Only with the full 4500 training samples in the CombOptNet paper do we get some reasonable generalization. See Figures 1-4 for training+test loss curves (using loss $\|\hat{x}-x^\ast\|^2$), for 700 training samples (Figures 1,2) and 4500 training samples (Figures 3,4). This is evidence that CompOptNet is more data-hungry than our 2S method.

2. We tested the differentiable projection idea in references [A,B] given by reviewer Pw5Y, on the Alloy Production benchmark. The projection in [B] is identical to the Hu et al. correction function, and so we only additionally tested the $\ell_2$ projection method in [A], implemented using cvxpylayers. The experiment set-up follows that of Table 1 in the submission: both training and testing use $\ell_2$ projection in the second stage, as opposed to solving the second stage optimization problem defined in Section 3. Table 3 in the new pdf shows both the post-hoc regret and training time for $\ell_2$ projection. We find that, not only is $\ell_2$ projection slow, but it has even worse post-hoc regret than the Hu et al. correction. We suspect that this is due to the Hu et al. correction function preserving the direction of the solution vector whereas $\ell_2$ projection can change the direction, and that this makes a difference for Alloy Production. In any case, this experiment confirms again that our Two-Stage framework has better post-hoc regret than a framework based on differentiable projections, reinforcing the main message of our paper.

**Runtime**: Appendix E gives the training time for each method tested in the submission. In the Alloy Production problem, which is the *only* setting where the Hu et al. IntOpt-C method can be applied, their running time is quite comparable with our proposed 2S method. In the additional experiments in the rebuttal (see Tables 2,3 in the new pdf), the 2S method is also faster to run than cvxpylayers and CombOptNet, while offering at least as good and sometimes substantially better learning performance. We believe that our method presents a reasonable tradeoff between runtime and learning in practice. If accepted, we will use the extra page to include a runtime discussion in the main paper.

**Literature**: We thank the reviewers for the additional references. The Predict+Optimize literature, and more generally the decision-aware learning literature, is rapidly growing in recent years, with different research groups even sometimes calling the same concepts different names. As such, it has become increasingly difficult to keep track of all the relevant literature. While we have cited all the works that directly inspire ours, we have nonetheless missed some other. We are grateful for the reviewers pointing us to works we have missed, and will address them in the paper.

Meta-review: The reviewers agree that the paper addresses an important problem (unknown parameters in the constraints) in Predict+Optimize with thorough experiments including detailed ablations and comparison with multiple baselines. The idea is also quite nice, paper well-written and easy to follow. The negative reviewer also agreed that the concerns regarding to literatures are also addressed.
Decision: Accept (poster)