What are the tradeoffs between "exact" and Reinforcement Learning methods for solving optimization problems

Question

Exact methods, e.g., models that utilize an MIP approach with a specified objective and constraints, have advantages like the following:

• Using off the shelf solvers
• Optimality gap provability
• Modelling approaches for domain problems is well understood

Reinforcement Learning (RL) presents the opportunity to train a model and then have it "predict" a solution.

Why would you use this method?

What is the effectiveness of this as a methodology?

It may be possible to get "better" solutions in less compute time given a pre-trained model.

Is any one else working on this type of approach? Or have references?

(Specifically for solving network flow and assignment problems on graphs.)

Answer 1

As far as I understand it, all machine learning approaches used for solving (combinatorial) optimization problems, and in particular reinforcement learning, work as follows:

Use a greedy algorithm to iteratively construct a solution (e.g., by iteratively selecting edges into a path or a tour), and "learn" the ranking (i.e., the ordering) of the next items to pick (e.g., an edge). This said, again, as far as I understand it, any ML based approach that follows these lines, is necessarily a local (search) approach.

It certainly is a heuristic.

It appears to need training for specialties of instances you see and does not (yet?) work generally.

Here is a reference: Dai et al.

A benefit of using an ML approach for optimization is (in my view): we may get a computational intuition about (patterns in) the solution that would not have spotted otherwise. If we would see such patterns, throw away all ML, get paper and pencil and try to prove what we see.

Answer 2

Reinforcement learning is set of the algorithms which are used to solve Markov Decision Processes and its variants, e.g. Partially Observed MDP (POMDP).

Most of the problems that we deal with them in the industrial engineering departments and in a larger extent in the Informs community, can be modeled as a MDP or POMDP. Although, in MDP we assume that we know the transition probability distribution for transiting between states, and also assume know the reward distribution too, which are not realistic assumptions. On the other hand, RL does assume availability of those distributions and tries to learn them, which is viable option since nowadays we have huge datasets. So, it might be a good idea to consider RL in OR community too.

Here are some papers which get better results with RL than the classical approaches:

VRP:

• Nazari, et al., Reinforcement Learning for Solving the Vehicle Routing Problem, 2018.

Inventory Optimization:

• Oroojlooyjadid, et al., A Deep Q-Network for the Beer Game: A Deep Reinforcement Learning algorithm to Solve Inventory Optimization Problems, 2019.
• Gijsbrechts, et al., Can Deep Reinforcement Learning Improve Inventory Management? Performance and Implementation of Dual Sourcing-Mode Problems, 2018

just to mention a few.

Disclaimer: I am one of the co-authors of the first two papers, and I am not posting the links to advertise them!

Answer 3

A main reason to use Reinforced Learning (RL) is because you don't know the dynamics (update rules) of the system. If you don't know the details of how the system will update, you will not be able to construct tight constraints for MIPs. For example, you may be able to write an MIP for the system with constraint $Ax = b$. However, the values of some elements in $A$ or $b$ maybe unknown.

Since we don't know the dynamics of the system, RL usually requires a huge number of samples from the system to learn the dynamics. There are two major solving approaches for RL.

• Model-based: Use samples to identify a proper model and then use more samples to calibrate that model.
• Model-free: Update the solution with upcoming samples according to certain rules. (Policy Gradient)

In terms of sample complexity, RL in general is quite inefficient comparing to methods with a known fitting model. But the strength of RL comes from its ability to learn the unknown dynamics.

I am not an expert in this field. But I would recommend Ben Recht's paper on the connection between RL and optimal control problems.

Answer 4

Reinforcement learning does not seem to be the most obvious choice in machine learning for optimisation. I have heard a lot of using supervised learning to decide the decisions to take when exploring a B&B tree (which could very straightforwardly be transformed into a reinforcement learning problem).

You also have research in ML giving directly a good answer to your problem. For instance, using recurrent neural networks to deal with graphs: the output is a probability distribution on "interesting" edges of your graph, the ones you should consider taking for your solution.

One reference for all of this: Machine Learning for Combinatorial Optimization:a Methodological Tour d’Horizon. Section 3.2.1 to get complete solutions from ML, 3.2.3 to use ML within the B&B exploration.