Data-driven optimization model customization

Mike Hewitt, Emma FrejingerEur. J. Oper. Res 2020 · OpenReview

Introduction: The Reality Gap in Operations Research

In the field of operations research (OR), mathematical models are powerful tools for decision-making. However, a persistent challenge remains: the "reality gap." A General Optimization Problem (GOP)—such as minimizing transportation costs or maximizing warehouse throughput—often fails to account for the nuanced, unwritten business rules that govern daily operations. For example, a "textbook" optimal delivery route might be rejected by a human planner because it ignores a specific customer's preference for early morning loading.

Traditionally, bridging this gap requires significant manual intervention. Consultants must interview stakeholders, identify these "hidden" constraints, and hard-code them into the optimization engine. For Software as a Service (SaaS) providers, this approach is unsustainable. Maintaining a single, clean codebase while catering to the unique operational realities of hundreds of different customers creates a significant technical and financial burden.

Methodology: Autonomously Learning Hidden Constraints

This research introduces a framework designed to automate the customization of optimization models using historical data. The core premise is that when human planners deviate from a GOP’s optimal solution, their decisions reflect valid, albeit un-modeled, business rules. By analyzing the discrepancy between "textbook" solutions and actual historical implementations, the framework transforms a generic GOP into an Adapted Optimization Problem (AOP).

The authors explored two primary mathematical strategies for learning these rules:

  1. Learning Linear Mappings: This approach utilizes linear regression to identify a functional relationship between the GOP's theoretical optimum and the plan executed in practice. It essentially models how users "tweak" the mathematical output to suit real-world needs.
  2. Learning a Separating Hyperplane: This method employs a quadratic program to define a geometric boundary (a hyperplane) that distinguishes "textbook" solutions from those that were actually implemented.

Once identified, these learned rules are integrated into the model as additional linear constraints and variables. A penalty parameter ($c$) is introduced to the objective function, serving as a "trust knob." This allows users to balance the original optimization goal (e.g., cost minimization) with the necessity of adhering to discovered business patterns.

Experimental Evaluation

The framework was evaluated using synthetic yet controlled datasets representing 200 to 1,000 days of operations across three classical Mixed Integer Linear Programming (MILP) problems:

  • Linear Knapsack Problem: Maximizing revenue by selecting items for a container.
  • Transportation Problem: Minimizing shipping costs from suppliers to customers.
  • Facility Location Problem: A complex logistics problem involving binary decisions regarding warehouse placement.

To test the system's efficacy, the researchers "hid" three specific types of business rules—equitability, binary exclusion, and capacity-based constraints—to determine if the framework could autonomously rediscover them.

Key Insights: Performance and Robustness

The study yielded several critical findings for the practical application of data-driven optimization:

  • Regression Superiority: The linear mapping (regression) approach consistently outperformed the separating hyperplane method. It proved more robust in generating solutions that satisfied hidden rules across diverse problem types.
  • High Feasibility with Low Overhead: In standard settings, AOP solutions achieved nearly 100% satisfaction of hidden rules once the penalty parameter was sufficiently tuned. Remarkably, this adaptation came with a minimal "efficiency tax"—the degradation of the original objective function was typically less than 6% compared to a model with perfect knowledge of the rules.
  • Sample Efficiency and Interpretability: The system demonstrated strong performance with as few as 100 days of training data, making it viable for new software deployments. Furthermore, because the framework relies on linear representations, the learned rules remain interpretable; developers can inspect regression coefficients to understand the logic the system has inferred.

Discussion and Future Work

While the framework offers a scalable solution for model customization, it has limitations. Currently, it is restricted to learning linear relationships to maintain the speed of MILP solvers. Highly complex, non-linear business logic may require more advanced modeling. Additionally, the penalty parameter ($c$) currently requires manual adjustment; future research could focus on automating this selection based on statistical fit.

For scenarios involving multiple, context-dependent rules, the authors suggest that a pre-processing stage—using clustering or deep learning for classification—could enhance the framework's ability to handle complex operational environments. By bridging the gap between generic math and specific reality, this data-driven approach paves the way for more adaptive and scalable optimization software.

Summary updated

BibTeX
@article{hewitt2020data,
  author = {Mike Hewitt and Emma Frejinger},
  title = {{Data-driven optimization model customization}},
  journal = {Eur. J. Oper. Res.},
  year = {2020},
  url = {https://openreview.net/forum?id=pp6dItf7B8},
}
Figure