Discrete Modeling, Optimization, and search using Answer Set Programming

Bart Bogaerts
Course description
Course Content:
  • In this course, we study the basic principles of knowledge representation and reasoning and apply them to the field of Answer Set Programming (ASP).
    We study the theoretical foundations underlying Answer Set Programming as a paradigm for solving NP-hard problems. We learn how to encode problems arising in various domains as answer set programs, and how to optimize problem encodings using heuristics, preferences, and multi-shot solving. Furthermore, we study modern grounding and solving techniques used in ASP and beyond, such as bottom-up grounding, semi-naive grounding, conflict-driven clause learning (from Boolean SATisfiability), and lazy clause generation (from constraint programming).

    This course is complementary to the course Declarative Programming.

    While Declarative Programming focuses on practical aspects of logic programming, we focus on a declarative semantics for them and how to model problem domains. Furthermore, we study search techniques that are used under the hood of modern logic programming systems, while in Declarative Programming, you learn how to write logic programs from a practical perspective.

    These two courses can be taken in any order.

Learning Outcomes:
  • Students obtain knowledge about the stable semantic of logic programs and how it can be used to encode NP-complete problems
  • Students obtain knowledge about modern search techniques
  • Students become skilled in modeling a problem domain as an answer set program
The corresponding competences:
  • w.r.t. knowledge:
    The student knows the basic principles of knowledge representation and reasoning and knows (characterizations of) the stable semantics of logic programs. They know the working of ASP systems and modern search techniques for SAT, ASP, and constraint solving, including conflict-driven clause learning, unfounded set propagation, lazy grounding, and lazy clause generation.
  • w.r.t. applying knowledge:The student can model a given problem in a given vocabulary and optimize their model towards the performance of the underlying system. The student can transfer modern search techniques to fields beyond what is studied in this course.
  • w.r.t. analyzingThe student can analyze a problem domain and critically evaluate whether the problems arising in the domain in question can be tackled using ASP. If yes, they can devise a suitable vocabulary.
  • w.r.t. evaluatingThe student can analyze the performance of an answer set solver on a given answer set program and can identify where the bottlenecks are.
  • w.r.t. creatingThe student can create declarative models of a given problem domain.

All detailed and official information about the course here >