{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,8]],"date-time":"2026-03-08T22:17:00Z","timestamp":1773008220452,"version":"3.50.1"},"reference-count":24,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T00:00:00Z","timestamp":1766188800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"},{"start":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T00:00:00Z","timestamp":1766188800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/doi.wiley.com\/10.1002\/tdm_license_1.1"}],"funder":[{"DOI":"10.13039\/501100008982","name":"National Science Foundation of Sri Lanka","doi-asserted-by":"publisher","award":["DMS\u20102318790"],"award-info":[{"award-number":["DMS\u20102318790"]}],"id":[{"id":"10.13039\/501100008982","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Networks"],"published-print":{"date-parts":[[2026,4]]},"abstract":"<jats:title>ABSTRACT<\/jats:title>\n                  <jats:p>\n                    Given a simple graph  with vertex set  and edge set , the minimum biclique cover problem seeks to cover all edges of the graph with a minimum number of bicliques (i.e., complete bipartite subgraphs). This paper proposes two compact mixed integer programming (MIP) formulations for solving the minimum biclique cover problem on general graphs: (i) A natural formulation in the edge space and (ii) an extended formulation in the edge and vertex spaces. While the natural MIP formulation of Cornaz and Fonlupt (\n                    <jats:italic>Discrete Mathematics<\/jats:italic>\n                    , 2006) has exponentially many constraints, our natural formulation enjoys only a polynomial number of their exponential \u201cno\u2010good\u201d cuts, along with another set of polynomial valid inequalities. We also employ bounding and variable fixing procedures that help solve most of our social network instances, which are not solvable to optimality in a one\u2010hour time limit without the bounding and fixing procedures. The instances that are not solved in the one\u2010hour time limit are submitted to the 2024 Mixed Integer Programming Library (MIPLIB 2024).\n                  <\/jats:p>","DOI":"10.1002\/net.70020","type":"journal-article","created":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T16:26:16Z","timestamp":1766247976000},"page":"257-265","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Compact Mixed Integer Programming Formulations for the Minimum Biclique Cover Problem"],"prefix":"10.1002","volume":"87","author":[{"given":"Bruno","family":"Burin","sequence":"first","affiliation":[{"name":"Computer Engineering Department Military Institute of Engineering  Rio de Janeiro Brazil"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7983-7262","authenticated-orcid":false,"given":"Hamidreza","family":"Validi","sequence":"additional","affiliation":[{"name":"Industrial, Manufacturing and Systems Engineering Texas Tech University  Lubbock Texas USA"}]},{"given":"Bochuan","family":"Lyu","sequence":"additional","affiliation":[{"name":"Computational Applied Mathematics and Operations Research Rice University  Houston Texas USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7815-796X","authenticated-orcid":false,"given":"Illya V.","family":"Hicks","sequence":"additional","affiliation":[{"name":"Computational Applied Mathematics and Operations Research Rice University  Houston Texas USA"}]}],"member":"311","published-online":{"date-parts":[[2025,12,20]]},"reference":[{"key":"e_1_2_8_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2018.0946"},{"key":"e_1_2_8_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-023-01955-3"},{"key":"e_1_2_8_4_1","volume-title":"Biclique Partitions, Biclique Covers, and Disjunctive Constraints","author":"Lyu B.","year":"2023"},{"key":"e_1_2_8_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60406-5_3"},{"key":"e_1_2_8_6_1","first-page":"17","article-title":"A Survey of Clique and Biclique Coverings and Factorizations of (0, 1)\u2010Matrices","volume":"14","author":"Monson S. D.","year":"1995","journal-title":"Bulletin of the Institute of Combinatorics and Its Applications"},{"key":"e_1_2_8_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548010138917X"},{"key":"e_1_2_8_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1377836.1377838"},{"key":"e_1_2_8_9_1","first-page":"1","volume-title":"International Workshop on Implementing Automata","author":"Amilhastre J.","year":"1999"},{"key":"e_1_2_8_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/1385-7258(77)90055-5"},{"key":"e_1_2_8_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)00350-R"},{"key":"e_1_2_8_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(95)00154-O"},{"key":"e_1_2_8_13_1","doi-asserted-by":"publisher","DOI":"10.37236\/8316"},{"key":"e_1_2_8_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00039-0"},{"key":"e_1_2_8_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_20"},{"key":"e_1_2_8_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579163"},{"key":"e_1_2_8_17_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness (Series of Books in the Mathematical Sciences)","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_8_18_1","doi-asserted-by":"publisher","DOI":"10.3390\/a5040545"},{"key":"e_1_2_8_19_1","volume-title":"Challenge Problems: Independent Sets in Graphs","author":"Sloane N. J. A.","year":"2005"},{"key":"e_1_2_8_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.09.036"},{"key":"e_1_2_8_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190010208"},{"key":"e_1_2_8_22_1","unstructured":"B.LyuandI. V.Hicks \u201cMaximal Clique and Edge\u2010Ranking Bounds of Biclique Cover Number \u201d arXiv preprint arXiv:2302.12775 (2023)."},{"key":"e_1_2_8_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.01.010"},{"key":"e_1_2_8_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-970-5"},{"key":"e_1_2_8_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511984068"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.70020","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/net.70020","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.70020","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,8]],"date-time":"2026-03-08T20:16:37Z","timestamp":1773000997000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.70020"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,20]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["10.1002\/net.70020"],"URL":"https:\/\/doi.org\/10.1002\/net.70020","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,20]]},"assertion":[{"value":"2024-07-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-28","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}