DOFramework: A testing framework for decision optimization model learners

Mathematical decision-optimization (DO) models provide business decision support for a wide range of scenarios. Take for example the winners and finalists of INFORM’s Franz Edelman Award from recent years. Those include the U.S. Census Bureau (Enumerator Assignments, $2.5B), the U.S. Federal Communications Commission (Wireless Service Auction, $20B), Vattenfall BA Wind (Wind Power Output, $170M), and Deutsche Bahn (Train Rotation Planning) among others.

In a mathematical DO model, often, hard-to-model terms can be learned from data. Learning, however, may result in a DO model that fails to capture the actual system that produced the data, leading to poor recommendations. For this purpose, we introduce DOFramework¹ as a playground for researchers and data scientists to test, tune, and compare novel approaches for integrating learning into DO models.

DOFramework generates multiple instances of optimization problems, feeds them to the user’s DO model learner, and collects its predicted optima. By comparing the predicted optimal values against the ground truth, DOFramework delivers a comprehensive prediction profile of the user’s DO model learner. Similarly to Gymnasium², which offers environments to develop and compare reinforcement learning (RL) algorithms, DOFramework addresses the need for benchmark playgrounds. DOFramework, however, samples problems at random rather than rely on a fixed library of those.

Learned DO models

A DO model is a mathematical formulation that incorporates an objective to optimize under constraints

The objective in this formulation is $f$, while the constraints are given by the inequality $g(x) ≤ 0$. We optimize over all realizations of the decision variable. The goal is to solve the optimization problem by finding an optimum $x^*$.

A DO model learner is an algorithm, routine, or pipeline that incorporates learning and knowledge into a DO model that integrates both. Its outcome is a learned DO model.

Integrating machine learning (ML) models into DO models offers tremendous opportunities whenever objective ($f$) or constraint ($g$) terms are unknown, but data is available.³ Unlike many existing works that assume knowledge of the DO model and focus on predicting its parameters,^{4, 5} DO model learning, also known as Optimization with Constraint Learning⁶ or Empirical Model Learning,⁷ seeks to embed an ML model into a DO model, considering (some of) its decision variables as features of the ML model.^{8, 9, 10}

Optimization problem instances

At its core, DOFramework generates synthetic optimization problem instances at random. An optimization problem instance is a tuple $(f, Ω, D, x^*)$ that consists of a continuous piece-wise linear function $f$ a bounded convex polytope $Ω = \{x | g(x)≤0\}$ (meaning $g$ is affine), a dataset $D = (x,y)$ associated with $f$ (that is, $y = f(x)$ + error), and the optimum $x^*$ of $f$ in $Ω$. The function is the objective target of the optimization problem, while the polytope provides the constraints. The ground-truth optimal value of the optimization problem instance is. The key algorithmic challenge of DOFramework lies in producing $(f, Ω, D, x^* )$ so that is known combinatorially rather than analytically.

Prediction profile

A DO model learner solves an optimization problem instance when it produces a learned DO model that fits the ground truth best. The best learned DO model will produce a learned optimum $x̂$ whose true value $f(x̂)$ is (or, more likely, close to) the true optimal value $f(x^*)$. A DO model learner acts as a black box that takes in data and knowledge (namely, those known terms of the DO model) and spits out a learned optimum $x̂$.

By comparing $f(x̂)$ to $f(x^*)$, over many generated optimization problem instances, DOFramework derives a prediction profile of the DO model learner. To put this more mathematically, DOFramework provides an empirical distribution that allows the user to estimate the probability

for any $0<ϵ<1$. It therefore quantifies how good we expect the learned optima to be. When considering minimization, the closer $(†)$ is to 1 the better, and the closer $ϵ$ is to 0, the harder it would be to achieve.

Here is an example of two prediction profiles derived by DOFramework. The prediction profile on the right comes from a baseline DO model learner that combines linear regression together with the PuLP solver.¹¹ The prediction profile on the left comes from OptiCL¹² with Trust Region. The comparison is done across “low” $(d = 2,3)$ and “high” $(d = 5,7)$ dimension problems.

We can see how OptiCL performs better over the baseline DO model learner: it is more consistent and therefore more reliable, though more conservative. We can quantify this observation by estimating the probability $(†)$ for various values, using these empirical distributions.

Could-distributed design

DOFramework was designed for scale, performance, robustness, and reproducibility, while keeping it agnostic to the user’s DO model learner, integrated as a black box. Combining Ray¹³ and Rayvens¹⁴ together with Cloud Object Storage (COS) allowed us to achieve exactly that: a fully-distributed, event-driven implementation that deploys easily on a Kubernetes cluster (IBM Cloud or AWS). DOFramework can be deployed locally as well, replacing COS with local storage. All we need is a storage “bucket,” whether an S3 bucket or a local folder.

The cloud-distributed computing framework Ray provides simple primitives for distributed applications. Rayvens provides abstractions for event management built on top of Ray. Combined with Ray, Rayvens provides a powerful tool for integrating event-driven stream processing together with cloud distribution.

Here is how we use Ray and Rayvens in practice. Once uploaded to the meta bucket, DOFramework input files (with essential metadata to generate problems) trigger Rayvens events: Rayvens feeds these inputs to a processor that uses them to generate objectives $f$ (with constraints $Ω$). These generation tasks are distributed asynchronously via Ray. Rayvens then streams each generated objective $f$ (with constraints $Ω$) as a file into the objectives bucket. Once objective files land in the objectives bucket, they trigger new events, again, handled by Rayvens, which feeds them into a second processor. This second processor uses each newly created objective $f$ (with constraints $Ω$) to generate datasets $D$. Rayvens then streams each dataset $D$ as a file into the data bucket. Then the pattern repeats itself: when dataset files land in the data bucket, they trigger events consumed by a third processor. This time it’s the user’s DO model learner, which takes in the dataset $D$ (together with its associated constraints $Ω$) and produces a learned optimum $x̂$. Each learned optimum is uploaded over the Rayvens stream to the final estimates bucket, where it’s ready for further analysis.

After the DO model learner has solved enough optimization problem instances, we are ready to derive its prediction profile and estimate how well it did $(†)$.

To learn more about our work, join our Optimization with Constraint Learning AAAI 2023 Lab on February 8th, 2023, or check out our GitHub OCL Lab repo. There you will find Jupyter Notebooks demonstrating OptiCL and DOFramework, together with detailed installation instructions for OCL Lab materials.