Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper presents a learning-based approach to solve combinatorial optimization problems with non-linear objectives and linear constraints. The paper introduces a linear surrogate cost function that can be used by existing solvers, and proposes to learn this surrogate cost in order to efficiently approximate the original problem. This idea is developed in two settings, either for solving individual instances or training a surrogate cost prediction model -- that can possibly be fine-tuned at test time. The approach is evaluated on two industrial problems.
strength_and_weaknesses: **Strengths**
1. The paper is well-written 
1. It addresses an important and challenging problem: non-linear combinatorial optimization 
1. Strong empirical results: clear improvements over the baselines in 2 problems.

**Weaknesses**
1. The paper proposes a surrogate g(c) that is used with the non-linear function f — and not instead of f. Theoretically and intuitively, it is not clear why optimizing f(g(c)) (ie Eq 2) is better than directly optimizing f (Eq 1)
   * I agree with the paper that the proposed optimization (Eq 2) allows to easily handle the linear constraints. But MINLP solvers also generally handle linear constraints (e.g. SCIP).
   * I don’t agree or did not understand the other arguments (see questions 1 to 7)

1. The theoretical analysis (Sec 3.4), that compares “learning solutions” versus the proposed “learning surrogate costs” only holds for a nearest neighbor regressor, which is a very special model and not realistic in practice. Therefore I don’t see how it supports the claims of the paper. 
   * For example, learning solutions for CO problems is often formulated as an auto-regressive task (e.g. Pointer Networks by [Vinyals et al 2015] or the Attention Model by [Kool et al 2019]) 
   * Are there any works that use nearest neighbor regression to predict the solutions of CO problems?

1. Important information is missing in the empirical evaluation:
    * How long did the training take, esp. in terms of number of calls to f?
    * Training datasets are very small: 50 instances for the Embedding Table Sharding problem and 25 instances for the Inverse Photonic Design problem. More information about how training converges and esp. if/how overfitting is avoided would be beneficial. 
    * Regarding Inverse Photonic Design, it is not clear what's the objective and what are the constraints. 
    * It looks like the objective may be the “design misspecification loss”. Which means that the complex constraints are in fact penalized in the objective. This is a fair strategy when feasibility is challenging but then the argument that the proposed method is more able to handle complex constraints than existing works does not seem fair. [Sec 5: “However, these approaches are unable to handle more complex combinatorial constraints that arise in practice such as those in inverse photonic design”]. Or maybe there are other constraints that are handled — hence the need for a clear formulation of the problem.
    * What’s the size of considered instances of the Inverse Photonic Design?





clarity,_quality,_novelty_and_reproducibility: **Clarity & Quality** 
The paper is generally well organized and well written. However there are several claims that need to be clarified and better motivated (see questions below).

**Novelty**
The novelty of the paper is the idea of introducing a linear surrogate to replace the variable of the non-linear optimization problem.

**Reproducibility**
Links to the datasets are provided. The precise description of the models hyperparameters is not provided. 

**Questions**
1. Sec 3.1: “it also helps escape from local minima, thanks to the embedded search component of existing combinatorial solvers”. To which local minima the paper is referring to here? The MIP solver indeed returns a global minimum for (3). But I don’t see the implication on escaping local minima w.r.t c in Eq (2).
2. Sec 3.2: “the N optimization procedures in the data collection stage are independent of each other, and can lead to excessive number of calls to f that are not helpful. ”. Data collection is solving N SurCo-Zero problems. Why would that lead to an excessive number of f evaluations? Isn't having a labeled training set a requirement of the proposed SurCo-Prior-lambda approach?
3. Sec 3.2: There is a confusion with the c_i: they are first introduced as being the labels in the training set {(y_i, c_i)} then $c_i$’s appear in the variables in Eq (4); then they don’t appear in Eq (5) although it is said “given the training set Dtrain”. Is the training set different at the end of this section?
4. Sec 3.2: “if $\hat{c}$ is a mapping to global optimal solution of c, then it will pull the solutions out of local optima to re-target towards global ones, even when starting from poor initialization, yielding fast convergence and better final solutions for individual optimization instances.” What is meant here by “a mapping to global optimal solution of c”? 
5. Sec 3.2: What’s the advantage of “SurCo-prior-λ” (Eq 4) w.r.t. “SurCo-prior” (Eq 5)?
6. Sec 3.2: “but at test time only require the feasible region and not the nonlinear objective.” Since the y is required to predict the c and the objective is defined as a family f(x,y), it looks characterized by y, then I don't understand what is meant by not requiring the objective at test time.
7. Is there any theoretical guarantee or justification on the number of calls needed to optimize f (Eq 1) versus f(g(c)) (ie Eq 2)? 
8. Sec 3.4.2: “the mapping y → c(y) can avoid too many connected components in its image c(Y ), by connecting disjoint components of x∗(Y ) together.” What does “too many” means here? Why would this mapping connect disjoint components?
9. Regarding the baselines: 
   * Why not using SCIP directly? The paper mentions that scale is a challenge for MINLP solvers but at least for the Embedding Table Sharding problem, it seems that the largest instances have 60x4=240 variables, which should be fine for SCIP?
   * What’s the motivation of using derivative-free methods for optimizing differentiable functions? (Appendix)

