The goal of the lecture is to present the latest achievements in Answer Set Programming (ASP). In particular, the focus of the lecture is on algorithms for solving optimization problems in ASP, that is, problems encoded by ASP programs with weak constraints. As usual in ASP, solutions of a problem instance are represented by its stable models, or answer sets. If the input program also comprises weak constraints, each of its stable model is associated with a cost determined by the unsatisfied weak constraints. Hence, weak constraints define a cost function, so that stable models of smaller cost are preferred.
The lecture overviews several algorithms for computing the most preferred, or optimal, stable models, and provides some details on core-guided algorithms, which proved to be effective on industrial instances of MaxSAT, the optimization variant of the satisfiability problem for propositional formulas. These algorithms work by iteratively checking satisfiability of a formula that is relaxed at each step by using the information provided by unsatisfiable cores, i.e., sets of weak constraints that cannot be jointly satisfied by any stable model of the input program.
The lecture is of the interest for both students visiting Logic Programming course as well as researchers of technical faculty working on declarative solving of hard problems.
Dr. Mario Alviano received his master degree from University of Calabria in 2007 and his PhD in 2010 from the same university. Both works were distinguished by awards: the master thesis won the “Italian best thesis in Artificial Intelligence” a prize awarded by AI*IA, the Italian Association for Artificial Intelligence and PhD thesis was one among three dissertations awarded with a honorable mention by the European Coordinating Committee for Artificial Intelligence (ECCAI). Since 2011 he worked as a post doc and then as Assistant Professor at the Department of Mathematics and Computer Science, University of Calabria. The research interests of Dr. Alviano are spread throughout the field of knowledge representation and reasoning with the main focus on theoretical background and applications of answer set programming.