Learning Hard Optimization Problems: A Data Generation Perspective
Authors: James Kotary
Ferdinando Fioretto
Pascal Van Hentenryck
Venue: NeurIPS 2021 Poster (2021)
Keywords: Combinatorial Optimization
Constrained Optimization
Supervised Learning
Data generation

Abstract: Optimization problems are ubiquitous in our societies and are present in almost every segment of the economy. Most of these optimization problems are NP-hard and computationally demanding, often requiring approximate solutions for large-scale instances. Machine learning frameworks that learn to approximate solutions to such hard optimization problems are a potentially promising avenue to address these difficulties, particularly when many closely related problem instances must be solved repeatedly. Supervised learning frameworks can train a model using the outputs of pre-solved instances. However, when the outputs are themselves approximations, when the optimization problem has symmetric solutions, and/or when the solver uses randomization, solutions to closely related instances may exhibit large differences and the learning task can become inherently more difficult. This paper demonstrates this critical challenge, connects the volatility of the training data to the ability of a model to approximate it, and proposes a method for producing (exact or approximate) solutions to optimization problems that are more amenable to supervised learning tasks.  The effectiveness of the method is tested on hard non-linear nonconvex and discrete combinatorial problems.

Learning Hard Optimization Problems: A Data Generation Perspective
James Kotary Syracuse University Syracuse, NY 13244 jkotary@syr.ed edu
Ferdinando Fioretto Syracuse University Syracuse. NY 13244 ffiorett@syr.co edu
Pascal Van Hentenryck Georgia Institute of Technology Atlanta, GA 30332 wwh@isye.gatecde edu
Abstract
Optimization problems ubiquitous in societies and present in almost every segment the economy. Many of these optimization problems are NP-hard and computationally demanding, often requiring approximate solutions for large- scale instances. Machine learning frameworks that learn to approximate solutions such hard optimization problems a potentially promising avenue to address these difficulties, particularly when many closely related problem instances must be solved repeatedly. Supervised learning frameworks the outputs of pre-solved instances. However, when the outputs are themselves approximations, when the optimization problem has symmetric solutions, and/or when the solver uses randomization, solutions to closely related instances may exhibit large differences and the learning task become inherently more difficult. This paper demonstrates this critical challenge, connects the variation of the training data to the ability of a model to approximate and proposes method for producing (exact or approximate) solutions to optimization problems that are more amenable supervised learning tasks. The effectiveness of the method is tested on hard non-linear nonconvex and discrete combinatorial problems.
train model using
Introduction
Constrained optimization (CO) is in daily use in our society, with applications ranging from supply chains and logistics, electricity grids, organ exchanges, marketing campaigns, and manufacturing to name only a few. Two classes of hard optimization problems of particular interest in many fields are (1) combinatorial optimization problems and (2) nonlinear constrained problems. Combinato- rial optimization problems are characterized by discrete search spaces and have solutions that are combinatorial in nature, involving for instance, the selection of subsets or permutations, and the sequencing scheduling of tasks. Nonlinear constrained problems may have continuous search spaces but are often characterized by highly nonlinear constraints, such as those arising electrical power systems whose applications must capture physical laws such Ohm's 's law and Kirchhoff's law in addition to engincering operational constraints. Such CO problems are often NP-Hard and may be computationally challenging in practice, especially for large-scale instances.
While the AI and Operational Research communities have contributed fundamental advances in optimization in the last decades, the complexity of some problems often prevents them from being adopted in contexts where many instances must be solved over long-term horizon (e.g., multi- year planning studies) or when solutions must be produced under time constraints. Fortunately, in many practical cases, including the scheduling and energy problems motivating this work, one interested in solving many problem instances sharing similar patterns. Therefore, the application of deep learning methods to aid the solving of computationally challenging constrained optimization problems appears to be natural approach and has gained traction in the nascent area the intersection
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