summary_of_the_review: I would vote for borderline reject.

The main contribution of the paper is the introduction of a linear surrogate cost in order to approximate non-linear combinatorial optimization problems. Although it leads to very good experimental results, the main idea is not well-motivated in my opinion, neither theoretically nor intuitively. This makes it hard to see why the proposed approach would work in general, beyond the two presented problems. Some parts of the paper lack clarity and several general claims/arguments need to be clarified or better justified.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper considers the problem of non-linear optimization with combinatorial constraints. A surrogate model based approach is proposed where the key idea is to learn a linear model of the underlying objective which is optimized via combinatorial solvers (for e.g. mixed integer program solvers SCIP) to generate a solution. This training is done in an end-to-end differentiable manner where the gradients are passed through the combinatorial solver generating the solution conditioned on the input weights (denoted as cost in the paper) of the linear model. There are three classes of the proposed approach: (1) SURCO-ZERO, which is applicable to individual instances of a problem, (2) SURCO-prior, which is applicable to a family of problem instances and (3) SURCO-HYBRID, which warm-starts the surrogate weights with that obtained from SURCO-prior. Experiments are performed on two real-world benchmarks: embedding table sharding and inverse photonic design.

strength_and_weaknesses: - The paper considers an important problem with many real world applications. Experiments demonstrate the efficacy of the proposed approach on challenging domains. 

- I found the paper to written quite well with clear description and motivation of the proposed approach. It will be really useful to the reader if a pseudo-code like algorithmic description of the key steps is added in the main paper.

- It is a little suprising to not see any discussion around Bayesian optimization (1) techniques which are quite relevant for this setting. In fact, similar ideas of incorporating combinatorial solvers (not in an end-to-end procedure) have been investigated in the Bayesian optimization literature (Mixed integer program in [2], semi-definite programming in [3], submodular optimization in [4]). Moreover, the setting of SURCO-PRIOR with multiple problem instances can be handled by multi-task or meta Bayesian optimization ([5, 6]). Gaussian processes are the go-to-choice in Bayesian optimization and there is some work on extending GPs to incorporate first-order gradient information as well ([7]). Please consider contextualizing the proposed approach along some of this related work. I feel most of these approaches cannot handle high dimensionality but still it would be nice to discuss the relevance.



References

[1] Shahriari, Bobak, Kevin Swersky, Ziyu Wang, Ryan P. Adams, and Nando De Freitas. "Taking the human out of the loop: A review of Bayesian optimization." Proceedings of the IEEE 104, no. 1 (2015): 148-175.

[2] Papalexopoulos, Theodore P., Christian Tjandraatmadja, Ross Anderson, Juan Pablo Vielma, and David Belanger. "Constrained discrete black-box optimization using mixed-integer programming." In International Conference on Machine Learning, pp. 17295-17322. PMLR, 2022.

[3] Baptista, Ricardo, and Matthias Poloczek. "Bayesian optimization of combinatorial structures." In International Conference on Machine Learning, pp. 462-471. PMLR, 2018.
 
[4] Deshwal, Aryan, Syrine Belakaria, and Janardhan Rao Doppa. "Mercer features for efficient combinatorial Bayesian optimization." In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, no. 8, pp. 7210-7218. 2021.

[5] Swersky, Kevin, Jasper Snoek, and Ryan P. Adams. "Multi-task bayesian optimization." Advances in neural information processing systems 26 (2013).

[6] Feurer, Matthias, Benjamin Letham, and Eytan Bakshy. "Scalable meta-learning for Bayesian optimization." stat 1050, no. 6 (2018).

