Generic ILP versus specialized 0-1 ILP: an update

• Main Authors: Aloul, F.A., Ramani, A., Markov, I.L., Sakallah, K.A.
• Format: Conference Proceeding
• Language: English
• Subjects: Application software; Boolean functions; Constraint optimization; Data structures; Design optimization; Electronic design automation and methodology; Field programmable gate arrays; Hardware; Integer linear programming; Routing
• ISSN: 1092-3152; 1558-2434
• DOI: 10.1109/ICCAD.2002.1167571

Optimized solvers for the Boolean Satisfiability (SAT) problem have many applications in areas such as hardware and software verification, FPGA routing, planning, etc. Further uses are complicated by the need to express "counting constraints" in conjunctive normal form (CNF). Expressing such constraints by pure CNF leads to more complex SAT instances. Alternatively, those constraints can be handled by Integer Linear Programming (ILP), but generic ILP solvers may ignore the Boolean nature of 0-1 variables. Therefore specialized 0-1 ILP solvers extend SAT solvers to handle these so-called "pseudo-Boolean" constraints. This work provides an update on the on-going competition between generic ILP techniques and specialized 0-1 ILP techniques. To make a fair comparison, we generalize recent ideas for fast SAT-solving to more general 0-1 ILP problems that may include counting constraints and optimization. Another aspect of our comparison is evaluation on 0-1 ILP benchmarks that originate in Electronic Design Automation (EDA), but that cannot be directly solved by a SAT solver. Specifically, we solve instances of the Max-SAT and Max-ONEs optimization problems which seek to maximize the number of satisfied clauses and the "true" values over all satisfying assignments, respectively. Those problems have straightforward applications to SAT-based routing and are additionally important due to reductions from Max-Cut, Max-Clique, and Min Vertex Cover. Our experimental results show that specialized 0-1 techniques tend to outperform generic ILP techniques on Boolean optimization problems as well as on general EDA SAT problems.