My research revolves around combinatorial optimisation, both developing specialised problem-specific algorithms and general-purpose techniques. Example application domains include timetabling and production-planning. Overall, my work can be roughly divided into four main lines of work:
- General-purpose combinatorial optimisation.
- Timetabling and production-planning.
- Resilience for combinatorial optimisation.
- Machine learning and optimisation.
General-Purpose Combinatorial Optimisation
The goal is to develop state-of-the-art algorithms for general-purpose optimisation technology, such as constraint programming and maximum satisfiability solvers. Once a combinatorial problem is expressed in a specified mathematical formalism, these tools can be invoked as a black-boxes to provide solutions, making them extremely flexible and valuable. In particular, I have been working on improving the anytime performance of these solvers i.e. techniques that provide good solutions quickly, rather than focusing on proving optimality. These kinds of approaches are particularly relevant for large-scale problems where the optimum solution might not be easily found in reasonable time.
- Solution-Based Phase Saving and Large Neighbourhood Search (CP18).
- LinSBPS (MaxSAT Evaluation 2018 Submission).
Timetabling and Production-Planning
In this line of work, I aspire to research novel algorithms which would produce high-quality timetables and plans based on input data, such as curriculum/production requirements and teacher/machine availability, in fully automatised fashion. I do so by using complete optimisation paradigms, such as constraint/integer programming and maximum satisfiability, metaheuristics, and the combination thereof. On an abstract level, the aim is to coordinate resources (e.g. rooms, teachers, machines) with times to fulfill certain goals, such as scheduling lectures or designing production-plans. These problems are omnipresent in today’s society, although their precise definitions might differ from one particular application to another. It is essential to obtain the utmost best solutions, as provided schedules directly contribute to the quality of the educational system and working environment, the satisfaction of students, staff, and workers, among other things. Therefore, designing timetables is an important and responsible task, as it can potentially affect hundreds of people for prolonged amounts of time. Thus, developing algorithms that automatically generate high quality timetables is of great importance.
- Constraint Programming for High School Timetabling: A Scheduling-Based Model with Hot Starts (CPAIOR18).
- MaxSAT Based Large Neighborhood Search for High School Timetabling (COR journal).
- Modeling high school timetabling with bitvectors (ANOR journal).
Resilience for Combinatorial Optimisation
This line of work aims to define notions and algorithms to take into account that unexpected changes can occur to the problem definition. For example, after forming a team of agents to perform a specific task, agents may unexpectedly become unavailable due to failure or illness, possibly making the team no longer functional. Therefore, it can be of crucial importance to analyse how resilient a solution to external factors. The focus is on combinatorial problems and providing worst-case guarantees on the solution in the event that a certain number of variables is forced to change their values after the solution has been computed.
Machine Learning and Optimisation
These two broad fields, typically, deal with clearly distinct problems: the former aims to estimate behaviors based on large qualities of historic data, while the latter seeks to provide solutions that respects a wide-range of constraints. In this line of work, there are two directions. The first is to improve the state-of-the-art from one field using methods from the other. For example, better predictions can be obtained if additional problem knowledge, given in the form of complex constraints, is considered during the solution process. The second direction is to understand the interplay between machine learning and optimisation. As an example, one might aim to produce a schedule that minimises production-costs based on predictions of electricity prices. While viewing the prediction and optimisation steps as two independent processes, more can be gained if the two are appropriately interleaved. We coined the term predict+optimize for this kind of interaction.