[R] Solving an optimization problem: selecting an "optimal" subset

[Hans W Borchers]

Dimitri Shvorob <dimitri.shvorob <at> gmail.com> writes:

>
> > This is a "subset sum" problem and has been discussed here in December 
> 
> Thanks a lot! Will investigate.
> 
> > Can you settle for an approximate solution? 
> 
> Absolutely.

You can use the script from the thread "subset sum problem" to find
approximate solutions. The trick is to round and multiply the numbers in
the set with some power of 10 and then solve as an integer problem. I did
that for the example and found a solution 2.000002 for target 2.0 and with
a subset of length 15.

> > Rcplex: This is a combinatorial problem and cannot be formulated as a
> > quadratic optimization problem. 
> 
> If the objective function can fit the pattern, we need to find the set of n
> coefficients, taking values 0 or 1, summing to m, for the m-out-of-n
> problem. 'Binary' version of Rcplex apparently would be able to handle that.

Right, you can force CPLEX to perform the exhaustive search itself, I would
not call this "quadratic programming", but it might be quite fast.

Taking my example "set.seed(8232); x <- runif(100)" with target value 2.0 and
subsets of fixed length 10, I sent a GAMS script modeling this problem to the
NEOS solvers and it returned the solution

    i <- c(7,10,25,32,45,76,77,78,81,96)
    sum(x[i])
    # [1] 2.000006

within 0.004 seconds of execution time for the BARON MINLP solver.

> > It is NP-hard and cannot be solved via Dynamic Programming. 
> 
> Why not? Discretize the [0, sum(x)] range and solve an m-step DP problem.
> The value function would minimize the distance from s, and penalize
> too-short (m* < m) subsets.

No, this will not work.

Hans Werner

> Thanks again! 
> 
>