1
$\begingroup$

I got a model of MILP but I want to add extra constraints.

$$ \min\{c^T x + d^T y:Ax+By=a,Cx+Dy \leq b,x,y\geq0,y \in \{0,1\}\} $$

More specificlly, I got extra original constraints with indicator function in the following form

$$ \frac{1}{N}\sum_{i=1}^{N}\mathbb{I}(z\mu_i-1) \geq 1-\epsilon,Ex+Fy+Gz\geq0 $$ where $z$ is extra matrix variable to be optimized.

The indicator function can be approximated by logistic function $g(x)=\frac{e^{-x/{\epsilon}}}{1+e^{-x/{\epsilon}}}$, transforming the above constrints to

$$ \frac{1}{N}\sum_{i=1}^{N}g(z\mu_i-1) \geq 1-\epsilon $$

So how could the resulting problem be solved?

$\endgroup$
5
  • 1
    $\begingroup$ Please give your definition of $\mathbb{I}(x).$ $\endgroup$
    – prubin
    Commented Apr 8 at 15:25
  • $\begingroup$ @prubin $\mathbb{I}(x)$ is the indicator function which takes 0 when $x$ is greater than 0 and 1 otherwise. $\endgroup$ Commented Apr 17 at 1:23
  • 1
    $\begingroup$ What are $z$ and $\mu_i$? On the one hand, you say $z$ a matrix variable. On the other hand, the constraint $Ex + Fy + Gz \geq 0$ indicates it's a vectorial variable, i.e. $z \in \mathbb{R}^n$. $\endgroup$
    – joni
    Commented Apr 17 at 9:30
  • $\begingroup$ @KaimingZhang what are you modelling with the indicator constraint? Should it be interpreted as something along the lines of "$z\mu_i\leq 1$ for $1-\epsilon$ percent of the $N$ constraints? $\endgroup$
    – Sune
    Commented Apr 19 at 9:15
  • $\begingroup$ @Sune Yes, that is the case. $\endgroup$ Commented Apr 25 at 3:22

1 Answer 1

0
$\begingroup$

I think you can achieve what you want as follows: Let $u_i$ be upper bounds on $z\mu_i$, for all $i=1,...,N$. Let furthermore $\alpha_i$ be binary variables equalling one, if $z\mu_i>1$ is allowed. Then you may formulate your requirement as \begin{align} &z\mu_i\leq 1+(u_i-1)\alpha_i,&&\text{for } i=1,..,N&(1)\\ &\sum_{i=1}^N\alpha_i\leq \lfloor N\epsilon\rfloor&&&(2) \end{align} This way, you allow violation of only $N\epsilon$ of the constraints ($\alpha_i=1$), stating that at least $N(1-\epsilon)$ of the constraints must be satisfied. You can round down the right hand side of (2) as the left hand side is an integer.

$\endgroup$
2
  • $\begingroup$ Thank you. I got what you mean. $\endgroup$ Commented Apr 29 at 2:49
  • $\begingroup$ @KaimingZhang, if it solves your problem, then please accept the answer for future visitors. $\endgroup$
    – Sune
    Commented Apr 29 at 6:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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