I have a MILP problem. Now I want to include a new constraint to it (upper bound the diagonal elements of an inversed matrix), i.e.,
${Y(x)^{-1}}_{ii}<k_i, \forall i\in\{1,2,...,n\}$
where $Y(x)\in \mathcal{R}^{n\times n}$ and $Y=Y^T$ is always invertible, $x$ is a vecter of $m\;(m<n)$ binary decision variables, which only appears as a affine function in the diagonal element of $Y$, i.e., $Y_{ii}=c_i^Tx+c_{i0}$. All the off-diagonal elements of $Y$, and $c_i^T$, $c_{i0}$, $k_i, \forall i\in\{1,2,...,n\}$ are known. Does anyone know how to deal with this kind of constraints? Any help would be appreciated.
I have 2 possible solutions but don't know which one is better in terms of efficiency.
Add a matrix $Z=Y^{-1}$ and expend the inverse relationship $YZ=I$ into $n^2$ linear equality constraints, i.e., $\sum_iY_{pi}Z_{q1}=1/0$ for all the combination of $p,q$ and set $Z_{ii}<k_i$. Although in this way the orginal constraint can be converted into $n^2$ linear (through big M) equality constraints and $n$ inequality constraint, it seems to be inefficient.
Rewrite the original constraint as: $e_i^T{Y(x)^{-1}}e_i<k_i, \forall i\in\{1,2,...,n\}$ where $e_i^T=(0,...,1,0,...,0)$. Using Schur complement, this can be convert to a linear matrix inequality (LMI), $\forall i$. But I am not sure if I can include binary varialbes into LMI? Furthermore, this problem would then become mixed integer-SDP, which is harder to solver then MILP.
Any comments are welcome.
If you go for an LMI approach, there are two mixed-integer semidefinite programming solvers available in the modelling language YALMIP (disclaimer, developed by me).
https://yalmip.github.io/solver/bnb/
https://yalmip.github.io/cutsdpsolver
As you say though, moving from MILP to MISDP is typically something you only do if you absolutely have to, but it might be that you have no choice (I would test both strategies you listed, both are easy to do in YALMIP, the first strategy can be done automatically using the command binmodel if you just want to test)
Note that the LMI approach only works if $Y(x)$ is positive definite, being non-singular is not enough.