Message-ID: <1264857939563-1457390.post@n4.nabble.com>
Date: 2010-01-30T13:25:39Z
From: Dimitri Shvorob
Subject: Solving an optimization problem: selecting an "optimal" subset
In-Reply-To: <loom.20100130T140256-328@post.gmane.org>
> 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.