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? Alternatively, is there an argument to be made that no such example exists?