Subset Selection Problem

The second class of problems (C2) is the Subset Selection. The problem of Admissible Subset Selection (AdSS, for short) concerns finding a subset of a given set so that a given set of constraints is satisfied. The initial set defining the search area can be specified explicitly or by providing a constructive enumeration procedure for generating its elements. For simplicity, it is assumed that the set is both discrete and finite. The basic formulation of the AdSS problem is as follows.

Let $U$ denote some finite and discrete set, to be called the universe. Further, let $F_{1}, F_{2},\ldots,F_{k}$ denote some constraints imposed on subsets of $U$ specified as logical predicates, i.e.

$$F_{i}\colon 2^{U} \to \{\mathbf{T},\mathbf{F}\},$$

where $\mathbf{T}$ and $\mathbf{F}$ denote logical values of true and false, respectively, and $i\in \{1,2,\ldots,n\}$. The problem is to find a subset $X$ of $U$ satisfying the given constraints. Mathematically, this can be put as follows.

Find $X$ such that:

$$X \subseteq U,$$ (2.4)

and

$$F_{i}(X) \quad \mbox{for} \quad i = 1,2,\ldots,k.$$ (2.5)

Note that the above problem is indeterministic one - there can be one or more solutions or no solution may satisfy the constraints. Alternatively, one may require to find all such subsets.

The problem of Admissible Subset Selection can take the form of Optimal Subset Selection (OpSS, for short) provided that a criterion function is given. Such a problem concerns finding a subset of a given set so that a given set of constraints is satisfied, and simultaneously some criterion function has an extremal value (maximum or minimum).

Assume $G$ denotes a criterial function of the form:

$$G\colon X \to \mathbf{R},$$

where $\mathbf{R}$ is the set of real numbers. Assume the goal is to find the maximal element. The basic formulation of the OpSS problem is as follows.

Find $X$ such that:

$$X \subseteq U,$$ (2.6)

and

$$F_{i}(X) \quad \mbox{for} \quad i = 1,2,\ldots,k,$$ (2.7)

such that

$$G(X) \geq G(Y),$$ (2.8)

for any $Y\subseteq U$.

Note that the above problem may also be indeterministic one - there can be one or more solutions or no solution may satisfy the constraints and the optimality condition. Alternatively, one may require to find all such subsets.