6
$\begingroup$

A model contains constraints of the following form

$R(k) \leq X(k) G(k)$

where $X(k)$ binary and $G(k)$, $R(k)$ non-negative variables.

The index $k$ runs from $1$ to $50$.

I linearise the equations as they are products of binary and continuous variables.

The question is, is there anything I can exploit to tighten the region these constraints define?

$\endgroup$
7
$\begingroup$

You want to enforce $X(k) = 0 \implies R(k) = 0$ and $X(k) = 1 \implies R(k) \le G(k)$. You can use indicator constraints for that.

Alternatively, a straightforward big-M formulation yields \begin{align} R(k) &\le M_1(k) X(k) \tag1 \\ R(k) - G(k) &\le M_2(k) (1 - X(k)) \tag2 \\ \end{align}

A natural choice for $M_1(k)$ is a small constant upper bound $\bar{G}(k)$ on $G(k)$, and a natural choice for $M_2(k)$ is $\bar{G}(k) - 0$. But notice that you can do better because $M_2(k)$ needs to be an upper bound on $R(k)-G(k)$ only when $X(k)=0$; in that case, $(1)$ forces $R(k)=0$, so you can take $M_2(k)=0$:

\begin{align} R(k) &\le \bar{G}(k) X(k) \tag1 \\ R(k) &\le G(k) \tag2 \\ \end{align}

Depending on other constraints in your model, you might be able to tighten further.

$\endgroup$
1
  • $\begingroup$ Hi Rob. Thank you very much again! Your idea was very useful. Through further tightening I was able to solve my problem, which otherwise "refused" to converge to the global optimum. $\endgroup$ – Clement Apr 23 at 16:21

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.