Tractable Continuous Approximations for Constraint Selection via Cardinality Minimization

We study a cardinality minimization problem that simultaneously minimizes an objective function and the cardinality of unsatisfied soft constraints. This paper proposes two continuous approximation methods that reformulate the discrete cardinality as complementarity constraints and difference-of-convex functions, respectively. We show that under suitable conditions, local and stationary solutions of the approximation problems recover local minimizers of the cardinality minimization problem. To demonstrate effectiveness, we apply the proposed methods to applications where violating as few preference conditions (or soft constraints) is desired. Our numerical study supports the use of methods based on our new approximations for cardinality minimization that produce comparable solutions with other benchmark formulations.

Funding: The authors acknowledge the Office of Engaged Learning at Southern Methodist University for its support of the work of D. Troxell. The work of M. Ahn was partially supported by NSF CRII [Grant IIS-1948341].