Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a method to generate solutions to optimization problems that are more amenable to supervised learning tasks. 
main_review: This paper proposes a method to generate solutions to optimization problems that are more amenable to supervised learning tasks. That is to say, when the parameters of a given problem gradually change, the solutions found also gradually change, such that the resultant data points are stable and learnable. This paper is interesting overall and the proposed method is simple yet effective.

1.	The key assumption is that optimization problems typically satisfy a local Lipschitz condition, i.e., if the inputs of two instances are close, then they admit solutions that are close as well. However, this may not be the case for graph problems, where a single local perturbation could result in significant change to the solution.

2.	Figure 3 covers the last part of line 165.

3.	The figures in the paper should be explained clearly. For example, in Figure 3 what is “Generator setpoint”? Since main part of Section 6 is motivated by Figure 3, it is hard to get the points of Section 6.

4.	Can you explain why in Figure 2 (center) the training loss of blue one is so high, compared to its test loss? It seems the training process can indeed improve the test performance even in case of Standard Labels. Does it mean that some patterns do exit in the training set, although they are not obvious to human but can be learned.

limitations_and_societal_impact: Please see the main review
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a method to optimize training data generation for supervised learning approaches to constrained optimization. First the authors show that the existence of various optimal solutions to the problem can make the learning more challenging. Then they Then they proceed with some theoretical insights that link this challenge to the representation capacity of ReLU neural networks. The paper introduces a method for training data generation for CO learning such that CO instances that are close (in terms of specifications) have solutions that are close too. Numerical validation is presented on a job shop scheduling problem (combinatorial optimization) and an Optimal Power Flow problem (non-linear, non-convex constrained pb).

main_review: # Originality

The problem of data generation optimization in the context of CO learning seems original and the proposed bi-level optimization and then its approximation too. There is a related work which handles symmetry and diversity in optimal CO solutions that could be cited:  

Li et al, Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search, NeurIPS 2018

# Quality
The paper is of high quality. The problem of data generation and its influence on the learning task is well motivated. I appreciated the intuition given by the figures, the theoretical justification and the numerical experiments. 

My main concern is about the applicability of the proposed method in general.

* In Algo 1 L3, where does y^\star^(i) comes from? If it is a bound based y^\star^(i+1) then it should be more explicit. Otherwise that would imply that 2 optimization problems are solved at each iteration?
* In L267 “a bound on y^\star^(i) can be inferred from y^\star^(i+1)” do you mean a bound on the value f(y^\star^(i)) ?
* Besides, also L267: warm starting the solver of the new instance with the solution of the previous instance only works if this latter is feasible, which is not guaranteed in general.

* The fact that this bound can be obtained easily is essential for the method to work. I wonder how realistic is this assumption. 
* In the job shop scheduling illustration, I understand that a training set is generated just by “slowing down“ one machine, then there is a way to order the instances such that the assumption holds.
* However this setting does not seem very realistic to me. I would guess that the job shop scheduling is solved repeatedly with different jobs. But if the jobs characteristics are say uniformly sampled in some intervals, it is not clear how to get such order. 
* Another CO problem that is often used as benchmark for learning-based heuristics is the Vehicle Routing Problem (and its variants). Related instances may have the same customers (nodes) but with a different demand in each instance. For a fixed vehicle capacity, the solution of 1 instance is likely to be infeasible for another instance so it won’t provide a bound nor an initial solution to warm-start and accelerate the solver.

* Because the data generation is focused on minimizing the training error, I wonder if the method has an impact on the generalization ability of the learned model to a slightly different test set? 
* Tables 1 and 2: are the reported prediction errors evaluated on the training or test set? 

# Clarity

The paper is generally well-written. I have a few questions and suggestions below:

## Statements to clarify:

* L29-32: the sentence implies that complex CO problems in realistic settings cannot be solved by OR and AI methods. While I may agree that AI-based optimisation may not (yet) be used in such applications, OR methods are of course applied.

