0
$\begingroup$

In my line of work, I have encountered the following variant of discrete knapsack and I was wondering if it has already been studied. E.g. We are given a set of 3 items (A,B,C). The goal is to maximize the value carried for a given weight constraint. The variant has the following additional constraints:

  • Step 1: The first item choice is always A.

    If the finite set with A's weights is $W_A = \{ 3.4 ,10, 12.5 \}$, we pick e.g the value $w=12.5$ once.

  • The choice $w$ of A's weight affects (deterministically) the weights and values of B and C. I.e. the weigt set $W_B = f(w)$ and the value set $V_B = g(w) $. Same for $W_C, V_C$.
  • Step 2: We want to maximize the value (for a given total weight) by adding items B and C in the knapsack.

Has this been studied before? Is solving it equivalent to performing knapsack once per weight choice in set $W_A$ ? (i.e. 3 times in the example above)

UPDATED with more formal definition:

Assume $n$ finite sets $A_1,A_2,...,A_n$

Assume you are allowed a single choice $a_i$ from each set, i.e. $a_1 \in A_1, ... , a_n \in A_n$

Assume the weight $w$ to be a function of all choices i.e. $w=f(a_1,...,a_n)$

Assume the value $v$ to be a function of all choices i.e. $v=g(a_1,...,a_n)$

Assume a maximum weight capacity $W_c$

Goal:

Find choices $(a_1,...,a_n)$ that maximize value $v=g(a_1,...,a_n)$, while $w=f(a_1,...,a_n) \le W_c$

$\endgroup$
  • $\begingroup$ Rephrasing it this way, it looks more like a nonlinear programming problem (functions f, g are nonlinear) $\endgroup$ – kostaspap Jan 12 '17 at 16:13
  • $\begingroup$ What exactly do you want to know? Rather than asking "has it been studied before", you're more likely to get useful answers if you tell us what you want to know about the problem. Do you want to know whether it is NP-hard? Do you want to know whether there are heuristics or approximation algorithms for it? $\endgroup$ – D.W. Jan 12 '17 at 16:48
0
$\begingroup$

This is a generic nonlinear optimization problem. Without further information about $f,g$, there's not much you can say about this. If you have absolutely no knowledge about $f,g$, the best strategy you can do is just exhaustively try all possible choices.

Of course in practice it's likely that $f,g$ will have some structure, and then there might be techniques or heuristics that have the potential to perform better -- but the techniques will depend on the kind of structure they have.

$\endgroup$

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.