Heuristic Set-Covering-Based Postprocessing for Improving the Quine-McCluskey Method
Finding the minimal logical functions has important applications in the design of logical circuits. This task is solved by many different methods but, frequently, they are not suitable for a computer implementation. We briefly summarise the well-known Quine-McCluskey method, which gives a unique procedure of computing and thus can be simply implemented, but, even for simple examples, does not guarantee an optimal solution. Since the Petrick extension of the Quine-McCluskey method does not give a generally usable method for finding an optimum for logical functions with a high number of values, we focus on interpretation of the result of the Quine-McCluskey method and show that it represents a set covering problem that, unfortunately, is an NP-hard combinatorial problem. Therefore it must be solved by heuristic or approximation methods. We propose an approach based on genetic algorithms and show suitable parameter settings.
[1] L. Brotcorne, G. Laporte and F. Semet, "Fast Heuristics for Large Scale
Covering-Location Problems," Computers & Operations Research, vol.
29, pp. 651-665, 2002.
[2] J.E. Beasley P.C. Chu, "A Genetic Algorithm for the Set Covering
Problem," Journal of Operational Research, vol. 95, no. 2, pp. 393-404,
1996.
[3] C.I. Chiang, M.J. Hwang and Y.H. Liu, "An Alternative Formulation for
Certain Fuzzy Set-Covering Problems," Mathematical and Computer
Modelling, vol. 42, pp. 363-365, 2005.
[4] P. Chu, "A Genetic Algorithm Approach for Combinatorial Optimisation
Problems," PhD thesis, The Management School Imperial College of
Science, Technology and Medicine, London, 1997.
[5] K. ─îul├¡k, M. Skalick├í, I. V├íňov├í, Logic (in Czech). Brno: VUT FE,
1968.
[6] P. Galinier and A. Hertz, "Solution Techniques for the Large Set
Covering Problem," Discrete Applied Mathematics, vol. 155, pp. 312-
326, 2007.
[7] F.C. Gomes, C.N. Meneses, P.M. Pardalos and G.V.R. Viana,
"Experimental Analysis of Approximation Algorithms for the Vertex
Cover and Set Covering Problems," Computers & Operations
Research, vol. 33, pp. 3520-3534, 2006.
[8] T. Grossman and A. Wool, "Computational Experience with
Approximation Algorithms for the Set Covering Problem," European
Journal of Operational Research, vol. 101, pp. 81-92, 1997.
[9] M.J. Hwang, C.I. Chiang and Y.H. Liu, "Solving a Fuzzy Set-Covering
Problem," Mathematical and Computer Modelling, vol. 40, pp. 861-865,
2004.
[10] G. Lan and G.W. DePuy, "On the Effectiveness of Incorporating
Randomness and Memory into a Multi-Start Metaheuristic with
Application to the Set Covering Problem," Computers & Industrial
Engineering, vol. 51, pp. 362-374, 2006.
[11] G. Lan, G.W. DePuy and G.E. Whitehouse, "An Effective and Simple
Heuristic for the Set Covering Problem," European Journal of
Operational Research, vol. 176, pp. 1387-1403, 2007.
[12] M. Mesquita and A. Paias, "Set Partitioning/Covering-Based
Approaches for the Integrated Vehicle and Crew Scheduling Problem,"
Computers & Operations Research, in press, 2006.
[13] E.J. McCluskey, "Minimization of Boolean Functions," Bell System
Technical Journal, vol. 35, no. 5, pp. 1417-1444, 1956.
[14] A. Monfroglio, "Hybrid Heuristic Algorithms for Set Covering,"
Computers & Operations Research, vol. 25, pp. 441-455, 1998.
[15] M. Ohlsson, C. Peterson and B. Söderberg, "An Efficient Mean Field
Approach to the Set Covering Problem," European Journal of
Operational Research, vol. 133, pp. 583-595, 2001.
[16] S.K. Petrick, "On the Minimization of Boolean Functions," in
Proceedings of the International Conference Information Processing,
Paris, 1959, pp. 422-423.
[17] Ch. Posthoff and B. Steinbach, Logic Functions and Equations: Binary
Models for Computer Science. Berlin: Springer-Verlag, 2005.
[18] W.V. Quine, "The Problem of Simplifying Truth Tables," American
Mathematical Monthly, vol. 59, no. 8, pp. 521-531, 1952.
[19] L. Sekanina, Evolvable Components. Berlin: Springer-Verlag, 2003.
[20] M. Solar, V. Parada and R. Urrutia, "A Parallel Genetic Algorithm to
Solve the Set-Covering Problem," Computers & Operations
Research, vol. 29, pp. 1221-1235, 2002.
[21] S.P. Tomaszewski, I.U. Celik and G.E. Antoniou, "WWW-Based
Boolean Function Minimization," International Journal of Applied
Mathematics and Computer Science, vol. 13, no. 4, pp. 577-583, 2003.
[22] M. Yagiura, M. Kishida and T. Ibaraki, "A 3-Flip Neighborhood Local
Search for the Set Covering Problem," European Journal of Operational
Research, vol. 172, pp. 472-499, 2006.
[1] L. Brotcorne, G. Laporte and F. Semet, "Fast Heuristics for Large Scale
Covering-Location Problems," Computers & Operations Research, vol.
29, pp. 651-665, 2002.
[2] J.E. Beasley P.C. Chu, "A Genetic Algorithm for the Set Covering
Problem," Journal of Operational Research, vol. 95, no. 2, pp. 393-404,
1996.
[3] C.I. Chiang, M.J. Hwang and Y.H. Liu, "An Alternative Formulation for
Certain Fuzzy Set-Covering Problems," Mathematical and Computer
Modelling, vol. 42, pp. 363-365, 2005.
[4] P. Chu, "A Genetic Algorithm Approach for Combinatorial Optimisation
Problems," PhD thesis, The Management School Imperial College of
Science, Technology and Medicine, London, 1997.
[5] K. ─îul├¡k, M. Skalick├í, I. V├íňov├í, Logic (in Czech). Brno: VUT FE,
1968.
[6] P. Galinier and A. Hertz, "Solution Techniques for the Large Set
Covering Problem," Discrete Applied Mathematics, vol. 155, pp. 312-
326, 2007.
[7] F.C. Gomes, C.N. Meneses, P.M. Pardalos and G.V.R. Viana,
"Experimental Analysis of Approximation Algorithms for the Vertex
Cover and Set Covering Problems," Computers & Operations
Research, vol. 33, pp. 3520-3534, 2006.
[8] T. Grossman and A. Wool, "Computational Experience with
Approximation Algorithms for the Set Covering Problem," European
Journal of Operational Research, vol. 101, pp. 81-92, 1997.
[9] M.J. Hwang, C.I. Chiang and Y.H. Liu, "Solving a Fuzzy Set-Covering
Problem," Mathematical and Computer Modelling, vol. 40, pp. 861-865,
2004.
[10] G. Lan and G.W. DePuy, "On the Effectiveness of Incorporating
Randomness and Memory into a Multi-Start Metaheuristic with
Application to the Set Covering Problem," Computers & Industrial
Engineering, vol. 51, pp. 362-374, 2006.
[11] G. Lan, G.W. DePuy and G.E. Whitehouse, "An Effective and Simple
Heuristic for the Set Covering Problem," European Journal of
Operational Research, vol. 176, pp. 1387-1403, 2007.
[12] M. Mesquita and A. Paias, "Set Partitioning/Covering-Based
Approaches for the Integrated Vehicle and Crew Scheduling Problem,"
Computers & Operations Research, in press, 2006.
[13] E.J. McCluskey, "Minimization of Boolean Functions," Bell System
Technical Journal, vol. 35, no. 5, pp. 1417-1444, 1956.
[14] A. Monfroglio, "Hybrid Heuristic Algorithms for Set Covering,"
Computers & Operations Research, vol. 25, pp. 441-455, 1998.
[15] M. Ohlsson, C. Peterson and B. Söderberg, "An Efficient Mean Field
Approach to the Set Covering Problem," European Journal of
Operational Research, vol. 133, pp. 583-595, 2001.
[16] S.K. Petrick, "On the Minimization of Boolean Functions," in
Proceedings of the International Conference Information Processing,
Paris, 1959, pp. 422-423.
[17] Ch. Posthoff and B. Steinbach, Logic Functions and Equations: Binary
Models for Computer Science. Berlin: Springer-Verlag, 2005.
[18] W.V. Quine, "The Problem of Simplifying Truth Tables," American
Mathematical Monthly, vol. 59, no. 8, pp. 521-531, 1952.
[19] L. Sekanina, Evolvable Components. Berlin: Springer-Verlag, 2003.
[20] M. Solar, V. Parada and R. Urrutia, "A Parallel Genetic Algorithm to
Solve the Set-Covering Problem," Computers & Operations
Research, vol. 29, pp. 1221-1235, 2002.
[21] S.P. Tomaszewski, I.U. Celik and G.E. Antoniou, "WWW-Based
Boolean Function Minimization," International Journal of Applied
Mathematics and Computer Science, vol. 13, no. 4, pp. 577-583, 2003.
[22] M. Yagiura, M. Kishida and T. Ibaraki, "A 3-Flip Neighborhood Local
Search for the Set Covering Problem," European Journal of Operational
Research, vol. 172, pp. 472-499, 2006.
@article{"International Journal of Information, Control and Computer Sciences:53835", author = "Miloš Šeda", title = "Heuristic Set-Covering-Based Postprocessing for Improving the Quine-McCluskey Method", abstract = "Finding the minimal logical functions has important applications in the design of logical circuits. This task is solved by many different methods but, frequently, they are not suitable for a computer implementation. We briefly summarise the well-known Quine-McCluskey method, which gives a unique procedure of computing and thus can be simply implemented, but, even for simple examples, does not guarantee an optimal solution. Since the Petrick extension of the Quine-McCluskey method does not give a generally usable method for finding an optimum for logical functions with a high number of values, we focus on interpretation of the result of the Quine-McCluskey method and show that it represents a set covering problem that, unfortunately, is an NP-hard combinatorial problem. Therefore it must be solved by heuristic or approximation methods. We propose an approach based on genetic algorithms and show suitable parameter settings.
", keywords = "Boolean algebra, Karnaugh map, Quine-McCluskey method, set covering problem, genetic algorithm.", volume = "1", number = "5", pages = "1252-6", }
