{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:12Z","timestamp":1740144492562,"version":"3.37.3"},"reference-count":33,"publisher":"EDP Sciences","issue":"1","license":[{"start":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T00:00:00Z","timestamp":1738800000000},"content-version":"vor","delay-in-days":36,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["310185\/2021-1"],"award-info":[{"award-number":["310185\/2021-1"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2024,12,18]]},"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:p>Given a graph <jats:italic>G<\/jats:italic> = (<jats:italic>V, E<\/jats:italic>), the Edge Clique Cover Problem (ECCP) asks for a minimum number of cliques so that every edge <jats:italic>e<\/jats:italic> <jats:italic>\u2208<\/jats:italic> <jats:italic>E<\/jats:italic> belongs to at least one of the subgraphs induced by the selected cliques. Rather than fine tuned ECCP algorithms, exact or heuristic, we investigate conceptual frameworks for designing them. In particular we focus on frameworks that are based on the formulation of ECCP as a Set Covering Problem (SCP). This formulation typically contains an exponential number of variables that are in a one-to-one relation with the distinct maximal cliques of <jats:italic>G<\/jats:italic>. Our frameworks firstly generate <jats:italic>reduced SCP formulations<\/jats:italic> that contain a conveniently small number of variables and then solve them to obtain feasible solutions to ECCP. Variables for these formulations are selected <jats:italic>via<\/jats:italic> two distinct clique sampling criteria. One of them relies on random considerations for selecting the cliques (variables) while the other is based on Linear Programming reduced costs. The latter one, in particular, is further refined here into a procedure that implements local search within a column generation environment and is straightforward to adapt to numerous other problems.<\/jats:p>","DOI":"10.1051\/ro\/2024229","type":"journal-article","created":{"date-parts":[[2024,12,20]],"date-time":"2024-12-20T19:47:11Z","timestamp":1734724031000},"page":"523-547","source":"Crossref","is-referenced-by-count":0,"title":["Conceptual clique sampling frameworks to design solution algorithms for the Edge Clique Cover Problem"],"prefix":"10.1051","volume":"59","author":[{"given":"Douglas","family":"Picciani","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6627-7692","authenticated-orcid":false,"given":"Abilio","family":"Lucena","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2025,2,6]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Abdullah W.M. and Hossain S., A sparse matrix approach for covering large complex networks by cliques, in International Conference on Computational Science. Springer (2022) 505\u2013517.","DOI":"10.1007\/978-3-031-08757-8_43"},{"key":"R2","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/BF02574385","volume":"12","author":"Agarwal","year":"1994","journal-title":"Discrete Comput. Geo."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Blanchette M., Kim E. and Vetta A., Clique cover on sparse networks, in 2012 Proceedings of the Fourteenth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM (2012) 93\u2013102.","DOI":"10.1137\/1.9781611972924.10"},{"key":"R4","unstructured":"Boole G., Of propositions numerically definite, 1868, in Chapter IV of Studies in Logic and Probability, Waters, London (1952)."},{"key":"R5","unstructured":"Bornd\u00f6fer R., Aspects of set packing, partitioning, and covering an analysis of example. Ph.D. thesis, Technischen Universit\u00a8at Berlin (1998)."},{"key":"R6","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/j.endm.2005.05.045","volume":"19","author":"Camp\u00ealo","year":"2005","journal-title":"Electron. Notes Discret. Math."},{"key":"R7","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0012-365X(94)90151-1","volume":"125","author":"Chang","year":"1994","journal-title":"Discrete Math."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Conte A., Grossi R. and Marino A., Clique covering of large real-world networks, in Proceedings of the 31st Annual ACM Symposium on Applied Computing (2016) 1134\u20131139.","DOI":"10.1145\/2851613.2851816"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Desrosiers J. and L\u00fcbbecke M.E., Branch-Price-and-Cut Algorithms. John Wiley & Sons, Ltd. (2011).","DOI":"10.1002\/9780470400531.eorms0118"},{"key":"R10","doi-asserted-by":"crossref","first-page":"106","DOI":"10.4153\/CJM-1966-014-3","volume":"18","author":"Erd\u00f6s","year":"1966","journal-title":"Can. J. Math."},{"key":"R11","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"Gavril","year":"1972","journal-title":"SIAM J. Comput."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Gramm J., Guo J., H\u00fcffner F. and Niedermeier R., Data reduction, exact, and heuristic algorithms for clique cover, in Proceedings of the Meeting on Algorithm Engineering & Expermiments. Society for Industrial and Applied Mathematics (2006) 86\u201394.","DOI":"10.1137\/1.9781611972863.9"},{"key":"R13","doi-asserted-by":"crossref","first-page":"725","DOI":"10.1016\/j.csda.2006.09.035","volume":"52","author":"Gramm","year":"2007","journal-title":"Comput. Stat. Data Anal."},{"key":"R14","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/j.ipl.2004.03.007","volume":"90","author":"Guillaume","year":"2004","journal-title":"Inf. Process. Lett."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Hermelin D., Rizzi R. and Vialette S., Algorithmic aspects of the intersection and overlap numbers of a graph, in International Symposium on Algorithms and Computation. Springer (2012) 465\u2013474.","DOI":"10.1007\/978-3-642-35261-4_49"},{"key":"R16","unstructured":"Hevia A., Kallus B., McClintic S., Reisner S., Strash D. and Wilson J., Solving edge clique cover exactly via synergistic data reduction. Preprint: arXiv:2306.17804 (2023)."},{"key":"R17","doi-asserted-by":"crossref","unstructured":"Hosseinian S., Fontes D.B., Butenko S., Nardelli M.B., Fornari M. and Curtarolo S., The maximum edge weight clique problem: formulations and solution approaches, in Optimization Methods and Applications. Springer (2017) 217\u2013237.","DOI":"10.1007\/978-3-319-68640-0_10"},{"key":"R18","unstructured":"Johnson D.S. and Garey M.R., Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Freeman (1979)."},{"key":"R19","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1145\/359340.359346","volume":"21","author":"Kou","year":"1978","journal-title":"Commun. ACM"},{"key":"R20","doi-asserted-by":"crossref","first-page":"1007","DOI":"10.1287\/opre.1050.0234","volume":"53","author":"L\u00fcbbecke","year":"2005","journal-title":"Oper. Res."},{"key":"R21","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/s10287-009-0116-5","volume":"7","author":"Lucena","year":"2010","journal-title":"Comput. Manage. Sci."},{"key":"R22","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"Lund","year":"1994","journal-title":"J. ACM (JACM)"},{"key":"R23","unstructured":"Markham A. and Grosse-Wentrup M., Measurement dependence inducing latent causal models, in Conference on Uncertainty in Artificial Intelligence. PMLR (2020) 590\u2013599."},{"key":"R24","doi-asserted-by":"crossref","unstructured":"McKee T.A. and McMorris F.R., Topics in Intersection Graph Theory. SIAM (1999).","DOI":"10.1137\/1.9780898719802"},{"key":"R25","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1287\/ijoc.8.4.344","volume":"8","author":"Mehrotra","year":"1996","journal-title":"INFORMS J. Comput."},{"key":"R26","doi-asserted-by":"crossref","unstructured":"Orlin J., Contentment in graph theory: covering graphs with cliques, in Indagationes Mathematicae (Proceedings). Vol. 80. Elsevier (1977) 406\u2013424.","DOI":"10.1016\/1385-7258(77)90055-5"},{"key":"R27","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1016\/0377-2217(95)00299-5","volume":"95","author":"Park","year":"1996","journal-title":"Eur. J. Oper. Res."},{"key":"R28","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1198\/1061860043515","volume":"13","author":"Piepho","year":"2004","journal-title":"J. Comput. Graph. Stat."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"Rajagopalan S., Vachharajani M. and Malik S., Handling irregular ILP within conventional VLIW schedulers using artificial resource constraints, in Proceedings of the International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES 2000) (2000) 157\u2013164.","DOI":"10.1145\/354880.354902"},{"key":"R30","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0166-218X(85)90061-7","volume":"10","author":"Roberts","year":"1985","journal-title":"Discrete Appl. Math."},{"key":"R31","unstructured":"Sab\u00f3ia C.H.M., Um Algoritmo Branch-and-Price para Inst\u00e2ncias de Grande Porte do Modelo Brasileiro de Planejamento da Expans\u02dcao da Gera\u00e7\u02dcao El\u00e9trica a Longo Prazo. Ph.D. thesis, Programa de Engenharia de Sistemas e Computa\u00e7\u02dcao \u2013 PESC\/COPPE, Universidade Federal do Rio de Janeiro (2013)."},{"key":"R32","unstructured":"St\u00fctzle T., Local search algorithms for combinatorial problems. Ph.D. thesis, Darmstadt University of Technology (1998)."},{"key":"R33","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.tcs.2006.06.015","volume":"363","author":"Tomita","year":"2006","journal-title":"Theor. Comput. Sci."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024229\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T08:54:04Z","timestamp":1738832044000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2024229"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1]]},"references-count":33,"journal-issue":{"issue":"1"},"alternative-id":["ro240395"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2024229","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2025,1]]}}}