Write a Blog >>
Wed 20 Jan 2016 14:20 - 14:45 at Grand Bay North - Track 1: Decision Procedures Chair(s): Loris D'Antoni

We propose a new optimization problem “Q-MaxSAT”, an extension of the well-known Maximum Satisfiability or MaxSAT problem. In contrast to MaxSAT, which aims to find an assignment to all variables in the formula, Q-MaxSAT computes an assignment to a desired subset of variables (or queries) in the formula. Indeed, many problems in diverse domains such as program reasoning, information retrieval, and mathematical optimization can be naturally encoded as Q-MaxSAT instances. Being query-guided allows us to focus on the subproblem relevant to the queries, therefore greatly improving efficiency. We describe an iterative algorithm for solving Q-MaxSAT. In each iteration, the algorithm solves a subproblem that is relevant to the queries, and applies a novel technique to check whether the partial assignment found is a solution to the Q-MaxSAT problem. If the check fails, the algorithm grows the subproblem with a new set of clauses identified as relevant to the queries. Our empirical evaluation shows that our Q-MaxSAT solver Pilot achieves significant improvements in runtime and memory consumption over conventional MaxSAT solvers on several Q-MaxSAT instances generated from real-world problems in program analysis and information retrieval.

Poster For "Query-Guided Maximum Satisfiability" (popl16.pdf)580KiB

Wed 20 Jan

14:20 - 16:00: Research Papers - Track 1: Decision Procedures at Grand Bay North
Chair(s): Loris D'AntoniUniversity of Pennsylvania
POPL-2016-papers14:20 - 14:45
Xin ZhangGeorgia Tech, Ravi MangalGeorgia Institute of Technology, Aditya NoriMicrosoft Research, UK, Mayur NaikGeorgia Tech
File Attached
POPL-2016-papers14:45 - 15:10
Anthony Widjaja LinYale-NUS College, Singapore, Pablo BarceloUniversity of Chile, Chile
Media Attached
POPL-2016-papers15:10 - 15:35
Luca CardelliMicrosoft Research and University of Oxford, Mirco TribastoneIMT Institute for Advanced Studies Lucca, Italy, Max TschaikowskiIMT Institute for Advanced Studies Lucca, Italy, Andrea VandinIMT Institute for Advanced Studies Lucca, Italy
Media Attached
POPL-2016-papers15:35 - 16:00
Matthew HagueRoyal Holloway University of London, UK, Jonathan KochemsDepartment of Computer Science, University of Oxford, C.-H. Luke OngUniversity of Oxford, UK
Media Attached