I'm interested generally in discrete optimization problems formulated as 0-1 integer programs; essentially, anything of the form
$$\Phi = \max_{\mathbf{x} \in \left\{0,1\right\} ^N} f(\mathbf{x})$$

My question is this: suppose the original problem is solvable in polynomial time.  Now, add a constraint that $x_i = 0$ or $x_i = 1$:

$$\Phi_{x_i;j} = \max_{\mathbf{x} \in \left\{0,1\right\} ^N, x_i=j} f(\mathbf{x})$$

Can you give me an example problem (preferably a moderately well-known combinatorial optimization problem) where $\Phi_{x_i;j}$ can no longer be found in polynomial time?  <strike>Alternatively, is there an argument to be made that no such example exists?</strike>

Edit:  clearly there are cases where a variable can switch between hard and easy problems, so examples will exist.  I'm looking for a case that isn't "contrived" in this sense--preferably a well-known combinatorial problem that becomes harder when you condition on a partial solution.  Is there some characteristic of functions/problems that describes whether they get harder or easier to solve as you condition on more variable assignments?