Representing an indicator function: binary variables and “indicator constraints”g:R_mde1fn tl 2ra9rra t * JdA(rtBlWwQqlw
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:
- is my binary-variables-based formulation attempt correct? Do you know better (performance wise) formulations?
- 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.
-
$\\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_{j \\in V} z_j=1$ and $\\sum_{j \\in V} j z_j=y$. $\\endgroup$ – Rob Pratt 8 hours ago
-
1$\\begingroup$ Something else to consider is to do a binary expansion of $y$, i.e., add the constraint $\\sum_{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 8 hours ago
-
$\\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 <= z_i, \\forall i, y>=\\sum_i z_i - (n-1)$. $\\endgroup$ – Ryan Cory-Wright 7 hours ago
-
$\\begingroup$ Related: or.stackexchange.com/q/76/38 $\\endgroup$ – LarrySnyder610♦ 26 mins ago
1 Answer
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).
