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


20

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


19

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


19

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


19

Regarding the paper, it's important to remember that general purpose MIP solvers are meant to be general purpose, hence it's not surprising that they can be improved by tailoring them to the test set, either using ML or some other form of automatic tuning. MIP solvers make many decisions while solving a problem and I guess it's quite natural to assume that ...


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


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


15

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


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


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


11

SCIP is not slow. SCIP's code is roughly as fast as the commercial alternatives. What makes SCIP seem slower to the user is that, by comparison, the commercial solver heuristics (cuts, primal heuristics, branching, tuning) are superior. Therefore, that paper actually makes a very sound comparison: "What if we had a machine figure out the heuristics ...


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

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


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

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


8

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


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


8

Has anyone tested this approach on a real world business problem? If the question is, more generally, "for a practical optimization problem, can ML somehow accelerate the performance of a state-of-the-art MIP solver, given that we have already solved a large number of similar instances in the past?", then the answer is yes. In the reference below, ...


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

MDP and ML: The run-time for solving Markov Decision Processes to find the optimal policy is exponentially increased when the problem size is increased. Exact methods for the large problems, most of the times, face the curse of dimensionality and failed to solve the problem in a fair amount of time. Sometimes heuristic methods can be used to find the near-...


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

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


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