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

Dimitri Shvorob dimitri.shvorob at gmail.com
Sat Jan 30 14:25:39 CET 2010

> 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? 


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

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

Thanks again! 

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

More information about the R-help mailing list