The Constraint Reasoning and Optimization group contributes to ECAI 2020 with four papers:
- Preprocessing in Incomplete MaxSAT Solving by Marcus Leivo, Jeremias Berg, and Matti Järvisalo, focusing the recent direction in maximum satisfiability (MaxSAT) research of developing incomplete solvers, studies the effects of preprocessing on the relative perceived costs of non-optimal solutions, shows that employing central preprocessing techniques misleads MaxSAT solvers in terms of their interpretation of the costs of non-optimal solutions seen during search, and proposes novel ideas for circumventing these negative effects in the context of stochastic local search algorithms for MaxSAT.
- Learning Chordal Markov Networks via Stochastic Local Search by Kari Rantanen, Antti Hyttinen, and Matti Järvisalo presents a novel stochastic local search (SLS) approach for the computationally hard task of finding a chordal Markov network structure that maximizes a given scoring function (CMSL for short). In practice, using only a fraction of the running times of the exact approaches, the SLS approach provides optimal or very close to optimal solutions for instance sizes that are within the reach of exact algorithms. Furthermore, an on-the-fly clique score computation approach circumvents issues in scaling up the approach towards hundreds of variables.
- Algorithms for Dynamic Argumentation Frameworks: An Incremental SAT-Based Approach by Andreas Niskanen and Matti Järvisalo presents an efficient Boolean satisfiability (SAT) based approach to reasoning over dy- namic argumentation frameworks, covering all of the reasoning tasks—credulous and skeptical acceptance, as well as the computation of a single and all extensions—and semantics—complete, preferred, stable, and grounded—constituting the ICCMA 2019 dynamic track based on employing incremental SAT solving. An implementation of the approach is highly competitive in practice.
- Strong Refinements for Hard Problems in Argumentation Dynamics by Andreas Niskanen and Matti Järvisalo proposes ways of extending the scalability of computational approaches to reasoning about dynamics of abstract argumentation frameworks, focusing on three recently proposed optimization problems underlying AF dynamics— two variants of enforcement in abstract argumentation and the synthesis of argumentation frameworks from examples—for semantics under which the problems are presumably complete for the second level of the polynomial hierarchy. By bridging recent theoretical results on the persistence of extensions under changes to the structure of AFs with Boolean satisfiability (SAT) counterexample-guided abstraction refinement algorithms, the scalability of state-of-the-art practical algorithms for each of the three problems can be significantly improved.