In the context of a MILP, I have variables $x_{t} \in \mathbb{R}$ which have a lower bound $x^{min}$ and an upper bound $x^{max}$.

Let $I_{1} = [x^{min},a_{1}], I_{2} = ]a_{1}, a_{2}], ..., I_{n} = ]a_{n-1}, x^{max}]$ form a partition of $[x^{min}, x^{max}]$.

The behaviour of the system I want to model depends on which $I_{p}$ the value of each $x_{t}$ belongs to, therefore I want other variables $y_{p,t} \in \{0,1\}$ such that $y_{p,t} = 1 \iff x_{t} \in I_{p}$.

The variables $y_{p,t}$ appear in the objective function in a sum of the type $$\sum_{t} \sum_{(p,q) \in \{1,n\}^2} c_{p,q}*y_{p,t}*y_{q,t-1}$$ where the $c_{p,q}$ are constant, positive factors1. We want to minimize the objective function, so the $y_{p,t}$ will be minimized by the solver.

I came up with the following constraints for the $y_{p,t}$ variables but I am not entirely satisfied and wondering if I could do better.

For each interval $I_{p} = ]a_{p-1}, a_{p}]$ we would have the following constraints on new variables, $z^{ub}_{p,t}$ and $z^{lb}_{p,t} \in \{0,1\}$ :

$$ z^{lb}_{p,t} \geq \frac{x_{t}-a_{p-1}}{M}$$ $$ z^{ub}_{p,t} \geq \frac{a_{p}-x_{t}}{M} + \epsilon$$ where $M$ and $\epsilon$ are appropriate constants.

The case $p = 0$ is different but obtained by adding epsilon to the first constraint right hand side as well.

Then $y$ would be obtained with a logical "and" between $z^{lb}$ and $z^{ub}$ : $$ y_{p,t} = z^{lb}_{p,t}*z^{ub}_{p,t} $$ which is easily linearized.

The reasons I am not satisfied with this, although I believe it should work, is both having to use $M$'s and $\epsilon$'s and having to linearize the logical "and" constraint. Is there a smarter way to design these constraints ?

Hopefully I provided enough information. I didn't include the whole model because it's quite long and I don't think it would be useful. But please let me know if that's not the case.

1 : I know this is not linear, but it is easily linearized and I think it is clearer this way.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.