Learning for Optimizing (Metaheuristics and Machine Learning for Combinatorial Optimization)
Model-Driven AI
Aim
The aim is to provide approaches where problems of combinatorial optimization are solved using metaheuristics and machine learning techniques (either by combining metaheuristics and machine learning to solve the same problem or by using them in a workflow where each one solves different parts of a larger problem).
What's at stake
Operations Research (OR) is a field of study concerned with optimization problems related to route planning, scheduling, supply chain management, manufacturing, etc. occurring in many sectors, such as logistics, industry, energy, mobility, telecommunication, and healthcare. Generally speaking, an optimization problem consists in finding a combination of decision variables that is:
- Optimal according to a certain cost measure
- Feasible, in the sense that it satisfies a given number of constraints.
The sheer number of possible combinations that can form a solution makes brute force approaches wildly impractical, which is why a lot of effort has been dedicated to developing efficient methodologies in the past several decades. Aside from exact methods, which are concerned with obtaining the optimal solution of a given problem, heuristic approaches have been proposed to find solutions of good enough quality for a given situation in a relatively short time. These methods range from problem-specific construction and improvement methods to problem-independent algorithms that only require specific components in order to be applied to a given scenario (which are called metaheuristics).
Machine learning (ML) is a field devoted to solving a wide class of problems that are not only difficult to solve but also to explicitly define (computer vision, speech recognition, recommendation systems, etc.) by developing methods that rely on existing data to first learn a model and subsequently propose a solution, instead of a classic algorithm that works on a user-defined model.
Conceptually, heuristics and ML methods propose a similar approach for building solutions to optimization problems: starting from experiences from real world situations, one attempts to devise a solving method where shortcuts are exploited to accelerate identifying an approximate solution quickly enough with a sufficient optimality. The main difference consists in whether the underlying model is developed manually or automatically derived from the data, therefore solutions methods typically limit themselves to one of these two approaches. Recently however, researchers have been interested in mixing these approaches into hybrid ones to accelerate search procedures.
Being able to deliver high-quality solutions for hard problems faced in logistics, industry, energy, mobility, telecommunication, healthcare and other sectors as efficiently as possible is crucial for the successful operations of these sectors. In particular, achieving the European Green Deal objectives to be carbon neutral in 2050 demands this efficiency for many of these sectors, given its emission requirements and the clear need to replace existing practices. Hence, techniques built from heuristics and ML suggest an interesting research direction.
Challenge(s)
Research on hybrid approaches is still at an early stage, and one major reason is that the OR and ML communities do not collaborate extensively yet. A main focus of OR practitioners, both in academia and industry, is in accurately defining models for a given problem before either developing a heuristic solving method or adapting a metaheuristic to the problem. On the other hand, applying ML methodologies requires considerably shifting the focus on data, both for training and validation. Because of this, while ML has gained widespread acceptance for solving very specific problems that are hard to model but for which it is easy to provide large amounts of data, when ML models are proposed as solutions to more general situations, the lack of explainability of certain ML models often raises questions from real world users. Proposing hybrid approaches could help lift the opacity resulting in explainable AI solutions.
The first non-technical challenge is to increase the level of collaboration among these communities. From a technical point of view, solutions are sought for:
- Optimizing complex problems that require making simultaneously different types of decisions, such as routing, scheduling and location.
- Providing explainable solutions to complex problems.
- Optimizing problems with uncertainty, particularly when little real-world data is available.
AI possible solution(s)
(Among many others to be proposed by researchers)
- Applying supervised or reinforcement learning to accelerate a component of a metaheuristic procedure
- Exploiting ML to identify the most suitable heuristic to use as search strategies for a given problem
Key AI tech topics
- Machine Learning
- Supervised Learning
- Reinforcement Learning
Get in Touch
- Stefano Michelini (stefano.michelini@cetic.be)
- Renaud De Landtsheer (renaud.delandtsheer@cetic.be)