11
$\begingroup$

I want to represent the indicator function: $$ \mathbb{1}_{(y=j)}$$

where $y$ is a non negative, integer variable.

My attempt is as follows: define a binary variable: $$ z_j =\begin{cases} 1 \qquad\text{if $y=j$} \\ 0 \qquad\text{otherwise} \end{cases} $$

the model of the indicator function would be:

$$ \sum_{j=0}^{n} z_j = 1 $$ $$ \sum_{j=0}^{n} j \cdot z_j = y $$

where $n$ is an upper bound for $y$.

Actually, this can be conveniently modeled in OPL Cplex (for example) using indicator constraints such as follows:

forall(j in 0..n){
    (y == j) == (z[j] == 1);
}

QUESTIONS:

  1. is my binary-variables-based formulation attempt correct? Do you know better (performance wise) formulations?
  2. in a hypothetical academic journal paper, is the second formulation (based on indicator constraints) acceptable? If yes, how would you formally express it in the paper in a way that is implementation-independent (that is, in a way that does not depend upon how a specific solver models such a constraint)? Or it is better to provide the more general, binary-variables-based formulation?

Thanks a lot.

$\endgroup$
  • $\begingroup$ This is correct, assuming $y \in \{0,\dots,n\}$. More generally, if $y$ takes (not necessarily integer) values in a finite set $V$, impose $\sum\limits_{j \in V} z_j=1$ and $\sum\limits_{j \in V} j z_j=y$. $\endgroup$ – Rob Pratt Aug 17 at 16:39
  • 1
    $\begingroup$ Something else to consider is to do a binary expansion of $y$, i.e., add the constraint $\sum\limits_{j=0}^m 2^j z_j=y$, where $2^m$ is an upper bound on $y$. Depending on the application you have in mind you might not be able to use this representation, but if you can I would imagine it's more efficient. $\endgroup$ – Ryan Cory-Wright Aug 17 at 17:19
  • $\begingroup$ Note that you will need to linearize a product of binary variables to recover the indicator function for a fixed $j$. This can be achieved via $y \le z_i, \forall i, y\ge\sum\limits_i z_i - (n-1)$. $\endgroup$ – Ryan Cory-Wright Aug 17 at 17:27
  • 1
    $\begingroup$ Related: or.stackexchange.com/q/76/38 $\endgroup$ – LarrySnyder610 Aug 18 at 0:59
  • $\begingroup$ @RyanCory-Wright considering the binary expansion, however, I should drop the $\sum\limits_{j=0}^{n} z_j = 1$ constraint, right? If so, I don't get the equivalence between the two formulations. $\endgroup$ – Libra Aug 21 at 11:24
7
$\begingroup$

First question: Yes, your algebraic formulation is correct.

Second question: I would lean toward using the algebraic formulation, for two reasons. First, it is not solver-specific. Second, a reader not familiar with indicator constraints will find interpreting the algebraic formulation a bit easier, while a reader familiar with indicators is not likely to find the algebraic formulation much harder. That said, it would not hurt to mention in the paper that the constraint can be implemented by indicators in a solver that supports them (or, if your computational results were produced using CPLEX and you used indicators, just say that in the section describing the experiments).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.