* L41-41: “learning good CO approximations in jointly training prediction and optimization models”. I don’t understand this 
* L95: What is meant by “surrogate models” here? This terminology is not used in the cited survey [23]
* L198: what is meant by *small* piecewise linear functions?
* What is the input to the Optimal Power Flow problem? In L347 it is “which generators will be committed to deliver energy and reserves during the 24 hours of the next day” then in L354 it’s the “load demands”. I thought the load demands were the input of the unit-commitment problem. I am confused…
* Figure 2 left: “percent increase in Processing Times” Are the processing times here the objective to minimise or a parameter of the instance? The problem not being defined at this point, I think it would be easier to understand if generic terms such that “objective”, “instance parameter”, etc are used. Or the correspondence clearly stated.
* Figure 3: same remark for “Generator setpoint” and “Base load factor”
* L212 “if the inputs of two instances are close, then they admit solutions that are close as well” and then equation (7): as it is written here, this contradicts the fact the initial observation that instances that are close can have very different solutions. I guess the authors mean *there exist* 2 solutions y(i) and y(j) that satisfy equation (7)

## Typos/details:

* L37: intersection *of*
* L48: may not have a *unique* (?) optimal solution
* L124: in y \in R^n —> remove in or y
* L268, L377 (and others): hot-start —> I believe the term is warm-start 
* L225: the training *of* good…
* L365: for —> form (or remove)
* L379: *is* its restriction 
* L368: when compared the OD approach to *standard* (?) data generation results 
* L368: ... data generation results in predictions that are closer —> not clear
* Equation 7: which norm is used?

# Significance

The idea of this paper is original and interesting. I have a concern about its applicability though. I would have loved to see it illustrated on a strong learning-based method for a CO problem and see that it indeed lead to a better *test* performance. 

# Update after rebuttal 

The authors have addressed my main concerns about the applicability and limitations of their approach. 

Since they mean to update their manuscript accordingly, I am happy to revise my score from 6 to 7.



limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper addresses a different aspect of learning-based problem solvers. 

Typical complex optimization problems are hard to find optimal solutions, and therefore learning datasets for a specific optimization problem class are volatile in general. Following this, the paper develops a method for optimal training data design, which is an optimization problem on the total variation of solutions. With the developed methods, two case studies (JSS and OPF) are demonstrated to show the effectiveness of their proposed methods.
main_review: Personally, I enjoyed reading this paper and am interested in this kind of approach.

- Pros
  - The targeting problem is novel and the author discusses a sound approach to tackle the problem.
  - The idea of using piecewise linear functions to represent the volatility is an interesting and effective approach for the problem illustrated in Fig.3.
  - Compared with the standard method to generate data sets, the proposed method could outperform such a baseline method.
- Cons
  - Explanations in challenges of the paper (Sec.5) are hard to follow. Many ambiguous terms (L1 from Root, Percent Increase in Processing Times, Test Loss, Constraint Violation, OD labels) are used, although the idea behind this part could be important to follow the problem set.
  - Some notations (see below comments) are confusing to clearly explain the idea.

### Questions and comments

- In Fig.1, three groups ($y^{(1)}_i, y^{(2)}_i, y^{(3)}_i$ for $i = 1, 2, 3, 4$) are illustrated, but the subscript $i$ is not explained explicitly. I conjecture that this corresponds to multiple solutions obtained from each instance $x^{(i)}$. What do the colors mean? (objective values?)
- In Eq. (1), $\mathcal{O}(x)$ is defined as the argmin of $f(y, x)$. When I first read this part, I assume that $\mathcal{O}(x)$ is a kind of value (not a set) which is a solution obtained after some methods (e.g., tie-braking, symmetry-braking, etc.). However, as in Sec.4, $y^{(i)}$ is in $\mathcal{O}(x)$ and $\mathcal{O}(x)$ is now a set of optimal solutions. I suggest noting explicitly $\mathcal{O}(x)$ is a (multi) set of optimal (or possibly sub-optimal) solutions to improve the readability.
    - This clarification could be important also for the projection operator $\pi_C$ as well because it is also defined with the argmin statement (i.e., operator finds 'the closest feasible point' = element).
    - This causes another problem in Eq. (9a) and (9b) because the $p$-norm among sets (if $y^{(i)}$ is a set) is not defined.
