# Expressing inner product of binary variables in MIP

I have a $$m$$ by $$n$$ matrix $$X$$ of binary variables in my MIP which represents a list of $$m$$ items each belonging to one of $$n$$ categories. $$m$$ is usually around $$1,000$$ while $$n$$ is much lower at around $$10$$. If $$X_{i,j}=1$$, then it means that item $$i$$ belongs to category $$j$$ (and 0 would mean that the item doesn't belong to that category).

In addition to this, I have a list of costs $$w_{i,j}$$ which contribute to a total cost $$C$$ if and only if item $$i$$ belongs to the same category as item $$j$$. For example, if $$w_{300,400}=999$$, then $$C$$ will be increased by 999 if items 300 and 400 belong to the same category (regardless of what category it is). Even though there are potentially up to a million possible pairs, the number of pairs in $$w$$ is usually at most around $$10,000$$.

What's the best way to represent this total cost $$C$$ in my MIP? My mathematical intuition would be to take the dot product of $$X_i$$ and $$X_j$$ and multiply by $$w_{i,j}$$ for all the pairs, but multiplying two variables is invalid in MIP.

But you can exploit some special structure in your setting and avoid most products. For each pair of items $$i$$ and $$j$$ (with $$i) that have positive cost $$w_{ij}$$, introduce binary (or nonnegative) variable $$Y_{ij}$$ to represent the inner product $$\sum_k X_{ik}X_{jk}$$. The problem is to minimize $$\sum_{i subject to \begin{align} \sum_k X_{ik} &= 1 &&\text{for all i}\\ X_{ik} + X_{jk} - 1 &\le Y_{ij} &&\text{for all k and all i0} \end{align} Contrast this with the usual linearization that would instead introduce four-indexed variables $$Y_{ikj\ell}$$ to represent the product $$X_{ik} X_{j\ell}$$.