Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

2001-01-01

Filename

WUCS-01-12.PDF

Technical Report Number

WUCS-01-12

Abstract

Many real-world problems involve constraints that cannot be all satisfied. The goal toward an overconstrained problem is to find solutions minimizing the total number of constraints violated. We call such a problem constraint minimization problem (CMP). We study the behavior of the phase transitions and backbones of CMP. We first investigate the relationship between the phase transitions of Boolean satisfiability, or precisely 3-SAT (a well-studied NP-complete decision problem), and the phase transitions of MAX 3-SAT (an NP-hard optimization problem). To bridge the gap between the easy-hard-easy phase transitions of 3-SAT, in which solutions of bounded quality, e.g., solutions with at most a constant number of constraints violated, are sufficient. We show that phase transitions are persistent in bounded 3-SAT and are similar to that of 3-SAT. We then study backbones of MAX 3-SAT, which are critically constrained variables that have fixed values in all optimal solutions. Our experimental results show that backbones of MAX 3-SAT emerge abruptly and experience sharp transitions from nonexistence when underconstrained to almost complete when overconstrained. More interestingly, the phase transitions of MAX 3-SAT backbones surprisingly concur with the phase transitions of satisfiability of 3-SAT. Specifically, the backbone of MAX 3-SAT with size 0.5 approximately collocates with the 0.5 satisfiablity of 3-SAT, and hte backbone and satisfiability seems to follow a linear correlation near this 0.5-0.5 collocation.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7QN6513

Download

Share

COinS