I have an instance of the stable marriage problem in which the first side $S_1$ has $n_1$ agents and the second side $S_2$ has $n_2$ agents with $n_2$ is very big in comparison to $n_1$. In addition, the agents of $S_2$ have the same preference list. The stability constraints can be modelled as follows:
$ 1 \leq \sum\limits_{j'\in F^{\leq}_{j}(i)}x_{ij'} + \sum\limits_{i'\in C^{\leq}_{i}}x_{i'j};$ $ i \in S_1$, $j \in S_2$
where $ F^{\leq}_{j}(i)$ is the set of agents of $S_2$ that $i$ ranks at the same level or better than $j$ and $C^{\leq}_{i}$ is the set of $S_1$ that are at the same level or better than $i$.
My question is: is there a way to model the stability constraints with a number of constraints in the order $O(n_1)$ rather than $O(n_1 n_2)$? because $n_2$ is very big and we already have a number of columns in order of $O(n_1 n_2)$.
