[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?
Absolutely.
> 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