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's gravatar image

LinYuan
80617
accept rate: 0%

edited 06 May '15, 19:24

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

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.\]

link

answered 06 May '15, 19:41

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

edited 07 May '15, 11:25

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

[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\}.\]

link

answered 08 May '15, 09:42

Mike%20Trick's gravatar image

Mike Trick ♦♦
1.0k16
accept rate: 21%

edited 08 May '15, 10:24

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412

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
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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

Asked: 05 May '15, 16:06

Seen: 1,031 times

Last updated: 12 May '15, 11:39

OR-Exchange! Your site for questions, answers, and announcements about operations research.