2

This is my first question here. I am working on a binary LP wherein I want to turn on a variable when a condition is met else make it zero. I want to share my formulation with you and need your help in understanding whether my constraint gets the job done.

My main motive is to express the following indicator constraint using the big-M formulation. $$f^{t}_{ls} = 1 \qquad if \sum_{c\in C}f^{t,c}_{ls} \geq d_t\qquad \forall t\in T, ls\in L_s\\ 0\qquad\qquad else\qquad\qquad\qquad\qquad $$

My objective is to minimise the costs incurred $$\textbf{min}\qquad \sum_{c\in C}\sum_{t\in T}\sum_{ls\in L_s}cost(c,ls)f^{t,c}_{ls}$$

To express the indicator constraint in the big-M version, I re-wrote this as follows:

$$\sum_{c\in C}f^{t,c}_{ls} + M(1-f^{t}_{ls}) \geq d_t \qquad \forall t\in T, ls\in L_s$$ where both variables $f^{t,c}_{ls} and f^{t}_{ls}$ are binary and $d_t\in Z^+$.

Could you please let me know if this works? I hope I didn't get anything wrong

Thanks a lot

pancini
  • 19,216
crypto
  • 147

1 Answers1

3

Yes this looks correct, for two reasons.

First, it is a linear formulation.

Second, test your constraint and see what happens in both cases: if $f_{ls}^{tc}=1$, you have $\sum f_{ls}^{tc}\ge d_t$: your are good. If $f_{ls}^{tc}=0$, you have $\sum f_{ls}^{tc}+M\ge d_t$.

The only part that is left is to choose M so that it is as small as possible, while guaranteeing that your inequality holds all the time. A possible choice would be $M=\sum_{t\in T} d_t$, or $M=\max_{t\in T}\{d_t\}$.

Note. The reason why you want $M$ as small as possible is that the bigger it is, the worse your linear relaxation will be, and so the longer the branch and bound will be to solve the model.

Kuifje
  • 9,584
  • I think you must include the subscript c in the variable and moreover, since I want to turn on and off the variable $f^t_{ls}$, I think I need to convert the objective to maximisation. Please correct me if I am wrong – crypto Nov 11 '15 at 16:09
  • Hmm. Not sure why you would want to change your objective. It will not affect the big M constraints. – Kuifje Nov 11 '15 at 16:14
  • The reason is that if $\sum_{c\in C}f^{t,c}{ls} \geq d_t$, then the Big M constraint will look something like $\sum{c\in C}f^{t,c}{ls} - d_t + M \geq Mf^t{ls}$. Lets assume some values in this case. If $\sum_{c\in C}f^{t,c}{ls}$ is 27 and $d_t$ is 25 and M is 100, this means that the big M constraint would now look like $102 \geq 100f^t{ls}$. So, $f^t_{ls}$ may now take 0 or 1. Setting the objective to maximise $f^t_{ls}$ will ensure it is 1 mostly. I hope my explanation isn't crap – crypto Nov 11 '15 at 16:40
  • I am a little confused. Why would you want $f_{ls}^{tc}$ to be 1 mostly? Isn't there a cost every time it is 1 that you want to avoid? Your constraints must not influence your objective function. Your objective function is decided before hand, and then you figure out a way for you constraints to be compatible with your objective function. – Kuifje Nov 11 '15 at 16:48
  • There is a bit of confusion that I'd like to clear. $f^t_{ls}$ is the indicator variable while $f^{t,c}{ls}$ is a binary variable. To turn on the indicator variable the condition $^{t,c}{ls}\geq d_t$ has to be met. So, whenever this condition is true $f^t_{ls}$ will be 1 but in this particular case where $102\geq 100f^{t}_{ls}$, where the condition is true and the indicator variable must be turned on, it can now either take 1 or 0. So, how do we force it to take zero? This is why I thought of changing the objective to maximising the indicator variable. Plz let me know if i need to be precise – crypto Nov 12 '15 at 06:23
  • Ok I think I understand. I think that you shouldn't worry about the value of $f_{ls}^t$ in this case, because it does not affect the objective function, and it does not violate any constraints. In other words, your solver will choose to put the indicator to 1 or 0, it has absolutely no importance here. – Kuifje Nov 12 '15 at 14:28