# How to transform these conditional constraints to linear integer ones in a more efficient way?

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 ?

• what are you decisions variables? are they binary? – Betty May 19 '20 at 11:55
• 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 – SAH May 19 '20 at 12:50

## 1 Answer

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.

• 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 – SAH May 19 '20 at 21:11
• I'm sorry, but I don't know what you mean when you say I proposed a nonlinear constraint. – prubin May 20 '20 at 15:37
• Doesn't x2.y term in the constraint impose non-linearity to the problem?! @prubin – SAH May 20 '20 at 15:47
• I don't see any multiplication of $y$ and $x_2$. You're not referring to $y\le x_2$, are you?? – prubin May 21 '20 at 16:10
• Sorry, there was a problem with my browser. Now I see them clearly with another browser. Thanks @prubin – SAH May 21 '20 at 16:57