[7] Ament, Sebastian E., and Carla P. Gomes. "Scalable First-Order Bayesian Optimization via Structured Automatic Differentiation." In International Conference on Machine Learning, pp. 500-516. PMLR, 2022.
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written and sufficiently novel. I encourage to provide the source code for helping in reproducibility. 
summary_of_the_review: Overall, I found the proposed approach interesting and novel while addressing an important and relevant problem for the ICLR community.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper propose, SurCO, a combinatorial solver using adaptively tuned linear surrogate models. SurCO utilizes off-the-shelf mixed integer linear program solvers and the differentiability through such solvers. With recent advances in differentiation through optimization layers, SurCO enables end-to-end differentiable training of linear surrogate models. Moreover, the authors propose a meta-learning approach, SurCO-HYBRID, that utilizes the optimization results of previously solved ones for more efficient optimization in new but similar problems. The paper provides a rigorous argument why directly learning a mapping from a problem instance to an optimum is difficult. SurCO is tested on two real-world combinatorial optimization problems.
strength_and_weaknesses: ### Strengths
- The paper presents a way to exploit readily available and efficient MILP solvers to solve even nonlinear problems. Especially, the usage of such solvers handles the feasibility of the solution, i.e. integer constraints, seamlessly and efficiently.
- While its basic for SurCO-zero efficiently utilizes off-the-shelf MILP solvers, its combination with SurCO-prior, SurCO-HYBRID provides a meta-learning approach enabling efficient optimization of the same type of problems by transferring knowledge of similar problems.
- The derivation of SurCO-prior is well-motivated from the regularization perspective.
- The authors rigorously show the difficulty of the widely adapted approach &mdash; using machine learning to learn a mapping from problem instances to solutions. 


### Weaknesses
- Limited empirical evaluations
    - Even though the authors admit that there is no performance guarantee, the authors say 'we argue that optimizing Eqn. 2 is better than optimizing the original nonlinear cost'. Considering that the experiments were conducted on two types of problems, this argument is not convincingly supported by extensive empirical analysis or some discussion on the rationale behind it.
- Any discussion on how easier SurCO formulation is compared with direct solution learning?
    - In 3.4, it is shown how difficult it is to learn a mapping from problem instances to an optimum. However, in a sense, SurCO finds an alternative to the optimum solution &mdash; weights of a linear model which can give an optimal solution. Since both have the same dimensionality, on the surface, the reasons for the benefit of SurCO over direction solution learning is not clear. Can you elaborate on this more?
- Reporting more details on the offline data used to fit SurCO-prior.
    - I guess that the number of data, training time, hyperparameters, etc. may affect the performance of SurCO-prior and SurCO-HYBRID significantly. Since the gain of it does not come for free, reporting such detail will be fairer to compare its runtime-related efficiency with baselines.
    - How was the offline data for SurCO-prior in inverse photonic design generated?


### Others
- Offline data for SurCO-prior generation
    - It is interesting that in embedding table sharding, SurCO-prior using offline data generated from DreamShard outperforms DreamShard quite significantly. Maybe some discussion on this highlights further the benefit of the approach.
clarity,_quality,_novelty_and_reproducibility: The description of the methods is clear. However, the details on the offline dataset generation and training details for SurCO-prior (in turn, SurCO-HYBRID) are not given enough to replicate the experiments. Also, some justification for why linear surrogate learning is better than direct solution learning is not well-conveyed. 
summary_of_the_review: The paper proposes an interesting way to solve combinatorial problems which can get the best of both, well-developed combinatorial solvers with their long history and data-driven combinatorial solver. The proposed method SurCO-HYBRID is quite appealing even though some intuition or rationale behind it can be discussed better. However, a weak theoretical justification can be made up by more extensive empirical analysis. Weak empirical analysis and not enough details on the experiment need to be improved. If those concerns can be addressed by experiments on other benchmarks or convincing discussions on the benefit of the method, I would increase my score.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper presents a learning-based approach to solve combinatorial optimization problems with non-linear objectives and linear constraints. It introduces a linear surrogate cost function that can be used by existing solvers, and proposes to learn this surrogate cost to efficiently approximate the original problem.
This idea is developed in two settings, either for solving individual instances or training a surrogate cost prediction model -- t
Training is done in an end-to-end differentiable manner where the gradients are passed through the combinatorial solver generating the solution conditioned on the input weights. The approach is evaluated on two industrial problems.

justification_for_why_not_higher_score: The paper proposes a surrogate that is used along with the non-linear function f.
Theoretically and intuitively, it is not clear why optimizing their proposed formulation is better than directly optimizing the original problem.
The theoretical analysis (Sec 3.4), that compares “learning solutions” versus the proposed “learning surrogate costs” only holds for a nearest neighbor regressor (which is a very special model and not realistic in practice).
Important information is missing in the empirical evaluation:
A discussion on how easier SurCO formulation is compared with direct solution learning could be refined.
justification_for_why_not_lower_score: The paper is well-written and addresses an important and challenging problem: non-linear combinatorial optimization
Strong empirical results were proposed, with some improvements over the baselines in two problems.
Decision: Reject