# Tag Info

24

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 ...

22

"General purpose optimization" is quite broad, so I'll take a step back first, to better identifying the motivation of using ML in optimization settings. To keep things simple, I'll consider a single-objective minimization problem with decision vector $x$, objective function $f$ and some constraints $x \in X$, i.e., \begin{align} (P) \ \ \ \min_{x} ...

16

In the operations research community, many study dynamic programming models and solution approaches. Since many interesting dynamic programming problems attempt to model information uncertainty over time, the term stochastic dynamic programming is sometimes used. The Markov decision process model is an example. Finding optimal policies to many dynamic ...

14

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 ...

11

Check Coursera, edX, Udemy, or any other online courses (such as those of Stanford). For example: Free: Discrete Optimization course on Coursera, covers column generation and an introduction to (meta)heuristic Optimization with Metaheuristics in Python on Udemy Lectures of Introduction to Meta-heuristics Artificial Intelligence: Reinforcement Learning in ...

10

RL (and Machine Learning in general) often use specialized forms of continuous optimization problems that enable one to use elegant solving techniques (e.g. training/learning on the GPU or even special hardware (TPU and friends)). See here for a nice overview of the underlying optimization problems in Machine Learning and Deep Learning. As @albert-...

10

There are a few courses on Coursera that offer such learning materials. Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming (Intermediate) The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal ...

8

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 ...

7

Something that I think is becoming more prominent is the use of RL for what would have traditionally been solved using exact solutions. https://medium.com/octavian-ai/finding-shortest-paths-with-graph-networks-807c5bbfc9c8 This is something that I'm following and will hopefully try and implement for a Prize Collecting Steiner Tree (PCST) and/or assignment ...

6

For heuristics you can take a look at this course. Also the book "How to solve it : Modern heuristics" by Zbigniew Michalewicz and David B. Fogel. Reinforcement Learning has similiarities with approximate dynamic programming, these video lectures by D. P. Bertsekas may be useful.

5

Institute of Applied Optimization Metaheuristic Optimization - prerequisite: Java programming Coursera Practical Reinforcement Learning - related

4

For Reinforcement learning and Deep Reinforcement learning, a wonderful online free course on RL by David Silver (the first author of the AlphaZero, AlphaGo algorithms) exists: YouTube links A more advanced course by Sergey Levine exists for free at: YouTube link For both course the link to the material of the course is available too.

3

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 ...

3

The previous answer provided a great list on the classical dynamic programming. For Reinforcement learning and Deep Reinforcement learning, a wonderful online free course on RL by David Silver (the first author of the AlphaZero, AlphaGo algorithms) exists: YouTube links A more advanced course by Sergey Levine exists for free at: YouTube link For both ...

1

Figured it out. It works exactly they way I originally intended to do it in my question. See this tutorial for detailed information on how to actually implement the procedure with real data.

1

It is just $$\sum_{n=1}^\infty a_n = \sum_{n=0}^\infty a_n - a_0 = \sum_{n=1}^\infty a_{n-1} - a_0,$$ where $$a_n=\lambda^n P^{d^\infty}(X_{n+1}=j\mid X_1=k).$$ In particular $$a_0=\lambda^0 P^{d^\infty}(X_1=j\mid X_1=k) = [j=k] = \begin{cases}1 &\text{if j=k}\\0 &\text{otherwise} \end{cases}$$

1

You can use RL in any step. But problem is optimality check of solution which is explained above. Also you can solve your problem directly using RL such as RL for VRP. And you can read this blog which is about RL usage. By the way your question is too broad to give detailed answer.

1

Not really, but approximately. By OR standards, a problem is "solved" once we manage to satisfy the KKT conditions. There is no machine learning algorithm to date that can consistently satisfy constraints. ML is designed to give pretty good approximations, and that's about it. For instance, image recognition can be posed as a convex optimisation ...

1

This is a clustering problem, i.e., you want split your services into two clusters, each of which will run on a different device. The way you would do this with RL is to use the goals an objective that includes weighted constraints. This of course assumes you have the right data/setup to train the algorithm. After enough training, your system will be able to ...

Only top voted, non community-wiki answers of a minimum length are eligible