Updates

Combining machine learning and mathematical optimization

Article five of five

In our first article we identified four scenarios where Machine Learning can cooperate with Mathematical Optimization. Here we identify further reading of two notable resources that can help us learn more about this topic. We encourage practitioners to review these two articles.

Machine learning for combinatorial optimization: A methodological tour d’horizon

[Article link]
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost

This paper surveys the recent attempts, both from the machine learning and operations research communities, at leveraging machine learning to solve combinatorial optimization problems.

Given the hard nature of these problems, state-of-the-art algorithms rely on handcrafted heuristics for making decisions which are otherwise too expensive to compute or mathematically not well-defined. Thus, Machine Learning looks like a natural candidate to make such decisions in a more principled and optimized way. We advocate for pushing further the integration of machine learning and combinatorial optimization and detail a methodology to do so.

A main point of the paper is seeing generic optimization problems as data points and inquiring what is the relevant distribution of problems to use for learning on a given task.

The second article:

On Learning and Branching: a Survey

[Article link]
Andrea Lodi & Giulia Zarpellon, volume 25, pages 207–236(2017).

This paper surveys learning techniques to deal with the two most crucial decisions in the branch-and-bound algorithm for Mixed-Integer Linear Programming, namely variable and node selections.

Because of the lack of deep mathematical understanding on those decisions, the classical and vast literature in the field is inherently based on computational studies and heuristics, often problem-specific, strategies. The authors both interpret some of those early contributions in the light of modern (machine) learning techniques, and give the details of the recent algorithms that instead explicitly incorporate machine learning paradigm.

In our next series we will focus on reinforcement learning, case studies that combine Machine Learning and Mathematical Optimization and how open source and commercial solvers can benefit from the new technologies.

‹ Previous Article