Solving covering problems using LPR-based lower bounds

Unate and binate covering problems are a subclass of general integer linear programming problems with which several problems in logic synthesis, such as two-level logic minimization and technology mapping, are formulated. Pre vious branch-and-bound methods for solving these problems exactly use lower bounding techniques based on finding maximal independent sets, In this pap er, we examine lower bounding techniques based on linear programming relaxa tion (LPR) for the covering problem. We show that a combination of traditio nal reductions (essentiality and dominance) and incremental computation of LPR-based lower bounds can exactly solve difficult covering problems orders of magnitude faster than traditional methods.