Ask HN: Solved this problem with stochastic beam search. Any alternatives?

I have the following problem:<p>Givens:<p>There are N types of item.<p>For each item type, M instances exist.<p>Each item instance has two integer attributes, A and B.<p>There is some subset S of item types (i.e. a set of up to N distinct item types)<p>Goal: For a given set S, choose the optimal set R of item instances corresponding to the set (i.e. one item instance in R for each item type in S).<p>Let SUM be the sum of all the values of A in R. Let MEAN be the mean of all the values of B in R.<p>The optimal set is one that meets one of the two following conditions (depending on which one we are looking for at the give moment)<p><pre><code> a) SUM is the minimum possible, and MEAN is within some range. b) MEAN is the maximum possible, and SUM is within some range. </code></pre> My approach: Two-part stochastic beam search. In the first part, the objective function is based on the distance from the center of the constraint space (i.e. the space where SUM or MEAN is within the acceptable range). This goes until we have k states within the constraint space. In the second part, the objective function is defined by the qualification for an "optimal set" defined in the paragraph above. At each step, only successor states within the constraint space are considered. Iteration continues until MAX_STEPS is exceeded.<p>What other approaches would you consider for solving this problem? One issue I have with the current approach is that, while it does generate results that satisfy the conditions, the results are not optimal, in the sense that I can run the algorithms several times and get different answers.