Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


A Novel Method for Modelling Cardinality and Rank Constraints


A.B. Hempel

IfA Internal Seminar Series, Zurich, CH

Constraints on the cardinality or rank of decision variables in optimization problems are generally modelled separately from algebraic constraints. In this paper we show that cardinality constraints on vectors and rank constraints on matrices can be represented using purely algebraic constraints on continuous variables, by exploiting classical results on the Ky Fan norm for matrices and its analogous norm for vectors. Using this technique, a vector cardinality constraint can be modelled via introduction of a small number of additional variables and linear constraints, in conjunction with a single bilinear inequality. Analogously, a matrix rank constraint can be modelled via introduction of additional matrix variables and linear matrix inequalities, in conjunction with a single bilinear matrix inequality. We discuss a number of variations on cardinality and rank constraints that can be modelled in a similar way.


Type of Publication:


File Download:

Request a copy of this publication.
(Uses JavaScript)
% No recipe for automatically generating a BibTex entry for (06)Talk
Permanent link