Integrating Machine Learning and Optimization to Boost Decision Making

1 Introduction

Constrained optimization (CO) is in daily use in our society, with applications ranging from supply chains and logistics to electricity grids, organ exchanges, marketing campaigns, and manufacturing to name only a few. Although these problems are often NP-hard and computationally challenging even for medium-sized instances, they constitute fundamental building blocks for the optimization of many industrial processes and are key to the stability of their operations with profound effects on our society and economy. The AI and Operations Research communities have devised a wide spectrum of techniques and algorithms to effectively leverage the problem structure and solve many hard CO problems instances within a reasonable time and with high accuracy. While this success has made possible the deployment of CO solutions in many real-world contexts, the complexity of these problems often prevent them to be adopted in contexts of repeated (e.g., involving expensive simulations, multi-year planning studies) or real-time nature, or when they depend in nontrivial ways on empirical data.

In many practical settings, we must solve many problem instances sharing similar patterns. This is the case with power system applications, for example, where the same problem is solved repeatedly with different inputs (e.g., loads and generation bids), or in industrial manufacturing scheduling, where the different inputs represent different tasks to be scheduled on a constant set of machines. Therefore, the application of deep learning methods to aid in solving computationally challenging constrained optimization problems is a promising approach and has gained traction in the nascent area at the intersection between constrained optimization and machine learning (ML) [Bengio et al., 2020; Kotary et al., 2021b; Vesselinova et al., 2020]. However, while deep learning has proven its power for unconstrained problem settings, it has struggled to perform as well in domains where it is necessary to satisfy hard constraints. For example, in power systems, materials science, fluid dynamics, and many other areas, the data follows well-known physical laws, and violation of these laws can lead to unreliable and unusable approximations. There is thus a critical need for fast deep learning approximators that can operate in settings where traditional optimizers are slow, yet feasibility criteria must be satisfied.

The goal of this paper it to summarize our recent research efforts made to address this need.

2 ProblemDefinition

Our research uses deep learning to approximate the optimal solutions to optimization problems of the form

where x ∈ Rn is a vector of decision variables, d ∈ Rm a vector of input data, and f : Rn+m → R+ is the problem objective. The set of constraints C is arbitrary. A recurrent class of problems we consider are nonlinear nonconvex programs defined by the constraint set C(d) = {x | H(x, d) = 0; G(x, d) ≤ 0}, where H and G describe p equality and q inequality constraints, respectively, hi(x, d) = 0 (i∈[p]) and gi(x, d) ≤ 0 (i∈[q]), each defined on Rn ×Rm. The training task is given a dataset D={(di, ⋆xi∈ P(di))}Ni=1 of N samples, where ⋆xi is a (possibly) optimal solution to Problem (1) for input di. The dataset is used to estimate a parametrized model represented by the function M. Given its parameters vector θ and input di, the model predicts ˆxi=Mθ(di)∈Rn , a vector of values from the output space of x.

3 Learning COApproximations

Given an optimization problem P of the form specified in Equation (1), the objective is to learn a parametric model Mθ : Rm →Rn that, given the problem input data d, predicts the optimal values ⋆x for the decision variables. The learning task must solve the following empirical risk optimization:

(a) Solution Quality.

(b) Objective cost distances and runtime.

Table 1: Lagrangian dual deep learning: Each test case represents a benchmark set with different load congestion scenarios. Results are averaged across all scenarios and best results are shown in bold fonts.

to obtain an approximation ˆ P =M⋆θ of P. The loss function L characterizes the similarity of the predictions ˆxi =Mθ(di) to the ground truth ⋆xi and C(ˆx, d) holds if the problem constraints ˆx ∈ C(d) are satisfied. However, this framework faces a fundamental challenge: deep learning frameworks cannot naturally handle the problem constraints.

