Answer set optimization

TLDR

Answer set optimization programs consist of a generating component that produces candidate solutions and a preference component that orders them. The paper investigates combining answer set programming with qualitative optimization, discusses applications, presents complexity results, proposes implementation techniques, and examines links to CP‑networks. The authors construct ASO programs where a generating program yields answer sets and a preference program induces a preference relation based on rule satisfaction, and they analyze the resulting complexity, implementation, and relation to CP‑networks.

Abstract

We investigate the combination of answer set programming and qualitative optimization techniques. Answer set optimization programs (ASO programs) have two parts. The generating program Pgen produces answer sets representing possible solutions. The preference program Ppref expresses user preferences. It induces a preference relation on the answer sets of Pgen based on the degree to which rules are satisfied. We discuss possible applications of ASO programming, give complexity results and propose implementation techniques. We also analyze the relationship between ASO programs and CP-networks.