3
$\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$
  • $\begingroup$ what are you decisions variables? are they binary? $\endgroup$ – Betty May 19 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 at 12:50
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.

| improve this answer | |
$\endgroup$
  • $\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 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 at 15:37
  • $\begingroup$ Doesn't x2.y term in the constraint impose non-linearity to the problem?! @prubin $\endgroup$ – SAH May 20 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 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 at 16:57

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.