CEC 2021 Tutorial

Title: Metaheuristics for NP-hard Combinatorial Problems

Name of the Speaker: Dr. Malek Mouhoub

Affiliation of the Speaker: Dept. of Computer Science, Univ. of Regina, Canada

Website: www.cs.uregina.ca/~mouhoubm

Duration: 120 min (including 15 minutes Q&A)

Tutorial Level: Introductory

Abstract

Combinatorial problems refer to those applications where we either look for the existence of a consistent scenario satisfying a set of constraints (decision problem), or for one or more good/best solutions meeting a set of requirements while optimizing some objectives (optimization problem). These latter objectives include user's preferences that reflect desires and choices that need to be satisfied as much as possible. Moreover, constraints and objectives (in the case of an optimization problem) often come with uncertainty due to lack of knowledge, missing information, or variability caused by events, which are under nature's control. Finally, in some applications such as timetabling, urban planning and robot motion planning, these constraints and objectives can be temporal, spatial or both. In this latter case, we are dealing with entities occupying a given position in time and space.

Because of the importance of these problems in so many fields, a wide variety of techniques and programming languages from artificial intelligence, computational logic, operations research and discrete mathematics, are being developed to tackle problems of this kind. While these tools have provided very promising results at both the representation and the reasoning levels, they are still impractical to dealing with many real-world applications, especially given the challenges we listed above.

In this tutorial, we will show how to apply metaheuristics, including nature-inspired techniques, in order to overcome these limitations. This requires dealing with different aspects of uncertainty, change, preferences and spatio-temporal information. The approach that we will adopt is based on the Constraint Satisfaction Problem (CSP) paradigm and its variants.

Biography of the Speaker

Dr. Malek Mouhoub obtained his MSc and PhD in Computer Science from the University of Nancy in France. He is currently Professor and was the Head of the Department of Computer Science at the University of Regina, in Canada. Dr. Mouhoub's research interests include Constraint Solving, Metaheuristics and Nature-Inspired Techniques, Spatial and Temporal Reasoning, Preference Reasoning, Constraint and Preference Learning, with applications to Scheduling and Planning, E-commerce, Online Auctions, Vehicle Routing and Geographic Information Systems (GIS). Dr. Mouhoub's research is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), the Canada Foundation for Innovation (CFI), and the Mathematics of Information Technology and Complex Systems (MITACS) federal grants, in addition to several other funds and awards.

Dr. Mouhoub is the past treasurer and member of the executive of the Canadian Artificial Intelligence Association / Association pour l'intelligence artificielle au Canada (CAIAC). CAIAC is the oldest national Artificial Intelligence association in the world. It is the official arm of the Association for the Advancement of Artificial Intelligence (AAAI) in Canada.

Dr. Mouhoub was the program co-chair for the 30th Canadian Conference on Artificial Intelligence (AI 2017), the 31st International Conference on Industrial, Engineering & Other Applications of Applied Intelligent Systems (IEA/AIE 2018) and the IFIP International Conference on Computational Intelligence and Its Applications (IFIP CIIA 2018).