# [R] Solving an optimization problem: selecting an &quot; optimal&quot; subset

Hans W Borchers hwborchers at googlemail.com
Tue Feb 2 13:07:44 CET 2010

```
Erwin Kalvelagen-2 wrote:
>
> Hans W Borchers <hwborchers <at> googlemail.com> writes:
>>     # Prepare inputs for MILP solver
>>     obj <- c(rep(0, n), 0, 1, 1, 0)
>>     typ <- c(rep("B", n), "B", "C", "C", "B")
>>     mat <- matrix(c(        s, -z, -1, 1, 0,    # a = a_p + a_m
>>                     rep(0, n), 1, 0, 0, 0,      # constant term
>>                     rep(0, n), 0, 1, 0, -M,     # a_p <= M * d0
>>                     rep(0, n), 0, 0, 1, M,      # a_m <= M * (d0-1)
>>                     rep(1, n), 0, 0, 0, 0),     # subset size <= k
>>         nrow=5, byrow=T)
>>     dir <- c("==", "==", "<=", "<=", "<=")
>>     rhs <- c(0, 1, 0, M, k)
>>     max <- FALSE
>
> You can drop the binary variable d0.
> The condition "one of a_p,a_m is zero" holds
> automatically as we are minimizing a_p+a_m.
>
> ----------------------------------------------------------------
> Erwin Kalvelagen
>
>

Right; for me adding M and d0 is kind of a reflex, but that is only
necessary when  a_p + a_m  is used as an intermediate result.

One more remark: I saw some spurious behavior with both solvers (Rsymphony,
Rglpk) -- that is, slightly different results in different runs.  It could
relate to the tolerance with which these solvers compare and identify
solutions.  At the moment I don't know how to change the tolerance as a
parameter.

I guess this will not happen when using a more powerful solver such as
CPLEX.

Hans Werner

--
View this message in context: http://n4.nabble.com/Solving-an-optimization-problem-selecting-an-optimal-subset-tp1446084p1459843.html
Sent from the R help mailing list archive at Nabble.com.

```