I'm curious whether Reinforcement Learning is or will become the state of the art solution for (mixed) integer programming. I imagine that this would fall under the umbrella of heuristics. Companies like Amazon have hundreds of thousands of vehicles to route, dozens of warehouses, and millions of items. Exact solutions through more traditional approaches are likely infeasible due to cost. And with the advent of cloud computing and state of research in deep learning, RL in this capacity seems inevitable. What is the status of research here?
$\begingroup$
$\endgroup$
1
-
4$\begingroup$ Here is the paper about the recent "Machine Learning for Combinatorial Optimization Competition" arxiv.org/abs/2203.02433 The conclusion states "The results indicate that machine learning for combinatorial optimization has potential, although more work must be done before it becomes relevant for practical, real-world use". Which is a politically correct way to say that currently it's not very useful $\endgroup$– fontanfCommented Sep 6, 2022 at 5:30
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Firstly, be ware that "traditional approaches" do not need to be exact. Heuristics are a big thing in OR for decades.
Now to answer your question: Reinforcement learning is not state-of-the-art for MILP problems (as of 2022). In fact, I am not aware of a single (well-known) (MI-) LP problem where RL outperforms specifically designed heuristics. I also do not believe companies like Amazon use RL for their routing decisions. If RL is used, then typically for stochastic and dynamic routing problems.
For further information I suggest you look at the following article
Yoshua Bengio, Andrea Lodi, & Antoine Prouvost (2021). Machine learning for combinatorial optimization: A methodological tour d’horizon. European Journal of Operational Research, 290(2), 405-421.
$\begingroup$
$\endgroup$
The combination of "traditional approaches" with, for example, RL-based approaches may be the state-of-the-art solution for the MIP (this reference as an instance, in which the RL help for learning the cuts of branch-and-bound to accelerate the convergence of a traditional approach).
