Strong MIP formulations for a large-scale mixed-integer nonlinear feasibility problem

Question

I'm trying to construct a strong MIP formulation for the following integer nonlinear feasibility problem.

Informally:

1. We have a $m \times n$ decision matrix of binary variables
2. Each row of the matrix has to sum to $2 \leq p \leq n$
3. Each row is associated with a set of other rows (this association is symmetric) such that for every pair of such rows, exactly $n-2$ of the variables take the same value
4. Each row is associated with another set of other rows (this association is also symmetric) such that for every pair of such rows, at most $n-4$ of the variables take the same value.

Formally: we are given natural numbers $m$, $n$, and $p$ with $2 \leq p \leq n$ and set-valued mappings $\mathcal{I}, \mathcal{K}:\{1,2,\dots,m\} \rightrightarrows \{1,2,\dots,m\}$ such that the mappings are:

1. Not reflexive: $i \not\in \mathcal{I}(i)$ and $i \not\in \mathcal{K}(i)$, $\forall i \in \{1,\dots,m\}$

2. Symmetric: $k \in \mathcal{I}(i) \implies i \in \mathcal{I}(k)$ and $k \in \mathcal{K}(i) \implies i \in \mathcal{K}(k)$

3. Of equal cardinality: $\lvert \mathcal{I}(i) \rvert = \lvert \mathcal{I}(k) \rvert$ and $\lvert \mathcal{K}(i) \rvert = \lvert \mathcal{K}(k) \rvert$, $\forall i, k \in \{1,\cdots,m\}$

4. Exclusive: $k \in \mathcal{I}(i) \implies k \not\in \mathcal{K}(i)$ and $k \in \mathcal{K}(i) \implies k \not\in \mathcal{I}(i)$.

We are required to find a decision $x \in \{0,1\}^{m \times n}$ such that:

\begin{align*} \sum_{j=1}^{n} x_{ij} &= p, \quad \forall i \in \{1,\dots,m\}, \\ \sum_{j=1}^{n} \lvert x_{ij} - x_{kj} \rvert &= 2, \quad \forall i \in \{1,\dots,m\} \: \text{and} \: k \in \mathcal{I}(i), \\ \sum_{j=1}^{n} \lvert x_{ij} - x_{kj} \rvert &\geq 4, \quad \forall i \in \{1,\dots,m\} \: \text{and} \: k \in \mathcal{K}(i). \end{align*}

I am interested in solving instances with $m \approx 250$, $n \approx 500$, $p \approx 100$, $\lvert \mathcal{I}(i) \rvert \approx 10$, and $\lvert \mathcal{K}(i) \rvert \approx 50$.

My current approach is to reformulate each individual absolute value term using MIP. For instance, to model $\lvert x_{ij} - x_{kj} \rvert$, I use the auxiliary variables and equations

\begin{align*} u_{ikj} &= v_{ikj} + w_{ikj}, \\ x_{ij} - x_{kj} &= v_{ikj} - w_{ikj}, \\ v_{ikj} &\leq z_{ikj}, \\ w_{ikj} &\leq 1 - z_{ikj}, \\ v_{ikj}, &w_{ikj} \geq 0, u_{ikj}, z_{ikj} \in \{0,1\}, \end{align*}

and replace the second and third set of constraints in the original problem with

\begin{align*} \sum_{j=1}^{n} u_{ikj} &= 2, \quad \forall i \in \{1,\dots,m\} \text{ and } k \in \mathcal{I}(i), \\ \sum_{j=1}^{n} u_{ikj} &\geq 4, \quad \forall i \in \{1,\dots,m\} \text{ and } k \in \mathcal{K}(i). \end{align*}

I've also tried to use a cutting-plane approach to solve this problem by iteratively adding violated second and third sets of constraints. These approaches, however, do not scale to the dimensions I want and I'm wondering if there is a stronger MIP formulation for this feasibility problem.

Answer 1

You can omit $v$, $w$, and $z$ and instead directly link $u$ and $x$ as follows: \begin{align} -(1 - u_{ikj}) \le x_{ij} + x_{kj} - 1 &\le 1 - u_{ikj} \tag1 \\ -u_{ikj} \le x_{ij} - x_{kj} &\le u_{ikj} \tag2 \end{align} Constraint $(1)$ enforces $u_{ikj} = 1 \implies x_{ij} + x_{kj} = 1$ (equivalently, $x_{ij} \ne x_{kj}$). Constraint $(2)$ enforces $u_{ikj} = 0 \implies x_{ij} = x_{kj}$.