# Linearize a product of binary variables with 2 indexes

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.

• Have you read this post?: or.stackexchange.com/questions/37/… Commented Oct 13, 2022 at 14:22
• Yes, I changed my question since I realized that the linearization i've done it's (apparently) correct to the one present in the literature Commented Oct 13, 2022 at 14:28

## 1 Answer

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}

• Can you clarify the "exponentially many" constraints part? I'm only see two constraints for each $(i,j)$ combination, one summing $x_{ik}$ and one summing $y_{jk}$, but those constraints don't do the job, so I assume I'm not understanding your notation.
– prubin
Commented Oct 13, 2022 at 15:57
• @prubin Yes, those are $2$ out of the $2^{|V|}$ constraints for each $(i,j)$. I updated my answer with more details. Commented Oct 13, 2022 at 16:15
• Thanks, that helps. I think you might have too many terms in the constraints, though. The original constraint sums over $k\neq i, k\neq j.$
– prubin
Commented Oct 13, 2022 at 17:59
• Yes just omit any such variables from those constraints. Commented Oct 13, 2022 at 23:04
• Thanks! @RobPratt. If i'm understanding it correctly, there will be very few (or maybe just one) inequalities that will actually provide useful upper bounds for $r_{ij}$. Let $x_{ik_2} = y_{jk_1} = 0$ then exists a constraint that would be $r_{ij}\leq x_{ik_2}+y_{jk_1}$ considering $|V| = 4$ and would make $r_{ij}\leq 0$. If that's how it works then I could have an aux. problem to check the condition and just add that constraint while branching so the exponential number of constraints shouldn't be a huge issue. Now I'd have to think on how to define $*_k$ in Gurobi or cplex Commented Oct 14, 2022 at 8:01