My research revolves around combinatorial optimisation. This includes developing state-of-the-art algorithms for timetabling, general-purpose optimisation, and machine learning algorithms specifically designed for use with combinatorial problems. I use a variety of techniques in my work, such as constraint/integer programming, maximum Boolean satisfiability (MaxSAT), metaheuristics, and the combination thereof. I have a broad interest in my fields, both from the implementation, theoretical, and application side.

Overall, my work can be roughly divided into four main lines of work:

- General-purpose combinatorial optimisation
- Timetabling and production-planning
- Data-driven decision making: Machine learning for combinatorial problems
- Resilience for combinatorial optimisation

Below I will go into more detail for each line of work and list the relevant publications along with a brief description of each selected paper. My full list of publications can be found here.

**General-Purpose Combinatorial Optimisation**

The goal is to develop state-of-the-art algorithms for general-purpose combinatorial optimisation technology, such as constraint programming and maximum satisfiability solvers. The main idea is to specify the problem at hand in a mathematical formalism and then invoke these tools as black-boxes to provide solutions. Thus, given the flexibility of these algorithms, they can be applied to a wide range of problems.

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 computing optimal solutions over longer runtimes. The motivation stems from practical large-scale applications, where optimality search cannot be done in a reasonable time, but optimised solutions are still desired.

Selected papers:

- Solution-Based Phase Saving and Large Neighbourhood Search (CP’18)
*The aim was to improve generic optimisation algorithms by directing the optimisation algorithm to search around the best-known solution, rather than focusing on optimality. This was implemented in a state-of-the-art solver, Chuffed, and our approach greatly improved its effectiveness in providing good solutions quickly, further advancing the state-of-the-art.*

- LinSBPS (MaxSAT Evaluation 2018 Submission)
*Inspired by*previous*success, the task was to improve the performance of solvers based on the Boolean optimisation paradigm. We developed a new algorithm, which initially solves a simplified version of the problem, and gradually refines the constraints until the complete problem is solved. When combined with solution-guided search, our algorithm demonstrated excellent performance and***won**the incomplete 300 seconds track of the MaxSAT Evaluation 2018. A long detailed version of this paper will be available by February.

- Further development of LinSBPS
*We improved LinSBPS by using core-based reformulations, which is particularly effective for problems that are suitable for core extraction. The paper is under review and will be made*available*end of January.*

**Timetabling and Production-Planning**

In this line of work, I research novel algorithms which would produce high-quality timetables and plans based on input data, such as curriculum/customer requirements, in a fully automatised fashion. On an abstract level, the aim is to coordinate resources (e.g. rooms, teachers, machines) with times to fulfil 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. Designing timetables is an important and responsible task, as it can potentially affect hundreds of people for prolonged amounts of time. Therefore, developing algorithms that automatically generate high-quality timetables is of great importance.

Selected papers:

- Constraint Programming for High School Timetabling: A Scheduling-Based Model with Hot Starts (CPAIOR’18)
*We developed a new approach for high school timetabling based on the constraint programming optimisation paradigm. When compared to previous algorithms from the literature, this approach provided excellent results for short runtimes, i.e. 20 minutes. One of the employed techniques, solution-guided search, proved to be exceptionally useful and I studied it in my other publications in a more general setting.*

- MaxSAT Based Large Neighborhood Search for High School Timetabling (COR’17 journal)
*We designed an algorithm for high school timetabling that combined complete- and local-search algorithms, which previously existed as separate techniques for timetabling. The resulting algorithm was, in a sense, the best of both worlds: it harnessed the advantages of a general-purpose MaxSAT algorithm and domain-specific knowledge.*

- Modeling High School Timetabling with Bbitvectors (ANOR’17 journal)
*We encode high school timetabling using*bitvectors*. Timetabling events are represented as 32/64-bit integers and constraint violations are computed as a series bit-operations on integers, such as AND and XOR. Such a representation allows to exploiting low-level processor operations and we show that order-of-magnitude improvements can be obtained for local search algorithms.*

