Solving covering problems using LPR-based lower bounds

ABSTRACT

Unate and binate covering problems are a special class ofgeneral integer linear programming problems with which several problemsin logic synthesis, such as two-level logic minimization and technologymapping, are formulated. Previous branch-and-bound methodsfor exactly solving these problems use lower-bounding techniques basedon finding maximal independent sets. In this paper we examine lower-boundingtechniques based on linear programming relaxation (LPR) forthe binate covering problem. We show that a combination of traditionalreductions (essentiality and dominance) and incremental computation ofLPR-based lower bounds can exactly solve difficult covering problemsorders of magnitude faster than traditional methods.

REFERENCES

• 1: R Barth. A Davis-Putnam based enumeration algorithm for linear pseudo-boolean optimization. Technical Report MPI-I-95- 2-003, Max-Planck-Institut far Informatik, January 1995. See www.mpi-sb.mp g.de/ g uide/staff/barth/publications/reports.
• 2: J.E. Beasley. An algorithm for set covering problem. European Journal of Operational Research, 31:85-93, 1987.
• 3: O. Coudert. On solving binate covering problems. In Proceedings of ACM/IEEE Design Automation Conference, June 1996.
• 4: Olivier Coudert , Jean Chritophe Madre, New ideas for solving covering problems, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.641-646, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217603]
• 5: J.F. Gimpel. A reduction technique for prime implicant tables. IEEE Trans. on Elec. Comp., 14:535-541, June 1965.
• 6: A. Grasselli and F. Luccio. A method for minimizing the number of internal states in incompletely specified machines. IEEE Trans. on Elec. Comp., 14:350-359, June 1965.
• 7: Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang, Instruction selection using binate covering for code size optimization, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.393-399, November 05-09, 1995, San Jose, California, United States
• 8: E.L. McCluskey, Jr. Minimization of boolean functions. Bell Sys. Tech. Journal, 35:1417-1444, April 1959.
• 9: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 10: W. V. O. Quine. A way to simplify truth functions. Am. Math. Monthly, 62:627-631, 1955.
• 11: W.V.O. Quine. On cores and prime implicants of truth functions. Am. Math. Monthly, 66:755-760, 1959.
• 12: Richard L. Rudell , Alberto Sangiovanni-Vincentelli, Logic synthesis for vlsi design, 1989

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Simulation

  C. Computer Systems Organization

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Design, Experimentation, Measurement, Performance, Theory

Keywords:
Covering problems, integer linear programming