I have a problem with the following optimisation problem:

In total there are $n=100$ items. A quality level $L_i \in \{0,1,2,3,4,5\} $ must be selected for each of these items. The greater $L_i$ is, the greater weight $w_i$ and its value $v_i$, starting with $w_i=0$ and $v_i=0$ for $L_i=0$. Furthermore, $w_i$ depends on both item $n$ and its quality level $L_i$ and is calculated using function $w_i = w(n,L_i)$. $v_i$ depends on the total set of items and their selected quality levels $L_0 \dots L_n$ and is calculated using the relatively cost-intensive function $V$.

The question now is, what are the optimal quality levels improvements for each item, given random initital quality levels for the items and a capacity $W$? An important restriction is that a quality level can only be increased by one level in total. Each item must be selected exactly once (quality level $L=0$ is effectively the same as if the corresponding item had not been selected).

I see a difficulty in the fact that an items's value v depends on all other items. Can the problem still be solved optimally with an acceptable time complexity, or would it be necessary to use other algorithms, if so which ones? Maybe greedy algorithms?

Thank you very much for your help!

  • $\begingroup$ What do you mean by "optimal quality level"? What objective function are you trying to optimize? $\endgroup$ – D.W. Apr 8 at 15:53
  • $\begingroup$ Can you narrow down the nature of the dependence of $v_i$ on all of the quality levels? Can you tell us anything about the form of that function? Or is it totally arbitrary? $\endgroup$ – D.W. Apr 8 at 15:54
  • $\begingroup$ Optimal quality level improvements are those quality level increases that maximise the total value in the knapsack, given the capacity W $\endgroup$ – IntegerProgramming Apr 9 at 12:53
  • $\begingroup$ Please don't answer in the comments -- please edit the question so that the question is self-contained. Also, I notice that you haven't responded to my second comment. $\endgroup$ – D.W. Apr 9 at 21:13

You can't. If the function $V$ (for computing the $v_i$'s) is arbitrary, in the worst case you will need to try all possible combinations of quality levels -- there is no algorithm faster in the worst case. That takes exponential time.

To do better, we need to know something about the function $V$: e.g., about its structure or proeprties.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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