# Can I tell a MILP solver to prefer solutions with fewer fractions?

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?

• Did you mean two optimal solutions? The answers below will let you minimize the number of fractional values. If you want to pick the optimal solution with fewest fractions, you need to use a lexicographic multiobjective model, with the original objective primary and one of the approaches below generating the secondary objective.
– prubin
Commented Jun 28 at 15:51
• How really can you get the first and the second solutions? Is the model a PIP or MIP? Commented Jun 28 at 16:36

## 2 Answers

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$$.

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)