1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.