{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T00:43:55Z","timestamp":1769906635198,"version":"3.49.0"},"reference-count":18,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2021,8,9]],"date-time":"2021-08-09T00:00:00Z","timestamp":1628467200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Logical Analysis of Data is a procedure aimed at identifying relevant features in data sets with both positive and negative samples. The goal is to build Boolean formulas, represented by strings over {0,1,-} called patterns, which can be used to classify new samples as positive or negative. Since a data set can be explained in alternative ways, many computational problems arise related to the choice of a particular set of patterns. In this paper we study the computational complexity of several of these pattern problems (showing that they are, in general, computationally hard) and we propose some integer programming models that appear to be effective. We describe an ILP model for finding the minimum-size set of patterns explaining a given set of samples and another one for the problem of determining whether two sets of patterns are equivalent, i.e., they explain exactly the same samples. We base our first model on a polynomial procedure that computes all patterns compatible with a given set of samples. Computational experiments substantiate the effectiveness of our models on fairly large instances. Finally, we conjecture that the existence of an effective ILP model for finding a minimum-size set of patterns equivalent to a given set of patterns is unlikely, due to the problem being NP-hard and co-NP-hard at the same time.<\/jats:p>","DOI":"10.3390\/a14080235","type":"journal-article","created":{"date-parts":[[2021,8,9]],"date-time":"2021-08-09T21:41:46Z","timestamp":1628545306000},"page":"235","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Computational Complexity and ILP Models for Pattern Problems in the Logical Analysis of Data"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5323-8483","authenticated-orcid":false,"given":"Giuseppe","family":"Lancia","sequence":"first","affiliation":[{"name":"Department of Mathematics, Computer Science and Physics, University of Udine, 33100 Udine, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paolo","family":"Serafini","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Computer Science and Physics, University of Udine, 33100 Udine, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,8,9]]},"reference":[{"key":"ref_1","unstructured":"Jaiwei, H., Jian, P., and Micheline, K. (2011). Data Mining: Concepts and Techniques, Morgan Kaufmann."},{"key":"ref_2","unstructured":"Kantardzic, M. (2003). Data Mining: Concepts, Models, Methods, and Algorithms, John Wiley & Sons."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"131","DOI":"10.3233\/IDA-1997-1302","article-title":"Feature Selection for Classification","volume":"1","author":"Dash","year":"1997","journal-title":"Intell. Data Anal."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Felici, G., and Triantaphyllou, E. (2006). Feature Selection for Data Mining. Data Mining and Knowledge Discovery Approaches Based on Rule Induction Techniques, Springer.","DOI":"10.1007\/0-387-34296-6"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Stacczyk, U., Zielosko, B., and Jain, L. (2018). Advances in Feature Selection for Data and Pattern Recognition: An Introduction Advances in Feature Selection for Data and Pattern Recognition, Springer. Intelligent Systems Reference Library.","DOI":"10.1007\/978-3-319-67588-6"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/s10472-007-9065-2","article-title":"Logical analysis of data\u2014The vision of Peter L. Hammer","volume":"49","author":"Alexe","year":"2007","journal-title":"Ann. Math. Artif. Intell."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Chikalov, I., Lozin, V., Lozina, I., Moshkov, M., Son Nguyen, H., Skowron, A., and Zielosko, B. (2013). Logical Analysis of Data: Theory, Methodology and Applications. Three Approaches to Data Analysis, Springer.","DOI":"10.1007\/978-3-642-28667-4"},{"key":"ref_8","unstructured":"Hammer, P., and Bonates, T. (2005). Logical Analysis of Data: From Combinatorial Optimization to Medical Applications, Rutgers University. RUTCOR Research Report, 10-05."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"889","DOI":"10.1016\/j.camwa.2006.12.093","article-title":"Logic classification and feature selection for biomedical data","volume":"55","author":"Bertolazzi","year":"2008","journal-title":"Comput. Math. Appl."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1126\/science.286.5439.531","article-title":"Molecular classification of cancer: Class discovery and class prediction by gene expression monitoring","volume":"286","author":"Golub","year":"1999","journal-title":"Science"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"2429","DOI":"10.1093\/bioinformatics\/bth267","article-title":"A comparative study of feature selection and multiclass classification methods for tissue classification based on gene expression","volume":"20","author":"Li","year":"2004","journal-title":"Bioinformatics"},{"key":"ref_12","unstructured":"Ortuno, F., and Rojas, I. (2016). The Complexity of Some Pattern Problems in the Logical Analysis of Large Genomic Data Sets. Bioinformatics and Biomedical Engineering. IWBBIO 2016, Springer. Lecture Notes in Computer Science."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.tcs.2016.12.018","article-title":"Separating sets of strings by finding matching patterns is almost always hard","volume":"665","author":"Lancia","year":"2017","journal-title":"Theor. Comput. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Boccia, M., Sforza, A., and Sterle, C. (2020). Simple Pattern Minimality Problems: Integer Linear Programming Formulations and Covering-Based Heuristic Solving Approaches. Informs J. Comput.","DOI":"10.1287\/ijoc.2019.0940"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/j.dam.2013.05.003","article-title":"Classifying negative and positive points by optimal box clustering","volume":"165","author":"Serafini","year":"2014","journal-title":"Discret. Appl. Math."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1109\/69.842268","article-title":"An implementation of Logical Analysis of Data","volume":"12","author":"Boros","year":"2000","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_17","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company."},{"key":"ref_18","unstructured":"Cormen, T., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, MIT Press. [3rd ed.]."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/8\/235\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:43:11Z","timestamp":1760164991000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/8\/235"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,9]]},"references-count":18,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2021,8]]}},"alternative-id":["a14080235"],"URL":"https:\/\/doi.org\/10.3390\/a14080235","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,9]]}}}