Sub-SAT: A formulation for relaxed Boolean satisfiability with applications in routing

Hui Xu, Robin A Rutenbar, Karem Sakallah

Research output: Contribution to conferencePaperpeer-review


Advances in methods for solving Boolean satisfiability (SAT) for large problems have motivated recent attempts to recast physical design problems as Boolean SAT problems. One persistent criticism of these approaches is their inability to supply partial solutions, i.e, to satisfy most but not all of the constraints cast in the SAT style. In this paper we present a formulation for "subset satisfiable" Boolean SAT: we transform a "strict" SAT problem with N constraints into a new, "relaxed" SAT problem which is satisfiable just if not more than k≪N of these constraints cannot be satisfied in the original problem. We describe a transformation based on explicit thresholding and counting for the necessary SAT relaxation. Examples from FPGA routing show how we can determine efficiently when we can satisfy "almost all" of our geometric constraints.

Original languageEnglish (US)
Number of pages6
StatePublished - 2002
EventISPD-2002: International Symposium on Physical Design - Del Mar, CA, United States
Duration: Apr 7 2002Apr 10 2002


OtherISPD-2002: International Symposium on Physical Design
Country/TerritoryUnited States
CityDel Mar, CA


  • Algorithms

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Sub-SAT: A formulation for relaxed Boolean satisfiability with applications in routing'. Together they form a unique fingerprint.

Cite this