MCS Extraction with Sublinear Oracle Queries

Carlos Mencía, Alexey Ignatiev, Alessandro Previti, Joao Marques-Silva:
MCS Extraction with Sublinear Oracle Queries. SAT 2016: 342-360

Abstract. Given an inconsistent set of constraints, an often studied problem is to compute an irreducible subset of the constraints which, if relaxed, enable the remaining constraints to be consistent. In the case of unsatisfiable propositional formulas in conjunctive normal form, such irreducible sets of constraints are referred to as Minimal Correction Subsets (MCSes). MCSes find a growing number of applications, including the approximation of maximum satisfiability and as an intermediate step in the enumeration of minimal unsatisfiability. A number of efficient algorithms have been proposed in recent years, which exploit a wide range of insights into the MCS extraction problem. One open question is to find the best worst-case number of calls to a SAT oracle, when the calls to the oracle are kept simple, and given reasonable definitions of simple SAT oracle calls. This paper develops novel algorithms for computing MCSes which, in specific settings, are guaranteed to require asymptotically fewer than linear calls to a SAT oracle, where the oracle calls can be viewed as simple. The experimental results, obtained on existing problem instances, demonstrate that the new algorithms contribute to improving the state of the art.

Relating as it does to explanation, this is a timely citation. The authors have made numerous contributions to this area.

The citation is to:

Barry O’Callaghan, Barry O’Sullivan, Eugene C. Freuder: Generating Corrective Explanations for Interactive Constraint Satisfaction. CP 2005: 445-459

Interactive tasks such as online configuration and e-commerce can be modelled as constraint satisfaction problems (CSPs). These can be solved interactively by a user assigning values to variables. The user may require advice and explanations from a system to help him/her find a satisfactory solution. Explanations of failure in constraint programming tend to focus on conflict. However, what is really desirable is an explanation that is corrective in the sense that it provides the basis for moving forward in the problem-solving process. More specifically, when faced with a dead-end, or when a desirable value has been removed from a domain, we need to compute alternative assignments for a subset of the assigned variables that enables the user to move forward. This paper defines this notion of corrective explanation, and proposes an algorithm to generate such explanations. The approach is shown to perform well on both real-world configuration benchmarks and randomly generated problems.

Constraint Programming and Artificial Intelligence Workshop

I have organized a Constraint Programming and Artificial Intelligence Workshop for the Constraint Programming conference in Toulouse in September 2016. The schedule and the submissions are online at the above link.

“From their early days, Constraint Programming has played an important role in Artificial Intelligence, and Artificial Intelligence has played an important role in Constraint Programming. Artificial Intelligence is currently experiencing a great surge of interest, attention and funding. This workshop is intended to encourage efforts to increase the participation and visibility at this time of Constraint Programming in the wider AI community, to the mutual benefit of both. In particular, the Workshop will seek to formulate specific recommendations as to actions that members of the community might undertake, individually, or collectively through the ACP, to further identified objectives. As a start, it is hoped that participants at the Workshop will volunteer to take on specific roles that are deemed useful for achieving these objectives.”

The Talk is an Advertisement for the Paper

Many people seem to believe that it is important to fit as much of the content of a conference paper into the conference talk as possible. In order to do so, they speakveryfast. This is rather like believing that the purpose of a movie trailer is to show as much of the movie as possible, and so running the trailer at double speed.

The dirty little secret is that no one in the audience is likely to remember more than the key idea of your talk a week after the conference (or perhaps even an hour after the talk), and if you try to fit too much in, they may miss that key idea. Be honest now, what do recall of the third talk in the fifth session that you attended at your last conference? However, if you get that key idea across effectively enough, your audience just might be motivated to go and read your paper.

People who speed up their talks to fit more in, and use very small fonts to squeeze as much as possible onto each slide, generally are too busy preparing all that material to stop and time their talk before presenting it. As a result they express surprise and bewilderment on the day when told that they have only 2 minutes left, with 20 slides — oh my gosh, my most important slides — left to go. At this point they begin speaking very fast. And when told that their time is up, since they are still not through their slides, they feel impelled to keep on going. At the very least they must present their conclusion. After all, the audience has to hear this.

The members of the audience, who gave up chasing after the speaker and squinting at the slides about 90 seconds in to the talk, but who have been waiting politely to clap at the end, upon realizing that the talk isn’t going to end, are likely to be so busy swearing under their breath that the speaker could give away the secret of life at that point and it would not be noticed.

So remember, less is more. If you can just convince your audience that your paper is worth reading, your talk will have been a great success.