Looking for a multidimensional optimization algorithm
Description of the problem
- There are different ones
categories
that contain an arbitrary amountelements
. - There are three different
attributes
A, B and C. Each element has a different distribution of theseattributes
. This distribution is expressed in terms of a positive integer value. For example, element 1 has attributesA: 42 B: 1337 C: 18
. The sum of these attributes does not match the elements. Some elements are more important than others.
Now the problem:
We want to select exactly one item from each category so that
- We will push a specific threshold on attributes A and B (moving is also possible, but not required)
- when getting the maximum amount of C.
Example: we want to hit at least 80 A and 150 V in total across all selected elements and as much C.
I have thought about this problem and cannot come up with an efficient solution. The sample sizes are around 15 categories, of which each contains up to ~ 30 elements, so working flawlessly is not very efficient as there are potentially 30 ^ 15 possibilities.
My model is that I think of it as a tree with a depth of the number of categories. Each depth level represents a category and gives us the choice of choosing an item from that category. On going through a node, we add the attributes of the presented element to our sum that we want to optimize.
If we hit the same attribute combination multiple times at the same level, we will merge them so that we can remove multiple computations of already computed values. If we reach a level where one path is less significant in all three attributes, we will no longer follow it from there.
However, in the worst case, this tree still has ~ 30 ^ 15 nodes in it.
Can any of you think of an algorithm that can help me solve this problem? Or could you explain why you think there is no algorithm for this?
source to share
This question is very similar to the variant of the knapsack problem . I would start by looking at solutions to this problem and see how well you can apply it to your stated problem.
source to share
My first inclination is trying to fork and tie. You can do it width first or depth first and I prefer depth first because I think it is cleaner.
To put it simply, you have a tree-walking routine walk
that can list all the possibilities (it might only have a 5-level nested loop). It is complemented by two things:
-
At every step, he monitors
cost
the moment when the cost can only increase. (If the cost can also decrease, it is more like finding a minimax game tree.) -
The procedure has an argument
budget
and does not look for any branches where the cost may exceed the budget.
Then you have an outer loop:
for (budget = 0; budget < ... ; budget++){
walk(budget);
// if walk finds a solution within the budget, halt
}
The amount of time it takes is exponentially in the budget, so simpler cases take less time. The fact that you run the search repeatedly doesn't matter much, because each budget level takes the same or longer time as all previous levels.
Combine this with some kind of heuristic order in which you look at branches, and that might give you an acceptable solution to the typical problems you give them.
IF that doesn't work, you can opt out of basic heuristic programming. That is, do a few things manually and pay attention to how you did it. Then program it the same way.
I hope this helps.
source to share