- Modeling High School Timetabling as Partial Weighted MaxSAT (LaSh workshop)
*We represent high school timetabling as propositional formula and use MaxSAT solvers to find solutions. This approach provides excellent results for problems where teachers are pre-allocated to lessons. A detailed version of this paper is ongoing and is expected in February.*

- Modeling and Solving an Automotive Paint Shop Scheduling Problem (PATAT’18 – Extended Abstract)
*We briefly discuss a real-life scheduling problem from the automotive industry. The problem contains several subproblems, each being an optimisation problem of its own. A more detailed version of the paper, along with solution techniques, is expected in late February.*

**Data-driven Decision Making: Machine Learning for Combinatorial Problems**

The idea is to develop machine learning algorithms that are specifically designed to be used with combinatorial problems. These algorithms are important when machine learning and optimisation must interact, for instance, when optimisation needs to be performed on data that is not entirely correct but is rather estimated with machine learning. This is becoming an increasingly common scenario as we enter the age of automation and big data. The main challenge is that conventional machine learning metrics, such as mean-square error, are not necessarily indicative for the outcome of the optimisation procedure. Ideally, the optimisation result would be used as the metric, but this gives rise to a nonlinear, noncontinuous, and nondifferentiable function. Hence, widely used techniques in machine learning, e.g. gradient descent, cannot be applied. The standard approach is to view optimisation and machine learning as two separate black-boxes, but better results can be obtained if the process is merged into a single pipeline. Thus, the aim of this research is to develop machine learning algorithms that incorporate additional optimisation-problem knowledge. Even though combinatorial optimisation and machine learning have been thoroughly studied, their interplay has yet to be understood. This is precisely what this line of work aspired to do. Furthermore, we investigate means of improving the state-of-the-art of one field by using methods from the other.

Selected papers:

- An investigation into prediction + optimisation for the knapsack problem (technical draft)
*We study the problem of solving the knapsack, a combinatorial problem, with data that is predicted with machine learning. We propose two new machine learning approaches that incorporate the optimisation objective function as a surrogate, namely a partitioning SVMRank-style approach and a simplification of an existing gradient-based approach. The results show that the problem is not easy for existing techniques, and in some cases, our methods provide better results.*

- Semi-Supervised Louvain (technical draft)
*We propose a novel algorithm for community detection where the user can specify pair-wise must- and cannot-link constraints. This was done by extending the widely used Louvain algorithm. The resulting method retains the scalability of the Louvain*algorithm,*while being able to take the constraints into account, outperforming existing semi-supervised community detection approaches.*

- Currently ongoing work
*I am developing a linear regression approach that directly optimises a ranking-style objective function, such as the one encountered in the knapsack problem. Early results are promising and I expected a finalised paper in February.*

**Resilience for Combinatorial Optimisation**

This line of work studies notions and algorithms for resilience in combinatorial optimisation, i.e. takes into account that unexpected changes might occur to the problem definition. For example, after forming a team of agents to perform a specific task, agents might fall ill, potentially rendering the team no longer functional. Therefore, it can be of crucial importance to not only solve the optimisation problem but analyse *resilience*, i.e. its recovery in the case external factors negatively impact the solution. 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, thus relating to risk management.

Selected papers:

- Recoverable Team Formation (AAMAS’18)
*We introduce the notion of resilience for the team formation (set covering) problem, defining recoverable team formation. Thus, the task is to select a subset of agents at a minimum cost, such that if k agents are rendered unavailable the remaining team can still perform the desired tasks. The paper presents an algorithm for solving the recoverable team formation problem and provides detailed proof of its computational complexity in general, which is the first kind of algorithm and theoretical result for recoverable combinatorial optimisation problems in a broader sense. Even though the problem is in the third level of the polynomial hierarchy Σ*._{3}^{P}-hard, our algorithm is still able to solve benchmarks with thousands of agents

- Robust Coalition Structure Generation (PRIMA’18)
*We introduce robustness in coalition structure generation, related to our team formation problem. As before, we provide a detailed complexity analysis (Σ*_{2}^{P}-hard) and an algorithm. In this case, the task is to partition a set of agents into coalitions, such that the utility is maximized given that k agents will fall ill.