# ILP - Maximize the number of pairs of variables with the same value

I have a 0-1 integer linear program for a set of $$2n$$ variables $$S = \{x_1, ..., x_n, y_1, ..., y_n\}$$. My objective is to maximize the number of pairs $$(x_i, y_i)$$ such that $$x_i = y_i$$, $$i = 1, ..., n$$.

$$\max \sum_{i=1}^n \mathbb{1}(x_i = y_i)$$

where $$\mathbb{1}(x_i = y_i) = 1$$ if and only if $$x_i = y_i$$, $$i = 1, ..., n$$.

The constraints are not important in this context. You may think the only constraints are: $$x_i \in \{0, 1\}, y_i \in \{0, 1\}, i = 1, ..., n$$

Obviously, this objective is not linear w.r.t the variables. I am wondering if there is a workaround (e.g., additional constraints) to construct a different objective function that is (1) linear and (2) also maximizes the number of such pairs of variables.

• You can keep it linear by introducing $z_i$ for each $i$ and adding $2n$ constraints: $z_i\ge x_i-y_i$ and $z_i\ge y_i-x_i$ and then change the objective to minimize the sum of the $z_i$. Dec 27, 2021 at 19:01
• blog.adamfurmanek.pl/2015/09/19/ilp-part-5 Dec 27, 2021 at 19:11
• @TickaJules Bravo! This really helps! Dec 27, 2021 at 19:13
• cs.stackexchange.com/q/12102/755
– D.W.
Dec 28, 2021 at 1:10