Linearize a product of binary variables with 2 indexes

Question

I have the following inequality that I would want to linearize. Consider that $r_{ij}, x_{ij}, y_{ij}$ are binary variables defined for every pair of nodes $(i,j) \in A$. Also, I have a set of nodes $V$ which its used later.

The following constraint holds: $$r_{ij} \leq \sum_{k \ne i, k \ne j}x_{ik}y_{jk}\qquad \forall (i,j) \in A$$

At first I thought that I should introduce a new family of 3-index binary variables $l^k_{ij}$ and define: $$l^k_{ij} \leq x_{ik}\qquad \forall (i,j) \in A, k\in V: i \ne k, j\ne k\\l^k_{ij}\leq y_{jk}\qquad \forall (i,j) \in A,k \in V:i\ne k, j\ne k\\ l^k_{ij} \geq x_{ik}+y_{jk}-1 \qquad \forall (i,j) \in A,k \in V:i\ne k, j\ne k$$

My ultimate goal is to be able to come up with a linearization that maintains the original number of indexes (although so far i haven't been able to do so and I think it may not be possible).

I've read this survey Transformation and Linearization Techniques in Optimization: A State-of-the-Art Survey and was wondering if there are any others papers like it that I could check as inspiration.

Answer 1

With your $\ell_{ij}^k$ variables, a linearization is: \begin{align} \ell_{ij}^k &\le x_{ik} \\ \ell_{ij}^k &\le y_{jk} \\ r_{ij} &\le \sum_k \ell_{ij}^k \end{align}

Without introducing new variables, an alternative formulation arises from rewriting the implication $$r_{ij} \implies \bigvee_k (x_{ik} \land y_{jk}) $$ in conjunctive normal form, but doing this yields exponentially many constraints: $$r_{ij} \le \sum_k *_k,$$ where each $*_k$ is either $x_{ik}$ or $y_{jk}$. Explicitly, for $|V|=3$, there are $2^3$ constraints for each $(i,j)$: \begin{align} r_{ij} &\le x_{i,1} + x_{i,2} + x_{i,3} \\ r_{ij} &\le x_{i,1} + x_{i,2} + y_{j,3} \\ r_{ij} &\le x_{i,1} + y_{j,2} + x_{i,3} \\ r_{ij} &\le x_{i,1} + y_{j,2} + y_{j,3} \\ r_{ij} &\le y_{j,1} + x_{i,2} + x_{i,3} \\ r_{ij} &\le y_{j,1} + x_{i,2} + y_{j,3} \\ r_{ij} &\le y_{j,1} + y_{j,2} + x_{i,3} \\ r_{ij} &\le y_{j,1} + y_{j,2} + y_{j,3} \end{align}