1
$\begingroup$

For me $a,c\in[0,1]$ and $\epsilon>0$ is small (say $0.01$).

Is it possible to set this condition

$$c\leq\max\bigg(\frac{(a-\epsilon)}{(1-\epsilon)}, 0\bigg)$$

in real linear program?

This does not work $$\frac{(a-\epsilon)}{(1-\epsilon)}\leq d$$ $$0\leq d$$ $$c\leq d.$$

Essentially I want $d=0$ if $\frac{(a-\epsilon)}{(1-\epsilon)}<0$ else set $d=\frac{(a-\epsilon)}{(1-\epsilon)}$ and set $c\leq d$ which is equivalent to $c\leq d$ where $d=0$ if $a<\epsilon$ else $d=\frac{(a-\epsilon)}{(1-\epsilon)}$. How do I do that?

$\endgroup$
  • $\begingroup$ See leandro-coelho.com/how-to-linearize-max-min-and-abs-functions $\endgroup$ – YukiJ Apr 23 '18 at 8:40
  • $\begingroup$ @YukiJ how do you penalize S^- and S^+ in a real linear program? $\endgroup$ – T.... Apr 23 '18 at 8:41
  • $\begingroup$ Only way seems to be $bS^- + (1-b)S^+$ where $b\in\{0,1\}$ which maked it MILP and not a real linear program. $\endgroup$ – T.... Apr 23 '18 at 8:48
  • $\begingroup$ what are the variables in this constraint? $\endgroup$ – LinAlg Apr 23 '18 at 13:11
  • $\begingroup$ @LinAlg only $a,c$ are variables $\epsilon$ is fixed. $\endgroup$ – T.... Apr 23 '18 at 13:12
3
$\begingroup$

The nonlinear constraint $$x\leq\max\bigg(\frac{y-\epsilon}{1-\epsilon}, 0\bigg)$$ where $x,y$ are variables and $\epsilon$ is a parameter, cannot be represented with purely linear constraints since it is not convex. You need an extra binary variable $z$ that indicates which of the two terms in the max is active, and a prespecified upper bound $M$ on the absolute value of the first term of the max expression. Then you can state this problem as: $$\begin{align}x &\leq \frac{y-\epsilon}{1-\epsilon} + zM \\ x &\leq 0 + (1-z)M \\ z &\in \{0,1\}. \end{align}$$

$\endgroup$

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.