0
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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$. $\endgroup$
    – TickaJules
    Dec 27, 2021 at 19:01
  • 1
    $\begingroup$ blog.adamfurmanek.pl/2015/09/19/ilp-part-5 $\endgroup$
    – TickaJules
    Dec 27, 2021 at 19:11
  • $\begingroup$ @TickaJules Bravo! This really helps! $\endgroup$
    – Null_Space
    Dec 27, 2021 at 19:13
  • 2
    $\begingroup$ cs.stackexchange.com/q/12102/755 $\endgroup$
    – D.W.
    Dec 28, 2021 at 1:10
  • 2
    $\begingroup$ Perhaps you can answer your own question now? $\endgroup$
    – D.W.
    Dec 28, 2021 at 1:10

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.