This paper deals with generalized pattern search (GPS) algorithms for linearly constrained optimization. At each iteration, the GPS algorithm generates a set of directions that conforms to the geometry of any nearby linear constraints, and this set is used to de ne the poll set for that iteration. The contribution of this paper is to provide a detailed algorithm for constructing the set of directions at a current iterate whether or not the constraints are degenerate. The main di culty in the degenerate case is in classifying constraints as redundant and nonredundant. We give a short survey of the main de nitions and methods concerning redundancy and propose an approach, which may be useful for other active set algorithms, to identify the nonredundant constraints.