We study the computational complexity of an optimization
version of the constraint satisfaction problem: given a set $F$ of
constraint functions, an instance consists of a set of variables $V$
related by constraints chosen from $F$ and a natural number $k$. The
problem is to decide whether there exists a subset $V' \subseteq V$ such
that $|V'| \geq k$ and the subinstance induced by $V'$ has a solution.
For all possible choices of $F$, we show that this problem is either
NP-hard or trivial. This hardness result makes it interesting to study
relaxations of the problem which may have better computational
properties. Thus, we study the approximability of the problem and we
consider certain compilation techniques. In both cases, the results are
not encouraging.