Heuristic Set-Covering-Based Postprocessing for Improving the Quine-McCluskey Method

Authors: Miloš Šeda

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.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1059733

References:

[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.