1
$\begingroup$

Thanks in advance for the help.

I have the following problem which, for lack of a better description, I'm referring to as the problem I've listed in the title.

Specifically I have a knapsack problem where I must exactly fill the knapsack. Additionally, the order in which I place the elements into the knapsack affects the strength of the solution (but not the volume of the individual elements). The function that is used to evaluate the strength, or goodness, of the packing is non linear and very complex. Because of this, I have a model that I will use to repeatedly simulate my evaluation function to get an idea of the strength of each solution rather than directly evaluating my evaluation function (sort of like a surrogate function).

For example, suppose I have a knapsack of size ten. The following would be possible solutions assuming integers are the elements that I can place into the knapsack (for all intents in purposes my actual problem can be visualized in this manner): [5,5], [3,3,4], [4,3,3], etc.

What I'm interested in is two-fold. First, does this problem reduce to any well studied problems from which I could read up more on how they are solved? I'm currently thinking about using some kind of heuristic search to solve this problem, such as a Genetic Algorithm (I don't have to have the optimal solution, though I would like the best that I can get). Second and somewhat related to the first, what work if any has been done on problems that fit the description that I have given above? The knapsack problem is a very well studied problem and I would find it hard to believe if there hasn't been any work done on problems that fit my current one. Unfortunately though, while I've found work somewhat related to my problem, I haven't been able to find anything that directly reduces to my problem.

Improve this question
$\endgroup$
3
  • $\begingroup$ Welcome to CS.SE! We're going to need to know something about the function you mention, or about the surrogate, to help you. Does it have any properties/structure? Is it monotonic (adding more elements always increases the goodness)? Is it approximately additive? sub-additive (upper-bounded by a linear function)? super-additive? convex? concave? Can you tell us anything useful about it? Without some kind of information about it, there's not likely to be any useful algorithm or answer possible, beyond saying that your problem is intractible. $\endgroup$
    – D.W. ♦
    Commented Aug 24, 2016 at 21:09
  • $\begingroup$ The surrogate function is essentially the output of a simulation; theres nothing else that I can really say about it besides that its complicated. The actual evaluation function outputs a probability that is computationally expensive to calculate. What I'm primarily interested in isn't so much a solution to my problem (after all, thats what the paper I intend publish will be about), but rather any work that's been done on similar problems. In particular, knapsack problems with the constraint that the knapsack must be completely filled and the property that solution quality is effected by $\endgroup$
    – HXSP1947
    Commented Aug 24, 2016 at 21:34
  • $\begingroup$ the order in which elements are placed into it. This is slightly different than the standard knapsack problem where each element placed in the knapsack contributes a certain amount to the solution quality as a function of its own constant individual contribution and an interaction with other elements in the knapsack (for example the simple case where each element has a constant value that is added to the solution quality). $\endgroup$
    – HXSP1947
    Commented Aug 24, 2016 at 21:37

1 Answer 1

Reset to default
1
$\begingroup$

If your function (or your surrogate function) has no structure, then there's nothing to say: you can't do any better than exhaustive search. In particular, you must examine every possible combination of the items that has the right weight. If your function has no structure, then you must evaluate it on each possible combination of items whose total weight matches the desired value: you can't rule out any of the possible combinations. There are exponentially such combinations, so your problem requires evaluating the function (or surrogate function) on exponentially many possible inputs.

Also, if your function has no structure, there are no heuristics or approximation algorithms that will do better than brute force (try some randomly chosen set of combinations and see which does best).

No, this case probably hasn't been studied, because it isn't interesting: there's nothing interesting or useful you can say about it, beyond what I've listed above.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.