I am trying to find the best possible fixed length (in this case len=5) combination from a given set.
Each item in this set has a collection of attributes that contribute to its "validity" value and attributes that contribute to its "objective" value.
The objective and validity values exist in the range 0 <= value <= 20 and there is a rough trade-off between the two.
A full combination must meet or exceed a given validity threshold to be considered, and assuming this is met the best combination is defined as the maximum possible objective value.
The approach I'm currently taking follows the Branch and Bound method, which requires an upper bound estimation function that takes a partial combination, the remaining items in the set that could complete the combination, and produces the objective upper bound given the partial combination. This is compared to the currently found best solution, and if it does not exceed this solution's objective value, the partial combination is discarded.
My initial approach to the upper-bound estimator involves selecting 5 - length of partial combo items from the remaining set with the highest combined validity & objective values, assuming the ideal distribution of each, and returning this as my upper-bound estimation.
I would prefer a more accurate upper-bound estimation that takes into account the needed remaining validity value needed so I do not consider partial combinations that would produce validity values far and above what's needed, but would never exceed the objective value of previously discovered solutions.
One approach I had for this involved determining the remaining validity value I needed from the partial combo, dividing it by 5 - length of partial combo, then searching the remaining items for one that met or exceeded this averaged needed validity and had the maximum objective value of this filtered set. However, I do not believe that this is provably an upper-bound estimator and could lead to discarding partial combos that could lead to the best solution.
Ultimately what I'm looking for is a proof that this approach is a valid upper-bound estimator, or other approaches/literature that could lead to new techniques.
Thank you all,