Affordable Access

Search Pruning Conditions for Boolean Optimization

Authors
Publication Date
Disciplines
  • Computer Science

Abstract

main.dvi Search Pruning Conditions for Boolean Optimization Vasco M. Manquinho Joa˜o Marques-Silva [email protected] [email protected] Polytechnical Institute of Portalegre Technical University of Lisbon, INESC/CEL Portalegre, Portugal Lisbon, Portugal Abstract. This paper proposes new algorithms for the Binate Covering Prob- lem (BCP), a well-known restriction of Boolean Optimization. Binate Covering finds application in many areas of Computer Science and Engineering. In Artificial Intelligence, BCP can be used for comput- ing minimum-size prime implicants of Boolean functions, of interest in Automated Reasoning and Non-Monotonic Reasoning. Moreover, Binate Covering is an essential modeling tool in Electronic Design Automation. The objectives of the paper are to briefly review branch- and-bound algorithms for BCP, to describe how to apply backtrack search pruning techniques from the Boolean Satisfiability (SAT) do- main to BCP, and to illustrate how to strengthen those pruning tech- niques by exploiting the actual formulation of BCP. Experimental results, obtained on representative instances indicate that the pro- posed techniques provide significant performance gains for different classes of instances. 1 Introduction The generic Boolean Optimization problem as well as several of its restrictions are well-known computationally hard problems, widely used as modeling tools in Computer Science and Engineering. These problems have been the subject of extensive research work in the past (see for example [1]). In this paper we address the Binate Cover- ing Problem (BCP), one of the restrictions of Boolean Optimization. BCP can be formulated as the problem of finding a satisfying assign- ment for a given Conjunctive Normal Form (CNF) formula subject to minimizing a given cost function. As with generic Boolean Op- timization, BCP also finds many applications, including the compu- tation of minimum-size prime implicants, of interest in Automated Reasoning and Non-Monotonic Reasoning [12], and as

There are no comments yet on this publication. Be the first to share your thoughts.