between CO and ML 19 using pre-solved CO instances and their solutions. However, learning the underlying combinatorial structure of the problem or learning approximations of optimization problems with hard physical and engineering constraints may be an extremely difficult task. While much of the recent research at the intersection of CO and ML has focused on learning good CO approximations in jointly training prediction and optimization models 18 22 25 32 and incorporating optimization algorithms into differentiable systems [ 27 34, 20 learning the combinatorial structure of CO problems remains an elusive task.
3T. In particular, supervised learning frameworks can train model
Beside the difficulty of handling hard constraints, which will almost always exhibit some viola- tions, two interesting challenges have emerged: the presence of multiple, often symmetric. solu- tions, and the learning of approximate solution methods. The first challenge recognizes that an optimization problem may not have a unique solution. This challenge is illustrated in Figure where the various yd represent optimal solutions to CO instances x0 and C the feasible space. As a result, a com- binatorial number of possible datasets may be generated. While equally valid as optimal solutions, some sets follow patterns which are more meaningful and recognizable. Sym- metry breaking is of course a major area of combinatorial optimization and may alleviate some of these issues. But different instances may not break symmetries in the same fashion, thus creating datasets that are harder to learn.
C
D
g
1/2
(1)
9/
The second challenge comes from realities in the application domain. Because of time constraints, the solution technique Figure 1: Co-optimal datasets due sym- may return a sub-optimal solution. Moreover, modern com- binatorial optimization techniques often use randomization and large neighborhood search to produce high-quality solutions quickly. Although these are widely successful, different runs for the same, or similar, instances may produce radically different solutions. As result, learning the solutions returned by these approximations may be inherently more difficult. These effects may be viewed source of noise that obscures the relationships between training data and their target outputs. Although this does not raise issues for optimization systems, it creates challenging learning tasks.
metries.
This paper demonstrates these relations, connects the variation in the training data to the ability of a model to approximate it, and proposes a method for producing (exact or approximate) solutions to optimization problems that are more amenable to supervised learning tasks. More concretely, the paper makes the following contributions:
shows that the existence of co-optimal or approximated solutions obtained by solving hard CO problems construct training datasets challenges the learnability of the task.
2. To overcome this limitation, it introduces the problem of optimal dataset design, which is cast as bilevel optimization problem. The optimal dataset design problem is motivated using theoretical insights the approximation of functions by neural networks, relating the properties of function describing a training dataset to the model capacity required to represent it.
3. It introduces a tractable algorithm for the generation of datasets that are amenable to learning, and empirical demonstration of marked improvements to the accuracy of trained models, as well as the ability to satisfy constraints at inference time.
4. Finally, it provides state-of-the-an -ttt accuracy results at vastly enhanced computational runtime learning two challenging optimization problems: Job Shop Scheduling problems and Optimal Power Flow problems for energy networks.
To the best of the authors' knowledge, this work is the first highlight the issue of learnability in the face of co-optimal or approximate solutions obtained to generate training data for learning to approximate hard CO problems. The observations raised in this work may result in broader impact as, in addition to approximating hard optimization problems, the optimal dataset generation strategy introduced in this paper may be useful to the line of work on integrating CO as differentiable layers for predictive and prescriptive analytics, as well as for physics constrained learning problems such as when approximating solutions to systems of partial differential equation.
2

---

2
Related work
The integration of CO models into ML pipelines to meld prediction and decision models has recently seen the introduction of several nonoverlapping approaches, surveyed by Kotary et al. [9]. The application of ML to boost performance in traditional search methods through branching rules and enhanced heuristics is broadly overviewed by Bengio et al. [ Motivated also by the need for fast approximations to combinatorial optimization problems, the training of surrogate models via both supervised and reinforcement learning is an active area for which a thorough review is provided by Vesselinova et al. (31] Designing surrogate models with the purpose approximate hard CO problem has been studied in a number of works, including [6 12 15]. An important aspect for the learned surrogate models is the prediction of solutions that satisfy the problem constraints. While this is a very difficult task in general, several methodologies have been devised. In particular, Lagrangian loss functions have been used for encouraging constraint satisfaction in several applications of deep learning, including fairness (30] and energy problems [15]. Other methods iteratively modify training labels to encourage satifaction of constraints during training [12]
This work focuses on an orthogonal direction with respect to the literature reviewed above. Rather than devising a new methodology for effectively producing a surrogate model that approximate some hard optimization problem, it studies the machine learning task from a data generation perspective. It shows that the co-optimality and symmetries of hard CO problem may be viewed as source of noise that obscures the relationships between training data and the target outputs and proposes an optimal data generation approach mitigate these important issues.
3 Preliminaries
constrained optimization (CO) problem poses the task of minimizing an objective function y x - R. of one or more variables y y s R", subject to the condition that a set of constraints C2 are satisfied between the variables and where æ E X R denotes a vector of input data that specifies the problem instance:
0 = argmin fly, x) subject to: y E Ca.
(1)
y
An assignment of values y which satisfies C2 is called a feasible solution; if, additionally fly. x) s f(w, .)) for all feasible w, it is called an optimal solution.
A particularly common constraint arising in practical problems takes the form C= = fy Ay b). where A E R. and b E R." In this case, C is a convex set. If the objective f is an affine function, the problem is referred to as linear program (LP). If, in addition, some subset of problem's variables are required to take integer values, it is called mixed integer program (MIP). While LPs with convex objectives belong the class of convex problems, and can be solved efficiently with strong theoretical guarantees on the existence and uniqueness of solutions (7]. the introduction of integral constraints (y E N") results in much more difficult problem. The feasible set MIP consists of distinct points in y E R", not only nonconvex but also disjoint, and the resulting problem is. in general, Na-Hard. Finally, nonlinear programs (NIPs) are optimization problems where some of the constraints or the objective function are nonlinear. Many NI.s are nonconvex and can not be efficiently solved (24).
The methodology introduced in this paper is illustrated on hard MIP and nonlinear program instances.
4 Problem setting and goals
This paper focuses on learning approximate solutions to problem [ via supervised learning. The task considers datasets x ((a!") yf " consisting of N data points with a! e X being vector of input data, as defined in equation [T. and nd E ()) being a solution of the optimization task. A desirable, but not always achievable, property is for the solutions yd to be optimal.
The goal is to learn a model fo : X + y, where 0 is a vector of real-valued parameters, and whose quality is measured in terms of a nonnegative, and assumed differenniable,, loss function : y x y R.. The learning task minimizes the empirical risk function (ERM):
1 N
min J(f:))
{fo(z")). (.)
(2)
3

---

Standard lnbels
123900
100300
50000
$2000
Congreie Mooereieee we
32*
43900
20
50030
60023
2200
40030
20002
Trariing Epoch
Training Esoch
Figure 2: Dataset solution "d comparison: LI Distance from a reference solution (left); Test loss (center); and Constraint violations (right).
with the desired goal that the predictions also satisfy the problem constraints: fo(a:") E C..
While the above task is difficult to achieve due to the presence of constraints, the paper adopts a Lagrangian approach [14,, which has been shown successful in learning constrained representations, along with projection operators, commonly applied in constrained optimization to ensure constraint satisfaction of an assignment. For a given point ÿ. e.g., representing the model prediction, a projection operator TT()) finds the closest feasible point y E C to ý under p-norm:
def argmin lly Ul1 subject to: E.
The full description of the Lagrangian based approach and the projection method adopted is delegated to the Appendix A
Challenges in learning hard combinatorial problems
One of the challenges arising in this area comes from the recognition that a problem instance may admit a variety of disparate optimal solutions for each input æ. To illustrate this challenge, the paper uses a of scheduling instances that differ only in the time required to process tasks on some machine. A standard approach to the generation of dataset in this context would consist in solving each instance independently using some SoTA optimization solver. However, this may create some significant issues that are illustrated in Figure (more details on the problem are provided in Section (8. The blue curve in Figure 2 (left) illustrates the behavior of this natural approach. In the figure, the processing times in the instances increase from left to right and the blue curve represents the Li-distance between the obtained solution to each instance (i.e., the start times of the tasks) and a reference optimal solution for some instance. The volatile curve shows that meaningful patterns can be lost, including the important relationship between an increase processing times and the resulting solutions. Figure (center) shows that, while the solution patterns induced by the target labels appear volatile, the ERM problem appears well behaved, in the face of minimizing the test loss. However, when training loss converges, accuracy (measured as the distance between the projection of the prediction gg) and the real label y) remains poor in models trained on such data (blue star). Figure 2 (right) shows the average magnitude of the constraints violation during training, corresponding to the two target solution sets of Figure 2 (left,, along with a comparison of the objective of the projection operator applied to the prediction: (}τT(()) ~ll. It is worth emphasizing that these issues are further exacerbated when time constraints prevent the solver from obtaining optimal solutions. Moreover, similar patterns also be observed for the data generated while solving optimal power flow instances that exhibit symmetries.
150
Additionally, extensive observations collected on the motivating applications of the paper show that, even when the model com- plexity (i.e., the dimensionality of the model parameters 6) is increased arbitrarily, the resulting learned models tend to have low-veriance. This is illustrated in Figure 3, where the orange and blue curves depict, respectively, a function interpolating the training labels and the associated learned solutions.
0.500
Dame Food Sector
0.00
1.00
Approximating highly volatile function results in low- variance models.
Figure 3:
The goal of this paper is to construct datasets that are well-suited for learning the optimal (or near-optimal) solutions optimization
problems. The benefit of such an

---

approach is illustrated by the orange curves and stars in Figure 2 which were obtained using the data generation methodology proposed in this paper. They considered the same instances and obtained (different) optimal solutions, but exhibit much enhanced behavior on all metrics.
6 Theoretical justification of the data generation
Although the data generation strategy necessarily heuristic, it relies on key theoretical insights on the nature of optimization problems and the representation capabilities neural networks. This section reviews these insights.
First, observe that, as illustrated in the motivating Figure 3, the solution trajectory associated with the problem instances various input parameters can often be naturally approximated by piecewise linear functions. This approximation is in fact exact for linear programs when the inputs capture incremental changes to the objective coefficients or the right-hand side of the constraints. Additionally, ReLU neural networks, used in this paper to approximate the optimization solutions, have the ability capture piecewise linear functions [17]. While these models are thus compatible with the task of predicting the solutions of an optimization problem, the model capacity required to represent target piecewise linear function exactly depends directly on the number of constituent pieces.
Theorem (Model Capacity 12). Let f R.d R be piecewise linear function with p pieces. f is represented by ReLU network with depth k then must have size least 1kp Conversely, any piecewise linear function f that is represented by a ReLU network of depth k + and size at most s, can have at most (22) pieces.
The solution trajectories may be significantly different depending on how the data is generated. Hence, the more volatile the trajectory, the harder will be to learn. Moreover, for network of fixed size, the more volatile the trajectory, the larger the approximation error will be in general. The data generation proposed in this paper will aim at generating solution trajectories that are approximated by piecewise linear functions with fewer distinct pieces. The following theorem bounds the approximation error when using continuous piecewise linear functions: it connects the approximation errors of piecewise linear function with the total variation in its slopes.
Theorem 2. Suppose a piecewise linear function for with p' pieces each width for ke [p'), is used to approximate a piecewise linear fp with p pieces, where p' sp.. Then the approximation error
ffp- S
14.1111
Lsksp
holds where L is the slope of piece k and Imax is the maximun width of all pieces.
Proof. Firstly, the proof proceeds with considering the special case in which fp conincides slope and value with for some point, and that each piece of for overlaps with most 2 distinet pieces of
fp. This is always possible when p' 2 J. Call l the interval which for is defined by its 1 piece. 4 overlaps with only one piece of fps then for x 4t
1f(() (x) =0
(3)
If overlaps with pieces & and k 1 of fp. then for It.
1fa(x) - for (x)l S he|La+1 Lal
(4)
Each of the above follows from the assumption that fp and for are equal in their slope and value some point within 4.. From this it follows that on 4t
Ip frlli = J 15--11 Spl
Σ Istsp
AMl L2l $ 1
M2
Σ 1shsp
|l++1 Lal.
(5)
2
so that on the entire domain of fp and fpr-
1 folli
2
Σ
|L+.1 Lgl.
isksp
Since removing the initial simplifying assumptions tightens this upper bound, the result holds.
5

---

The final observation that justifies the proposed approach is the fact that optimization problems often satisfy local Lipschitz condition, i.e. if the inputs of two instances are close, then they admit solutions that are close as well, i.e., there exist y ( O(x!)) and ý E O(x!"), where
|| 1 ÿ 1| Cl - x
for some C O and ||x أااها e, where is small value. This is obviously true in linear programming when the inputs vary in the objective coefficients or the right-hand side of the constraints, but it also holds locally for many other types of optimization problems. That observation suggests that, when this local Lipschitz condition holds, it may be possible to generate solution trajectories that are well-behaved and can be approximated effectively. Note that Lipschitz functions can be nicely approximated by neural networks as the following result indicates.
Theorem (A (Approximation
9 If f [0, 1]" R is L-Lipschitz continuous, then for every E there exists some single-layer neural network of size N such that llf plloa <, where N = (ut M
The result above illustrates that the model capacity required to approximate given function depends to non-negligible extent the Lipschitz constant value of the underlying function.
Note that the results in this section are bounds on the ability of neural networks to represent generic functions. In practice, these bounds themselves rarely guarantee the training of good approximators, as the ability to minimize the empirical risk problem in practice is often another significant source of error. In light of these results however, it is to be expected that datasets which exhibit less variance and have small Lipschitz constant will be better suited to learning good function approximations. The following section presents method for dataset generation motivated by these considerations.
7 Optimal CO training data design
Given a set of input data (a that solve the following problem
| the goal to construct the associated pairs nd for each e [N],
min B. N (ffo(("))))) "
(8a)
subject to : y argmin f(y, ))
(8b)
y
One often equips the data point set ( with an ordering relation I such that æ x x' + ||>|| S ||æ''| for some p-norm. For example, in the scheduling domain, the data points æ represent task start times and the training data are often generated by "slowing down" some machine, which simulates some unexpected ill-functioning component in the scheduling pipeline. the energy domain, æ represent the load demands and the training data are generated by increasing decreasing these demands, simulating the different power load requests during daily operations in a power network. For simplicity, this paper assumes the existence of such useful ordering over the entire set of instances in a learning task.
From the space of co-optimal solutions y to each problem instance ① the goal is to generate solu- tions which coincide, to the extent possible, with target function of low total variation and Lipschitz factor, as well as a low number of constituent linear pieces in the case of discrete optimization. While may not be possible to produce a target set that simultaneously optimizes each of these metries, they are confluent and can be improved simultaneously. Natural heuristics are available which reduce these metrics substantially when compared with naive approaches.
One heuristic aimed at satisfying the aforementioned properties reduces to the problem of determining that minimizes their total variation:
a solution set NNN for the inputs ( of problem (T) i=1
minimize TV OONN
O
ll (--1) 10
(9a)
F=1
subject
の argmin x(
(9b)
yeC.m
'The notation here is used to denote its discrete equivalent, indicated in Equation 7

---

In practice, this bi-level minimization cannot be achieved, due partially to its prohibitive size. It is possible, however,
Algorithm 1: 1: Data Generation
to minimize the individual terms of (9a), each subject to the result of the previous, by solving individual instances sequentially. Algorithm[] ensures that solutions to subse- quent instances have minimal distance with respect to the chosen p-norm (the experiments of Section 8 use p 1). This method approximates a set of solutions with minimal total variation, while ensuring that the maximum magni- tude of change between subsequent instances is also small. When the data represent the result of discrete optimiza- tion, this coincides naturally with representative function which requires less pieces, with less extreme changes in slope. The method starts by solving target instance, c.g., the last in the given ordering (line D. Therein, Ô denotes the solution set of (possibly approximated) minimizer for problem ( In the case the job shop scheduling, for example, Ô represents a local optimizer with suitable time-limit. The process then generates the next dataset instance yd in the ordering N by solving the optimization problem given in line 3 The problem finds solution to problem a0 that close to adjacent solution (f- while preserving optimality, i.e., the objective of the sought y is constrained to be at most that of ÿ E Ōlz²)).
input : [-x" Input data y ju E )
for == N - down to do
y - Ōlxe))
argmin y
lly
y subject to:
y E a [Wy S SV
return X = =1(x0)) )
"
When the difficulty of the underlying optimization instances makes the sequential solving of Algo- rithm Iimpracticl,, structural properties of the CO problem may be exploited to increase efficiency, i.e. by the use of warm-starts or solution-guided search. In the Job Shop Scheduling case study, ((-1) is feasible the subsequent problem and may be used warm-start its solution, carrying forward solution progress between iterations of Algorithm T Therefore, a byproduct of this data-generation approach is that the optimization problem in line 3 can be well-approximated within short timeout. When such exploits are not available, the secondary optimization of line 4 may be applied over independently pre-solved instances an analogous way.
In addition to providing enhanced efficacy for learning, this method of generating target instances is generally preferable from modeling point of view. When predicted solutions related decision problems are close together, the resulting small changes are often more practical and actionable, and thus highly preferred in practice. For example, small change in power demands should result in an updated optimal power network configuration which is easy to achieve given its previous state.
8 Application to case studies
The concepts introduced above are applied in this section to two representative case studies, Job Shop Scheduling (JSS) and Optimal Power Flow (OPF). Both are of interest in the optimization and machine learning communities as practical problems which must be routinely solved, but are difficult to approximate under stringent time constraints. The JSS problem represents the class of combinatorial problems, while the OPF problem is continuous but nonlinear and non convex. Both lack solution methods with strong guarantees on the rate of convergence, and the quality of solutions that can be obtained. In the studies described below, a deep neural ReLU network equipped with a Lagrangian loss function (described in details in Appendix (A) is used predict the problem solutions that are approximately feasible and close to optimal. Efficient projection operators are subsequently applied to ensure feasibility of the final output (See Appendix B and C
Job shop scheduling
Job Shop Scheduling (JSS) assumes set of J jobs, each consisting of list of M tasks to be completed in a specified order. Each task has a fixed processing time and is assigned to one of M machines, so that each job assigns one task to each machine. The objective is to find schedule with minimal makespan, or time taken to process all tasks. The no-overlap condition requires that for any two tasks assigned to the same machine, one must be complete before the other begins. See the problem specification in Appendix [ The objective of the learning task is to predict the start times of all tasks given a JSS problem specification (task duration, machine assignments).
Data Generation Algorithms The experiments examine the proposed models on a variety of prob- (88). The ground truth data are constructed as follows: different
lems from the JSPLIB library
7

---

Instance
Size
Prediction Error
Constraint Violation
Optimality Gap (%)
Time SoTA Eq. (6)
J x M
Standard
OD
Standard
OD
Standard
OD
Standard
OD
ta25
20x20
193.9
23.4
180.0
45.5
10.3
4.0
24
550
yn02
20x20
153.2
38.9
124.9
70.3
9.1
4.5
27
45
swv03
20x 10
309.4
12.4
206.9
31.6
18.0
2.2
15
65
swv07
20x15
330.4
19.9
280.1
67.2
17.0
3.0
155
60
swvl1
50x10
1090.0
51.2
906.4
151.7
28.5
4.5
13
100
Table I: Standard vs OD training data: prediction errors, constraint violations, and optimality gap (the smaller the better), Time SoTA Eq. (the larger the better). Best results are highlight in bold.
input data T are generated by simulating a machine slowdown, i.e., by altering the time required to process the tasks on that machine by a constant amount which depends on the instance i. Each training dataset associated with a JSS benchmark is composed of total of 5000 instances. Increasing the processing time of selected tasks may also change the difficulty of the scheduling. The method of sequential solving outlined in Section 7 is particularly well-suited to this context. Individual problem instances can ordered relative to the amount of extension applied to those processing times, so that when de represents the time required to process task of job j in instance i, d - d(itt) j,,t. In this case, any solution to instance di-D is feasible to instance d, (tasks in a feasible schedule cannot overlap when their processing times are reduced, and start times held constant). As such, the method can be made efficient by passing the solution between subsequent instances as a warm-star
The analysis compares two datasets: One consisting of target solutions generated independently with a solving time limit of 1800 seconds using the sfate-of-the-art IBM CP Optimizer constraint programming software (denoted as Standard), and one whose targets are generated according to called the Optimal Design dataset (denoted as OD).
algorithm D
Figure A presents comparison of the total variation result- ing from the two datasets. Note that the OD datasets have total variation which is orders of magnitude lower than their Standard counterparts. Recall that small total variation is perceived as a notion of bellebehasssess from the per- spective of function approximation. Additionally, it is noted that the total computation time required to generate the OD dataset at least an order of magnitude smaller than that required to generate the standard dataset (13.2h vs. 280h).
Instance
Size
Total Variation (x10")
x
Standard Data
OD Data
la25
20x20
67.8
0.194
yn02
20x
55.0
0.483
swy03
20x 10
109.4
0.424
SWV07
20x15
351.2
0.100
swvll
50x10
352.0
1.376
Figure 4: Standard vs OD training data: Total Variation.
Prediction Errors and Constraint Violations Table rreports the prediction errors as Li-dittance between the (feasible) predicted variables, i.e., the projections π()) and their original ground-truth quantities (z), the average constraint violation degrees, expressed as the Ly-distance between the predictions and their projections, and the optimality gap, which is the relative difference in makespan (or, equivalently objective values) between the predicted (feasible) schedules and target schedules. All these metrics are averaged over all perturbed instances of the dataset and expressed in percentage. In the case of the former two metrics, values are reported as percentage of the average task duration per individual instance. Notice that for all metrics the methods trained using the OD datasets result in drastic improvements (i.e., one order of magnitude) with respect to the baseline method, Additionally, Table I (last column) reports the runtime required by CP-Optimizer to find value with the same makespan as the one reported by the projected predictions (projection times are also included). The values are to be read as the larger the better, and present remarkable improvement over the baseline method. It is also noted that the worst average time required to obtain a feasible solution from the predictions is 0.02 seconds. Additional experiments, reported in Appendix D also show that the observations are robust over a wide range of parammerssssssss adopted to train the learning models.
The results show that the OD data generation can drastically improve predictions qualities while reducing the effor required by a projection step to satisfy the problem constraints.
AC Optimal Power Flow
Optimal Power Flow (OPF) the problem of finding the best generator dispatch to meet the demands in power network. The OPF is solved frequently in transmission systems around the world and is
8

---

Instance
Size
Prediction Error
Constraint Violation
Optimality Gap (%)
No. buses
Standard
OD
Standard
OD
Standard
OD
Peguse-89
198.3
5.02
1.21
1.01
20.1
7.0
IEEE-118
118
172.5
13.31
2.12
1.98
32.5
9.6
JEEE-300
300
194.2
24.12
2.63
2.04
44.2
15.2
Table 2: Standard vs OD training data: prediction errors, constraint violations, and optimality gap.
increasingly difficult due to intermittent renewable energy sources. The problem is required to satisfy the AC power flow equations, that are non-convex and nonlinear, and are a core building block in many power system upplications. The objective function captures the cost of the generator dispatch, and the Constraint set describes the power flow operational constraints, enforcing generator output, line flow limits, Kirchhoff's ' Current Law and Ohm's ' Law for a given load demand. The OPF receives its input from unit-commitment algorithms that specify which generators will be committed to deliver energy and reserves during the 24 hours of the next day. Because many generators are similar in nature (e.g., wind farms solar farms connected the same bus), the problem may have large number of symmetries. If a bus has two symmetric generators with enough generator capacities, the unit commitment optimization may decide choose one of the symmetric generators or commit both and balance the generation between both of them. The objective of the learning task is to predict the generator setpoints (power and voltage) for all buses given the problem inputs (load demands).
Data Generation Algorithms The experiments compare this commitment strategy and its effect on learning on Pegase-89, which is coarse aggregation of the French system and IEEE-118 18 and IEEE-300, from the NESTA library [10]. All base instances are solved using the Julia package PowerModels.ji [1] with the nonlinear solver IPOPT (3). Additional data is reported in Appendix C A number of renewable generators are duplicated at each node to disaggregate the generation capabilities. The test cases vary the load data by scaling the (input) loads from 0.8 to 1.0 times their nominal values. Instances with higher load pattern are typically infeasible. The unit-commitment strategy sketched above can select any of the symmetric generators a given bus (Standard data). The optimal objective values for a given load are the same, but the optimal solutions vary substantially. Note that, when the unit-commitment algorithm commits generators by removing symmetries (OD data). the solutions for are typically close to each other when the loads are close. As result, they naturally correspond to the generation procedure advocated in this paper.
Prediction Errors and Constraint Violations As shown in Table 2 the OD approach to data generation results in predictions that are closer their optimal target solutions (error expressed in MegaWatt (MW)), reduce the constraint violations (expressed as L Lidisttncce between the predictions and their projections), and improve the optimality gap. which is the relative difference in objectives between the predicted (feasible) solutions and the target ones.
Limitations and Conclusions
This paper was motivated by engineering applications where problem instances share an underlying "infrastructure" (e.g., the power grid in optimal power flow or the manufacturing floor in job shop scheduling) which is stable and does not evolve too rapidly. These problems are pervasive in applications ranging from supply chains and logistics, to electricity grids, and manufacturing, to name a few. Note that the approach to data generation presented in this paper is not intended for direct application to every task of learning to solve constrained optimization. In general, data generation approaches should be tailored to exploit the properties of their respective optimization problems and experimental settings, but the algorithms and insights demonstrated above may be exploited in variety of settings.
While the proposed methodology is limited to machine learning tasks in which optimization problem instances admit useful orderings with respect to their parameters, this property may hold only locally over particular distribution of problems. For example, in timetabling applications, as in the design of employees shifts, a desired condition may be for shifts to be diverse for different but similar inputs. The proposed methodology may, in fact, induce a learner to predict similar solutions across similar input data. A possible solution to this problem may be that of generating various trajectories of solutions, learn from them with independent models, and then randomize the model selection to

---

generate a prediction. These more complex settings may require composition or extension of the solutions presented in this paper, and generalizations of the approach are an avenue for future work.
In addition to the inherent difficulty of learning feasible CO solutions, a practical challenge is represented by the data generation itself. Generating training datasets for supervised learning tasks requires solving many instances of hard CO problems, which can be time consuming and imposes toll on energy usage and CO2 emissions. In this respect, an advantage of the proposed method, its ability to use warm-starts to generate instances incrementally, resulting in enhanced efficiency even for hard optimization problems that require substantial solving time when treated independently.
Aside these limitations, the observations raised in this work may be significant several areas: In addition to approximating hard optimization problems, the optimal dataset generation strategy introduced this paper may be useful to the line of work on integrating CO and machine learning for predictive and prescriptive analyties, as well as for physies constrained learning problems, two areas with significant economic and societal impacts.
Acknowledgments and Disclosure of Funding
This research is partially supported by NSF grant 2007164. Its views and conclusions are those of the authors only.
References
[1] B. Amos and J. Z. Kolter. Optnet: International Conference on Machine Learning, pages 136-145, 2017.
Differentiable optimization layer in neural networks. In
[2] R. Arora, A. Basu, P. Mianjy, and A. Mukherjee. Understanding deep neural networks with rectified linear units. In 6th International Conference on Learning Representations, 2018.
[3] M.-F. Balcan, T. Dick, T. Sandholm, and E. Vitercik. Learning to branch. In International conference machine learning, pages 344 353. PMLR, 2018.
[4] M. E. Baran and F. F. Wu. Optimal capacitor placement on radial distribution systems. In- ternational Conference on Energy Efficient Technologies for Sustainability, pages 725-734, 1989.
[5] Y. Bengio, A. Lodi, and A. Prouvost. Machine learning for combinatorial optimization: methodological tour d' horizon. European Journal of Operational Research, 2020.
[6] A. Borghesi, G. Tagliavini, M. Lombardi, L. Benini, and M. Milano. Combining learning and optimization for transprecision computing. In Proceedings of the 17th ACM International Conference on Computing Frontiers, pages 10-18, 2020.
[7] S. Boyd, S. Boyd, and L. Vandenberghe. Convex optimization. Cambridge university press, 2004.
[8] M. B. Cain, R. P. O' neill, and A. Castillo. History of optimal power flow and formulations op- timal power flow paper 1. https://www. ferc. hwt.g/////nussrree///eeeetrii//a act/ warket-planninggoor www.ps-pppers.aas. 2012.
[9] K. F. E. Chong. A closer look at the approximation capabilities of neural networks. In 8th International Conference Learning Representutions, 2020.
[10] C. Coffrin, D. Gordon, and P. Scott. NESTA, the NICTA energy system test case archive. CoRR, abs/1411.00 2014. URL //axxvv.a/ivvee/aa org/ abs/ 1411.0359
[11] C. Coffrin, R. Bent, K. Sundar, Y. Ng. and M. Lubin. Powermodels.jl: An open-source framework for exploring power flow formulations. In Power Systems Computation Conference, 2018.
[12] F. Detassis, M. Lombardi, and M. Milano. Teaching the old dog tricks: supervised learning with constraints. In A. Saffiotti, L. Serafini, and P. Lukowicz, editors, Proceedings of the First International Workshop New Foundations for Human- Centere- Al, CEUR Workshop Proceedings, pages 44-51, 2020.
[13] Poutche-Fnergue-Ae Agentur. The e-highway2050 project http://www.e-bighwyy225555 eu 2019. Accessed: 20-9-11-19.
10

---

[14] F. Fioretto, P. V. Hentenryck, T. W. K. Mak, C. Tran, F. Baldo, and M. Lombardi. Lagrangian duality for constrained deep learning. In Y. Dong, G. Ifrim, D. Mladenic, C. Saunders, and S. V. Hoecke, editors, Machine Learning and Knowledge Discovery in Databases. Applied Data Science and Demo Track European Conference 2020, pages 118-135. Springer, 2020.
[15] F. Fioretto, T. W. Mak, and P. Van Hentenryck. Predicting ac optimal power flows: Combining deep learning and lagrangian dual methods. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 630-637, 2020.
[16] E. B. Fisher, R. P. O' Neilil, and M. C. Ferris. Optimal transmission switching. IEEE Transactions on Power Systems, pages 1346-1355 2008.
[17] C. Huang. Relu networks are universal approximators via piecewise linear or constant functions. 2020.
Neural Computation, pages
[18] E. Khalil, P. Le Bodic, L. Song, G. Nemhauser, and B. Dilkina, Learning to branch in mixed integer programming. In Proceedings of the AAAI Conference on Artificial Intelligence, 2016.
[19] J. Kotary, F. Fioretto. P. Van Hentenryck, and B. Wilder. End-to-end constrained optimization learning: A survey. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, publisher = International Joint Conferences Artificial Intelligence Organiza- tion, editor = Zhi-Hua Zhou, pages 4475-4482, year = 2021, note = Survey Track doi 10. 10.24963fjcai.202.. 20tpcai..221/11000 url http::/ddooorg//0.2499//f/ 2tti:aaii.202111 1/610..
[20] Mandi, P. Stuckey, T. Guns, al. Smart predict-and-optimizze for hard combinatorial optimization problems. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 1603-1610, 2020.
[21] A. Monticelli, M. Pereira, and S. Granville. Security-constrained optimal power flow with post-contiggency corrective rescheduling. IEEE Transactions Power System, pages 175-180, 1987.
[22] V. Nair, S. Bartunov, F. Gimeno, I. von Glehn, P. Lichocki, I. Lobov, B, O' O'Donoghue, N. Son- nerat, C. Tjandraatmadja, P. Wang, R. Addanki, T. Hapuarachchi, T. Keck, J. Keeling, P. Kohli, I. Ktena, Y. Li, O. Vinyals, and Y. Zwols. Solving mixed integer programs using neural networks. CoRR, 2020.
[23] Niharika, S. Verma, and V. Mukherjee. Transmission expansion planning: review. In International Conference Energy Efficient Technologies for Sustainability, pages 350-355. 2016.
[24] J. Nocedal and S. Wright. Numerical optimization. Springer Science & Business Media, 2006.
[25] A. Nowak, S. Villar, A. S. Bandeira, and J. Bruna. Revised note on learning quadratic assignment with graph neural networks. In 2018 IEEE Data Science Workshop, pages 1-5. IEEE, 2018
[26] C. Pache, J. Maeght, B. Seguinot, A. Zani, S. Lumbreras, A. Ramos, S. Agapoff, L. Warland,
L. Rouco, and P. Panciatici. Enhanced pan-european transmission planning methodology. In IEEE Power Energy Society General Meeting, 2015.
[27] M. V. Pogančić, A. Paulus, V. Musil, G. Martius, and M. Rolinek. Differentiation of blackbox combinatorial solvers. International Conference on Learning Representations, 2020.
[28] tamy0612. Jsplib: Benchmark instances for job-shop scheduling problem, Nov 2014. URL https://gi thub. wwt. tamy0612222 02t JSPLIB
[29] Tong and H. Ni. Look-ahead multi-time frame generator control and dispatch method in PIM real time operations. In IEEE Power and Energy Society General Meeting, July 2011.
[30] C. Tran, F. Fioretto, and P. V. Hentenryck. Differentially private and fair deep learning: A lagrangian dual approach. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 9932-9939, 2021.
[31] N. Vesselinova, R. Steinert, D. F. Perez-Ramirez, and M. Boman. Learning combinatorial optimization on graphs: A survey with applications to networking. IEEE Access, pages 120888- 120416, 2020.
[32] O. Vinyals, M. Fortunato, and N. Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, pages 2692-2700, 2015.

---

[33] A. Wächter and L. T. Biegler. On the implementation of an interior interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming. pages 25-57, 2006.
[34] B. Wilder, B. Dilkina, and M. Tambe. Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization. In Proceedings the AAAI Conference Artificial Intelligence, pages 1658-1665, 2019.
12


Reviews:
[{"review_id": "vnIWEPhF5Yy", "reviewer": "Reviewer_WzHp", "summary": "This paper proposes a method to generate solutions to optimization problems that are more amenable to supervised learning tasks. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "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.\n\n1.\tThe 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.\n\n2.\tFigure 3 covers the last part of line 165.\n\n3.\tThe 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.\n\n4.\tCan 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see the main review", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4h"}, "extra_text": {}}, {"review_id": "ZFHeKf3V3DK", "reviewer": "Reviewer_tnZz", "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Novelty\n\nTo 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. \n\n### Significance / Impact\n\nIn 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.\n\n### Soundness\n\nThe 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.\n(Only the argument regarding energy consumption and CO2 seems a bit artificial, although still correct.)\n\n### Clarity\n\nThe paper is very well written and easy to follow.\n\n### Minor Comments\n\n* “a optimal solution” → “an optimal solution”\n* Figure 3 overlaps a bit with the text “symmetries”\n\n### Questions for Rebuttal\n\n1. How do the results in Table 1 and 2 compare to a real constraint solver? \n2. Why is it better to maximize the time SOTA in Table 1?\n3. Would this approach also be applicable to NP-hard decision problems such as SAT?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Only briefly addressed, but I think it is fine.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "VRYKtyVM8_", "reviewer": "Reviewer_EWPX", "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).\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Originality\n\nThe 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:  \n\nLi et al, Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search, NeurIPS 2018\n\n# Quality\nThe 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. \n\nMy main concern is about the applicability of the proposed method in general.\n\n* 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?\n* 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)) ?\n* 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.\n\n* The fact that this bound can be obtained easily is essential for the method to work. I wonder how realistic is this assumption. \n* 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.\n* 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. \n* 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.\n\n* 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? \n* Tables 1 and 2: are the reported prediction errors evaluated on the training or test set? \n\n# Clarity\n\nThe paper is generally well-written. I have a few questions and suggestions below:\n\n## Statements to clarify:\n\n* 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.\n\n* L41-41: “learning good CO approximations in jointly training prediction and optimization models”. I don’t understand this \n* L95: What is meant by “surrogate models” here? This terminology is not used in the cited survey [23]\n* L198: what is meant by *small* piecewise linear functions?\n* 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…\n* 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.\n* Figure 3: same remark for “Generator setpoint” and “Base load factor”\n* 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)\n\n## Typos/details:\n\n* L37: intersection *of*\n* L48: may not have a *unique* (?) optimal solution\n* L124: in y \\in R^n —> remove in or y\n* L268, L377 (and others): hot-start —> I believe the term is warm-start \n* L225: the training *of* good…\n* L365: for —> form (or remove)\n* L379: *is* its restriction \n* L368: when compared the OD approach to *standard* (?) data generation results \n* L368: ... data generation results in predictions that are closer —> not clear\n* Equation 7: which norm is used?\n\n# Significance\n\nThe 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. \n\n# Update after rebuttal \n\nThe authors have addressed my main concerns about the applicability and limitations of their approach. \n\nSince they mean to update their manuscript accordingly, I am happy to revise my score from 6 to 7.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7 (main review) + 2 (rebuttal)"}, "extra_text": {}}, {"review_id": "CKeuZ7P4XgF", "reviewer": "Reviewer_vJwj", "summary": "This paper addresses a different aspect of learning-based problem solvers. \n\nTypical 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Personally, I enjoyed reading this paper and am interested in this kind of approach.\n\n- Pros\n  - The targeting problem is novel and the author discusses a sound approach to tackle the problem.\n  - The idea of using piecewise linear functions to represent the volatility is an interesting and effective approach for the problem illustrated in Fig.3.\n  - Compared with the standard method to generate data sets, the proposed method could outperform such a baseline method.\n- Cons\n  - 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.\n  - Some notations (see below comments) are confusing to clearly explain the idea.\n\n### Questions and comments\n\n- 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?)\n- 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.\n    - 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).\n    - This causes another problem in Eq. (9a) and (9b) because the $p$-norm among sets (if $y^{(i)}$ is a set) is not defined.\n- 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?\n- 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.\n- 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?\n- Some minor comments\n    - What does 'OD labels' mean in Figure 2? (Optimal Data generation?)\n    - A missing sentence behind Figure 3 (symmetries?).\n    - Figure 4 should be captioned as a table.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

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)