- In Algorithm 1, the loop $i$ starts with $N-1$ but $f(y) \leq f(y^\star (i))$ does not make sense as that of $i = N-1$ is not defined a priori. Does it mean $i+1$ or others?
- The paper assumes that similar instances generate similar optimal results and the bound of $i$-th instance can be inferred from $i+1$-th instance. As noted, this kind of relationship could hold for LPs. In Sec. 6, the authors said a kind of local Lipschitz condition holds also for many other types of optimization problems. Please clarify the scope of this word; 'many other types' to show the generalization ability of the proposed method.
- The standard approach assumes independence among data. However, for example in combinatorial optimization literature, re-optimization or life-long optimization is a branch of the research domain. Therefore, I suspect that the used standard approach is a bit week (a naive baseline). Do you have any other choice?
- Some minor comments
    - What does 'OD labels' mean in Figure 2? (Optimal Data generation?)
    - A missing sentence behind Figure 3 (symmetries?).
    - Figure 4 should be captioned as a table.
limitations_and_societal_impact: The paper covers some problem examples, and the paper and appendix explain the idea adopted. However, I guess that it is not trivial to follow the proposed approach for other problem classes.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: Training predictive models for solutions of NP-hard constrained optimization problems is a very challenging task, since symmetric solutions are possible, solvers can exhibit strong non-deterministic behavior and solutions vary strongly although the instances are fairly similar. The authors of the paper at hand propose a new way of generating training data for supervised predictive models and show that their models outperform previous sota training-data-generation strategies on nonlinear nonconvex and hard-combinatorial problem instances under the challenges listed before.
main_review: ### Novelty

To the best of my knowledge, it’s one of the few papers -- maybe the first thorough paper -- that addresses the problem of training data generation in this context. The authors convincingly demonstrate potential challenges for this task and provide a theoretical analysis and a practical approach. 

### Significance / Impact

In the last few years, the application of ML to constrained optimization has become a more and more important field of research and the authors clearly contribute to this. I believe that this paper both pushes the state of the art for the task clearly and opens up ample future research directions.

### Soundness

The theory, the proposed approach and the empirical analysis are sound and I don’t have found any major issues. In addition, the authors clearly state the assumption of their approach and convincingly discuss the limitations in the last section.
(Only the argument regarding energy consumption and CO2 seems a bit artificial, although still correct.)

### Clarity

The paper is very well written and easy to follow.

### Minor Comments

* “a optimal solution” → “an optimal solution”
* Figure 3 overlaps a bit with the text “symmetries”

### Questions for Rebuttal

1. How do the results in Table 1 and 2 compare to a real constraint solver? 
2. Why is it better to maximize the time SOTA in Table 1?
3. Would this approach also be applicable to NP-hard decision problems such as SAT?

limitations_and_societal_impact: Only briefly addressed, but I think it is fine.
review_title: null

Meta-review: This paper provides a methodology for generating datasets for  supervised learning for combinatorial optimization problems. This is an interesting perspective as it focuses on the importance of generating the right datasets for the supervised learning problem. The authors highlight several challenges that characterize  combinatorial optimization problems and provide some theoretical insights for the proposed methodology. In particular the authors propose an approach that formulates the problem of optimal dataset design as a bilevel  optimization problem and introduces an efficient algorithm for  dataset generation. They show the effectiveness of the approach  for job shop scheduling and optimal power flow problems. There was unanimous consensus on accepting the paper. 
Decision: Accept (Poster)