Branch & Learn for Recursively and Iteratively Solvable Problems in Predict+Optimize
Authors: Xinyi HU
Jasper C.H. Lee
Jimmy H.M. Lee
Allen Z. Zhong
Venue: NeurIPS 2022 Accept (2022)

Abstract: This paper proposes Branch & Learn, a framework for Predict+Optimize to tackle optimization problems containing parameters that are unknown at the time of solving. Given an optimization problem solvable by a recursive algorithm satisfying simple conditions, we show how a corresponding learning algorithm can be constructed directly and methodically from the recursive algorithm. Our framework applies also to iterative algorithms by viewing them as a degenerate form of recursion. Extensive experimentation shows better performance for our proposal over classical and state of the art approaches.

Branch & Learn for Recursively and Iteratively Solvable Problems in Predict+Optimize
Xinyi Hu', Jasper C.H. Lee2, Jimmy H.M. Lee', Allen Z. Zhong'
Department of Computer Science and Engineering
The Chinese University of Hong Kong, Shatin, N.T., Hong Kong
Department of Computer Sciences & Institute for Foundations of Data Science University of Wisconsin-Madison WI, USA
(xyhujjec.zwzhhong (ecse.cuhk.ede jasper.lee wisc.edu
Abstract
This paper proposes Branch & Learn, framework for Predict+Optimize to tackle optimization problems containing parameters that are unknown at the time solving. Given optimization problem solvable by recursive algorithm satisfying simple conditions, we generalize previous work substantially by showing how a corresponding learning algorithm be constructed directly and methodically from the recursive algorithm. Our framework applies also to iterative algorithms by viewing them degenerate form of recursion. Extensive experimentation shows better performance for our proposal over classical and state of the art approaches.
Introduction
In the intersection of machine learning and constrained optimization, the Predict+Optimize framework tackles optimization problems with parameters that are unknown solving time. Such uncertainty is common in daily life and industry. For example, retailers need to pick items to restock for maximizing profit, yet consumer demand is a-priori unknown.
The task is i) predict the unknown parameters, then ii) solve the optimization problem using the predicted parameters, such that the resulting solutions are good even under true parameters. Traditionally, the parameter prediction uses standard machine learning techniques, with error measures independent of the optimization problem. Thus, the predicted parameters may in fact lead to low- quality solution for the (true) optimization problem despite being "high-quality" for the error metric. The Predict+Optimize framework uses the effective regret function [3, 6. 9] as the error metric, capturing the difference in objective (computed under the true parameters) between the estimated and true optimal solutions. However, the regret function is usually not babb)ddiffreentiabl, and gradient-based methods do not apply.
Prior works have focused on the regime where the optimization problems contain unknown objective and known constraints, and proposed ways overcome the non- differentiability of the regret. They can be roughly divided into two approaches: approximation and exact. The former tries to compute (approximate) gradients (approximations of) regret function. Elmachtoub el al. [6] propose differentiable surrogate function for the regret function, while Wilder et al. [17] relax the integral objective in constrained optimization and solve a regularized quadratic programming problem. Mandy and Guns [12] focus mixed integer linear programs and propose interior point based approach. While novel, approximation approaches are not always reliable. Exact approaches exploit the structure of optimization problems train models without computing gradients. Demirović et al. [4] investigate problems with the ranking property and propose a large neighborhood search method to learn linear prediction function. They [5] further extend the method enable Predict-Optimize for problems amenable to tabular dynamic programming (DP).
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

