Dear OR experts, I am confronted with the following condition in my problem, but I have no idea how to linearize it. Variable \(x\) and \(z_i\) are binary, \(f(y)\) is a linear function of \(y = \sum\limits_{i}{z_i}\), \(c\) is an integer constant. \(z_i=1\) means facility \(i\) is open. So \(y\) is the number of open facilities. If only and if \(f(y)=c\), then \(x=1\), which means that if \(f(y)\neq c\),then \(x=0\). Do you know how to represent this relationship in a linear expression? Do I need to introduce an additional binary variable or big \(M\)? Thank you very much. Any suggestions will be greatly appreciated. asked 05 May '15, 16:06 LinYuan
showing 5 of 8
show 3 more comments

Given that \(y \in \{L, \dots, U\}\) (it does not matter how it is obtained), \(x\) is a binary variable and \(c \in \{L, \dots, U\} \) is an integer constant, the condition \(x = 1 \iff f(y) = c\) can be formulated as follows. Introduce additional binary variables \(s\) and \(t\), along with the following constraints: \[s + t + x = 1\] \[f(y) \ge c + (Lc)s + t\] \[f(y) \le c  s + (Uc)t.\] answered 06 May '15, 19:41 Paul Rubin ♦♦ Dear Prof. Rubin, This is fantastic! No big M, and also linear constraints. Thank you very much! And the mathematical description of this proposition really insprises me a lot.
(06 May '15, 19:56)
LinYuan
I am not criticizing Paul Rubin's answer. But to LinYuan, Paul's solution looks like Big M to me, where Big M is based on L and U, i.e., big enough M.
(07 May '15, 11:15)
Mark L Stone
I like to think of it as "notsobigM", but it's definitely the same sort of constraint as a "big M" constraint. One performance key is to make \(L\) and \(U\) the actual minimum respectively maximum values that \(f(y)\) can take. Also, I just fixed a typo: I had \(y\) where I meant to say \f(y)\).
(07 May '15, 11:25)
Paul Rubin ♦♦
If the range \([L, U]\) turns out to be wide enough that these constraints are loose/lead to "big M" performance problems, the only alternative I can think of is combinatorial Benders decomposition (which sometimes works, but is not for the faint of heart).
(07 May '15, 11:27)
Paul Rubin ♦♦
Yes, I see that they are big\(M\) approach. In my problem, I can find a quite tight range \([L, U]\). So these three constraints work well. Thank you. Dr. Rubin, you just mentioned combinatorial Benders Decomposition. Can Benders be used in this logic condition? I thought it would require a series of master problem and sub problem. What is the basic idea in implementing Benders Decomposition? Thanks.
(07 May '15, 17:56)
LinYuan
For a description of combinatorial Benders, see: Codato, G. & Fischetti, M. "Combinatorial Benders' Cuts for MixedInteger Linear Programming", Operations Research, 2006, 54, 756766. In my answer, I use \(s\) and \(t\) in essence to turn inequalities "on" or "off". Combinatorial Benders replaces that with a master problem/subproblem decomposition with those constraints in the subproblem. For a given master solution, if \(s=1\) then only the constraint \(f(y) \le c1\) appears in the subproblem and so on.
(07 May '15, 18:12)
Paul Rubin ♦♦
showing 5 of 6
show 1 more comments

[This was tried to be posted by Slavko.] I have tried several times to post my answer but akismet wasn't allow me to do it. My proposition was: If \( c > 0 \) and \( f(y) > 0 \), then the constraint can be formulated as follows. \[\left\{ \begin{align} f(y) \ge x c \\ f(y) \le x c \end{align} \right\}.\] answered 08 May '15, 09:42 Mike Trick ♦♦ Paul Rubin ♦♦ 1
This would limit \(f(y)\) to only two possible values: \(c\) (if \(x=1\)) or 0 (if \(x=0\)).
(08 May '15, 10:26)
Paul Rubin ♦♦
Yes, indeed... So, below is a correction, which is based on Your earlier post. In those constraints \(u\) and \(v\) are binary and \( M \) is enough big. \[ f(y) \ge c uM +v \\ f(y) \leq c +vMu \\ u+v+x=1 \]
(12 May '15, 11:23)
Slavko
@Slavko, Thanks for your consideration and comments. Yes, I am expected your constraints will work better, because binary variables \(u\) and \(v\) don't appear in the same constraint. But I think it need to be improved, see a small counterexample, \(f(y)=c=1, M=2\), we have \[1 \geq 13u\] \[1 \leq 1+v\] in which \(u=1, v=0, x=0\) is satisfied. However, we require that \(x=1\) in this case.
(12 May '15, 11:33)
LinYuan
1
Yes, it works well in this time. Just now, I didn't refresh my browser, my last comment was based on the previous one. Thank you.
(12 May '15, 11:39)
LinYuan

Just now, I have an idea, \(M(1x) \geq f(y)c\) and \(M(x1) \leq f(y) c\), these two inequalities can ensure that when \(f(y) \neq c\), then \(x=0\); but when \(f(y) =c \), \(x = 0, 1\) is both OK. Do you have some other ideas to improve these inequalities, or introduce other constraints? Thank you.
This condition seems very strict. But it exists exactly in my formulation. Do you have some ideas? I will really really appreciate that.
Is \(y\) a scalar binary variable or a vector of binary variables?
@Paul Rubin, \(y\) is a scalar binary variable (actually, a sum of a vecor of binary variables, but the value will be 1 or 0). Thank you very very much.
If \(y\) is scalar, then you should know which value(s) of \(y\) yield \f(y)=c\). If neither does, \(x=0\). If both do, \(x=1\). If only \(y=1\) does, \(x = y\). If only \(y = 0\) does, \(x = 1  y\). This is too simple, so perhaps I am misunderstanding the question?
@Paul Rubin, Thanks for your comments. But the question is, we do not know which value(s) of \(y\) yield \(f(y) = c\).
In my problem, \(y=\sum\limits_{i}{z_i}\) is the sum of a vector of binary variables, in which \(z_i\) is also a decision variable. So which value yield \(f(\sum\limits_{i}{z_i}) = c\) is not easily determined. And the supplement of my last comment, \(y = \sum\limits_{i}{z_i}\) can be any integer less than the number of \(z_i\), not just 0 or 1, representing the number of facilities that are open. In this way, how to express this constraint? Thank you.
There's your problem. I believe you originally said \(y\) is binary, but it is not; it is a nonnegative integer variable. That changes the nature of the question. I see that you have corrected it in an edit.
@Paul Rubin, Dear Prof. Rubin, yes, the description is now correct. \(y\) is an nonnegative integer variable. I am really sorry for the confusion incurred. We can think the problem as, if right \(c\) facilities are open, then \(x = 1\). Do you have some ideas to express this?