I have a linear program
$$\max c^T x \text{ s.t. } A x\leq b, x\geq 0.$$
I would like a solution that, among all optimal solutions, has the largest number of integer variables. For example, if the objective is $x_1+x_2+x_3$, and two feasible solutions are $0.5,0.5,0.5$ and $1,0,0.5$, I would like the solver to return $1,0,1/2$. Is there a LP/IP/MIP solver that can do this?
For each variable $x_i \in [0,1]$, define binary variables $y_i^{-},y_i^+$ such that $$ y_i^- = 1 \implies x_i = 0 \quad\text{and}\quad y_i^+ = 1 \implies x_i = 1 $$ This can be linearized as follows: \begin{align} y_i^+ \le x_i &\le 1-y_i^- \tag{1}\\ y_i^+ + y_i^- &\le 1 \tag{2} \end{align} And maximize $\sum_i y_i^+ + y_i^-$. A similar strategy can be used if $x_i$ is integer (and not binary)
Introduce integer variable $y_i$, continuous variable $f_i\in[0,1]$, and binary variable $z_i$ to indicate whether $f_i>0$. Now minimize $\sum_i z_i$ subject to \begin{align} x_i&=y_i+f_i \\ f_i&\le z_i \end{align} The idea is that $y_i$ represents $\lfloor x_i\rfloor$ and $f_i$ represents the fractional part of $x_i$.
