Internship - Fitness landscapes of tree-search heuristics (F/M)

Created in 2008, the Inria center at the University of Lille employs 360 people, including 305 scientists in 15 research teams. Recognized for its strong involvement in the socio-economic development of the Hauts-De-France region, the Inria center at the University of Lille maintains a close relationship with large companies and SMEs. By fostering synergies between researchers and industry, Inria contributes to the transfer of skills and expertise in the field of digital technologies, and provides access to the best of European and international research for the benefit of innovation and businesses, particularly in the region.

For over 10 years, the Inria center at the University of Lille has been at the heart of Lille's university and scientific ecosystem, as well as at the heart of Frenchtech, with a technology showroom based on avenue de Bretagne in Lille, on the EuraTechnologies site of economic excellence dedicated to information and communication technologies (ICT).

This research internship is intended for final-year Master’s students or engineering school students with an interest in combinatorial optimization, constraint programming, and stochastic (hyper-)heuristics.

The project will be carried out within the BONUS team at the Inria Center of the University of Lille, in the context of an ANR-funded project (EVARISTE) conducted in collaboration with the University of Angers. The selected student will interact regularly with the various colleagues involved in the project.

Solving a constraint decision problem consists in assigning a value to each of its variables such that all of its constraints are satisfied. Solutions are often sought using complete, non-polynomial search strategies based on tree exploration, which consists in successively considering variables and their possible values, with the observation that some branches of the search tree can be pruned as soon as they cannot lead to satisfiable solutions. The efficiency of these techniques depends heavily on the ordering heuristic that defines the structure of the search tree, whether in terms of variable ordering or the order in which values in the domains are explored. This tree-based search principle can also be generalized to the design of meta-algorithms or hyper-heuristics, where the choice of the order in which different algorithmic components are combined (e.g., search neighborhoods, branching strategies, etc.) can have a significant impact on performance.

The choice of these parameters in solvers remains largely empirical and constitutes a major obstacle to efficient solving. One line of research within the framework of the ANR EVARISTE project is to improve our ability to predict the effectiveness of an ordering heuristic based on the properties of problem instances. In this project, we will primarily focus on the analysis of ordering heuristics using the fitness landscape framework.

A fitness landscape is defined by a set of individuals X, a distance function d defining a measure of proximity between individuals, and a fitness function f that assigns a fitness value to each individual, reflecting its quality and serving as a reference for establishing a preference relation between individuals. In our simplest example, X will represent a space of variable orderings and, by extension, a space of search trees, structured by means of the distance function d. Since the space of variable orderings corresponds to the set of permutations of [n], we will consider a variety of fitness landscape structures by imposing different restrictions on [n], using different distance measures between permutations, and defining different fitness functions. These functions will serve as comparative measures between search trees and will make it possible to analyze the relationships between problem instances, heuristics, and search performance.

We will then seek to characterize good ordering heuristics with respect to the fitness functions and to interpret them. The objective is therefore to discover new solving strategies by analyzing these landscapes, which make it possible to abstract the solving mechanisms within a simpler framework.

In general, the scientific objectives are structured at three levels, which will be addressed according to the candidate's profile and progress throughout the internship.

• Definition of landscapes: This first step will establish the formal foundation of the project by abstracting the space of (hyper-)heuristics into alternative representations defined by their variable parameters. Different models for defining tree-based landscapes will allow the analysis of various correspondences between representation and evaluation. The goal is to formalize models of tree spaces based on elements defining a heuristic, and then to propose relevant fitness functions that indicate the quality of a tree.
• Analysis of order landscapes: This step will enable the characterization of meaningful heuristic descriptions with respect to the previously defined fitness functions, while incorporating the challenge of scalability. We will aim to interpret the variable orders associated with high fitness values and to comparatively study the properties of reference heuristics. Finally, we will analyze the robustness and consistency of information in sub-landscapes in order to identify relevant insights that can be extracted from partial explorations.
• Emergence of ordering heuristics: The next step will involve interpreting the correlations between problem instance properties and those of tree-search heuristics. We will use these results to infer and construct ordering heuristics, with the goal of employing them within the framework of hyper-heuristics. In addition, we will aim to develop predictive fitness functions.

Technical skills and level required : computer science, algorithms, and optimization

Languages : French and/or English

Other valued appreciated : interest in fundamental research that includes a strong experimental component.

• Subsidized meals
• Partial reimbursement of public transport costs
• Leave: the number of days off depends on the number of days the intern is actually present at the center
• Professional equipment available (videoconferencing, loan of computer equipment, etc.)

According to legal scale: 4.50€ / hour