# To linearize a logical constraint

 0 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 80●6●17 accept rate: 0% Just now, I have an idea, $$M(1-x) \geq f(y)-c$$ and $$M(x-1) \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. (06 May '15, 10:14) LinYuan This condition seems very strict. But it exists exactly in my formulation. Do you have some ideas? I will really really appreciate that. (06 May '15, 17:09) LinYuan Is $$y$$ a scalar binary variable or a vector of binary variables? (06 May '15, 17:49) Paul Rubin ♦♦ @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. (06 May '15, 17:52) LinYuan 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? (06 May '15, 17:58) Paul Rubin ♦♦ @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. (06 May '15, 18:57) LinYuan 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. (06 May '15, 19:28) Paul Rubin ♦♦ @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? (06 May '15, 19:45) LinYuan showing 5 of 8 show 3 more comments

 1 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 + (L-c)s + t$ $f(y) \le c - s + (U-c)t.$ answered 06 May '15, 19:41 Paul Rubin ♦♦ 14.6k●5●13 accept rate: 19% 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 "not-so-big-M", 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 Mixed-Integer Linear Programming", Operations Research, 2006, 54, 756-766. 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 c-1$$ appears in the subproblem and so on. (07 May '15, 18:12) Paul Rubin ♦♦ showing 5 of 6 show 1 more comments
 0 [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 ♦♦ 1.0k●1●6 accept rate: 21% Paul Rubin ♦♦ 14.6k●5●13 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 +vM-u \\ 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 1-3u$ $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
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×65
×7
×2
×1

Seen: 1,193 times

Last updated: 12 May '15, 11:39