A Surrogate Objective Framework for Prediction+Programming with Soft Constraints
Authors: Kai Yan
Jie Yan
Chuan Luo
Liting Chen
Qingwei Lin
Dongmei Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: prediction
optimization
surrogate objective
soft constraint
linear programming
quadratic programming

Abstract: Prediction+optimization is a common real-world paradigm where we have to predict problem parameters before solving the optimization problem. However, the criteria by which the prediction model is trained are often inconsistent with the goal of the downstream optimization problem.  Recently, decision-focused prediction approaches, such as SPO+ and direct optimization, have been proposed to fill this gap.  However, they cannot directly handle the soft constraints with the max operator required in many real-world objectives.  This paper proposes a novel analytically differentiable surrogate objective framework for real-world linear and semi-definite negative quadratic programming problems with soft linear and non-negative hard constraints. This framework gives the theoretical bounds on constraints’ multipliers, and derives the closed-form solution with respect to predictive parameters and thus gradients for any variable in the problem.  We evaluate our method in three applications extended with soft constraints: synthetic linear programming, portfolio optimization, and resource provisioning, demonstrating that our method outperforms traditional two-staged methods and other decision-focused approaches

A Surrogate Objective Framework for Prediction+Optimization with Soft Constraints
Kai Yan"
Jie Yan Microsoft Research Beijing, China j jiey@mi com com
Department of Computer Science University of Illinois Trbana-Champaigh Urbana, IL 61801 kaiyan3@illinois.. edu
Chuan Luo
Liting Chen" Microsoft Research Beijing, China
Qingwei Lin
Microsoft Research
Microsoft Research Beijing, China
Beijing, china
chuan. www.eoicooooottccoo.o com
98chenliting@gaal.cco com
glinemicrosoft.com com
Dongmei Zhang Microsoft Research Beijing, China
dongmeizumicroseee
Abstract
Prediction-optimizatinn is a common real-world paradigm where we have to pre- dict problem parameters before solving the optimization problem. However, the criteria by which the prediction model is trained are often inconsistent with the goal of the downstream optimization problem. Recently, decision-focused pre- diction approaches, such as SPO+ and direct optimization, have been proposed fill this gap. However, they cannot directly handle the soft constraints with the mar operator required in many real-world objectives. This paper proposes novel analytically differentiable surrogate objective framework for real-worke linear and semi-defing negative quadratic programming problems with soft linear and non non-negative hard constraints. This framework gives the theoretical bounds constraints" multipliers, and derives the closed-form solution with respect to predictive parameters and thus gradients for any variable in the problem. We evaluate method in three applications extended with soft constraints: synthetic linear programming, portfolio optimization, and resource provisioning, demon- strating that our method outperforms traditional two-staged methods and other decision-focused approaches.
Introduction
Mathematical optimization (a.k.a. mathematical programming), c.g., linear and quadratic program- ming, has been widely applied in decision-making processes, such as resource scheduling M. goods production planning (2), portfolio optimization [3]. and power scheduling [4] In practice, problem parameters (e.g., goods demands, and equity returns) are often contextual and predicted by models with observed features (c.g.. history time series). With the popularity of machine learning techniques and increasing available data, prediccionn-opiinzzaioon has become a normal paradigm [5]
"Contributed during internship Microsoft Research. Corresponding Author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Prediction becomes critical to the performance of the full prediction--opimiiationn workflow since modern optimization solvers (e.g., Gurobi 66] and CPLEX 777 can already efficiently find optimal solutions for most large scale optimization problems. Traditionally, prediction is treated separately as a general supervised learning problem and learned through minimizing a generic loss function (e.g.. mean squared error for regression). However, studies have shown that minimization of the fitting errors does not necessarily lead to better final decision performance [ 9 [.]
Recently a lot of efforts on using optimization objective to guide the learning of prediction models have been made, which are decision-focuse when training prediction models instead of using traditional prediction metrics, e.g. mean squared error losses. For linear objectives, the 'Smart Predict then Optimize' ((TO) proposes the SPO+ loss function to measure the prediction errors against optimization objectives, while direct optimization ((12) updates the prediction model's s parameters by perturbation. For quadratic objectives, OptNet [L3 14] implements the optimization as an implicit layer whose gradients can be computed by differentiating the KKT conditions and then back propagates to prediction neural network. CVXPY [15 uses similar technologies with OptNet but extends to more general cases of convex optimization. However, all the above state-of-the- ofttt--rttttt approaches do not contain the soft constraints in their objectives. soft-constraints', penalty in the form of max(z, 0), where Cx d is projection of decision variable x E R" and context variables C' E m Xm d E RT. Such soft constraints are often required in practice: for example, they could be the waste of provisioned resources over demands or the extra tax paid when violating regulatory rules. Unfortunately, the max(-, 0) operator is not differentiable and thus cannot be directly handled by these existing approaches. To differentiate soft constraints is primary motivation of this paper.
this paper, We consider linear
In this paper, we derive surrogate objective framework for a broad set of real-world linear and quadratic programming problems with linear soft constraints and implement decision- dif- ferentiable predictions, with the assumption of non-negativity of hard constraint parameters. The framework consists of three steps: 1) rewriting all hard constraints into piece-wise linear soft constraints with a bounded penalty multiplier; 2) using differentiable element-wiss surrogate to substitute the piece-wise objective, and solving the original function numerically to decide which segment the optimal point is on; 3) analytically solving the local surrogate and obtaining the gradient; the gradient is identical to that of the piecewise surrogate since the surrogate is convex/concave such that the optimal point is unique.
Our main contributions are summarized as follows. First, we propose a differentiable surrogate objec- tive function that incorporates both soft and hard constraints. As the foundation of our methodology, in Section 3 we prove that, with reasonable assumptions generally satisfied in the real world, for linear and semi-definite negative quadratic programming problems, the constraints can be transformed into soft constraints; then we propose an analytically differentiable surrogate function for the soft constraints max(-, 0). Second, present the derived analytical and closed-fone solutions for three representative optimization problems extended with soft constraints in Section 4 - linear programming with soft constraints, quadratic programming with soft constraints, and asymmetric soft constraint minimization. Unlike KKTT-based differentiation methods, our method makes the calculation of gradients straightforward for predicting context parameters in any part of the problem. Finally, apply with theoretical derivations and evaluate our approach in three scenarios, including synthetic linear programming, portfolio optimization, and resource provisioning in Section 4, empirically demonstrate that our method outperforms two-stage and other predict-optimization approaches.
2 Preliminaries
2.1 Real-world Optimization Problems with Soft Constraints
Our target is solve the broad set of real- real-world mathematical optimization problems extended with mar(2, 0) term in their objectives where z depends on decision variables and predicted context parameters. In practice, maz(2, 0) is very common; for example, it may model overhead of under- provisioning, previiooviionnnn of goods, and penalty of soft regulation violations in investment portfolios. We call the above mar(2, 0) term in an objective as soft constraints, where z S is allowed to violate long the objective improves.
2

