Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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. 
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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.

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.

However, 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. 

questions: 1. In the experimental evaluation, how many intervals do you consider for the piecewise linear functions? How do you choose the intervals?
 
2. 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?

[Post Rebuttal] Thanks for your answers. They clarified some of my concerns.
limitations: see above
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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).

This 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.
strengths_and_weaknesses: - The method is new and generalizes [5] from DP to recursive algorithms.
- 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.
- 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.
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?
- 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?
- 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.
- 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?

**Suggestions**
- Algorithm 2, Function ReSolve: $R$ is not defined, should be $(x^*,C^*)$ instead?
- 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

The 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.

The 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.

On 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).

The 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.

Finally, 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.

The 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.
strengths_and_weaknesses: ### Originality
This 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.

### Quality
Overall 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.

I 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.

I 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.
Besides 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.

A 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.

### Clarity
The clarity of the paper is good.

### Significance
I 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.
However, 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.


###### Literature
[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.

[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.

[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.
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.
- The authors have addressed limitations of linear prediction.
- 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.
review_title: null

Meta-review: metareview: This paper considers the general setting of the predict+optimize framework, where "optimize" part of the problem is typically solved via a recursive algorithm. The paper proposes a new exact algorithm to directly optimize the regret in this setting. An extensive evaluation of the new methodology is also provided.

This paper represents a significant generalization of the existing techniques and is definitely of interest to Neurips community.
confidence: Certain
Decision: Accept