# Constraint terminology

If we want to pick a solution $S$ from a collection of items $C$ to maximize some function $f(S)$.

The constraint that we pick at most $k$ item, i.e., $|S| \leq k$, is called the cardinality constraint.

If the items in $C$ belongs to different groups and we are allowed to picked at most $k_i$ items from group $i$, what is the right terminology for this constraint? I think some paper used to call it the group cardinality constraint but I'm not sure if it's still the popular terminology.

• I'd say cardinality constraints are typically over a set of variables, e.g. Sudoku etc. So for me what you're describing is just a bunch of cardinality constraints. – Mikolas Oct 25 '17 at 17:27
• "If the items in C belongs to different groups" => C is a multiset. Perhaps you can go with "multisets with cardinality constraints" or "cardinality constraints on multisets". – Marzio De Biasi Oct 25 '17 at 19:12

This is not clear from your question, but I am going to assume that the groups are disjoint. I.e. $C = \bigcup_i C_i$ and $C_i \cap C_j = \emptyset$ for every $i \neq j$. Then the collection of sets $\mathcal{S} = \{S \subseteq C: |S \cap C_i| = k_i \ \ \forall i\}$ is the collection of bases of a partition matroid. In the context of combinatorial optimization then the constraint $S \in \mathcal{S}$ is often called a partition constraint. This is a special case of matroid constraints. There is, for example, an extensive body of work on maximizing a submodular function $f(S)$ subject to matroid constraints, i.e. subject to the set $S$ being a basis of a matroid.

• Yes, I was thinking about disjoint groups. – HTV Oct 25 '17 at 20:47

To be clear that I understand the context, I'm going to first reproduce you situation worded differently.

Consider a sequence of sets, $C_i$, and a target function, $f$. Let $\cup C_i=C$. We wish to find a subset $S\subseteq C$ that maximizes $f(S)$ under the constraint that $\forall i, |S\cap C_i|<k_i$ and $|S|<k$.

I would agree with the commenter that this should be referred to as a cardinality constraint or a collection of cardinality constraints. I might also call it a "structural constraint," but I would specifically avoid calling it a "group carnality constraint" as "group" already has a meaning. In general, I would advocate for avoiding referring to a collection as a "group," "set," or "class" unless your object actually satisfies the required axioms. "Collection" is a good, general word that doesn't have a mathematical meaning.

If you don't want to use the term "carnality constraint" you can always introduce a term to refer to this specific restriction in your context. This can be helpful because it allows you to highlight the context-sensitive meaning of the constraint in a way that a more general term doesn't. For example, I have a paper with a constraint of this form that I refer to as an "isolation condition" because, when $S$ satisfies it, $S$ is isolated from the structure of the rest of the graph in a relevant way. This gives me a simple and intuitive way to refer to the condition, while simultaneously telling the reader what is important about the condition every time it comes up.

• I think it's fair to come up with a new terminology like you said. On the other hand, I want to make sure that I know the right or often used terminology for literature research as well. – HTV Oct 26 '17 at 1:21
• @HTV Indeed, that was meant as a side comment and not the focus of my answer. – Stella Biderman Oct 26 '17 at 2:23