Skip to search boxSkip to navigationSkip to main content

Enumerating infeasibility: Finding multiple MUSes quickly

  • Mark H. Liffiton
    ,
  • Ammar Malik
Scholarship:
Chapter in Book/Report/Conference proceeding
Conference contribution
Research

Abstract

Methods for analyzing infeasible constraint sets have proliferated in the past decade, commonly focused on finding maximal satisfiable subsets (MSSes) or minimal unsatisfiable subsets (MUSes). Most common are methods for producing a single such subset (one MSS or one MUS), while a few algorithms have been presented for enumerating all of the interesting subsets of a constraint set. In the case of enumerating MUSes, the existing algorithms all fall short of the best methods for producing a single MUS; that is, none come close to the ideals of 1) producing the first output as quickly as a state-of-the-art single-MUS algorithm and 2) finding each successive MUS after a similar delay. In this work, we present a novel algorithm, applicable to any type of constraint system, that enumerates MUSes in this fashion. In fact, it is structured such that one can easily "plug in" any new single-MUS algorithm as a black box to immediately match advances in that area. We perform a detailed experimental analysis of the new algorithm's performance relative to existing MUS enumeration algorithms, and we show that it avoids some severe intractability issues encountered by the others while outperforming them in the task of quickly enumerating MUSes.

Scholarship

Output type

Scholarship:
Chapter in Book/Report/Conference proceeding
Conference contribution
Research

Original language

English

Pages from-to (Number of pages)

Pages 160-175 (16 pages)

Publication milestones

  • Published - 2013

Publication status

Published - 2013

Publication series

  • Publication series name: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    ISSN (Print): 0302-9743
    ISSN (Electronic): 1611-3349
    Volume: 7874 LNCS
9783642381706

Publication IDs

  • Scopus: 84879924242

Host publication title

Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems - 10th International Conference, CPAIOR 2013, Proceedings