Lagrangian dual deep learning. To drive the DNNpredictions toward satisfying the problem constraints, our work has proposed several integrations of optimization techniques with deep learning [Kotary et al., 2021b; Fioretto et al., 2020b; Kotary et al., 2022b]. In particular, one approach exploits Lagrangian duality to integrate trainable and weighted regularization terms that encapsulate constraints violations [Fioretto et al., 2020a]. Indeed, the ML loss function should be guided by both data and the task at hand. The Lagrangian relaxation of problem P with C ={x|H(x)=0; G(x)≤0} is a weighted sum of objective and constraint functions fL :Rn×Rp×Rq → R, defined as:

where λhi and λgi ≥ 0 are the Lagrangian multipliers associated with constraints hi(x) = 0 and gi(x) ≤ 0, respectively. The presentation omits the input data d∈Rm in the various functions and constraints.

To approximate problem P with a DNN model Mθ while accounting for the problem constraints, we parametrize the model loss function L by the Lagrangian multipliers λ = {λc}c∈C, as Lλ(ˆx, ⋆x) = LO (ˆx, ⋆x) + LCλ (ˆx), where ˆx = Mθ(d) represents the model prediction, LO (ˆx, ⋆x) measures the prediction error and LCλ (ˆx) = ∑c∈C λcνc(ˆx) the constraint violations of the prediction. For multipliers λ, solving the optimization problem

produces an approximation ̂ Pλ = M⋆θ(λ) of P. The Lagrangian dual computes the optimal multipliers, i.e.,

to obtain, ̂ P ∗ =M⋆θ( ⋆λ) , i.e., the strongest Lagrangian relaxation of P. Learning ̂ P ∗ relies on an iterative scheme that interleaves the learning of a number of Lagrangian relaxations (for various multipliers) with a subgradient method to learn the best multipliers and described in [Fioretto et al., 2020a].

A glimpse of its effectiveness. The effectiveness of the Lagrangian dual learning framework was shown in several domains, including learning power flows in energy systems [Fioretto et al., 2020b; Mak et al., 2021], learning optimal compression settings in gas networks [Fioretto et al., 2020a], trasnprecision computing [Fioretto et al., 2020a], ML model pruning [Kaur et al., 2022], and fair machine learning [Tran et al., 2021b; Tran et al., 2022; Nagar et al., 2021].

In the following we provide an overview of the results obtained to the problem of finding the least cost generator dispatch to meet the demands in a power network (AC-OPF). The problem is required to satisfy the nonconvex nonlinear AC power flow equations that are a core building block in many power system applications. Table 1 summarizes results for power systems with up to 1,000+ lines [Fioretto et al., 2020b; Chatzos et al., 2020]. It compares the Lagrangian dual method M against the DC-OPF model (DC)- which is a linear approximation of the AC-OPF-and a DNN model M- whose loss function only includes the prediction error LO (ˆx, ⋆x) component (i.e., it does not encourage constraint satisfaction). The DNN architectures are based on a feed-forward multi-task network to predict the various physical quantities (generators power and voltage) [Fioretto et al., 2020b]. Table 1a compares the accuracy of the proposed DNN model against the approximation found by the DC-OPF model and the optimal AC-OPF solutions. The solution quality is measured by first finding the closest AC feasible solution to the predictions returned by the DC or by the DNN models to restore feasibility. Then, the dispatch values are compared to the original ones. The table reports the average distances (%) for the active power (pg ) and voltage magnitude (v) against the model predictions (left sub-table) and the AC-OPF solutions (right sub-table). The table reports the results for three benchmark networks (with 30, 118, and 300 buses) and the last row reports the average results for an extensive set of medium-size networks [Fioretto et al., 2020b; Chatzos et al., 2020]. The results illustrate that the Lagrangian dual model is up to two orders of magnitude more precise than the DC model and the baseline DNN. Table 1b compares accuracy and runtime of the proposed DNN model and DC against the AC-OPF solutions found by a state-ofthe-art (SoTA) nonlinear solver. The left sub-table reports the average L1-distances of the dispatch costs against the optimal costs and the right sub-table illustrates the time required to find an AC-OPF solution, a linear DC approximation, and a prediction using the proposed Lagrangian approach. Observe that the proposed model finds dispatches whose costs are at least one order of magnitude closer to the true solution than those returned by the DC while being several orders of magnitude faster. These results are significant: They suggest that the integration of optimization and deep learning has the potential to replace approximations, such as the DC model in energy systems, and deliver solutions with greater fidelity and computing speed.

