2
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – prubin
    Commented Jun 28 at 15:51
  • $\begingroup$ How really can you get the first and the second solutions? Is the model a PIP or MIP? $\endgroup$
    – A.Omidi
    Commented Jun 28 at 16:36

2 Answers 2

6
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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)

$\endgroup$
0

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.