---

The general problem formulation is max g(0, 2) a" 0), 2 Cx - d, s.t. Ax S b, Br - c, x 20
(I)
x
where g is utillity function, _ the decision variable, and 0 E I2 the predicted parameters.
Based on observations on a broad set of practical problem settings, we impose two assumptions on the formulation, which serves as the basis of following derivations in this paper. First, we assume A E _ 2 0, b E I 2 O. B E R==xx= Z 0 ,and с E I 2 hold. This is because for problems with constraint non-negative. Second, we assume the linearity of soft constraints, that is = C2 d, where C E R==sxn, and d IRms, This form of soft constraints make sense in wide application
weights, quantities or their thresholds, these parameters are naturally
E R situations when describing the penalty of goods provisoiovi or over-provisioning, a vanish in marginal profits, or running out of current materials.
Now we look into three representative instances of Eq extracted from real-world applications.
Linear programming with soft constraints, where ((z, 0) = 6Txx. x. The problem formulation
max 8 x - o² max(Cr - d, 0), s.t. Az S b, Bæ = 2 2 0
(2)
where a 2 0. Consider the application of logistics where 0 represents goods' prices, (A, B, C) are the capability of transportation tools, and [b, ct are the thresholds. Obviously, A, b, B, c 2 0 hold.
Quadratic programming with soft constraints, where g(0,x) = 0 - x Qz. One example is the classic minimum variance portfolio problem [T6] with semi-definite positive covariance matrix Q and expected return 0 to be predicted. We extend it with soft constraints which, for example, may represent regulations on portions of equities for some fund types. Formally with a 2 0, we have:
max ="Qq= a" max(Crr d..). Br x x 0.
(3)
Optimization of asymmetric soft constraints. This set of optimization problems have the objective to match some expected quantities by penalizing excess and deficiency with probably different weights. Such formulation represents widespread resource provisioning problems, e-g. power and cloud resources where we minimize the cost of under-provisioning and over-provisioning against demands. Formally with 011, Q22 > O, we have:
max-(al max(Cx d) az max(d Cx, 0)), s.t. Ba c, x 0.
(4)
In this paper, we consider a challenging task where C' a matrix to be predicted with known constants d. In reality, the Cx d term may represent the "wasted" part when satisfying the actual need of d.
2.2 PrediitionnOOpiimizztioo
For compactness we write Eq as max f(z, 0), where f is the objective function and X' is the feasible domain. The solver for f is to solve x² argmax (x. 0). With parameters known, 2 can be solved by mature solvers like Gurobi [6] and CPLEX 77.
In prediction-oopimiiztionn, 0 is unknown and needs to be predicted from some observed features g E E. The prediction model is trained on a dataset = {(E,, 0.) this paper, we consider the prediction model, namely Φ neural network parameterized with 1.. In traditional supervised learning, & is learned by minimizing a generic loss, e.g., LI (Mean Absolute Error) or L2 (Mean Squared Error), which measures the expected distance between predictions and real values. However, such loss minimization is often inconsistent with the optimization objective f. especially when the prediction model is biased ....
Instead, decision focused learning directly optimizes ta with respect to the optimization objective f. that is, max, E(g,o)~D (x (E)). 0)). The full computational flow is illustrated in Fig In the gradient-based learning, update of ii's gradient is 8r 88 Bu' or where utility r= fx 0). Re
The Jacobian 00/0 0/ is computed implicitly by auto-diifeereniiation of deep learning frameworks (e.g, PyTorch 17 ). and Ôr trrā is analytical. The main challenge is to compute dx /00, which depends on differentiating the argmax operation. One recent approach is to rewrite the objective to be convex (by adding quadratic regularizer if necessary), build and differentiate the optimality conditions (c.g..
3

---

arg fx, 0)
dr
dy
f 0
Figure Computation graph of the decision-focusse prediction methods.
which map θ to the solution 2²,, and then apply implicit function theorem to obtain Oz" /80. Alternatively, in this paper we propose novel approach that rewrites the problem as an unconstrained problem with soft constraints and derives analytical solutions, based on our observations on the real-world problem structures and coefficient properties.
KKT conditions) 18
Methodology
Our main idea is derive a surrogate function for f with closed-form solution such that the Jacobian dr is analytical, making the computation of gradient straightforward. Unlike other recent work [13] 14 [5] 31, our method does not need to solve KKT optimality condition system. Instead, convert the constrained problem into unconstrained one. With the assumption concavity, we prove that there exist constant vectors B1, B2, 83, such that [en be equivalently transformed into unconstrained problem:
by adding reasonable costs for infeasibility,
max L(x) max g(2, 0) aa maxx(x=d,00) - max(Ar - b. (0-0))3 3 Br- 33 max(- (5)
The structure of this section is as follows. Section 3.1 proves that the three types of hard constraints be softened by deriving bounds of 31, B2, By for this paper, we will assign each entry of the three vectors the equal value (with a slight abuse of notation, we denote 3, = 32 = B3 = 33 for the proofs of bounds;
align with the worst bound applicable to the problem formulation.) Section de 3.2 proposes a novel surrogate function of max(-, 0), such that the analytical form of 20 can be easily derived via techniques of implicit differentiation (18) and matrix differential calculus [19] on equations derived by convexity (20). Based on such derived 0e we develop our end-to-end learning algorithm of prediction--ptimizzaion whose detailed procedure is described in Appendix C.
3.1 Softening the Hard Constraints
For any hard constraints w = Ar b S O, we denote its equivalent soft constraints as H(w) 3T max(w, 0). (w)) should satisfy two conditions: 1) for
(feasible r), Hww) 0; 2) for w 2 (infeasible r). Hww) is larger than the utility gain(i.e., improvement of the objective value) R f(z 0) Aa <b fI1, 0) by violating Ar - b < 0. Intuitively, the second condition requires a sufficiently large-valued / O to ensure that the optimization on the unconstrained surrogate objective never violates the original Ax. < b; to make this possible,
assume that the bounded by constant E. The
12-norm of the derivative of the objective f before conversion difficulty of requirement 2) is that the distance of point to the convex hull / is not bounded by the sum of distances between the point and each hyper-plane in general cases, so the utility gain obtained from violating constraints unbounded. Fig. (a) shows such an example which features the small angle between hyper-planes of the activated cone. We will refer such kind of 'unbounding' as "acute angles" below.
The main effort of this subsection is to analyze and bound the effect caused by such acute angles. Given a convex hull C (z R= < b) (A > is required here) and any point C, let To E C be the nearest point of C to x, and A'x : 2 represent all active constraints at x. then all such active constraints must pass through mo The domain K. {= E A'= 2 8/} is cone degraded
Otherwise, there must exist an active constraint and a small neighbourhood of Zo. say B(2a, c), such that Zz B(zo.e) c). Aiz- by * 0, which implies that either constraint is inactive (< 0) or zo C 0).

