{"corpus_id":235458292,"paper_sha":"28c93d18069075d8c341b919bc806bbfc9d84e0a","doi":null,"arxiv_id":"2106.09606","pmid":null,"pmcid":null,"mag_id":null,"dblp_id":"journals/corr/abs-2106-09606","acl_id":null,"title":"Cardinality Minimization, Constraints, and Regularization: A Survey","year":2021,"publication_date":"2021-06-17","venue":"arXiv.org","journal":{"name":"ArXiv","pages":null,"volume":"abs/2106.09606"},"journal_issn":null,"journal_title":null,"publication_types":["JournalArticle","Review"],"pubmed_pub_types":null,"s2_fields_of_study":["Mathematics","Computer Science"],"reference_count":402,"citation_count":49,"influential_citation_count":2,"is_open_access":false,"arxiv_categories":["math.OC","cs.IT","math.IT"],"arxiv_license":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/","arxiv_journal_ref":null,"mesh_headings":null,"chemicals":null,"comments_corrections":null,"source_flags":1,"s2_open_access_pdf_url":null,"s2_open_access_landing_url":null,"s2_open_access_license":null,"s2_open_access_status":null,"pmc_open_access_pdf_url":null,"pmc_open_access_landing_url":null,"pmc_open_access_license":null,"pmc_open_access_status":null,"unpaywall_open_access_pdf_url":null,"unpaywall_open_access_landing_url":null,"unpaywall_open_access_license":null,"unpaywall_open_access_status":null,"abstract":"We survey optimization problems that involve the cardinality of variable vectors in constraints or the objective function. We provide a unified viewpoint on the general problem classes and models, and give concrete examples from diverse application fields such as signal and image processing, portfolio selection, or machine learning. The paper discusses general-purpose modeling techniques and broadly applicable as well as problem-specific exact and heuristic solution approaches. While our perspective is that of mathematical optimization, a main goal of this work is to reach out to and build bridges between the different communities in which cardinality optimization problems are frequently encountered. In particular, we highlight that modern mixed-integer programming, which is often regarded as impractical due to commonly unsatisfactory behavior of black-box solvers applied to generic problem formulations, can in fact produce provably high-quality or even optimal solutions for cardinality optimization problems, even in large-scale real-world settings. Achieving such performance typically draws on the merits of problem-specific knowledge that may stem from different fields of application and, e.g., shed light on structural properties of a model or its solutions, or lead to the development of efficient heuristics; we also provide some illustrative examples.","claims":[{"public_id":"cl_61a42778a203ba3de5bd6a61adcd07e4","status":"active","text":"Cardinality optimization problems can be organized into general problem classes and models under a unified viewpoint.","confidence":0.89,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_61a42778a203ba3de5bd6a61adcd07e4"},{"public_id":"cl_c2893f3baf7b601d00ce03fb3c951460","status":"active","text":"General-purpose modeling techniques and both broadly applicable and problem-specific exact and heuristic solution approaches are discussed for these optimization problems.","confidence":0.86,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_c2893f3baf7b601d00ce03fb3c951460"},{"public_id":"cl_69b360b40155b8cecdbccc685112557c","status":"active","text":"Modern mixed-integer programming can produce provably high-quality or even optimal solutions for cardinality optimization problems, including in large-scale real-world settings.","confidence":0.95,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_69b360b40155b8cecdbccc685112557c"},{"public_id":"cl_a6d46954e76d958850900e8107d048c4","status":"active","text":"Problem-specific knowledge can improve performance by revealing structural properties of models or solutions and by enabling efficient heuristics.","confidence":0.91,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_a6d46954e76d958850900e8107d048c4"}],"concepts":[{"public_id":"co_01dd704be8a458d7fbd7d4d05b5ee9e4","status":"active","name":"efficient heuristics","description":"Approximate solution methods designed to find good solutions quickly.","types":["solution approach"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_01dd704be8a458d7fbd7d4d05b5ee9e4"},{"public_id":"co_19b3697475c6d0ba7f0aead4987660cc","status":"active","name":"problem-specific knowledge","description":"Information tailored to a particular application or model that can guide formulation or solution design.","types":["knowledge source"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_19b3697475c6d0ba7f0aead4987660cc"},{"public_id":"co_234f966b8fe77775e31fe0860a29d070","status":"active","name":"cardinality optimization problems","description":"Optimization problems in which the cardinality of a variable vector appears in the objective function or in constraints.","types":["optimization problem"],"aliases":["cardinality minimization problems"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_234f966b8fe77775e31fe0860a29d070"},{"public_id":"co_5194ade0faef5d2ae4102e59cdfeac33","status":"active","name":"unified viewpoint","description":"A common perspective used to relate different cardinality optimization formulations and applications.","types":["perspective"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_5194ade0faef5d2ae4102e59cdfeac33"},{"public_id":"co_63dc20664c5a7d60c1ac56bf7816c00e","status":"active","name":"large-scale real-world settings","description":"Practical application settings involving large problem instances from real data or operational use.","types":["application setting"],"aliases":["large-scale settings"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_63dc20664c5a7d60c1ac56bf7816c00e"},{"public_id":"co_68671f23ed623395b129312dc41738cb","status":"active","name":"heuristic solution approaches","description":"Methods that seek good feasible solutions without optimality guarantees.","types":["solution approach"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_68671f23ed623395b129312dc41738cb"},{"public_id":"co_7a2e398b40df4dff1d8eb85018f15dc5","status":"active","name":"general-purpose modeling techniques","description":"Modeling methods intended to apply across many cardinality optimization problems.","types":["modeling technique"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_7a2e398b40df4dff1d8eb85018f15dc5"},{"public_id":"co_8100035f3553ea3f0a6d44e37c4f1dea","status":"active","name":"exact solution approaches","description":"Methods that aim to prove optimality for a given optimization problem.","types":["solution approach"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_8100035f3553ea3f0a6d44e37c4f1dea"},{"public_id":"co_9fe6db0c5ad16ed7222d4dbc410e7ae6","status":"active","name":"general problem classes and models","description":"Abstract formulations used to categorize and represent cardinality-based optimization problems.","types":["model class"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_9fe6db0c5ad16ed7222d4dbc410e7ae6"},{"public_id":"co_b0b3f1a27c11c829ba13d4867d80ab78","status":"active","name":"structural properties","description":"Mathematical or combinatorial features of a model or its solutions that can be exploited algorithmically.","types":["property"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_b0b3f1a27c11c829ba13d4867d80ab78"},{"public_id":"co_ca87994e56e37334e519fd0b22aa0dd8","status":"active","name":"modern mixed-integer programming","description":"A mixed-integer optimization framework for modeling problems with discrete and continuous variables.","types":["optimization method"],"aliases":["MIP","MIP formulations"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_ca87994e56e37334e519fd0b22aa0dd8"}],"external_ids":{"DOI":null,"ArXiv":"2106.09606","PubMed":null,"PubMedCentral":null,"MAG":null,"DBLP":"journals/corr/abs-2106-09606","ACL":null},"open_access":{"is_open_access":true,"pdf_url":"https://arxiv.org/pdf/2106.09606","landing_url":"https://arxiv.org/abs/2106.09606","source":"arxiv","pdf_url_source":"derived_arxiv","license":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/","reason":null},"reference_availability":{"status":"available","references_indexed":true,"full_text_available":true,"full_text_source":"arxiv","count_basis":"semantic_scholar_metadata","extraction_status":"not_applicable","reason":null},"source":{"provider":"episteme2","base_corpus":"semantic_scholar_dump","freshness_mode":"unknown","basis":["semantic_scholar_metadata","postgres_metadata"],"limits":["paper metadata is based on indexed upstream scholarly datasets","claims and concepts are available only for extracted papers","absence of claims or concepts means no extracted graph data is available in this response"],"status":"available","degraded":false,"degraded_reasons":[],"diagnostics":{"status":"available","degraded":false,"degraded_reasons":[],"metadata_status":"available","graph_status":"available","abstract_status":"available"},"source_flags":1},"paper_id":635728,"paper_uid":"463322e3-66be-42e5-9dcf-1975e5fb678d","canonical_identity":{"paper_id":635728,"paper_uid":"463322e3-66be-42e5-9dcf-1975e5fb678d","identity_status":"available","lookup_basis":"semantic_scholar_external_id","compatibility_path":"corpus_id"},"url":"https://sah.borca.ai/papers/235458292"}