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. The ACP is the primary international representative association in the central research area of constraint programming.
The ACP award committee stated 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[.]
“I am very happy and honoured for the recognition and would like to express my sincerest gratitude to the ACP for this award. Additionally, I would like to thank my PhD supervisor Matti Järvisalo and the Doctoral Programme in Computer Science, as well as all of my collaborators; working with all of you has been very rewarding”, Berg states.
Constraint programming is a major research area in computer science and artificial intelligence. Constraint programming studies and develops generic problem-solving techniques through declarative means. Its applications vary 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 also a critical core technology that enables automatically and efficiently solving hard search and optimization problems underlying real-world and industrial settings at large.
Novel MaxSAT-based approaches
Berg’s thesis is based on research done in the Constraint Reasoning and Optimization at the 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 successful applications of MaxSAT in vast numbers of real-world problem domains, often surpassing alternative algorithmic solutions in efficiency.
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 been published at top peer-reviewed international venues, including Artificial Intelligence Journal and the IJCAI, AISTATS, ECAI, and CP conferences.
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.