Solving covering problems using LPR-based lower bounds

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Solving covering problems using LPR-based lower bounds

Full text

Pdf (87 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 34th annual Design Automation Conference table of contents

Anaheim, California, United States

Pages: 117 - 120

Year of Publication: 1997

ISBN:0-89791-920-3

Authors

Stan Liao	Advanced Technology Group, Synopsys, Inc.
Srinivas Devadas	Department of EECS, MIT

Sponsors

EDAC : Electronic Design Automation Consortium
IEEE-CAS : Circuits & Systems
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 16, Citation Count: 12

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/266021.266046 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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

CITED BY 12

	Evguenii I. Goldberg , Luca P. Carloni , Tiziano Villa , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Negative thinking by incremental problem solving: application to unate covering, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.91-98, November 09-13, 1997, San Jose, California, United States
	Xiao Yu Li , Matthias F. Stallmann , Franc Brglez, Effective bounding techniques for solving unate and binate covering problems, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	Alessandro Pinto , Luca P. Carloni , Alberto L. Sangiovanni-Vincentelli, Constraint-driven communication synthesis, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
	Vasco M. Manquinho , Joao Marques-Silva, Effective Lower Bounding Techniques for Pseudo-Boolean Optimization, Proceedings of the conference on Design, Automation and Test in Europe, p.660-665, March 07-11, 2005
	S. Liao , K. Keutzer , S. Tjiang , S. Devadas, A new viewpoint on code generation for directed acyclic graphs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.1, p.51-75, Jan. 1998
	Vasco M. Manquinho , João Marques-Silva, On using satisfiability-based pruning techniques in covering algorithms, Proceedings of the conference on Design, automation and test in Europe, p.356-363, March 27-30, 2000, Paris, France
	Michael Dimopoulos , Panagiotis Linardis, Search space pruning techniques in ATPG for VLSI circuits, Proceedings of the 9th International Conference on Circuits, p.1-6, July 11-13, 2005, Athens, Greece
	Vasco M. Manquinho , João P. Marques-Silva, Satisfiability-Based Algorithms for Boolean Optimization, Annals of Mathematics and Artificial Intelligence, v.40 n.3-4, p.353-372, March 2004
	Darko Kirovski , Yean-Yow Hwang , Miodrag Potkonjak , Jason Cong, Intellectual property protection by watermarking combinational logic synthesis solutions, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.194-198, November 08-12, 1998, San Jose, California, United States
	Zhaohui Fu , Sharad Malik, Solving the minimum-cost satisfiability problem using SAT based branch-and-bound search, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	Roberto Cordone , Fabrizio Ferrandi , Donatella Sciuto , Roberto Wolfler Calvo, An efficient heuristic approach to solve the unate covering problem, Proceedings of the conference on Design, automation and test in Europe, p.364-371, March 27-30, 2000, Paris, France
	Olivier Coudert , Tsutomu Sasao, Two-level logic minimization, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001