IEEE SSCI 2025 tutorial

Abstract

Combinatorial optimization problems are encountered in many real-world situations and scenarios. Often, these problems are NP-hard, meaning that they cannot be solved optimally, but rather must be solved using various heuristic methods, most commonly improvement-based metaheuristics. However, for many real-world cases these improvement-based methods cannot be applied, since problems are stochastic or dynamic, and as such all the information about the problem is not available in advance, or the problems are simply too large to efficiently search the solution space, even heuristically. In those cases, constructive based heuristics usually represent the method of choice for solving such problems. Constructive based heuristics construct the solution step by step, only by determining the next decision that needs to be performed. Therefore, they can easily adapt to changes in the problem. The main issue with constructive heuristics is that they are difficult to design manually for the various problems that are encountered. For that reason, researchers have turned to the application of hyper-heuristics methods, i.e., methods that can be used not to solve the problem by themselves, but rather to generate a heuristic that can be used to solve any new problem of the type for which it was developed. Although many hyper-heuristic methods have been proposed in the literature, genetic programming has become the most popular method for that purpose. Over the years genetic programming has been used to generate heuristics for various combinatorial optimization problems, including various scheduling, routing and similar problems. Especially in recent years the research in this topic has been gaining on additional attention from the research community, with many different research directions being investigated, thus outlining the importance of this topic.

The goal of this tutorial is to provide a brief introduction into the topic of automated heuristic design with the use of generic programming. For that purpose, the tutorial will introduce genetic programming as an evolutionary computation method. After that, the application of genetic programming to the automated design of heuristics will be described, i.e., this part focuses on how genetic programming is used as a hyper-heuristic method. Here it will be outlined how the method needs to be adapted and how this problem is tackled, i.e., what steps are required to successfully apply genetic programming to generate a heuristic for a chosen combinatorial optimization problem. All of this will be done using a simple combinatorial optimization problem as a showcase. The tutorial will also present several applications of genetic programming to generate heuristics for various combinatorial optimization problems from the literature to outline the wide range applicability of the method, but also to emphasize differences and challenges encountered for various problems. The tutorial will cover some recent developments in the automatic generation of dispatching rules, as well as outline several new research directions in this field, such as multi-objective heuristic generation, application of ensemble learning methods, construction of surrogate models, etc. Finally, the current limitations and open issues of the approach will be outlined. The tutorial will help the interested researchers to acquire a good overview of this emerging and interesting research area, as well as the key ideas and challenges for future studies. Thus, the audience should gain knowledge that should help them successfully apply genetic programming to a given combinatorial optimization problem.

Tutorial schedule

The planned duration of the tutorial is 90 minutes. The outline of the tutorial is the following:

• Introduction (5 min) - introduction of the presenter, overview of the presentation and introduction and motivation for the tutorial.
• Genetic programming (15 min) - introduction to genetic programming, explanation of the most relevant concepts (representation of the individuals in the form of expression trees, crossover and mutation in genetic programming, problems like bloating). Explanation of the difference between genetic programming and genetic algorithms.
• Hyper-heuristics (35 min) - description of the application of genetic programming as a generative hyper-heuristic. A small toy problem will be used to go through all the elements that need to be performed, such as specifying the scheme for generating solutions, selecting relevant features for the problem and using them as terminals, designing the training set, etc.
• Applications (20 min) - showcase of applying genetic programming to generate heuristics for selected combinatorial optimisation problems, such as the unrelated machines environment, vehicle routing problem and the container relocation problem. Through these problems the idea is to help the audience get the intuition of how to perform the steps mentioned in the previous step.
• Limitations and recent advancements (15 min) - limitations and challenges of developing heuristics with the use of genetic programming and similar methods. Recent research directions that have been examined, such as multi-objective optimisation, ensemble learning, multitask learning, and similar.
• Conclusion (5 min) - conclusions of the tutorial and open research topics and challenges in this area.
• Questions and discussion (10 min) - time for additional questions and discussion.

Materials

The presentation and other materials will be made available prior to the tutorial presentation.