---

X (a) 2D acute angle
(b) 3D acute angle
(c) Non-degraded cone
(d) Degraded cone
Figure 2: (a) and (b) are 2 and 3-dimensional "acute angles"; (c) and (d) shows two corresponding activated cones for given acute angles. The green area is the feasible region, is the red point and zo is the yellow point; the red is the derivative of an objective g(z, 0) = 0² x.
cone where the tip of the cone is a subspace of R" For the rest of the paper, we will call K. activated cone, as shown in Fig. Note that for any degraded activated cone, x 2g is always perpendicular to the tip subspace; therefore, we may project the cone onto the complementary space of the tip and get the same multiplier bound on the projected activated cone with lower dimensions.
Ideally, we aim to eliminate the utility gain R obtained from violating A'x < 1' with the penalty (A''x b'), d').... i.e., ensure 3 (A'x b') 2 R hold for any æ. For the compactness of symbols and simplicity, we will assume that the main objective is g(z, f) = 0 x in this section; however note that our proofs upply with the existence of soft constraints and quadratic terms g. which is discussed at the beginning of Appendix A. With such assumption, we now give a crucial lemma, which is the core of our proof for most of our theorem:
Lemma 1. (Bounding the utility gain) Let f(x, max f 0) be the utility gain, then S f(x,0) f 8) S cos 1A 61), where x is an infeasible point, A'x S b' the active constraints at x, po L(A"", ,0) where A!" and 0 are the optimal solution of maxg minA; cos,(A', 0) (i.e., the maximin angle between O and any hyperplane of the activated cone K {2 E R2 2n E (o))( and no the projection of x to the tip of cone C = {2 E A'' 2 b¹). E is the upper bound of
((.-)) denotes the angle of two vectors.
Thus, cos po
a feasible choice of 3, and it suffices by finding the lower bound for cos Po- For the rest of the section, we find the lower bound of cos by exploiting the assumed properties of A', e.g, A' > 0; give the explanation of the full proofs for all theoretical results in Appendix A.
3.1.1 Conversion of Inequality Constraints Ar <b
Let us first consider the constraints w = AA - b < O, where 2 0, 2 is easy to prove that given A 2 0 and b > O, the distance of point the convex hull Ax S b is bounded. More rigorously, we have the following theorem, which guarantees the feasibility of softening the hard constraints of inequalities Ar < b:
Theorem 2. Assume the optimization objective 8T with constraints Ax S b, where A 0. and b > 0. Then, the utility gain R obtained from violating Ar - b S 0 has an upper bound of O max(w;; F). where w A'r bi, and A'r S V/ is the active constraints.
3.1.2 Conversion of Inequality Constraints x 2
With inequality constraints Ar < b converted, we now further enforce x 2 0 into soft constraints. It seems that the constraint of this type may form very small angle to those w Ar However, as -r is aligned with the axes, we can augment x 2 0 into soft constraints by proving the following theorem:
Theorem 3. When there is at least one entry of 2 in the activated cone, the utility gain R from deviating the feasible region is bounded by O(" "E, moz(w,))) ), where p is the smallest angle between axes and other constraint hyper-planes and w is the union of Ax b and E.
siup
Hence, we can set O(
O sinp
Specially, for binary constraints may set 3 O(n E):
5

---

Corollary 4. For binary constraints where the entries of A are either 0 or 1, the utility gain R of violating 2 constraint is bounded by
max(w,, 0)), where w, = A b, or -I.
which gives a better bound for a set of unweighted item selection problem (e.g. select at most k items from particular subset).
3.1.3 Conversion of Equality Constraints Br =
Finally, we convert Bz = into soft constraints. This is particularly difficult, as Br = c implies both Br S c and -Br S -c, which will almost always cause acute angles. Let's first consider special case where there is only one equality constraints and A is an element matrix Taxn.
Theorem 5. If there is only one equality constraint Bx (i.e., ,, B degrades a row vector, such like Σ, Dz = 1) and special inequality constraints x 2 0, Ix S b, then the ulility gain R from violating constraints is bounded by O (" L, (.))) where is the same with theorem 3, w is the union of Br - c and -.
siup
Intuitively, when there is only one equality constraint, the equality constraint be viewed as unequal one, for at most one side of the constraint can be in non-degraded activated cone. Thus, we can directly apply the proof of Theorem and 3, deriving the same bound O n (1.6 for 3.
sinp
Finally, we give bounds for general Az - b, Br = with A, b, B, c 2 O as below: Theorem 6. Given constraints Az S b, x 2 O, and Ba G, where A, B, b, c the utility gain R obtained from violating constraints is bounded by O O(ynAmar Σ, max(w;; 0)), where Xmaz is the upper bound for eigenvalues of P" P(P: : + Px is an orthogonal transformation for an n-sized subset of normalized row vectors in A, B and - I), and w is the union of all active constraints from Ax S b, x 2 0, Bx S caand - BB S cc
In this theorem, P is generated by taking an arbitrary n-sized subset from the union of row vectors in A, B and -I, orthogonizing the subset, and using the orthogonal transformation matrix as P: there are (n+ma++-g +22) different cases of P. and Amar is the upper bound of eigenvalues of pT p over all possible cases of P. Note that there are no direct bounds on Amaz with respect to n and the angles between hyper-planes. However, empirical results (see Appendix for details) show that for a diverse set of synthetic data distributions, Amaz O(n²) follows. Therefore, empirically we can use for 3 So far, we have proven that all hard constraints can be transformed into sin p soft constraints with bounded multipliers. For compactness, 5 is rewritten unified form:
n
a bound O(" 2.6 "g
C
d
1 c'=
L(x) 0(x,0) - -mar(C'r d'), where 7
0
2 E
B
d'
(6)
sin
3.2 The Unconstrained Soft Constraints
As 5 is non-differentiable for the max operator, we need to seek a relaxing surrogate for differ- entiation. The most apparent choice of the derivative of such surrogate S(z) for = = C'x d' is sigmoidal functions; however, is difficult to derive closed-form solution for such functions, since sigmoidal functions yield z in the denominator, and z cannot be directly solved because C is not invertible (referring to Appendix B for detailed reasons). Therefore, we have to consider piecewise roundabout where we can first numerically solve the optimal point to determine which segment the optimal point is on, and then expand the segment to the whole space. To make this feasible, two assumptions must be made: 1) this function must be differentiable, and 2) the optimal point must be unique; ensure this, the surrogate should be convex/concave piece-wise function. The second property is for maintaining the optimal point upon segment expansion. Fortunately, there one simple surrogate function satisfying our requirement:
if <
IK
S(x)
)2 K(2 + OR
4k S Kk
if 2 aR
For real optimization problems, sample A' from A and estimate the largest eigenvalue of pT

---

Let M and U be diagonal matrices as the indicator of S(z), which are M.. 2K| and US, = l zi]. where [-] is an indicator function. K 0 is hyper-parameter that needs to be balanced. Larger K makes the function closer to original; however, if K is too large, then the training process would be destabilized, because when the prediction error is large at the start of the training of
S 2k
ik!
process, as & might be too steep. Then consider the optimal point for the unconstrained optimization problem maximizing 8J x 7" "mxx(C=== d', 0), by differentiaing on both sides, we can obtain:
0 C Mdiag(>))C - d') CT
1 ( 4K
M + +U
(8)
This equation reveals the closed-form solution of x with respect to 0 and thus the calculation of 0z becomes straightforward:
dr = (C M' 00
(9)
C Cdd is invertible long as at least soft constraints are on the quadratic segment (i.e., active), which is the necessary condition to fix particular optimal point n in R" With such solution, we can train our prediction model with stochastic gradient descent (SGD). For each batch of problem instances, we first solve optimization problems numerically using solvers like Gurobi to get the matrix M and U, and then calculate gradients with the analytical solution. The parameters of the prediction model are updated by such gradients. The sketch of our algorithm is outlined in Appendix C.
4 Applications and Experiments
We apply and evaluate approach the three problems described in Section 2, i.e.,linear program- ming, quadratic programming, and asymmetric soft constraint minimization. These problems are closely related three applications respectively: synthetic linear programming, portfolio optimiza- tion, and resource provisioning, which are constructed using synthetic or real-world datasets. The detailed derivation of gradients for each application can be found in Appendix D.
In our experiments, the performance measured in regret, which is the difference between the objective value when solving optimization over predicted parameters and the objective value when solving optimization over actual parameters. For each experiment, we choose two generic two-stage methods with L1-loss and L2-loss, well decision-focusee
methods for comparison baselines. We choose both SPO+ [10] and DF proposed by Wilder et al. [9 for synthetic linear programming and DF only for portfolio optimization as the former specially designed for for linear objective. For resource provisioning, we use a problem-specific weighted L1 loss, as both SPO+ and DF are not designed for gradients with respect to variables in the soft constraints. All reported results for each method are obtained by averaging on 15 independent runs with different random seeds.
As real-world data is more lenient than extreme cases, in practice bound than the upper bound proved in section 3.1., e.g., constants of around 20 and 5 where n is the number of dimensions of decision variables. One rule of thumb is start from reasonable constant or a constant times vnz where such "reasonable constant" is the product a constant factor (e.g. 5 10) and roughly estimated upper bound of ||01| (which corresponds to E in our bounds) with specific problem settings; then alternately increase the constant and time an extra vn while resetting the constant until the program stops diverging, and the hard constraints are satisfied. In our experiments, we hardly observe situations where such process goes for two or more steps.
a much lower empirical
4.1 Synthetic I Linear Programming
Problem setup. The prediction dataset {(E,, 0,) is generated by a general structural causal model (2Il), ensuring it is representative and consistent with physical process in nature. The programming parameters are generated for various scales in numbers of decision variables, hard constraints, and soft constraints. Full details are given in Appendix E.
'The method 3 and its variant with dimension reduction 9 have same performance in terms of regret on this problem, thus choose the former for comparison convenience.
7

---

Regret (the lower, the better)
N
Problem Size
L1
L2
SPO+ [10]
DF [9]
Ours
100
(40, 40, 0)
2.232
2.493:10.295
2.506 0.2994
2.258 2.4455
(40, 40, 20)
2.626-0.307
2.3303
2.667
2.336
2.350=10.263
(80, 80, 0)
5.736-0.291
5.831+0.361
5.711 +0.309
5.756-+0.317
5.200+00.506
(80, 80, 40)
4.786-0.403
0.596
1.939+0.382
4.902+0.537
4.590+0.390
1000
(40, 40, 0)
1,463=0.143
1.447
1.454+0.148
1.434
1.346
(40, 40, 20)
1.626=0.141
1.613+0.110
1.618=0.103
1.529:+.111
1.506=0.100
(80, 80, 0)
3.768=0.132
3.718=0.1117
3.113
3.532++0.102
3.431=
(80, 80, 40)
2.982-0.176
2.91310.172
2.
3.351
2.781=0.165
5000
(40, 40. 0)
10077=0.105
1.080=0.109
10090=0.105
1.79
1.037=10.00
(40, 40, 20)
1.283=0.070
1.277=0.077
1.298=0.077
1.291
1.220=0.071
(80, 80, 0)
2.943+0.091
2.926
2.869
2.845
(80, 80, 40)
2.129
2.224 106
2.234
2.748
2.172++0.09
Table I: Performance comparison (regret mean with std. deviation) for the synthetic linear pro-
gramming problem. is the size of the training dataset, and problem size is a triplet (# of decision variables' dimension, # of hard constraints, # of soft constraints).
Experimental setup. All five methods use the same prediction model a fully connected neural network of two hidden layers with 128 neurons for each and ReLU [22 for activation. We use AdaGrad [23 as the optimizer, with learning rate 0.01 and gradient clipped at le 4. We train each method for epochs, and early stop when valid performance degrades for 4 consecutive epochs. Specially, to make DF(9] work right on the non-differentiable soft constraints, we first use black-box solvers to determine whether each soft constraint active on the optimal point, and then optimize with its local expression (i.e. 2nd-order Taylor expansion at optimal point).
Performance analysis. Our experiments cover four programming problem scales with three predic- tion dataset sizes. Results are summarized in Table I In all cases, our method performs consistently better than two-stage methods, DF and SPO+. Even for the cases with only hard constraints (i.e., the third parameter of problem size is 0), our method still has significant advantage, demonstrating its effectiveness on handling hard constraints. Surprisingly, although the main objective linear, SPO+ often performs even worse than two-stage methods. Detailed analysis (see the appendíx) shows that SPO+ quickly reaches the test optimality and then over-fits. This may be due to that, unlike our method, SPO+ loss is not designed to align with the soft constraints. This unawareness of soft constraint is also why DF is performing worse than our method, as DF working on an optimization landscape that is non-differentiabbe at the boundary of soft constraints, on which the optimal point usually lies. Besides, with the increment of the samples in train data, the performance of all methods is improved significantly and the performance gap among ours and two-stage methods becomes narrow, which implies that prediction of two-stage methods becomes better and with lower biases. Even so, method has better sample efficiency than two-stage methods.
We also investigated effect of the appendix. Through our experiments, K's effect to regret is not monotonic, and its optimal value varies for different problem sizes. Interestingly, K's effect is approximately smooth. Thus, in practice, we use simple grid search to efficiently find the best setting of K.
in our surrogate max function, detailed in the
4.2 Portfolio Optimization
Problem and experimental setup. The prediction dataset is daily price data of SP500 from 2004 to 2017 downloaded by Quandl API (24) with the same settings in [3]. We use the same fix as that in linear programming experiment to make DF work with non-differentiable soft constraints, which was also used in S for non-conved optimization applications. Most settings are aligned with those in [. including dataset configuration, prediction model, learning rate (0.01), optimizer (Adam), gradient clip (0.01) and number of training epochs (20). We set the number of soft constraints to 0.4 times n, where n the number of candidate equities. For the soft constraint af max(Cx - d. 0).
15,, where each element of is generated randomly at uniform from (0, 1); the elements of matrix C is generated independently from (0, 1), where the probability of is 0.9 and 1 is 0.1. K set as 100.
8

---

Regret measured in % (the lower, the better)
#Equities
LI
L2
DF [9]
ours(K = 100)
4..366
4.472:1:0385
4.016:10.889
3.662.10.25
100
4..231
4.320:1:.229
3.500=
3.214:10.138
150
3.878 +0.281
3,950=+0.287
3.219=00281
3.109::0.162
200
3.755+0.221
3.822++0.273
3.406
3.212:10.135 Table 2: Performance comparison (regret mean with std. deviation) for portfolio optimization.
250
3.751 3.721
3.335=0.115
Regret (the lower, the better) Weighted L1
0n /02
L1
1.2
Ours K = 0.05)
100
105.061+21.954
93.193+:2.8815
79.0141:32.09
20.829
13.061+2.713
63.275=1.208
1.343
2.746=
1
4.267=0.618
5.136=0.722
4.267=0.618
5.839::0.512
0.1
10.846
13.619422.15
16.462.+:2.99
10.240 1.:400-11.244 1.248
0.01
19.1419
118. 118.112--29.97
230.825
94.341 : 29.821
Table 3: Performance comparison (regret mean with std. deviation) for resource provisioning.
Performance analysis. Table summarize the experimental results. In total, on all problem sizes (#equities), our method performs consistently and significantly better than both two-stage (L1 and L2) methods and the decision focused DF[9]. Among the three baselines, DF is significantly better 3. fact, DF under this setting can be viewed as variant of our method with infinite K and no conversion of softening Σ; H; 1. The comparison DF also demonstrates the advantage of our method on processing such non-differentiable cases against the simple 2nd-order Taylor expansion. Besides, with the increment of the number of equities, regrets all methods decease, which indicates that for the constraint >; 2e = 1, larger number of equities brings smaller entries of on average (with the presence of Q, there are many non-zero entries of z), lowering the impact of prediction error for any single entry.
than two-stage methods, similar results
4.3 Resource Provisioning
which contains hourly data of energy output from 2013 to 2018, 52535 data points in total. We use the last 20% samples for test. We aim to predict the matrix C E R 24x8 the loads of 24 hours in regions. The decision vairable x 8-dimensional, and d = 0.5 x 1 + 0.1N(O,) 1). We test five sets of (2), with an / ranging from 100 to 0.01.
Problem setup. We use ERCOT energy dataset 25
Experimental setup. We AdaGrad with learning rate of 0.01, and clip the gradient with norm 0.01. For the prediction model, we use McEIWee's s network (26) which was highly optimized for this task, with (8 24 77)-dimensional numerical features and embedding ones as input.
Performance analysis. Table 3 shows the experimental results. The absolute value of regret differs largely across different ratios of a1 /a22 Our method is better than other methods, except for a1 01/a2 = 1, where the desired objective is exactly L1-loss and thus L1 performs the best. Interestingly, compared to L1/L2, the Weighted L1 performs better when a1/0ş > 1, but relatively worse otherwise. This is probably due to the dataset's 's inherent sample bias (e.g., asymmetric distribution and occasional peaks), which causes the systematic bias (usually underestimation) of the prediction model. This bias exacerbates, when superposed with weighted penalty multipliers which encourage the existing bias fall on the wrong side. Besides, the large variance for weighted L. a1/02 0.01 is caused by a pair of outliers.
5 Related Work
Differentiating argmin/argmax through optimality conditions. For convex optimization prob- lems, the KKT conditions map coefficients to the set of solutions, and thus can be differentiated for argmin using implicit function theorem. Following this idea, existing work developed implicit layers of argmin in neural network, including OptNet [3] for quadratic programs (QP) problems and CVXPY [4] for more general convex optimization problems. Further with linear relaxation and

---

QP regularization, Wilder et al. derived an end-to-end framework for combinatorial programs [9] which accelerates the computation by leverage the low-rank properties of decision vectors [3] and is further extended to mixed integer linear programs in MIPaal. 27 Besides, for the relaxed I.P problems, instead of differentiating KKT conditions, IntOpt (8 proposes an interior point based approach which computes gradients by differentiating homogeneous self-dual formulation.
Optimizing surrogate loss functions. Elmachtoub and Grigas [0] proposed convex surrogate loss function, namely SPO+, measuring the decision error induced by prediction, which can handle polyhedral, convex and mixed integer programs with linear objectives. TOPNet [29] proposes learned surrogate approach for exotic forms of decision loss functions, which however is hard to generalize handle constrained programs.
Differentiating argmin is critical for gradient methods to optimize decision-focused prediction models. Many kinds of efforts, including regularization for specific problems (e.g., differentiable dynamic programming [30. differentiable submodular optimization (31). reparameterization [32,
perturbation [33] and direct optimization (lI2), are spent for optimization with discrete continuous variables and still actively investigated.
As comparison, our work proposes surrogate loss function for constrained linear and quadratic programs extended with soft constraints, where the soft constraints were not considered principally in previous work. Also, unlike OptNet [B] and CVXPY [15], our method does not need to solve KKT conditions. Instead, by adding reasonable costs for infcasibility, we convert the constrained optimization problem into unconstrained one while keeping the same solution set, and then derive the required Jacobian analytically. To some degree, we reinvent the exact function 34 in prediction+opimiizaiinn.
Conclusion
In this paper, we have proposed a novel surrogate objective framework for prediction+oopimizatinn problems on linear and semi-definite negative quadratic objectives with linear soft constraints. The framework gives the theoretical bounds on constraints' multipliers, and derives the closed-form solution well as their gradients with respect to problem parameters required predict by model. We first convert the hard constraints into soft ones with reasonably large constant multipliers, making the problem unconstrained, and then optimize a piecewise surrogate locally. We apply and empirically validate our method on three applications against traditional two-stage methods and other end-to-end Decision-focuseee methods. We believe our work is an important enhancement to the current prediction-oppimizztoon toolbox. There are two directions for the future work: one is to seek solutions which can deal with hard constraint parameters with negative entries, and the other is to develop the distributional prediction model rather than existing point estimation, to improve robustness of current prediction+opiimizatonn methods.
10

---

References
[1] Chuan Luo, Bo Qiao, Xin Chen, Pu Zhao, Randolph Yao. Hongyu Zhang, Wei Wu, Andrew Zhou, and Qingwei Lin. Intelligent virtual machine provisioning in cloud computing. In Proceedings of IJCAI 2020, pages 1495-1502, 2020.
[2] Sirikarn Chansombat, Pupong Pongcharoen, and Christian Hicks. A mixed-integer linear programming model for integrated production and preventive maintenance scheduling in the capital goods industry. International Journal of Production Research, 57:1-22, 04 2018 8. doi: 10. 10.1080/00207543.0 2018.1459923.
[3] Kai Wang, Bryan Wilder, Andrew Perrault, and Milind Tambe. Automatically learning compact quality-aware surrogates for optimization problems. In NeurlPS 2020, Vancouver, Canada, 2020.
[4] Emir Demirovi, Peter Stuckey, Tias Guns, James Bailey, Christopher Leckie, Kotagiri Ramamohanarao, and Jeffrey Chan. Dynamic programming for predict+optimise. Pro- ceedings of the AAAI Conference on Artificial Intelligence, 34:1444-144 1451, 04 2020. doi: (0.16099aaai..34440.555
[5] Gartheeban Ganeshapillai, John Guttag, and Andrew Lo. Learning connections in financial time series. Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 109-117, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR.
[6] LLC Gurobi Optimization. Gurobi optimizer reference manual, 2021. URL http://www //ww gurobi com
[7] IBM ILOG Cplex. Release notes for cplex 20.1.0. 2020. httpp::::///w wtt..cmmmm.......momm.mooooooooe /
en/icos am/icos/20. reee notes-
[8] Yoshua Bengio. Using a financial training criterion rather than a prediction criterion. Int. Neural Syst., 8(4):433-443, 1997. doi: 10. 211142/20009657777000000 URL httptt//s//o
org/10. /11114////011997777700000222
[9] Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-decisions pipeline: Decision- focused learning for combinatorial optimization. In The Thirty-Third AAAI Conference Artificial Intelligence, pages 1658-1665. AAAI Press, 2019.
[10] Adam Elmachtoub and Paul Grigas. Smart "predict, then optimize". Management Science, 10 2017. doi: 10. 1tw.1//mmmmc.2220..9999
[11] Priya L. Donti, Brandon Amos, and Zico Kolter. Task-based end-to-end model learning in stochastic optimization. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, page 5490-5500, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 978151086099 10860964.
[12] Yang Song, Alexander Schwing, Richard, and Raquel Urtasun. Training deep neural networks via direct loss minimization. In Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2169-2177, New York, New York, USA, 20-22 Jun 2016. PMLR.
[13] Brandon Amos and J. Zico Kolter. OptNet: Differentiable optimization layer in neural networks. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 136-145, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR. mlr www.sppe/ssssmseeeee http://cwe.aaaa.....rrssrsr////a amos 11 17a. html
URL http::/pproceedingg mir.
[14] Brandon Amos. Differentiable Optimization -Based Modeling for Machine Learning. PhD thesis, Carnegie Mellon University, May 2019.
[15] Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and J. Zico Kolter. Differentiable convex optimization layers. Advances Neural Information Processing Systems, volume 32, pages 9562-9574. Curran Associates, Inc., 2019.

---

[16] Harry M. Markowitz. Portfolio Selection: Efficient Diversification of Investments. Yale University Press. 1959. ISBN 9780300013726. URL http::/ttt..wsstttt org/ arg/stable/j
ctt1bh4c8h
[17] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019.
[18] A. Griewank and A. Walther. Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, Second Edition. Other Titles in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM, 3600 Market Street, Floor 6, Philadelphia, PA 19104), 2008 ISBN 9780898717761.
[19] Jan R. Magnus Jan R. Magnus. Matrix Differential Calculus with Applications in Statistics and Econometrics, Third Edition. Wiley Series in Probability and Statistics. Wiley, 2019. ISBN 9781119541201
[20] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[21] Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference. The MIT Press, 2017.
[22] Vinod Nair and Geoffrey E. Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML'10, page 807-814, Madison, WI, USA, 2010. Omnipress. ISBN
9781605589077
[23] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121-2159, 07 2011.
[24] Sp500 data set. 2021. URL
[25]
Ercot data set. 2021. URL
load_ fodd_ffrrcast/aaaa
[26) Kevin McElwee. Predict daily electric consumption with neural networks, 2020. URL https www.aarroonaalyticc..... com/ http:///iiicccoomooaadaaeeeeeeee -ooo///aad-ooe
[27] Aaron Ferber, Bryan Wilder, Bistra Dilkina, and Milind Tambe. Mipaal: Mixed integer program as layer. In AAAI Conference on Artificial Intelligence, 2020.
[28] Jayanta Mandi and Tias Guns. Interior point solving for lp-based prediction-optimisation In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 7272-7282. Curran Associates, Inc., 2020.
[29] Di Chen, Yada Zhu, Xiaodong Cui, and Carla Gomes. Task- learning via fask-oriented prediction network with applications in finance. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pages 4482. International Joint Conferences on Artificial Intelligence Organization. 7 2020. doi: 10.24963/ijcai. 2020/617. 20200/661..... Track on AI in FinTech.
URL htttps://ooi..... org 10. 34963/ijjai.. 2020/617 Special
[30] Arthur Mensch and Mathieu Blondel. Differentiable dynamic programming for structured prediction and attention. In 35th International Conference on Machine Learning, volume 80, pages 1459-3468 2018.
[31] Josip Djolonga and Andreas Krause. Differentiable learning of submodular models. In Advances in Neural Information Processing Systems, volume 30, pages 1013-1023. Curran Associates, Inc., 2017.
12

---

[32] Danilo Jimenez Rezende. Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and upproximate inference deep generative models. In Proceedings of the 31st International Conference on International Conference on Machine Learning Volume 32, ICMI''1, page 11-1278-1-12280 JMI.R.org 2014.
[33] Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Jean-Philippe Vert, and Francis Bach. Learning with differentiable perturbed optimizers. arXiv preprint arXiv:2002.0860 2020.
[34] Dimitri Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48 (3):334-334, 1997.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [Yes]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] We did not crowdsourcing, nor did we conduct research with human subjects.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "qlr5FXCmkM8", "reviewer": "Reviewer_Vxh4", "summary": "This paper provides a method for addressing the \"prediction + programming\" problem in the case where the programming problem contains a $\\max(z,0)$ term in the objective. To do so, the authors rewrite the optimization problem as an unconstrained optimization problem by converting all hard constraints of the optimization problem to soft constraints in the objective. They then pick the coefficients of those soft constraints in a way that is meant to prevent constraint violations, and then relax these soft constraints via a surrogate function. They then embed the resultant approximate optimization problem within a method where some $\\theta$ is output by a neural network, the approximate optimization problem is solved for that value of $\\theta$, and gradients are updated by differentiating end-to-end through the approximate optimization problem. The authors demonstrate their method on three synthetic settings, and report improved performance over two-stage methods and SPO+.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper addresses an important prediction + programming setting, and provides an interesting surrogate objective framework for addressing it. However, one of the central motivational claims of the paper is flawed, which unfortunately compromises the premise of the paper. In additional, several of the assumptions made throughout are rather strong, and this is not properly flagged.\n\n### Central motivational claim\n\nThe central claim on which this work is built is that existing methods cannot handle the setting where there is a $\\max(z,0)$ term in the objective function. However, this setting can indeed be handled by existing methods. For instance, the class of programming problems studied can be differentiated through using cvxpylayers (see example code at the end of this review), and KKT differentiation approaches such as those proposed in OptNet [13] can also be used (by obtaining the optimal $z^\\star$ via some solver, rewriting $\\max(z^\\star, 0) = z^\\star$ or 0 depending on the value of this optimal solution, and differentiating through the KKT conditions of the resultant problem). These differentiable layers can then be directly used within the end-to-end learning approaches proposed in [9, 11] to address the prediction + programming problem.\n\nNow, the approaches I have described above are certainly far from perfect: For instance, they are likely to be computationally expensive to train (as KKT differentiation-based approaches tend to be). In contrast, the method proposed in the present paper is potentially cheaper to train. However, this is not the axis of improvement that the paper currently aims to demonstrate (i.e., time comparisons to cvxpylayer- or OptNet-based methods are not shown). \n\nIf the authors were to revamp the paper (both the motivation and the experiments) to address the problem of decreasing computational cost (rather than the current motivation of addressing a previously-unaddressed setting), I think this would significantly strengthen the paper (and accordingly, I would potentially be open to increasing my score).\n\n### Assumptions\n\nSome of the assumptions made throughout are also rather strong. While this is okay for the purposes of developing a specialized method, these should be properly flagged and described as limitations rather than being described as common circumstances:\n* Line 74: The assumption that all terms in $A$ are non-negative is rather strong, in particular because encoding box constraints on $x$ (that is, $x_l \\leq x \\leq x_u$ for $x_l, x_u > 0$) would require the presence of negative terms in $A$. Such box constraints are rather common.\n* Line 141: The assumption that the l2 norm of $\\nabla f$ is bounded is also potentially rather strong, particularly in the quadratic case (Equation 3). This should be flagged and discussed.\n* Line 193: It would be helpful if the definition of $P$ could be more clearly described, as it is not immediately clear from the description in the main text why $\\lambda_{max}$ would be bounded in practice.\n\n### Other comments\n\n* Line 149: Is \"active constraints at $x$\" supposed to refer to all constraints that are violated by $x$? (Given that $x \\not\\in \\mathcal{C}$, \"active constraints\" may not be the correct terminology.)\n* Line 201: This statement should be corrected. As described above, Equation 5 can indeed be differentiated through at its optimum since the \"max\" operation can be replaced by either the linear term or 0 depending on the value of $x^\\star$ that is obtained. This rewritten problem can then be differentiated through via the implicit function theorem.\n\n### Sample cvxpylayers code\n\nAs mentioned above, here is some sample code for setting up a differentiable layer for Equation 2 via cvxpylayers. \n\n\timport cvxpy as cp\n\timport torch\n\tfrom cvxpylayers.torch import CvxpyLayer\n\timport numpy as np\n\n\t# Random seeds for param generation (picked so the problem is feasible)\n\tnp.random.seed(0)\n\ttorch.random.manual_seed(6)\n\n\t# Initialize problem vars and params\n\tn, m, k = 2, 3, 5\n\tx = cp.Variable(n)\n\ttheta = np.random.randn(n)\n\t# pick alpha as the ones vector (see \"sum\" in the objective)\n\tA = cp.Parameter((m, n))\n\tb = cp.Parameter(m)\n\tB = cp.Parameter((n, n))\n\tc = cp.Parameter(n)\n\tC = cp.Parameter((k, n))\n\td = cp.Parameter(k)\n\n\t# Set up cvxpy problem\n\tobjective = cp.Maximize(theta@x - cp.sum(cp.maximum(C@x + d, 0)))\n\tconstraints = [A@x <= b, B@x == c, x >= 0]\n\tproblem = cp.Problem(objective, constraints)\n\tassert problem.is_dpp()  # True\n\n\t# Create cvxpylayer\n\tcvxpylayer = CvxpyLayer(problem, parameters=[A, b, B, c, C, d], variables=[x])\n\tA_tch = torch.randn(m, n, requires_grad=True)\n\tb_tch = torch.randn(m, requires_grad=True)\n\tB_tch = torch.eye(n, requires_grad=True)\n\tc_tch = torch.ones(n, requires_grad=True)\n\tC_tch = torch.randn(k, n, requires_grad=True)\n\td_tch = torch.randn(k, requires_grad=True)\n\n\t# Solve the problem\n\tsolution, = cvxpylayer(A_tch, b_tch, B_tch, c_tch, C_tch, d_tch)\n\n\t# Compute the gradient of the sum of the solution with respect to problem params\n\tsolution.sum().backward()   # works", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As mentioned in my main review, I think the authors could do a better job flagging some of the assumptions they make and describing their significance.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "ZrfqBJYmkQ1", "reviewer": "Reviewer_FE8x", "summary": "This paper presents an approach for \"predict, then optimize\" problems that is amenable to derivative-based learning methods. It involves converting hard constraints into soft constraints (i.e. implicitly enforced through objective penalization). The main theoretical contributions are bounds on the magnitude of objective change that can be attributed to infeasibility with respect to the original hard constraints.", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is quite difficult to read. The theoretical results are presented informally in the body of the paper to the point of confusion, and it is difficult to glean what the conclusions from them should be. As such, it is difficult to assess the technical soundness of the work. As one example, the second condition on H (line 137) is written confusingly and informally (what does \"increments\" mean in this context? How do you formally measure \"gain\" with respect to violation of the linear constraints?). As a second, the statement of Lemma 1 is also informal--what is the maximin discussed taken with respect to? As a third, Corollary 4 does not formally define what \"cardinal constraints\" means (should be \"cardinality constraints\"?) and what their implications are for the structure of the problem data. As a fourth, the theoretical results in Section 3 only seem to indicate asymptotic guidance as to the maximum penalty weights to be considered, not how they should actually be set in practice, let alone to guarantee optimality w.r.t. the true problem. This vagueness continues in Section 4 and the Appendix, where (contra 3(b) in the checklist) the penalty terms gamma are described only in asymptotic notation; the reader is not told how these values are actually set in the experiments.\n\nThe approach presented to smooth the max constraints is not particularly surprising, though I have no reason to question its novelty. The computational results seem promising, though the lack of details about the implementation make it difficult to see how readers would glean insight into how to take these results and apply to new problems or extend them.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not feel that the authors adequately confront the limitations of their work. Most of the results restrict the problem data to be nonnegative. They claim that \"constraint parameters usually represent weights, quantities or their thresholds, and thus are always nonnegative.\" This is overly broad--there are many, many \"realistic\" optimization problems that do not satisfy this condition. The wide swath of network optimization problems are just one set of examples. This restriction is a reasonable enough one as many problems _do_ satisfy it, but the paper should be suitably rewritten to soften its claims.\n\nThere is no direct negative societal impact of the work.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "P48UL-xdvAk", "reviewer": "Reviewer_rNgo", "summary": "The paper develops a surrogate function with closed-form solution for objective functions with \"soft constraints,\" here defined as those with the term $\\alpha^T \\\\max\\\\{0,z(x)\\\\}$ for affine $z$, component-wise $\\\\max$, and $\\alpha > 0$. The goal is to apply such functions within the context of smart \"predict-then-optimize\" (SPO) by also relaxing the hard constraints with a sufficiently large penalty $\\alpha$. To develop their surrogate, the authors evaluate bounds on the utility gained when violating the soft constraints using primarly a geometric perspective, specifically evaluating the angles or corners of infeasible points with respect to the convex hull of feasible solutions (and related properties). Numerical results compare their approach with the standard SPO+ loss function and a DF metric for portfolio optimization.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality**\n\nThe paper is part of a current stream of papers that investigate different strategies to smooth the underlying loss function within the SPO framework, which is itself a quite challenging problem. Within that context, I found the polyhedral perspective provided by this paper quite interesting and, to the best of my knowledge, original as well. The general ideas are quite relevant given that $\\\\max\\\\{0,z\\\\}$ functions are quite pervasive, e.g., in A.I. and operations.\n\n\n**Quality**\n\nOverall, I believe the paper is well structured but I do have some few technical concerns. More specifically:\n\n1. When softening hard constraints and calculating their penalty, the terms involve angle, smallest corner calculations, and other complex functions such as $\\\\sin$. I wonder if there could be challenges associated with numerical stability? Furthermore, how time consuming was calculating such angles and auxiliary parameters for the instances tested?\n\n2. Many of the bounds are defined as within function classes $O(\\\\cdot)$. From my understanding of the structural results, the actual functions to be used in the penalties could be associated with large constants (e.g., due to $c_1$, l.651, in pg.18, supplemental material), which could make the approximation too weak. Perhaps I misunderstood, but I believe some further discussion on how to prescribe the bounds precisely could be beneficial here, including some intuition on the quality of these bounds.\n\n\n**Clarity**\n\nThe main text is well-written and the supplemental material is comprehensive. My few comments here are as follows.\n\n3. It would be best if the assumptions are more clearly described in the text. In particular, non-negativity of $\\alpha$ could not necessarily be always the case (e.g., in Benders or cut-generation linear programs, where similar ideas could be useful). Furthermore, I believe the constant $E$ is an important factor for the development of the results and it could be emphasized further.\n\n4. The proofs were overall rigorously written and are clear to the best of my analysis. The auxiliary figures are extremely helpful. However, Theorems 3 and 5 are relatively more difficult because many statements are posed more vaguely (e.g., in 591-595, how to project the cone to its tip?). I would suggest just to extend them somewhat with more hand-holding and appropriate formalism, if possible.\n\n5. Some statements in the main require references (or at least authors could cite related papers earlier) - for example: \"modern solvers ... can already efficiently find optimal for most large scale programming problems,\" or \"it may model overhead of under-provisioning, over-provisioning of goods.\" \n\n**Significance**\n\nIn my view, this is a paper that provides a clear and useful contribution and may attract a broader interest within the A.I. community. The idea of \"softening\" constraints by exploiting polyhedral corners/angles is original within the context of SPO, to the best of my knowledge. Nonetheless, the calculation of the softening constraint is more involved and some practical aspects (quality of the bounds, complexity, and numerical stability) requires some more clarification, which I believe can be easily addressed by the authors. \n\n**Minor Points**\n\n- The references have a few errors. For example, there is no journal information in [10], reverence [7] should be updated with CPLEX v20 (2021) etc. \n- \"more loyal\" --> \"closer?\"\n- There is often a missing \"the\" prior to the word \"programming\" throughout the text.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not discussed in the text. The paper could greatly benefit from a discussion concerning the limitations and trade-offs of their methodology.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "9kk6KBe1Nr", "reviewer": "Reviewer_WmBF", "summary": "The paper proposes a new method to integrate soft constraints in the predict+programming paradigm that focuses on mathematical programming models with a prediction component that needs to be considered during optimization/solving.\nThe new method works by reformulating the problem into piecewise linear constraints and then optimizing a surrogate for the original problem.\nA theoretical analysis and motivation is provided as well as an experimental evaluation that underlines the effectiveness of the method.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "As a disclaimer, I'm broadly familiar with predict+optimize, but am not a specialist in this area of mathematical programming and did not follow the theory in detail.\nHowever, the methodological approach seems sound and well supported by the theory.\n\nI was wondering why the methodology was framed as \"prediction+programming\" rather the, in my view, more established \"predict+optimize\". Also, even though mathematical programming is an established term, using \"programming\" might lead to some confusion in regards to software programming.\n\nIn general, I think this is solid work and of relevance for this area.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no dedicated discussion of societal impacts, but it is also not particularly relevant in this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: A majority of reviewers recommend acceptance although, notably, a majority of reviewers also raise clarity concerns with the paper.  For the most part, the reviewers felt that these concerns were satisfactorily addressed in the significant rebuttal discussion.  The reviewers request the authors to revise the paper in light of the reviews and rebuttal discussion, which all reviewers agree would be manageable within the time frame for revision of accepted NeurIPS papers.
Decision: Accept (Poster)