Jeremias Berg of the Constraint Reasoning and Optimization Group has been awarded the 2020 Doctoral Research Award of the Association for Constraint Programming (ACP) for his PhD thesis Solving Optimization Problems via Maximum Satisfiability: Encodings and Re-Encodings.
Constraint programming in itself is a major research area in computer science and artificial intelligence, studying and developing generic problem solving techniques through declarative means. Indeed, from e.g. formal verification of safety-critical hardware and software systems to optimizing the use of natural, human and financial resources in various real-world settings, constraint solving is a critical core technology that enables automatically and efficiently solving hard search and optimization problems underlying real-world and industrial settings at large. The ACP Doctoral Research Award, with ACP being the primary international representative association in the central research of area of constraint programming, is awarded annually to a promising young researcher working in the area of constraint programming and who defended his/her thesis within the previous two years.
The thesis, supervised by Associate Professor Matti Järvisalo, is based on research done in the Constraint Reasoning and Optimization at University of Helsinki under funding from DoCS Doctoral Programme in Computer Science within the DoNaSci Doctoral School in Natural Sciences. Earlier, Berg won the 2018 University of Helsinki Doctoral Dissertation Award for the thesis.
Berg's thesis is centered around practical solving methods for the rising Boolean optimization paradigm of maximum satisfiability (MaxSAT for short) and their applications. Building on the extraordinary success of Boolean satisfiability (SAT) as a generic tool for solving NP-hard decisions and search problems, rapid progress in increasing effective MaxSAT solving techniques has recently resulted in a successful applications of MaxSAT in vast numbers of real-world problem domains, often surpassing in efficiency of alternative algorithmic solutions.
With his thesis, Berg contributes to this progress by advancing the theory and practice of preprocessing in the context of MaxSAT, and presents novel MaxSAT-based approaches for the exact solution of two relevant computational problems stemming from the field of machine learning and data analysis. The contributions presented in the thesis have already been published at top peer-reviewed international venues, including Artificial Intelligence Journal and the IJCAI, AISTATS, ECAI, and CP conferences.
Quoting the ACP award committee's statement on Berg's winning thesis:
The thesis brings substantial improvements to the state of the art in MaxSAT solving with both theoretical and practical contributions, ranging from preprocessing solving techniques to encodings for specific relevant application problems.[...]
As well as impressive papers arising from his thesis, he has additional papers as first author and as a co-author before obtaining his PhD. He developed several open-source software and MaxSAT benchmark sets that are openly available to the community[.]
Berg gives an invited award talk at CP 2020, the main international conference on constraint programming, on September 11.
Currently Berg continues his research as a postdoc in the Constraint Reasoning and Optimization group at University of Helsinki and Helsinki Institute for Information Technology HIIT after extended postdoctoral visits to University of Melbourne, Australia and University of Toronto, Canada.