25
$\begingroup$

Can someone give me a few examples, if they exist, of problems in operations research that could be solved using machine learning.

I am aware that machine learning examples are data-driven and do not give exact solutions, so I am expecting heuristics, and possibly solutions that are specific for a particular instance of the problem.

I am looking for 'direct' machine learning solutions that use machine learning to find a solution of the actual problem, and not just 'indirect' approaches that try to improve existing methods.

EDIT: I am looking for examples in which the ML approach outperforms other methods.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Can you define what you mean by "out-perform" ? Obviously not more accurate since (as you state) ML solutions mostly don't give exact solutions (especially if you forbid anything that looks like using ML to enhance a standard method)? Do you mean faster? It is very easy to make a faster method, if you don't also constrain to be accurate (e.g. linear regression). $\endgroup$
    – Frames Catherine White
    Commented Jul 6, 2019 at 9:19
  • $\begingroup$ As far as I understand, one heuristic is better than the other if they give better results in the same amount of time. If we consider the ML approach as an heuristic, I am asking for an example in which a ML heuristic is better than other non-ML heuristics. $\endgroup$
    – klaus
    Commented Jul 9, 2019 at 16:38

5 Answers 5

Reset to default
16
$\begingroup$

There are many recent and not so recent papers that use ML to "solve" optimization problems, like Learning Combinatorial Optimization Algorithms over Graphs. A very, very good entry to the subject is the survey Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon.

In your last sentence you probably ask too much. For optimization problems, there are basically two kinds of approaches, exact and heuristic. For all optimization problems you can think of, both approaches have been suggested. Of course (of course!) no algorithm can beat an exact approach, at least not in terms of solution quality as these - by definition - find the best possible solutions. This is not the case for heuristics, which can be of better or worse quality (but maybe beat the exact methods in terms of runtime, so there is a tradeoff). Therefore, when you ask for ML approaches to beat optimization algorithms, these can beat, at best, other heuristics. And again: An ML approach is (almost always) a heuristic approach, and I would add "yet another heuristic approach". You cannot expect them to beat existing heuristics, but you can be lucky, which is true for any other heuristic.

edit: re-reading your question I conclude that I could not really contribute to an answer.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ The paper "Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon" that you provided answered my question. More specifically, section "3.2.1 End to end learning" was exactly what I was looking for. $\endgroup$
    – klaus
    Commented Jul 12, 2019 at 2:09
  • $\begingroup$ @klaus great! I love that paper, too. $\endgroup$
    – Marco Lübbecke
    Commented Jul 12, 2019 at 4:57
11
$\begingroup$

Bertsimas and Stellato just put up a new preprint which proposes a method to solve online mixed-integer optimization (MIO) problems at very high speed using machine learning. They benchmark their method against Gurobi and obtain speedups of two to three orders of magnitude on benchmarks with real-world data.

https://arxiv.org/abs/1907.02206

Improve this answer
$\endgroup$
3
  • 4
    $\begingroup$ Note that in this paper the computation times are really short for both Gurobi and their ML algorithm, so it is not clear whether the speedup would scale up and is not just due to a higher "startup" time. $\endgroup$
    – Michael Feldmeier
    Commented Jul 6, 2019 at 7:47
  • 1
    $\begingroup$ Thanks for pointing this out! $\endgroup$
    – CMichael
    Commented Jul 6, 2019 at 7:48
  • 1
    $\begingroup$ I would also make a distinction between learning to solve, and learning to represent the solution of a parameterized problem. What is done here is simply that a multi-parametric problem is solved by approximating the solution function, using sample solutions, and a function approximation which happens to be a NN. ReLUs work very nicely as the optimal solution to this parameterized MIQP indeed is piecewise affine (We did a similar thing last year in a master thesis project, learning the output from an QP based MPC controller, resulting in close to MHz speed while Gurobi ran in 100Hz or so.) $\endgroup$
    – Johan Löfberg
    Commented Jul 9, 2019 at 10:19
6
$\begingroup$

Using OR in ML is a very popular approach due to the optimization nature lying behind ML.

However, as you ask, there are also many examples (younger, newer) where you apply ML to solve OR problems. For example, for routing problems: https://arxiv.org/pdf/1803.08475.pdf

The list can be appended, but I think your question needs to be improved before.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ The paper you cited has quite a few examples in the related work section. However they claim that "The goal of our method is not to outperform a non- learned, specialized TSP algorithm such as Concorde...". I edited my question to narrow my search for examples that do outperform non-learned algorithms. $\endgroup$
    – klaus
    Commented Jul 4, 2019 at 22:30
4
$\begingroup$

There is a paper Learning Fast Optimizers for Contextual Stochastic Integer Programs where they develop a "learnable local solver" to solve problems where the MIP solvers did not scale.

I have not studied the paper, yet, but it may fit your bill.

EDIT: From the abstract/introduction: The problems are two-stage stochastic optimization, where the learned local solver is applied to the first stage, after which the (deterministic) second stage is handed to a MIP solver. This performs better than handing the overall problem to a MIP solver (better objective within same time limit).

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ The problems are two-stage stochastic optimization, where the learned local solver is applied to the first stage, after which the (deterministic) second stage is handed to a MIP solver. This performs better than handing the overall problem to a MIP solver (better objective within same time limit). $\endgroup$
    – Robert Schwarz
    Commented Jul 5, 2019 at 5:42
  • $\begingroup$ Perhaps this comment would be better served as an edit to the answer for the benefit of future visitors $\endgroup$
    – SecretAgentMan
    Commented Jul 8, 2019 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.