I am trying to think of contraint(s) that can linearize constraint below.
$\sum_{T} \sum_{TR} Z_{(T,D)}* Y_{(TR,T)} \leq CAP_{(D)} \forall D$
Both Z nad Y are Binary Variables and CAP is capacity parameter.
I tried to apply big M but without luck.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ you need to linearize each product, so you get $\sum_ t \sum_{tr} x_{t,d,rt} \leq cap(d)$ $\endgroup$LinAlg– LinAlg2020-12-09 15:38:07 +00:00Commented Dec 9, 2020 at 15:38
-
$\begingroup$ Yeah I was trying to do it without introducing third variables with three indices to keep the complexity of the algorithm minimal, so do you mean I need a third variable ? $\endgroup$Basil Abu Mallooh– Basil Abu Mallooh2020-12-11 16:17:51 +00:00Commented Dec 11, 2020 at 16:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
Although the usual linearization of a product of two binary variables requires three inequalities, you can get by with only one here. You can enforce $(Z \land Y) \implies X$ via linear constraint $Z + Y - 1 \le X$.
-
$\begingroup$ I don't understand how this works, I will try to give some context, Z gives value of 1 if truck t is used for distribution centre d and y gives value of 1 if trip t is utilized for truck t , i want to give capacity constraint thus : 40* $\sum_{T} \sum_{TR} Z_{(T,D)}* Y_{(TR,T)} \leq CAP_{(D)} \forall D$ $\endgroup$Basil Abu Mallooh– Basil Abu Mallooh2020-12-11 16:10:42 +00:00Commented Dec 11, 2020 at 16:10
-
$\begingroup$ I think I Got you , I need to introduce third binary variable X and use it in the original constraint right? $\endgroup$Basil Abu Mallooh– Basil Abu Mallooh2020-12-11 16:27:24 +00:00Commented Dec 11, 2020 at 16:27
-
$\begingroup$ Yes, like in @LinAlg's comment. $\endgroup$RobPratt– RobPratt2020-12-11 16:42:22 +00:00Commented Dec 11, 2020 at 16:42