13
$\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.

Improve this question
$\endgroup$
6
  • 1
    $\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$
    – RobPratt
    Commented Aug 17, 2019 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
    Commented Aug 17, 2019 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
    Commented Aug 17, 2019 at 17:27
  • 2
    $\begingroup$ Related: or.stackexchange.com/q/76/38 $\endgroup$
    – LarrySnyder610
    Commented Aug 18, 2019 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
    Commented Aug 21, 2019 at 11:24

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$

Your Answer

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

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