I have a very general question.
I am looking for a reference that discusses how adding a dimension to a large linear integer program with binary variables affects the optimal solution. In particular, I would like to understand under what conditions adding a dimension changes all the optimal matching/assignments in a matching(-like) problem?
Adding one new binary variable $x_{new}$ essentially means you now have two possibilities in terms of the original variables: the original problem (corresponding to $x_{new}=0$) and a new problem with $x_{new}=1$. If the optimal objective value of the new problem is better than that of the old, there's no reason why every variable assignment shouldn't change.
For example, consider this problem: maximum matching in a linear graph with $4$ vertices $a,b,c,d$.
maximize $x_{ab} + x_{bc} + x_{cd}$
subject to $x_{ab} \le 1,\ x_{ab}+x_{bc} \le 1, \ x_{bc}+x_{cd} \le 1,\ x_{cd} \le 1$, all variables $\in \{0,1\}$.
The optimal solution is $x_{ab} = x_{cd} = 1$, $x_{bc} = 0$.
Now add a new variable for a new edge $x_{ad}$ and give it additional weight, so the problem is
maximize $x_{ab} + x_{bc} + x_{cd} + 2 x_{ad}$
subject to $x_{ab}+x_{ad} \le 1,\ x_{ab}+x_{bc} \le 1, \ x_{bc}+x_{cd} \le 1,\ x_{cd}+x_{ad} \le 1$, all variables $\in \{0,1\}$.
The new optimal solution is $x_{bc} = x_{ad}=1$, $x_{ab} = x_{cd} = 0$.