Cardinality Minimization, Constraints, and Regularization: A Survey

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

  • Andreas Tillmann - , Technische Universität Braunschweig (Autor:in)
  • Daniel Bienstock - , Columbia University (Autor:in)
  • Andrea Lodi - , Cornell University (Autor:in)
  • Alexandra Schwartz - , Professur für Mathematische Optimierung (Autor:in)

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 we give concrete examples from diverse application fields such as signal and image processing, portfolio selection, and 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 the 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 involves drawing on the merits of problem-specific knowledge that may stem from different fields of application and, e.g., can shed light on structural properties of a model or its solutions, or can lead to the development of efficient heuristics. We also provide some illustrative examples.

Details

OriginalspracheEnglisch
Seiten (von - bis)403-477
Seitenumfang75
FachzeitschriftSiam review
Jahrgang66
Ausgabenummer3
PublikationsstatusVeröffentlicht - 1 Sept. 2024
Peer-Review-StatusJa

Externe IDs

Scopus 85201541528

Schlagworte