How to linearize or reformulate an implication constraint that implies that a decision variable belong to an interval?

19 Views Asked by At

I am an electrical engineer who is working in computer network and I need to model my delay with respect to a binary variable $x$ as folow

$\left\{ {\begin{array}{*{20}{c}} {x = 1 \Rightarrow \left( {t - 1} \right)a \le D \le \min \left[ {\underbrace {\left( {t - 1} \right)a + \Delta }_{{\rm{Lower Bound}}},\underbrace {ta}_{{\rm{Upper bound}}}} \right]}\\ {\underbrace {\left( {t - 1} \right)a + \Delta }_{{\rm{Lower Bound}}} \le \underbrace {ta}_{{\rm{Upper bound}}}} \end{array}} \right.$

Here $x$ is some binary decision variable, the decision variable $D$ is the delay and it is bounded both above and below. $\Delta$ here is also a decision variable but it is not binary.

Due to my extensive knowledge and measurement, I know for sure that this delay $D$ must be the minimum between two numbers, that is $\min \left[ {\underbrace {\left( {t - 1} \right)a + \Delta }_{{\rm{Lower Bound}}},\underbrace {ta}_{{\rm{Upper bound}}}} \right]$.

Sadly, I do not have much experience in reformulation of optimazation problem.

Please help me with this,

Thank you for you enthusiasm !

Note The second constraint ${\underbrace {\left( {t - 1} \right)a + \Delta }_{{\rm{Lower Bound}}} \le \underbrace {ta}_{{\rm{Upper bound}}}}$ here is just a sanity check from an engineering point of view to make sure that the decision variable $\Delta$ does not get to big.

1

There are 1 best solutions below

0
On BEST ANSWER

Suppose $\underline{D} \le D \le \overline{D}$ and $\Delta \ge \underline{\Delta}$ for some constants $\underline{D}$, $\overline{D}$, and $\underline{\Delta}$. You can linearize the implication $$x = 1 \implies (t-1)a \le D \le (t-1)a + \Delta$$ via big-M constraints \begin{align} (t-1)a - D &\le ((t-1)a - \underline{D})(1-x) \\ D - (t-1)a - \Delta &\le (\overline{D} - (t-1)a - \underline{\Delta})(1-x) \end{align}