MIAO Talk by Matti Järvisalo and Jeremias Berg
The implicit hitting set approach and its instantiation for pseudo-Boolean optimization
(Matti Järvisalo and Jeremias Berg, University of Helsinki)
The so-called implicit hitting set (IHS) approach offers a generic framework for developing practical algorithms for solving various types of optimization problems, the decision problems counterparts of which are NP-complete or presumable even harder. With firm fundamental basis in so-called hitting set duality, successful instantiations for IHS have been developed for a range of computationally hard problems, including different declarative optimization paradigms (including MaxSAT, MaxSMT, answer set optimization, finite-domain constraint optimization) as well as for various specific problems setting (including causal discovery, inconsistency analysis in (quantified) propositional logic, and propositional abduction among others), by making use of state-of-the-art integer programming systems and declarative approaches to inconsistency analysis.
The goals of this two-part talk are to (1) provide a generic introduction to IHS with a high-level survey on its successful applications, and to (2) describe in more detail a recently-developed practical IHS-instantiation in the realm of pseudo-Boolean optimization (PBO, aka 0-1 integer linear programming).
The second part of the talk is based on:
- Pavel Smirnov, Jeremias Berg, Matti Järvisalo: Improvements to the Implicit Hitting Set Approach to Pseudo-Boolean Optimization. SAT 2022.
- Pavel Smirnov, Jeremias Berg, Matti Järvisalo: Pseudo-Boolean Optimization by Implicit Hitting Sets. CP 2021.
MIAO seminars:
We will run this as a hybrid seminar at the University of Copenhagen. Local participants are warmly welcome on UCPH campus --- the exact location will be communicated later. Other participants are equally warmly welcome to join virtually at https://lu-se.zoom.us/j/61925271827 . Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://youtube.com/@MIAOresearch for people who would like to hear the talk but cannot attend.
Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners a self-contained overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)
More information about upcoming MIAO seminars can be found at http://www.jakobnordstrom.se/miao-seminars/ . In particular, on Monday November 28 we have a ca-2-hour tutorial on the latest advances in provably correct combinatorial optimization by a trio of speakers including yours truly, and on Thursday December 1 we have the pleasure of welcoming Srikanth Srinivasan from Aarhus University. If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn@di.ku.dk.