4 Why Constraints help Predictions?

While this line of research has been shown effective to approximate CO solutions, still little is known on when and why these models can predict solutions to CO problems accurately, as well as about their predictions robustness. In an effort to address this knowledge gap, and recognizing that answers to this questions may depend on the target problem and computational budgets, in [Dinh et al., 2021] we focused on AC-OPF predictions.

Solution trajectories as piecewise linear functions. To answer why DNNs are able to approximate OPF solutions with low errors, we studied the relation between the training data and their target outputs. Figure 1 (top) shows, with solid lines, how generator outputs change as a function of the total demand for selected IEEE-118 generators. Observe that, the solution trajectory associated with the problem instances on various input parameters can 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 have the ability to capture piecewise linear functions [Moon, 2021].

However, while these models are thus compatible with the task of predicting the solutions of an optimization problem, the model capacity required to represent a target piecewise linear function exactly depends directly on the number of constituent pieces. In a [Kotary et al., 2021a] we characterized the error associated with the classes of functions that can be learned by a ReLU network model with fixed capacity with respect to a target trajectory. When many variables have simple solution trajectories, thus, highly accurate approximation can be obtained by a ReLU networks, even if ignoring the problem constraints. In the figure we illustrate that a model equipped with ReLU activations (dotted line) can indeed better approximate a model equipped with TanH activations (dashed lines).

The importance of constraints. Givne the result above, it is to be expected that larger DNN models will be better suited to learning more complex solution trajectories. However, this aspect was not consistently observed in our experiments [Dinh et al., 2021]. Figure 1 (bottom) illustrates this surprising behavior for three generators with complex trajectorires, showing that the prediction error does not decrease at increasing of the model size. To understand why this behavior occurs, in [Dinh et al., 2021] we examined the dynamics of highly volatile solution trajectories, which, incidentally, are also associated with high prediction errors, when a DNN (unconstrained) model is used to predict them. In the paper we show that, the highly volatile portions of the solution trajectories are often associated with binding constraint in the problem and that the prediction errors arise as the hidden representation of the DNN does not accurately learn the operational and physical constraints which regulate the behavior of the OPF solutions. When constraints are explicitly encoded in the model, e.g., via the Lagrangian dual method described above, these behaviors largely disappear obtaining highly accurate predictions.

5 Dealing with Data and Discrete Structures

Section 3 focused on endowing deep learning models with the ability to satisfy constraints. In all these studies, the ML frameworks that learn to approximate solutions to hard optimization problems are assumed to have access to supervision labels that can guide the construction of the solutions to target problems. However, when these labels are themselves approximations, when the optimization problem has symmetric solutions, and/or when the optimization solver uses randomization, solutions to closely related instances may exhibit large differences and the learning task can become inherently more difficult. This issue particularly acute when learning proxies to discrete optimization problems, whose solution spaces often present a large number of symmetries.

These challenges are illustrated in Figure 2 (Standard Labels/blue curves). The left subplot shows the L1-distance between the obtained solution to each training instance (i.e., the start times of the tasks in a job shop scheduling problem), sorted by processing times, and a reference optimal solution for some instance. The curve shows that meaningful patterns can be lost, including the important relationship between an increase in processing times and the resulting solutions. Figure 2 (right) shows that, despite the high volatility, the learning 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 ΠC(ˆx) of the prediction ˆx onto the schedule-feasible space C and the real label ⋆x) remains poor (blue star). Similar observations pertain to constraints violations, which remain high. It is worth emphasizing that these volatility issues are further exacerbated when time constraints prevent the solver from obtaining optimal solutions.

In [Kotary et al., 2021a] we have analyzed this critical challenge, connecting the volatility of the training data to the ability of a model with given capacity to approximate it. In addition, we devised a method for producing (exact or approximate) solutions to optimization problems that are more amenable to supervised learning tasks.

