DIMACS  Challenge Abstract
January 15, 1993

Maximal Satisfiability as a Maximal Constraint Satisfaction Problem

Eugene C. Freuder
Department of Computer Science 
University of New Hampshire
Durham, NH 03824
ecf@cs.unh.edu

I have only recently gotten involved in the DIMACS Challenge, so this will
be quite short, just an indication of interest really. 

I work on constraint satisfaction problems in artificial intelligence (CSPs
in AI). These involve finding values for problem variables subject to
restrictions on which combinations of values are allowed. Satisfiability,
clique finding, graph coloring, can all be viewed as CSPs (as well as AI
problems in fields like diagnosis, design, language understanding, etc.). A
general problem solving paradigm like constraint satisfaction facilitates
the development of general methods that apply to a variety of problem
domains. Attempts to apply the paradigm to specific domains may suggest new
general methods. 

I have recently been working, along with Richard Wallace, on maximal CSPs,
where the objective is to satisfy a maximal number of constraints. We have
been working with branch-and-bound-based techniques analogous to
backtrack-based CSP techniques. We would like to study MAX-SAT as a maximal
CSP. Our research plan is as follows: 

1. Generalize our techniques, which operate with binary constraints, to
handle the n-ary constraints needed to fully study MAX-SAT, and apply our
techniques to hard problems. 

2. Compare our results with the literature, especially recent AI local
search work. 

3. Look for other CSP techniques that might be particularly useful in this
domain, considering, in particular, some algorithms developed recently in
my own group. 

4. Look for new CSP techniques motivated by our experience in this domain.