Venue

On November 27, 2023, 14:00-16:00:
FAV Hörsaal 3 Zemanek
TU Wien, Faculty of Informatics
1040 Vienna, Favoritenstraße 9-11

On November 28, 2023, 10:00-12:00:
Seminarraum FAV EG B von Neumann
TU Wien, Faculty of Informatics
1040 Vienna, Favoritenstraße 9-11

Program

Monday, November 27, 2023, 14:00-16:00

Location: FAV Hörsaal 3 Zemanek, 1st Floor, TU Wien, Faculty of Informatics

• Antti Kuusisto and Tomi Janhunen: Explaining with Short Boolean Formulas in Practice

Abstract: In this work, we investigate explainability in terms of short Boolean formulas in the context of data models based on unary relations. An explanation is a Boolean formula (of length k) that minimizes error with respect to a target attribute being explained. On the theoretical side, we provide novel quantitative bounds on expected error in this scenario. Besides this, we also demonstrate explanations in practice by studying three concrete data sets. For each set, we discover explanation formulas of different lengths using an encoding in Answer Set Programming. The most accurate formulas achieve errors similar to other machine learning methods on the same data sets. Due to potential overfitting, however, these formulas are not ideal as explanations, so we use a cross validation scheme to figure out a suitable length for explanations. By limiting to shorter formulas, it is possible to avoid overfitting while the respective explanations are still reasonably accurate and also, most importantly, human interpretable by nature. This talk is based on joint work with Reijo Jaakkola, Masood F. Rankooh, and Miikka Vilander.

• Masood F. Rankooh: Pruning Redundancy in Answer Set Optimization Applied to Preventive Maintenance Scheduling

Abstract: Multi-component machines deployed, e.g., in paper and steel industries, have complex physical and functional dependencies between their components. This profoundly affects how they are maintained and motivates the use of logic-based optimization methods for scheduling preventive maintenance actions. Recently, an abstraction of maintenance costs, called miscoverage, has been proposed as an objective function for the preventive maintenance scheduling (PMS) of such machines. Since the minimization of miscoverage has turned out to be a computationally demanding task, the current paper studies ways to improve its efficiency. Given different answer set optimization encodings of the PMS problem, we motivate constraints that prune away some sub-optimal and otherwise redundant or invalid schedules from the search space. Our experimental results show that these constraints may enable up to ten-fold speed-ups in scheduling times, thus pushing the frontier of practically solvable PMS problem instances to longer timelines and larger machines.

Tuesday, November 28, 2023, 10:00-12:00

Location: Seminarraum FAV EG B von Neumann, 1st Floor, TU Wien, Faculty of Informatics

• Tomi Janhunen: Generalizing Level Ranking Constraints for Monotone and Convex Aggregates

Abstract: In answer set programming (ASP), answer sets capture solutions to search problems of interest and thus the efficient computation of answer sets is of utmost importance. One viable implementation strategy is provided by translation-based ASP where logic programs are translated into other KR formalisms such as Boolean satisfiability (SAT), SAT modulo theories (SMT), and mixed-integer programming (MIP). Consequently, existing solvers can be harnessed for the computation of answer sets. Many of the existing translations rely on program completion and level rankings to capture the minimality of answer sets and default negation properly. In this work, we take level ranking constraints into reconsideration, aiming at their generalizations to cover aggregate-based extensions of ASP in a more systematic way. By applying a number of program transformations, ranking constraints can be rewritten in a general form that preserves the structure of monotone and convex aggregates and thus offers a uniform basis for their incorporation into translation-based ASP. The results open up new possibilities for the implementation of translators and solver pipelines in practice.

• Antti Kuusisto: Descriptive Complexity for Distributed Computing with Circuits

Abstract: We consider distributed algorithms in the realistic scenario where distributed message passing is operated by circuits. We show that within this setting, modal substitution calculus MSC precisely captures the expressive power of circuits. The result is established via constructing translations that are highly efficient in relation to size. We also observe that the coloring algorithm based on Cole-Vishkin can be specified by logarithmic size programs (and thus also logarithmic size circuits) in the bounded-degree scenario.

Supporters

This workshop is supported by ZIF.

ZIF