Exploiting the problem structure. This training data generation process was used to learn highly accurate job shop scheduling problems [Kotary et al., 2022a], a notoriously challenging combinatorial optimization problem, due to its disjunctive constraints. When dealing with such problem, we also observe that the network architecture plays a nontrivial role in helping the training process to converge to better minima and, even, to help generating predictions that satisfy the problem constraints. More specifically, in [Kotary et al., 2022a] we devise a network that differentiates three types of layers: Job layers, that process processing times organized by jobs, Machine layers, that process processing times organized by machines, and Shared layers, that process the outputs of the job layers and the machine layers to return a prediction. Such architecture exploits directly the job-shop problem structure and was shown highly beneficial to the learning task. We believe that this observation is highly generalizable to other contexts and decision tasks.

Learning constrained policies. Despite the high quality results obtained in the learning methods described in the previous sections, their predictions offer no guarantees on the satisfaction of the problem constraints. This issue is often mitigated by a post-prediction step that projects the predictions returned by the learning models onto the feasible space. While these projections steps use a classical optimization solver, they are generally extremely fast, as the solvers can be warm-started with the predicted solutions, which are already very close to the optimal ones.

This issue however, complicates further in the presence of discrete structures, where efficient projections may not exists or where many symmetric solutions exists, as pointed out above. Motivated by this challenge, we have proposed a integration of constrained optimization programs within a deep learning pipeline which is trained end-to-end to produce optimal (constraint-satisfying) solutions. This technique is studied in [Kotary et al., 2022b] in the context of fair learning to rank tasks. The task consists in learning a mapping between a list of items and a permutation of such list, which defines the order in which the items should be ranked in response to a user query while enforcing some desired notion of group fairness over rankings. In addition to providing a certificate on the fairness requirements, this method allows the modeler to enforce a large number of fairness concepts that can be formulated as linear constraints over rankings and is shown to significantly improve current state-of-the-art fair learning-torank systems with respect to established performance metrics.

Finally, we have shown how the integration of machine learning and optimization can be used to enforce fairness constraints on predictors and obtain state-of-the-art results when minimizing disparate treatments [Fioretto et al., 2020a]. This technique can be used in combination with differential privacy to achieve a privacy-preserving deep learning algorithm that also encourages the satisfaction of a variety of fairness constraints, as we have shown in [Tran et al., 2021a; Tran et al., 2021b].

6 Opportunities and Challenges

Our research on integrating constrained optimization with end-to-end machine learning is part of a larger effort embarked by a nascent community at the intersection between operations research and artificial intelligence [Kotary et al., 2021b]. Despite the encouraging results, a number of challenges remain that must be addressed to allow an integration that lives up to its full potential. (1) In predicting solutions to constrained optimization problems, the current methods cannot robustly guarantee arbitrary problem constraints to be satisfied. This critical shortcoming may be addressed by integrating ML approaches with methods from the robust optimization literature or by developing ad-hoc layers to project the predictions onto the feasible space. (2) Despite the variety of approaches, the success of integrating an optimization solver within a ML model in the loop has been demonstrated on a relatively limited set of optimization problems and, focusing mostly on linear programming formulations. Challenges posed by the parametrization of constraints stand in the way of broader applications. (3) Issues associated with the runtime of combinatorial solvers in-the-loop still make some potential applications impractical. (4) Finally, this area still lacks theoretical results providing guarantees on the classes of optimization problems that can be approximated via a learning proxy and their performance.

In summary, the integration of constrained optimization and learning promises to produce a new generation of solvers that will enable novel operation assessments at unprecedented scales (e.g., over multi-years simulation studies) and may transform the current concepts of robustness and high-quality solutions in many engineering and scientific applications.

Acknowledgments

This research is partially supported by NSF grants 2007164, 2133169, NSF CAREER Award 2143706, and a Google Research Scholar Award. Its views and conclusions are those of the authors only.