# Tag Info

23

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

21

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

18

There are tons of applications of ML for making forecasts in business settings, but in my opinion the more interesting approach is to use ML directly to make decisions—use it for prescriptive, rather than predictive, analytics. In other words, think of ML as essentially nothing more than a (potentially very powerful) heuristic for solving an optimization ...

17

When you build up your portfolio, you should ask yourself why a specific project is interesting to you (and potentially to a broader audience). What advantage could it have to combine OR and ML, or why use one instead of the other? In my opinion, these considerations add additional value to your portfolio, as they go beyond 'just' displaying your technical ...

16

Besides the "obvious" marriage of ML and optimization (namely, use ML to prepare the input for optimization), there can be combinations that make use of the respective strengths: ML is good for decisions that are repetitive, ill-structured, simple in their solution; opt is good for well-structured situations, complex in their solution. Thus, a ...

16

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

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

14

You can have a look at the program of the Deep Learning in Discrete Optimization by William Cook. In addition to the references to material relevant to your question, you can find at the end of the page a small section about 7 possible "final projects". An update list of references and projects is available on 2019 version of the course. Those projects do ...

13

Great question. You might be interested in this paper here: Learning MILP Resolution Outcomes Before Reaching Time-Limit by Martina Fischetti, Andrea Lodi, and Giulia Zarpellon. They don't exactly answer your question but you may see why the question is hard to answer and what partial progress can be made. A priori estimating the tree size is estimating ...

11

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

11

Here two examples that would combine OR and ML swiftly: Suppose you have a math program in which the objective function can only be computed via simulation (very realistic engineering problem). Since you can’t tackle such an objective function in a math program, you could use a regression (to keep things simple for now) to estimate the objective function (...

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

First, I would argue that the technologies are not necessarily complementary, but can be supplementary. A paper uploaded to Optimization Online just last month discusses the use of machine learning to decide how to linearize MIQP models. My answer to your first question is no doubt shaped by my being an academic, which means I rarely solve the same problem ...

9

As the borders between statistics and machine learning are diffuse, I take freedom to include statistics. Some links: Non-negative least squares, posts on cross validated. But often restrictions can be implemented just by reformulation. Order-restricted statistical inference should be better known and more used. There is a new R package being developed ...

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

This is a post that of my interest. I can give you one such example. I am currently working on an optimization problem, where we have a large LNG gas compressor network (eg. a connected graph with nodes as compressors and arcs as trunklines), and the goal is to find the operational conditions of the compressors such that we end up minimizing the total power ...

7

There are many good answers already, but here are a few viewpoints I have not seen yet. Machine Learning (including deep learning) is nothing but mathematical optimization. Indeed, training a model amounts to minimize a loss function. The main difference between ML/DL and optimization used in OR/MS is that the former is usually non-linear and ...

7

Machine learning can sometimes be used to create inputs into an optimisation problem. For example, we make a commercial vehicle route optimisation system for dynamic/realtime routing. Travel times between locations are an input into the optimisation algorithm. We have a module which uses machine learning to estimate travel times from historic journey data, ...

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

7

Certainly, and to take the problem's structure into account, one could model the queue knowing - or guessing - prior information about the queue's structure and/or parameter distribution and use Bayesian inference. See for example the following sources and their references: Armero, C., & Bayarri, M. J. (1994). Bayesian prediction in M/M/1 queues. ...

7

I would call them decision-relevant data, because most optimization problems in practice help people do decisions better, which they already do in a heuristic fashion. This puts the focus on the decision and what is needed to effectively make this decision. Alternatives would be system-describing data/system-boundary data, because the data defines the ...

7

I would just call it "planning data". I think it might be easier to convince an administrator that "planning data" needs to be recorded/captured than to sell them on "<insert techno-jargon phrase here> data". Administrators grasp what planning is (whether or not they are adept at doing it), and at some visceral level they ...

6

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.

6

A recent paper by Quantum Computing Inc people is showing experiments on graph partitioning where QUBO approaches lead to better results than the state of the art. Here is the paper: https://arxiv.org/pdf/2006.15067.pdf Nevertheless, one can argue that this graph partitioning problem is not in essence what we can call a real-world OR problem. But it seems ...

6

This is an interesting question. One way that I'm thinking about this question is to look at how companies are actually using the term AI. I wrote blog post arguing that AI is being used by industry as an umbrella term. And as an umbrella term, it includes deep learning, machine learning, and optimization. I didn't call it out in the blog, but Constraint ...

6

I go out on a limb and have a controversial answer: All the problems in machine learning are not optimization problems. Before you object, think twice. What about training a deep net? Isn't that an optimization problem. It sure is! But the underlying problem, i.e. the one which is the machine learning problem, is to build a deep net that is able to predict ...

6

Adhering to the rules of encapsulation, I would simply call it "parameters". If we're thinking of an optimisation model and, as you said, what changes is the number of things (number of students, number of classrooms, a table with the teachers' schedule, etc.), that's what we call usually parameters in optimisation modelling so I don't see a reason ...

6

In addition to the hyperheuristics mentioned by batwing, you can look for the broader topic of (automatic) algorithm selection and configuration. Generally speaking, algorithm selection is the task of choosing one algorithm among a set of possible ones, based on some information (features) about the problem and instance you want to solve. Configuration is ...

6

I'm going to interpret "in OR" as appearing in OR journals and/or written by people who identify as OR/MS/IE researchers. I'm a bit familiar with the intersection of optimization and statistical estimation. Machine learning, OLS and LAV regression, lasso regression etc. all rely on solving optimization problems to fit models. In addition, ...

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