We propose novel exact method for problems solvable with recursive algorithm (under some restrictions), significantly generalizing the work of Demirović et al. [5]. By viewing iteration as special case of recursion with single branch, our framework applies also to iterative algorithms. Recall that DP is a special case of recursion, where the recursion structure has overlapping sub- problems, enabling the use of memoization to avoid recomputation. In particular, tabular DP is implemented as an iterative algorithm, computing the table row by row. While tabular DP is a widely applicable technique, it is not universal in that many naturally recursively solvable problems are not known to have a DP algorithm. For example, many modern combinatorial search algorithms are still fundamentally based exhaustive search. Our work thus subsumes the method by Demirović er al. [5] and extends the Predict+Optimize framework to a much wider class of optimization problems. Experiments 3 benchmarks with artificial and real-lit -ife data against 9 other learning approaches confirm the superior solution quality and scalability of our method.
The concurrent work by Guler ef al. [9]. just accepted to AAA122, proposes a divide and conquer algorithm, extending the work of Demirović et al. [5] by considering optimization problems whose objective function is bilinear function in the decision variables and the unknown parameters. While both Branch & Learn and [9] are exact methods for Predict+Optimize, there are problems amenable to Branch & Learn but not [9], and vice versa. The techniques used are also very different between the two works. Section 6 compares the two pieces of work in more detail.
2 Background
Without loss of generality, an optimization problem is to find x² = arg min, obj(z) s.t. C(z), where x E Idd is vector of decision variables, obj : Rd - R a function mapping x to an objective value to be minimized, and C' is set of constraints over x. Thus, x= is optimal solution and (x") is the optimal value. In this (and prior) work, we focus on cases where only the objective contains uncertainty. A parameterized optimization problem (Para-OP) P(O) thus extends the problem P as:
x²
(0) arg min obj 0) s.t. C(x)
where 0 E IR' is vector of parameters. The objective now depends also on 0. When the parameters known, Para-OP is just optimization problem.
Example 1. Consider a project funding problem to maximize Ei= Pi Iy subject to the budget constraint 2 + 2x² I3 T4 S 3, where p is an array representing the profits of projects. The problem is an instance of 0-1 knapsack. However, p is usually unknown at decision time, with only some features related to il given, such as proposal scores and the reputation of each applicant.
In Predict+ Optimize [5], the true parameters 0 E RR' for a Para-OP are unknown at solving time, and estimated parameters 0 are used instead. Suppose each parameter is estimated by m features. The estimation will rely on a machine learning model trained over n observations of a training data set {(A', ((A',")),.. _.')..... (A" (")), where A' R is a feature matrix for 6', so to yield prediction function f Rm - R for estimating parameters 0 = f(A).
The quality of the estimated parameters ê is measured by the regret function, which is the objective difference between the true optimal solution x: (0) and the estimated optimal solution x (0) under
the true parameters 8. Formally, we define the regret function Regret(A. 8) R' x R R>o to be:
Regret (0, obj(z' (o))(=(())))) - (z)(x
where obj( (0), 8) is the estimated optimal value and obj( (B), is the true optimal value.
Following the empirical risk minimization principle, Elmachtoub et al. [7] choose the prediction function from the set of models F attain the smallest average regret over the training data:
1 Regret(f(A').
f" arg min JEF n
(1)
For discrete optimization problems, the regret is not (sub) differentiable, Hence, traditional (sub- bgradient-based training algorithms are not applicable.

---

Algorithm 1: Coordinate Descent
Input: A Para-OP P(O) and training data set {(A', 01), (.),..... (A", 0²)}
Output: a coefficient vector 1mm
1 Initialize a arbitrarily and t- 0:
while not converged A resources remain do
3 k + (k: mod m) + 1;
Initialize L to be the zero constant function;
5 for i E
do
(Pi, To) - Ccontrruc(((00)) A+)
7
Et()) + Convert Io);
L'(r) + Evaluate([
1o);
L(7) - L(n) + (1));;
10
Ok + arg min
11 return ar;
Demirović et al. [5] study the class F of linear prediction functions and propose to represent the solution structure of Para-OP using (continuous) piecewise linear functions. A piecewise linear function h is velluv function defined
finite set of (closed) intervals I((h) partitioning R.
Each interval I E I(hh) is associated with a linear function h[[]] of the form h[[](r = air + by. and the value of (r(r) for real number E I is given by hr(](r) where E I. An algebra can be canonically defined on piccewise linear functions [15]. For piecewise linear functions h and g. we define pointwise addition (h + (r) h(r) + g(r) for all R. Pointwise subtraction, max/min and scalar products are similarly defined. All five operations can be computed efficiently by iterating over intervals of the operands [5].
In the rest of the paper, we assume that the prediction function is a linear mapping of the form ((A) Aar for some m-ddimnnsional vector of coefficients a E IRm..
To (approximately) solve problem (1), Demirovié et al. [5] proposes to update the coefficients a of iteratively via coordinate descent (Algorithm 1), in which a are initialized arbitrarily and updated in round-robin fashion. Each iteration (lines 3-10) contains three functions. Const ruct constructs Para-OP as a function of the free coefficient, fixing the other coefficients in a, with an initial domain Ju. Convert returns a piecewise linear function of the free coefficient from the Para-OP, and each interval of the function corresponds to estimated optimal solution. Evaluat takes the returned function and the true parameters as inputs, computes the estimated optimal value, and obtains the regret as a piecewise constant function of the free coefficient.
As Algorithm shows, in each iteration (lines 3-10), an coefficient on is updated. Iterating index A E: {I,...,,,, m), we replace in with a variable I by constructing a + (7 Jeke,, where E7 is unit vector for coordinate k. In lines 5-10, we wish to update ag as:
Oj < arg min YER
Regret(A (arrett(''s7-00 + A'(a - 0*
Let us describe lines 6-8 in more detail. For notational convenience, let = Alex E R and b' A'(a agex) R" which are vectors independent of the free variable y. Construct synthesizes the parameterized problem
Pj = x 2a'7 + b)) = arg min obj a'y 8¹) s.t. C(x)
Sometimes, the parameterized problem also have an initial domain In R for 7. For instance,
we may restrict the estimated profits to be non-negative Example 1. Convert takes P to create a function E' mapping to the estimated objective E7()) = (x (2 + b'), b)) + b²). Associated with each interval E I(E"())), a linear function maps ? the objective computed with the estimated parameters a'> + b², and the estimated optimal solution x (a'y+b" remains the same each interval / [4, 5]. From this, Eva uate computes the regret L for each interval I, i.e.
L [ Regret(a' x(I) + 6¹, (.00) obj(2* (a'x(1) + 6¹), 0*) obj(=" (
3

---

Algorithm 2: Generic Recursive Solving and Recursive Learning
Function ReSolve(P. 0):
Function ReLearn (P, Io):
2
if issaaseaase()) then
II
if issaseeasee P. 1o) then R|[o] (PseCaseL(P.)):
(=*(0), BaseCase(P,0); else
else
5
< (xtract(P.0):
Ty f- ExtractI(Pa,.u)) for each interval / E I(TT, do
PL f Branch(P,d,T):
7
RL + Map(ReSolve, PL);
16
PL f [
(0), (0)) t Reduce @ RL);
RL f- Map(ReLeara)) PL);
return R;
I8
R[1] + Reduce RI.);
19
return R;
where X is a function arbitrarily selecting a value from an interval I. The resulting function L is piecewise constant and represents the regret for different values of the free coefficient. If ş Io- the value of L is set to a sufficiently large constant to indicate impracticability of the estimation = =ay' + 6². Line 9 sums all L' L'(r) into piecewise constant total regret L(7) across all training examples, and line 10 minimizes L(y) by simply iterating over each interval of L(7).
While coordinate descent is a standard technique, the key contribution by Demirović er al. [5] is show how to build the Convert function for a tabular DP algorithm, by computing modified DP table with essentially the same structure. In this paper, we significantly generalize the method by constructing Convert for recursive and iterative algorithms, opening the Predict+Optimize framework to a much wider class of problems than just those solvable using DP algorithms. A major obstacle the generalization is that different prediction coefficients 7 can lead to wildly different executions of the recursion, all of which need to be explored in order to optimize for minimizing the empirical regret. high level, recursive algorithms (ReSol ve in Algorithm 2), which we show can be cleanly adapted (ReLearn) to algorithmically enumerate all the possible recursion executions based the free coefficient T
overcome this challenge by presenting standard template for
Recursively Solvable Problems
This section describes the general form (ReSolve in Algorithm 2) of recursive algorithms considered, which in particular captures also all DP algorithms without memoization applied. This template uses the following two higher-order functions:
Definition 1 (Map). Suppose D are two sets and f D + S is function. Map(S, (dI,...,dd) returns a list .f())........... where di...., ds E D and f(d,) E S.
Definition 2 (Reduce). Suppose S is a set and + + ... S is commutative and associative operation. Reduce( @,, [81, 81)) returns
The ReSolve function takes a recursively solvable Para-OP P and known parameters 6, and returns the optimal value and decisions C* and x² for P(f). It has several key components: i) isBaseCase checks if P(0) is a base case, and if so, BaseCase returns the result of P(0). ii) Extract, using the current problem P and current parameters 0, computes the list of subproblems. iii) Branch, using only T, creates and returns list PL of subproblems, and computes the corresponding parameters from both T and the current parameters subproblem in PL is solved recursively, via Map mapping ReSo ve to PL. After the recursive calls, the partial results in RL are aggregated by binary operation via Reduce. As mentioned, the ReSolve ve template also captures iterative algorithms as recursion with a single branch.
information T which will determine
iv) Each
We also restrict attention algorithms satisfying: the only arithmetic operations involving the unknown parameters are +, -, max, min and multiplication with known constants, ii) there are no conditionals within Branch, and iii) isBaseCase is independent of the parameters 6.
Example 2. ReSol 1 ve_Kv____ KS in Algorithm 3 is instantiation of ReSol I ve for solving the project funding (0-1 knapsack) problem Example 1. ReSol vi__v_____ KS takes inpul (p, e, n, W. S) where is the number of remaining projects to consider, W is the available funding, and S are the

---

Algorithm 3: Recursive Solving and Recursive Learning for 0-1 Knapsack Problem
Function ReSol ve_ _e____ n, W,S):
Function ReLearn Reeiearn_KS(ppcGG
C, S,
2
if nt = 0 or W < 0 then
10 if n = or W S then
R 1W 0) Liespli]:
R[]] CiesP,1i)
else
else
5
[1 Pa| + Branch__att c. n, W, 1)
[P1, P2] +
RL Map(Resllve KS, PL);
BranchL ks n,n, W, S);
7
R + Reduce RI));
14
RL + Map(ReTeamm rn rn_ksn_____________ PL);
R[T] < Reduce RT.);
8
return R;
return R[T];
selected projects so far: Initially, S 0. Extract KS no-op. Branch RS returns [(p c, n W, S), 1, ( the two subproblems for whether the n²th project is selected or not. isSaseCase checks if the total cost exceeds the budget or if no projects are left to consider.
Limitations of requirements the recursive algorithm Before Example quirements on recursive algorithms considered in this paper. Even though the framework is general, there are algorithms that the framework excludes. Perhaps the most stringent restrictions on the arithmetics we allow in ReSolve ve. Using two examples, we illustrate some limits of our framework.
specified re-
One simple (but perhaps unnatural) problem that the proposed framework cannot handle directly the following: given n items with unknown "rewards" r, find the two items with the maximum product of their rewards (rery). Computing the product of rewards involves multiplying (instead of adding) unknown parameters, which our framework cannot handle directly. On the other hand, the problem is equivalent to maximizing the sum of the logarithm of the two rewards. Thus, in this case, a simple reformulation the problem makes it amenable to Branch Learn (though whether the learning would work well is a different question, and depends the data and the parameters).
However, we can make the problem and objective slightly more complicated (and contrived): choose 3 items, and maximize the sum of pairwise products of rewards, i.e. find items i, j, k to maximize ryr, + TyTk Tyrk- It much less obvious how we can find natural reformulation of the problem that makes it still amenable to Branch & Learn, illustrating some of the limits of the approach.
The Branch & Learn Framework
The proposed Branch & Learn (B&L) framework methodically transforms recursive algorithm (ReSolve in Algorithm 2) as described in the last section into Predict+Optimize learning algorithm. In particular, we adapt the recursive algorithm into the Relearn template of Algorithm 2, for use as the Convert function (line The intellectual core of the approach Algorithm 1.
Recall from Section 2 that, in the context of the coordinate descent algorithm (Algorithm 1), Convert (ReLearn here) takes as input i) the problem P, c.-nosttrueeed from as well as the current training example (A, the problem P expressed
function of the free coefficient coordinate 7, and ii) the domain To of 7, also constructed from (A, 0) (for example, to ensure basic properties of parameters such non-negativityy. From these inputs, ReLearn computes piecewise linear function, mapping intervals (that partition In overall) to objectives (computed under the estimated parameters) of estimated optimal solutions using y taking values within that interval. To construct such a ReLearn procedure, we can simply adapt from the corresponding ReSolve algorithm, and we explain each component of ReLearn here.
ReSolve (Algorithm 2) comprises isBaseCase, BaseCaseL, ExtractL, BranchL, Map and Reduce. Since isBaseCase, Map and Reduce do not directly involve any parameters, they are unchanged from ReSolve. As for BaseCaseL, Ext ract and BranchL, they are obtained from ReSolve by replacing all arithmetic operations with their piecewise linear generalizations.
With these component functions, the structure of ReLearn can then be based on that of ReSol 1 ve. ReLearn first checks whether the current subproblem is base case, and if so, returns the corre-
5

---

sponding objective under the estimated parameters. Otherwise, it performs the recursion as follows: i) Extract computes information T, for deciding which subproblems branch into, where crucially this information will depend on the parameters and hence also on the free coefficient 7. Thus the result of ract. is data structure mapping each disjoint subinterval of To to some information [T]. In ReLearn, we denote the set of subintervals as T(T,). ii) With the result of Extractinn we iterate over each / E I(TT),, and perform the corresponding BranchL, Map and Reduce to get the estimated objective values for each y E I. Note that, since we map ReLear instead of ReSolve ve to PL, even within the current interval 1, the final estimated objective will generally be further subdivided into smaller pieces. Thus, within I, it will be piecewise linear function instead of just a linear function. Reduce, using the canonical piecewise linear extension E of (B, handles the further subdivisions as desired. iii) Finally, the resulting piecewise linear function R[[] is returned.
The adapted ReLearn_ in Algorithm 3 solves the parameterized 0-1 knupsack problem with the inputs of the parameterized problem P = (px, C, n, W,S) S) and an initial domain Io. The estimated profits P- is an array of linear functions of the free coefficient 7, and Io is the initial domain depending are essentially the same as those of ReSolve_ KS (Algorithm 3), except that the addition in line 11 and the max operation in the Reduce function are replaced by their canonical extensions.
Example 3.
A' such that p, 2 0 for all r E lo. The components of ReLearn KS
We also note that, while it is possible to completely formalize the framework into a syntactic transformation, the correctness (or the required restrictions on ReSolve) of the formalization will depend highly on the precise programming language used (e.g. issues of side effect), and require significant low-level work on the level of the grammar of the language, detracting from the key intuitions and principles behind our framework. For this reason, we do not embark on such formalization in this paper. Nonetheless, in the next section, we give several case studies showcase problems that are amenable to our framework and show how to adapt those recursive/iteratiee algorithms to ReLearn functions, demonstrating the applicability of the proposed framework.
5 Case Studies
This section gives several case studies for our framework. We first demonstrate, using the example of the shortest path problem (SPP), how our framework can recover the DP based method of Demirović et al. [5]. We then showease our framework on a more complicated iterative algorithm for solving the capacitated minimum cost flow problem (MCFP). To demonstrate the full recursion generality that our framework can handle, we use it on the tree-search algorithm for the NP-hard problem of minimum cost vertex cover (MCVC). The last example is the multi-stage scheduling (MSS) problem, which can be handled by our framework straightforwardyy but not by many other prior Predict+ Opttiize methods. We describe the problems in the main paper while details are given in Appendix A.
Shortest Path Tabular DP can be viewed as an iterative algorithm, computing the subproblem table row by row-the Branch operation in ReSo lve generates single subproblem P', which is independent of the unknown parameters (only the parameters to P' depend on the unknown parameters). With this perspective, the work of Demirović al. [5] is special case of our method.
concrete example the Bellman-Ford algorithm [2] for SPP in a weighted directed graph with potentially negative weights. We instantiate ReSolve for solving SPP to obtain ReSolve_SPP as follows. Suppose V is the set of vertices of the graph. The inputs of ReSolve_
are (G D, 8, NN, where G E IR [ is a matrix with entry (G)).. equal to the cost along the directed edge uv, N is a counter, D is an array of shortest (V N -h)hhp distances from the source to each vertex, and and t are the source and terminal. Initially, N = =iV|- and all elements in D are initialized to sufficiently large number (signifying infinity), except that D[s] is set to 0. isBaseCase__sa SPP tests whether N = 0, and BaseCase_ s_t_sss__P_PPP___ returns D(t). Extract_SPP computes array D' where each element D'[v) is computed by iterating over every vertex / and computing D' ['uu] = min(
((n] p). D uJ] + (w)) Branch_ Sappachh_pPp_____ returns a single subproblem [P'] where P' (G D', s,t,N - 1), on which ReSolve SPPP is called recursively.
We consider the Predict+Optimize setting where the edge costs are unknown. In the parameterized problem P,,, parameterized by the free coefficient y in the coordinate descent, the edge costs are non-negative parameters represented by linear functions of 7. Correspondingly, all operations in ReLearn_ SPP involving edge costs are replaced by their piccewise linear counterparts (Section 2).

---

ReLearn_SPP outputs a piecewise linear function that is the cost of the estimated shortest path under the estimated parameters. which as explained in Section 2 can be used to compute the regret. See Appendix A. for the pseudocode of ReSol ve_SPP and ReLearn_sPP
Capacitated Minimum Cost Flow We now apply the B&L framework to another iteratively solvable problem: MCFP in a directed graph, where at most one edge exists hetween any two vertices. Each graph edge has a non-negative capacity and a non-negative cost per unit of flow. Given input K, we want to find the least cost to route K units of flow from the source s to the terminal t. We consider the parameterized problem where only the edge flow costs are unknown.
We instantiate ReSolve for solving MCFP using the successive shortest path algorithm [16], to obtain ReSolve MCFP. Suppose the set of vertices is V. The inputs of ReSolve @SSoive_MCFP
R VI and G E IR 20 |V|x|V|
(GP, G s,t. The two matrices GP and the edge (unit) flow cost of the graph respectively. For the successive shortest path algorithm, we preprocess the graph by adding, for every edge ue in G, a reverse edge ew with 0 capacity and the negated cost (G The variable F' E [ edge so far. isBaseCase MCFP tests whether there is no longer path from to t with non-zero capacity in GP or whether the sum of all flows sent to is no less than K, and BaseCase_MCR adds the costs of all flows in F, i.e. R E(n.v) Fuu (G)).v Extract_McFF computes path T from & with lowest cost (per unit flow) in GO. Branch_MCFT updates the capacity graph GP and the flow graph F given path T' The capacity of each edge in the path 7 is decreased and the capacities of the reverse edges in GP are increased by the value of the sending flow. The value of the sending flow is the minimum value between the largest flow value allowed on T and the remaining flow need be sent to The flow is also added to F. ReSolve_ MCFF is called recursively on these new GP and F as well as the original G", s and t.
represent the edge capacity
20
is matrix representing the flow sent along each
Correspondingly in ReLearn RM_M the input is problem P., parameterized by the free coefficient Y, and all edge costs (the unknown parameters) are expressed as linear functions of 7. The initial domain To for 7 is restricted that the edge cost estimates non-negative for all 7 To- Extract MCFP adapts from the Bellman-Ford ReLearn_St _SPP in the previous case study, which computes a piecewise data structure T. mapping intervals (for 7) to different shortest paths (in addition to just the path lengths). For each interval I of T,, Branch_MCF3 constructs a subproblem Pa, by updating GP using T. [T. Relearn MCFF is recursively called on P', until the base case is reached. See Appendix A.2 for the pseudocode of ReFF and ReLearn_Mee _CFP.
Minimum Cost Vertex Cover Our third example is the MCVC problem, where show how to apply our framework to a (non- graph G = (V, E), there is an associated cost c E R denoting the cost of picking each vertex. The costs are unknown parameters. The goal is to pick subset of vertices, minimizing the total cost, subject to the constraint that all edges need to be covered, namely at least one of the two vertices on an edge needs to be picked. This problem is relevant in applications such as building public facilities. Consider, for example, the graph being a road network with edge values being traffic flow, and we wish to build speed cameras at intersections with minimum cost, while covering all the roads.
recursive algorithm (with multiple branches). Given a
The recursive algorithm reSolve_Mon _CVC takes input (G, CC,e&&.. n, chosen), where G,G,& & are as before, n is the number of levels of (binary) recursion remaining and chosen is the current list of chosen vertices. BaBaaeeCae__Maee __MV checks if n = O, and RaseCase_MCC __MC returns the total cost of vertices in chosen if all edges in G are covered, and returns infinity otherwise. Extract_Mcve a no-op. Branch_MCyy creates two subproblems (G,c, c, n 1, chosen) and I, chosen U (n]), i.c. choosing vertex or not, and Reduce takes the min of the two op- tions. Correspondingly, ReLearn_ Licearrn__CCCCC_ replaces all arithmetic and min operations by piecewise lin- counterparts. See Appendix A.3 for the pseudocode of ReSolve MCVC and ReLearn_McTV
Multi-stage Scheduling Our last example is the MSS problem, where a set of items needs to be processed by two machines sequentially. Each machine can process only one item at time, and each item must be processed first by machine 1 and then machine 2. Furthermore, the items must be processed by both machines in the same order. The goal is to find an ordering for processing items that minimizes the total elapsed time. For this problem, the unknown parameters are the individual item processing times on the machines. We note that host of prior Predict+Optimize methods
7

---

cannot be applied to this problem, including the tabular DP method of Demirović et al. [5], as well as the recent work of Guler et al. [9] and any linear programming based methods which all require a problem formulation with objective that is bilinear in the unknown parameters and the decision variables (that is, a dot produet between these two vectors). Our method on the other hand handles this problem relatively straightforwardly by directly adapting Johnson's is rule. See Appendix A.4 for details of ReSolve_Msr MSS and ReLearn_MSS as well as their pseudocode.
Comparing Branch & Learn with Latest Work
Both Branch & Learn and the work of Guler et al. [9] are exact methods for Predict+Optimize, since they both directly optimize the regret, instead of any surrogates. Both also use coordinate-descet as the high-level optimization routine. The main differences lie in the kind of problems that the methods can apply to, as well as the very different techniques used to achieve each coordinate poordinate-descent step.
In terms of applicable problems, Branch & Learn applies to all optimization problems solvable by an algorithm fitting the ReSolve template Section 3. On the other hand, [9] applies to problems with an objective that is bilinear in both the decision variables and the unknown parameters- -te objective the inner product between the two vectors. There are problems amenable to Branch & Learn but not [9], and vice versa. Here we can give some intuition about when each method is applicable.
Suppose we have an optimization problem with a finite feasible solution set. For most practical purposes, such a solution set is enumerable by a recursive algorithm (but not always, since finite sets need not be enumerable for computability reasons). If, additionally, the objective function is bilinear as in the assumption of [9], then Branch & Learn would be able to handle such a problem. In this sense, an optimization problem with finite solution set that is solvable by [9] would also be solvable by Branch & Learn. The multi- stage scheduling problem with unknown per-item/machine processing times is an example problem with no such bilinear-objective representation (unless we use an exponentially large integer linear program to represent the problem, with exponentially many unknown parameters), yet is easy to fit into our framework.
On the other hand, if the solution space is continuous, Branch & Learn might not be able to handle such an optimization problem. The reason is that Branch & Learn (as it is currently formulated) requires explicitly computing the entire empirical regret function, which is possible only if the regret has a finite representation (say, as a piecewise linear function). When the solution space is continuous, the regret might be general smooth function even if the objective is bilinear. By contrast, [9] never computes the entire regret function explicitly. Instead, just computes the regret function at query points, and performs numerical optimization on the function (which is convex when the objective is bilinear). this sense, [9] is more capable than Branch & Learn these continuous settings.
In terms of techniques, Branch & Learn automatically generates the "transition points" in the piecewise linear functions by essentially simulating the recursive algorithm. This contrasts the approach of [9], where they leverage the convexity structure in the problem arising from their bilinearity assumption on the objective, and they use a numerical optimization approach (essentially variant of binary/ternary search) to perform a mordiintte-esceen step.
7 Experimental Evaluation
In this section, we compare our proposed B&L method with other methods for Predict+Optimize. We include 4 classical regression methods: linear regression (LR). k-nearest neighbors (k-NN), classification and regression tree (CART) and random forest (RF) [8]; 3 approximation methods: smart predict then optimize (SPO) [6], quadratic programming task loss (QPTL) [17], and interior point based approach (IntOpt) [12]; and exact methods: SPO tree and SPO forest [7]. We experiment on three optimization problems: MCFP, MCVC and MSSS-problems that the previous DPP method cannot handle- and use both artificial and real-life data on real-life graphs. For MCFP, we use USANet [11] (24 vertices and 43 edges) and GÉANT [10] (40 vertices and 61 edges). For the NP-hard problem of MCVC, we use two smaller graphs from the Survivable Network Design Library [13]: POLSKA (12 vertices and 18 edges) and PDH (11 vertices and 34 edges). MCFP, the edge costs are unknown, and the capacities are sampled from [10, 50). The flow value is set to 20, and we select random sources and sinks. In MCVC, the edge costs are unknown. In MSS, the processing times for each item and machine are unknown. We vary the number of jobs from 10 to 40.
8

---

Table 1: Mean regrets and standard deviations for MCFP with unknown parameters.
Araiiia Diiset
Hie Dinnet
USANS
GIAANT
USANCE
GRANT
Size
103
2011
120
301
103
HBV
100
300
TBR
TGPP MA
122
Y2ASHAUS
4X
LX
1798 022-928.0
1149 241091 16
76a. 158385 OY
245.206 28X.204.299 Ms
171-994156.5 53
141 01 60
614185k 111
X5 18.06461.21
2-NN
1783 00..002283..8 84
7991614715.00
801.55390.87
759 7598772278.6 67
285 063.902260000 60
223.95x:12..8 56
137-73679.25
121-75x68.45
CART
2329, 029.7744999.0000 06
2436.3 14363774922.00 07
1310-52-422775
1260.654347.5 26
339.414219.50
313.364:755.0 566
157.83262.1 13
194.62458.12
RF
1781 54-354443 26
138002687
103. 103.02456-31
2193 5775977700 07
2071
1011
907.578252.00
204
139.5569362
52,49671
SL11555795
QPTL
2244
1953
259
1796. 098.3337766.4 94
7787777770000
06
200.991
140.98a58.5
62.42568.85
$7.61555.05
SPU'Tire
1743 0887744 PM
1722% 642695 23
1457 1887771199M
(44885 68
185 152-666116.5
153.4741008
163.575107
120.16485.00
SPO Forest
M64089 84
745.436764.07
2477 024-00042220
17% 354 146
145, 524
135 98-1 (0)
192.02477720
Arrrage
10335, 103905
0331.072
Table 2: Mcan regrets and standard deviations for MCVC with unknown parameters.
Artificial Daraser
Real life Dataset
POLSKA
PDH
POI SKA
PDH
Size
100
100
BEL
109.45115.42
110J416635
30.402K.00
53.7125.02
2.2281.36
11820049
7.5736.04
5,5122..2
LR
115.69115.59
116.3618.60
55.1519.98 98
26.5916.70
3.5612.07
3.0910.91
8.3245.86 86
6.1012.67
123.06+117.26
116.97=11.26
56.5848.77
38.36666.16
5.1642.11
5.02+1.00
11.7747.23
9.78=2.91
CART
117.23+14.88
125.61+13.20
89.68-15.95
89 49.4999
5.47+2.29
5.38+1.21
16.92+7 64
11,70+3.51
RF
116.38:14.75
117.13+11.75
58.75:9.88
8416662
4.1721.83
3.91:0.92
13.4517.m 70
7.7613.36
SPO
117.50+16.94
116.7249.1
14.74:14.58
461666666
2.94=1.54
2.78:0.8
10.00+7
6.58:3007
QPTL
118.14118.07
117.5249.14 14
81.70=11.83
79.3115.72
2.58.1.37
2.5740.62
10.8916.19
9.28.1399
IntOpt
119.52+16.04
118.44+9.70 7000
69 14.44
66. 12+8.44
1.55
2.30=0.51
10.9346.55 55
8,79=3.93
SPO
118.90+177
117.55499.4
56.51 00.51+8.900
77.70+6.77
2.68+1.31
2.57+0.65
14,1246.75
11.1944.13
SPO
119:00+18.72
117.25+10.95
55.07+8.96
$6.8566.00
2.8611422
2.66+0.64
13.1147.40
11.45+3.22
Average TOV
649.00s21.02
654.82.11.83
817.76a26.29
622.72411.222
321.1116.11
317.9626.96
102.17430.42
503.57a12.39
We run 30 simulations for each problem configuration. In each simulation, we build datasets con- sisting of n E {100, pairs of (feature matrix. parameters). In the artificial and real-life datasets, each parameter has 4 and features respectively. Given that we are unable to find datasets specifically for the MCFP, MCVC and MSS problems, we follow the experimental approach of Demirović et al. [3, 4, 5] and use real data from different problem (the ICON scheduling competition) as numerical values required for our experiment instances. We use 70%/30% training/testing data split. Details of the data generation method are in Appendix B. We use the scikit-learn library [1] to implement LR, k-NN, CART and RF, and OR-Tools [14] as the problem solver in SPO Tree and SPO Forest. All models are trained with Intel(R) Xeon(R) CPU E5-2630 v2 @ 2.60GHz processors.
Solution Quality Table 1, 2, and 3 report the mean regrets and their standard deviations for each method on MCFP, MCVC and MSS respectively. Mean regret + sid is the metric used to demonstrate the performance. At the bottom of the table also report the average true optimal values (TOV) to compare the relative error on the artificial and real-life datasets.
As shown in Table 1, B&L achieves the best performance in all cases. On the artificial dataset, B&L, LR, k-NN, RF, IntOpt, and SPO Forest achieve similar performance on both of the two graphs, while SPO Tree performs well on USANet but has a poor performance on GÉANT. With the real-life dataset, B&L shows the most significant advantages. Compared with other methods, B&L obtains 20.38% -3.35% (n- 100) and 1..1%%660 60.-600.666 60.86% (n 300) smaller regret on USANet, and 12.13%- 54.11% % (n = 100) and 18.70%%-4.8. 4.3% (n 300) smaller regret on GÉANT. We observe that all methods achieve smaller relative error with real-life data than with artificial data. B&L, for example, achieves 1466-15.68%% and 1.12%%2.7%%% relative error with artificial and real-life data respectively. This is consistent with how the artificial dataset is purposefully designed to be highly non-linear (see Appendix B), and thus harder to learn. Nevertheless, B&L still achieves the smallest regret.
Table shows the results for MCVC. We can see that B&L has the smallest mean regrets in all cases. On the artificial dataset, all methods achieve similar good performance on POLSKA, while CART and all approximation methods perform poorly on PDH. The performance differences among different methods are larger in the real-life dataset, and the advantages of B&L are more evident. B&L obtains 12.95%-59.41 (n = 100) and 5.22%-55.533% (n = 300) smaller regret in POLSKA, and 2.05%-55.26% (n 100) and 9.71%-52.889
(n 300) in PDH. Similar to the results of MCFP, all algorithms achieve better performance in the real-life dataset. B&L achieves 6. 16%--16.86% relative error in the artificial dataset, and 0.68%-1.51 % relative error the real-life dataset.
Our implementation is available https//ggittbb.ooo//dddaaa////ut BranchAndLeanm

---

Table 3: Mcan regrets and standard deviations for MSS with unknown parameters.
Artifccal Dabiece
Real-Iif Thilnee
Johs
40 Jobs
10:lobs
Jobs
100
300
B&L
112.23210.74
118.0336.40
216.23::8.10
220.88+12.25
2,633:1
2.4120.37
18.52a2.98
21.1711.55
LR
121.91a12.12
121 5316.66
226.71621.35 134
225.80116.266
3,0811 37
2.82100.58
20. 20.78.:3.55
23.4812.01
A-NN
122.//114.31
123 3926966. 98
227. 007.96=288.4 40
221.45+12.00
7.88+2 14
7.46600.93
54. 54.24e7.81
48.2364.17
CART
117.79414.46
123.6747.41
225.29924.91
227.99412.45
8.5342 23
6.4340.96
52.45:8.86
35.1925.50
120.72412.35
123 9016..661
223.29
228.13116.86
5.71a1.00
31.01a:124
SPO Thee
122.21+16.07
122
231.14=1008
229,43+17.39
4.53+1
4.19+0.83
29.21
42.98=5.59
SPO Forest
125.37412.52
121 66
223 223.20:22.00 00
230.55412.96
3.38+1 40
3.3140.69
46. 18=10.05
35,5943.25
Average TOV
1215.1925588
1223 12216616
1606.86157.62
4599.35138,33
518.9911979
55005113.55
26:1.8613.:5
Table 4: Average runtime (in seconds) for MCFP, MCVC and MSS on real-life data.
Minimum cost flow problem
Minimum cost vertex covering problem
Multi-stage scheduling problem
USANet
GEANT
POLSKA
PDH
10 Jobs
40 Jobs
Size
100
300
300
B&L
22.47
70.37
20.63
59.17
651.76
1965.00
298.22
896.00
8.02
27.74
1427.34
4302.60
SPO Tree
20.94
61.93
35.94
439.19
484.77
6281.35
223.53
2798.22
7.88
41,80
156.56
4683.33
SPO Forest
17.26
73.05
22.07
369.21
980.32
4277.86
488.36
2125.27
11.03
49.17
66.05
2424.03
We show the mean regrets and standard deviations in the MSS experiment in Table Note that linear programming based methods including SPO, QPTL and IntOpt are not applicable to this problem as mentioned in Section 5. Due to the space limitation, we only show the results when the number of johs is 10 and 40-see Appendix C for more results. B&L has the best performance in all cases with the rial-life dataset, achieving 0.4 0..9% relative error compared to the TOV. Contrasting other methods, B&L. obtains 14.58%-69.22 100%%%6660088 (n 100) and 14.47%-6? 77.7%%667.7774 73% (n 300) smaller regret for 10 jobs, and 10. 60.55%-65..0 65.85% (n = 100) and 9 9.84%-55..00% (n = 300) for 40 jobs. On the artificial dataset, all algorithms perform essentially the same, achieving 4.69%-9.65% relative error.
Scalability/Runtime Learning using regression or approximate methods fast, but these methods sacrifice the accuracy of the learned model, which is the motivation for the line of work on Pre- dict+Optimize. On the other hand, many optimization problems are expensive to solve. Although exact methods achieve lower regret, their runtime scalability can be an issue since their learning process requires solving optimization problems multiple times. For a fair comparison, therefore, we compare B&L only with other exact methods: SPO Tree and SPO Forest. Table 4 shows the average runtime across 30 simulations for different cases. Overall, we observe that B&L scales at least as well as SPO Tree and SPO Forest in most of the cases. Of note is the (MSS, 40 jobs, dataset size 100) setting where B&L runs slower than SPO Tree and Forest, due to the fact that MSS is a permutation- based scheduling problem, where B&L takes significant training time to explore all the possible predictions. Nonetheless, if we consider the ratio of runtimes between dataset sizes 100 and 300, B&L scales significantly better than SPO Tree and Forest with respect to the dataset size.
8 Summary
Given ReSol ve function for recursively or iteratively solvable problem, we propose systematic approach to synthesize a ReLearn function for learning with the regret loss, by replacing operators in ReSolve with their piecewise linear counterparts. Our proposal is methodical and straightforward to implement. Furthermore, our framework encompasses a wide class of recursive algorithms demonstrated by our case studies. Most importantly, B&L empirically achieves the lowest regrets against classical machine learning and contemporary Predict+Optimize algorithms with runtime comparable with the latter.
vve
(ReSolve ve functions),
Acknowledgments
We thank the anonymous referees for their constructive comments. In addition, we acknowledge the financial support of a 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.
10

---

References
[1] L. Buitinck, G. Louppe. M. Blondel, F. Pedregosa, A. Mueller, O. Grisel, V. Niculac, P. Pretten- hofer, A. Gramfort, J. Grobler, R. Layton, J. VanderPlas, A. Joly, B. Holt, and G. Varoquaux. API design for machine learning software: experiences from the scikit-learn project. In ECML PKDD Workshop: Languages for Data Mining and Machine Learning, pages 108-122, 2013.
[2] T. H. Cormen, C. E. Leiserson, R. L.. Rivest, and C. Stein. Introduction Algorithms, Third Edition. The MIT Press, 3rd edition, 2009.
[3] E. Demirović, P. J. Stuckey, J. Bailey, J. Chan, C. Leckie, K. Ramamohanarao, and T. Guns. An investigation into prediction optimisation for the knapsack problem. In International Conference on Integration of Constraint Programmingg Artificial Intelligence, and Operations Research, pages 241-257, 2019.
[4] 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. In Proceedings of the Twenty-Fighte International Joint Conference on Artificial Intelligence, pages 1078-1085, 2019.
[5] E. Demirović, P. Stuckey, T. Guns, J. Bailey, C. Leckie, K. Ramamohanarao, and J. Chan. Dy- namic programming for predict+otiimise, Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, pages 1444-1451, 202...
[6] A. N. Elmachtoub and P. Grigas. Smart "predict, then optimize". Management Science, 68(1):9-26, 2022.
[7] A. N. Elmachtoub, J. C. N. Liang, and R. McNellis. Decision trees for decision-making under the predict-then-optinie framework. In Proceedings the 37th International Conference Machine Learning, pages 1558-2867, 2020.
[8] J. Friedman, T. Hastie, and R. Tibshirani. The elements of statistical learning, volume 1. Springer series in statistics New York, 2001.
[9] A. U. Guler, Demirović, J. Chan, J. Bailey, C. Leckie, and Stuckey. A divide and conquer algorithm for predict+ optimize with non-convex problems. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 3749-3757. 2022.
[10] M. LLC. Geant topology map 2ec2018 copy. https: /www geant. arg/Resources Documents/GAAn TewieNTTTTppooio w 09-10.
Map_Deecmber_ beaeeeeeberreee...._1eeeee 2018. pdf, 2018. Accessed: 2020-
[11] D. Lucerna, N. Gatti, G. Maier, and A. Pattavina. On the efficiency a game theoretic approach to sparse regenerator placement in WDM networks. In GLOBECOM 2009-2009 IEEE Global Telecommunications Conference, pages 1-6. IEEE, 2009.
[12] J. Mandi and T. Guns. Interior point solving for LP-based prediction+ optimisation. Advances in Neural Information Processing Systems, 33:7272-7222 72822, 2020.
[13] S. Orlowski, M. Pióro, A. Tomaszewski, and R. Wessäly. SNDlib 1.0 (urvivvive Network Design Library. In Proceedings of the 3rd International Network Optimization Conference, April 2007. http://sndlibzzi..de extended version accepted in Networks, 2009.
[14] L. Perron and V. Furnon. OR-Tools.
https: /tos:///deeee devel opers www.ss.oooogo..om com/
optimii zat o,. 2022.
[15] M. Von Mohrenschildt. A normal form for function rings of piecewise functions. Journal of Symbolic Computation, 26(5):607-619, 1998.
[16] G. R. Waissi. Network Flows: Theory, Algorithmms, and Applications. JSTOR, 1994.
[17] B. Wilder, B. Dilkina, and M. Tambe. Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization. In Proceedings of the Thirty-Thirl AAAI Conference on Artificial Intelligence, pages 1658-1665, 2019.


Reviews:
[{"review_id": "h4X0Kk2jb5-", "reviewer": "Reviewer_2JwE", "summary": "The paper presents a novel predict+optimize framework, named Branch and Learn, that extends the work of [5] to problems solvable via a recursive algorithm. Experimental results show that Branch and Learn performs better than competing methods and supports a wider variety of benchmarks.", "questions": "Could the authors detail the high-level differences to [9]?", "limitations": "It would be nice if the authors could group all the limitations of their work in a section in the appendix.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The experimental results consistently show that Branch and Learn yields lower regret than many existing methods on a variety of benchmarks, without incurring significant overheads. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "e508M6v69jN", "reviewer": "Reviewer_1y7n", "summary": "The paper considers the predict+optimize problem where a constrained optimisation problem contains parameters that are unknown at the time of solving. Specifically, a branch&learn framework is developed to deal with problems solvable by a recursive or an iterative algorithm. The framework extends recent work that focuses on dynamic programming type of algorithms. The experimental evaluation is carried out on an extensive set of benchmarks and demonstrates the superiority of the proposed approach compared with existing state-of-the-art methods.\n", "questions": "1. In the experimental evaluation, how many intervals do you consider for the piecewise linear functions? How do you choose the intervals?\n \n2. Dynamic programming can also be viewed as a recursive procedure but in the opposite direction and therefore I'm wondering if the approach described in Demirovic et al AAAI-20 paper is equivalent to the one proposed here. Is recursion here meant to capture search-based algorithms like depth-first branch and bound?\n\n[Post Rebuttal] Thanks for your answers. They clarified some of my concerns.", "limitations": "see above", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is fairly well written and organised. The experimental evaluation appears to be comprehensive in terms of benchmark problems and includes relevant baselines.\n\nHowever, a major weakness of the paper is the quality of the presentation which is rather poor in my opinion. I think the paper needs a more detailed running example that would add more clarity to the technical contribution. Examples 1, 2, and 3 are good but they are too high level to help the reader get a better understanding of the proposed algorithms. I suggest adding more details to the project funding example such as: a possible choice of intervals for the piecewise linear function, the search tree that illustrates the recursion process, as well as example features and training data that is used to learn the unknown parameters. \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_0nY5D94i5Y", "reviewer": "Reviewer_nihh", "summary": "In the Predict+Optimize framework, parameters (costs) of an optimization problem are predicted from features and then processed by a combinatorial algorithm (solver). This paper fits a narrower line of P+O works that aims to learn a linear model minimizing the regret (difference of predicted and true objective value). As the regret is non-differentiable, standard gradient-based methods cannot be used. Existing methods either use surrogate gradients (called approximation methods, like SPO [6] for instance) or coordinate descent with exhaustive search (called exact methods). Exact methods are less general (linear model), require more resources (large run times), but achieve better performance (smaller regret).\n\nThis paper builds on an exact method of Demirovic et al. [5] that allows for using any tabular dynamic programming algorithm (DP) as a solver and extends it for optimization problems solvable by a recursive algorithm (under some mild conditions). The authors explain the background in detail, describe their approach (denoted as B&L) and how it covers existing algorithms. Finally, they experimentally show the method's performance on existing and also one new case-studies compared to competing methods.", "questions": "- I did not understand the run times scaling paragraph. From Algorithm 1 it seems that the method scales linearly with dataset size $n$ which is also in consent with the experimental results. Can you also comment why SPO tree and SPO forest do not scale linearly as well?\n- Coordinate descent may get stuck at a non-stationary point if the level sets are not smooth. In theory, this may occur. Does it happen in practice? Can the coordinate descent be adjusted to other than canonical basis?\n- Why don't you include the experimental comparison to [5] when applicable, as B&L generalizes it? The performance should be the same, but the runtime comparison might be useful.\n- You claimed that method of [9] is not applicable to Multi-stage scheduling algorithm. Does B&L also generalize this work, or is there any real-world applicable algorithm that fits [9] and not B&L?\n\n**Suggestions**\n- Algorithm 2, Function ReSolve: $R$ is not defined, should be $(x^*,C^*)$ instead?\n- The tables with experiment results are hard to parse. A (box)plots would be much more reader-friendly.", "limitations": "The authors addressed the limitations and I found no negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The method is new and generalizes [5] from DP to recursive algorithms.\n- The article is logically organized, well written, typed with care without many misprints. It is easy to read; I found it as one of the most comprehensible in this line of work.\n- My major concern is in significance. This research area is very narrow and fits more into operations research community, where the domain of use is fixed and the performance requirements outweight the large runtimes. I do not think that it is very likely that NeurIPS audience would benefit much from or build upon ideas presented in this paper.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8vsbl5PfdA", "reviewer": "Reviewer_v3Mn", "summary": "This paper proposes the Branch and Learn framework for Predict+Optimize. In this setting, the parameters of an optimization problem are learned from features, and the goal is to predict parameters such that the corresponding predicted solution achieves a low regret under the true parameters.\n\nThe proposed framework falls under the category of exact methods, which in contrast to approximate methods do not rely on computing gradients of regret relaxations, at the cost of increased runtime and restriction of the parameter prediction to linear functions.\n\nThe framework is applicable to learning the parameters of optimization problems that are solvable via recursive algorithms (under some restrictions). This generalizes previous approaches, which were applicable to iterative and dynamic programming algorithms, to also cover e.g. combinatorial search methods.\n\nOn a technical level, the framework follows previous works by performing coordinate descent in the parameter space, i.e. all parameters are held fixed while a single one is updated to achieve the best possible regret over the dataset. To compute this update, it is necessary to construct a function that for a single datapoint computes for every value of the free parameter the corresponding optimal value of the optimization problem. This function is piecewise linear, with the disjoint intervals defined by constant optimal solutions of the optimization problem over the interval. Computing this function is challenging, as depending on the value of the free parameter, the computational flow of the recursive algorithm for solving this problem can dramatically change. The authors provide an algorithm template, which is based on the original recursive algorithm, that computes this piecewise linear function, importantly exploiting the same algorithmic tricks incorporated in the original algorithm (e.g. optimal substructure).\n\nThe paper demonstrates the wide applicability of the framework in multiple case studies, covering manifestations of the framework for the shortest path, capacitated min-cost flow, min-cost vertex cover, and the multi-stage scheduling problem.\n\nFinally, the authors conduct an experimental study, comparing their proposed method to multiple classical regression methods as well as three approximation methods and two exact methods. The experiments include the min-cost flow, min-cost vertex cover, and multi-stage scheduling problem, with each experiment considering an artificial dataset and a real-life dataset of varying difficulty and size.\n\nThe experiments show that the proposed method consistently outperforms all baselines in terms of mean regret. In terms of runtime, it is comparable to (and mostly faster than) the other examined exact methods, while clearly being much slower than approximate and classical regression methods by design.", "questions": "See weaknesses in the quality section: Is there a good reason for the missing comparisons?", "limitations": "- The authors have addressed limitations of saclability/runtime.\n- The authors have addressed limitations of linear prediction.\n- The authors have addressed limitations of requirements on the recursive algorithm, however, it would be good to name an example of an algorithm that does not fit these requirements to give a better idea of the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Originality\nThis paper generalizes and extends previous works. The idea of using coordinate descent with an adapted version of the optimization problem as an exact technique for predict+optimize is not novel, but it is the first method to allow predict+optimize for general recursive algorithms.\n\n### Quality\nOverall the quality of the paper is good, the only weakness in terms of quality I could identify was in the experimental comparison to previous works.\n\nI believe a comparison (in terms of runtime and performance on the MCFP and the MSS) to the framework presented in [1], which captures algorithms based on dynamic programming, would have been important, as the presented method claims to generalize this work.\n\nI would also like to point out that a (very similar) version of [2], which is not compared to as it is a very recent publication, already appeared on arxiv [3] in 2020, therefore a comparison to this work could also have been possible, which would have been very interesting given the close relationship between the two methods.\nBesides an experimental comparison, it would be good to know if there also exist problems that the framework in [2] can handle, and the presented method cannot.\n\nA minor comment is that it could be good to add some additional more general related work on combining deep learning and constrained optimization, e.g. differentiating through the optimal solutions of convex and combinatorial problems when the optimization problem is not the final component of the architecture.\n\n### Clarity\nThe clarity of the paper is good.\n\n### Significance\nI find the setting of restricting the prediction network to a linear layer very limiting, as it prevents the use of any of the deep learning methods that have proven to be extremely powerful at extracting parameters for decision making even from raw data. Such deep learning approaches are possible with the approximate methods mentioned in the paper, while they are out of reach for the presented method.\nHowever, I agree that there are also important applications of such a shallow learning approach, and in the line of work revolving around this setting, the presented work seems to be significant. It generalizes existing methods, allows the use of previously unusable solver algorithms, and shows superior performance on the conducted experiments.\n\n\n###### Literature\n[1]: E. Demirovíc, P. J. Stuckey, T. Guns, J. Bailey, C. Leckie, K. Ramamohanarao, and J. Chan. Dynamic programming for predict+optimise. In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, pages 1444–1451, 2020.\n\n[2]: A. U. Guler, E. Demirovíc, J. Chan, J. Bailey, C. Leckie, and P. J. Stuckey. A divide and conquer algorithm for predict+optimize with non-convex problems. In Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022.\n\n[3]: A. U. Guler, E. Demirovíc, J. Chan, J. Bailey, C. Leckie, and P. J. Stuckey. Divide and Learn: A Divide and Conquer Approach for Predict+Optimize. https://arxiv.org/abs/2012.02342, 2020.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept