2
$\begingroup$

The conditional constraints A and B can be transformed to a set of linear integer constraints as follows:

A) $\text{if} \ x_1=0 \ \text{then} \ d_1=1 \ \text{else} \ d_1= 0\\ x_1\in {\rm I\!R}^{\geq 0} , d_1 \in \{0,1\}, M=10^6, m=10^{-6}$

transformed to

$\qquad \text{A1)} \quad m(1-d_1) \leq x_1 \leq M(1-d_1)$

B) $\text{if} \ x_2 < K \ \text{then} \ y= x_2 \ \text{else} \ y \leq K;\\ x_2,y \in {\rm I\!R}^{\geq 0}, d_2 \in \{0,1\}, \\ K \text{ is positive constant}$

transformed to

$\qquad \text{B1)}\ y \leq K $

$\qquad \text{B2)}\ {-M} \cdot (1-d_2) \leq x_2 - K \leq M \cdot d_2$

$\qquad \text{B3)}\ {-M} \cdot d_2 \leq x_2 - y \leq M \cdot d_2 $


Q1) Is the above transformation correct?

Q2) How can I formulate A and B in a more efficient way (such as convex-hull) rather than the big-M method ?

$\endgroup$
2
  • $\begingroup$ what are you decisions variables? are they binary? $\endgroup$
    – Betty
    May 19, 2020 at 11:55
  • $\begingroup$ In the first set of constraints (A and A1): x1 is a non-negative continuous decision variable and d1 is a binary indicator decision variable. In the second set of constraints (B,B1,B2 and B3), x2 and y are non-negative continuous decision variables , d2 is a binary indicator decision variable and K is a positive constant. M / m are relatively large / small constants of the Big-M approach. @Betty $\endgroup$
    – SAH
    May 19, 2020 at 12:50

1 Answer 1

2
$\begingroup$

I don't think you can improve on A1 (which looks correct), other than perhaps tightening the bounds $M$ and $m$ (which would be dependent on the specifics of the problem). Regarding B, would the solver prefer larger values of $y$ over smaller values? (Again, this is problem dependent.) If so, you could eliminate the use of a binary variable and just use the constraints \begin{equation*}y\le x_2\\y \le K\end{equation*}(in which I'm assuming that your $k$ and $K$ are the same thing). If not, I think you need a big-M formulation, and yours looks correct.

$\endgroup$
5
  • $\begingroup$ Yes, K and k are the same. However, the constraint you have proposed is non-linear and I am seeking for a linear transformation. On the other hand, I am looking for a more efficient method such as convex-hull as suggested here : or.stackexchange.com/questions/76/… @prubin $\endgroup$
    – SAH
    May 19, 2020 at 21:11
  • $\begingroup$ I'm sorry, but I don't know what you mean when you say I proposed a nonlinear constraint. $\endgroup$
    – prubin
    May 20, 2020 at 15:37
  • $\begingroup$ Doesn't x2.y term in the constraint impose non-linearity to the problem?! @prubin $\endgroup$
    – SAH
    May 20, 2020 at 15:47
  • $\begingroup$ I don't see any multiplication of $y$ and $x_2$. You're not referring to $y\le x_2$, are you?? $\endgroup$
    – prubin
    May 21, 2020 at 16:10
  • $\begingroup$ Sorry, there was a problem with my browser. Now I see them clearly with another browser. Thanks @prubin $\endgroup$
    – SAH
    May 21, 2020 at 16:57

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.

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