Closest classical (heuristic) optimization problem in literature to the problem I have given

Question

Thanks in advance for the help.

Throughout optimization and heuristic search literature there are several classical problems including, but not limited to, traveling salesman, 8 queens, knapsack, etc. Consider the following optimization problem that I have given below.

Let $X$ be a discrete solution (specifically a set of elements) and $f(X)$ an evaluation function that I would like to optimize. $X$ may have any number of elements as long as $\sum_{x \in X}x = P$ where $P \in N^+$ and $\forall x \in X, x \in N^+$.

I'm interested in using a heuristic to solve this specific problem and would like to read up about how problems of this type have been solved in literature. This problem seems to be relatively simple and therefore I would assume that it can be classified as a specific case of a much more general, classical and well studied problem such as the traveling salesman problem. Is this the case, and if so, what would the problem be? If not, is anyone aware of work that has been done on problems of this type or similar? (It is somewhat similar in someways to the knapsack problem but I'm hoping for something much similar or a classical problem that the problem I have given reduces to).

edit: I should also add that the order of the elements $x$ within the set $X$ impacts the value of $f(X)$. There are no constraints, however, on this ordering. One solution might be 2,1,2,3; another 2,1,3,2; and finally another 4,4

Answer 1

If your problem is very similar to a finding a solution to the knapsack problem, you might try using a backtracking algorithm. They tend to work "pretty fast" (i.e. still exponential, but much faster than a simple brute force search). Backtracking tends to work well when you need to find an exact answer and there is an easy way to determine whether or not a possible solution tree can be abandoned. Backtracking also has the benefit of finding all the possible solutions.

Greedy algorithms only really work for things like the Travelling Salesman problem, where you are trying to minimize or maximize a value, and even then they are only good starting points, as they do not actually find the best solution. A greedy algorithm with a backtracking algorithm would set you up pretty well.

Tabu searches appear to work well when you are trying to get within a range of values, like the knapsack problem adjusted so that instead of adding up to an exact number, you have to add up to any number within a range. Tabu searches also have the problems of not necessarily finding all possible solutions and occasionally getting stuck inside a loop.

I don't know a lot about VNS, but it seems to be generally applicable to a lot of situations.

From what I can gather, I would suggest either using backtracking or VNS.

Answer 2

If the properties of the function $f(X)$ is unknown (ie, any relations between its value is unknown), the only way - complete listing of all possible combinations of elements.

If the function increases with any new element adding then some optimization methods became available. In particular, if function increases, moreover for large items - to a greater extent, it becomes possible "greedy" brute force methods, with which to carry on sorting in descending order. That case can be considered as variant of knapsnack problem.