Is this a knapsack problem?

Question

I have a set of $K$ keywords. Each of this keywords can have set of bids from $1\$,\dots,N\$$. For each bid for a keyword, it will get a specific amount of clicks and a specific cost. Clicks and Cost are monotonic in bids. Now, the problem is this

Select a bid for each of the keyword such that overall clicks across the keywords is maximized such that the cost is still within a given budget $B$. Let $\text{Clicks}(W_i)$ and $\text{Cost}(W_i)$ denote the clicks and cost on the keyword $i$. Then (informally) the problem is to select a value of bid for each keyword such that \begin{align}\max\sum_{i=1}^{K}&\text{Clicks}(W_i) \\s.t.&~~\sum_{i=1}^{K}\text{Cost}(W_i)\leq B\end{align} Is this a type of knapsack problem? Are there known heuristic in literature.

Following is not important for the question (and thus can be skipped), but is for the curious ones to know how I am solving this currently. Let $S_{ij}$ denote the cost for using bid $j$ for keyword $i$ and let $C_{ij}$ be the clicks for the same. Let $x_{ij}$ be the indicator variable for using bid $j$ for keyword $i$. Then among variables $x_{i1},\dots,x_{iN}$ only one can be non-zero (i.e. $x_{ij}=1$) whereas the rest is zero (since only one bid can chosen for keyword). Thus the whole problem can be formulated mathematically as \begin{align}\max_{x_{ij}}~&\sum_{i=1}^{K}\sum_{j=1}^{N}x_{ij}C_{ij} \\s.t.~~\sum_{i=1}^{K}\sum_{j=1}^{N}&x_{ij}S_{ij}\leq B\\\sum_{j=1}^{N}x_{ij}=1&~~\forall i\in \{1,\dots,K\}~~,~~x_{ij}\in\{0,1\}\end{align}Last two constraints ensures they are indicator variables and only one bid is chosen for a given keyword. Solving this should solve the original problem.

Answer 1

Yes, you are optimizing a knapsack problem.

The objects, or "items" in most knapsack problem (KP) definitions, in your case is a set $S=\{s_{00}, s_{01}, ..,s_{0n}, s_{10}, .. s_{kn}\}$, which contains composite keyword-bid pairs, so $s_{ij}$ denotes an object labeled "keyword $i$ bid $j$". The reason you should think of your items as composite this way is that the benefit/cost values (clicks/costs in your post, respectively) are attached to keyword-bid pairs.

The clicks and fee associated with each $s_{ij}$ are:
- $c_{ij}$: the number of clicks for "keyword $i$ at bid $j$" composite object, and
- $f_{ij}$ is the fee you pay for that keyword-bid combination (I avoided using "C"ost not to confuse it with "C"licks).

You can now feed your clicks $C$, the corresponding fees $F$, and threshold $B$ to any knapsack solver to find the optimal solution (this is a good one if your $B$ is a reasonably small).

You can prove that your problem is a knapsack problem (KP) by reducing KP into your problem (creating a mapping that can transform any KP instance to a corresponding instance of your problem). Following KP's definition here:

• KP's items map to your $S$
  
• KP's values map to your clicks
  
• KP's weights map to your fees (you called them costs).
• KP's capacity maps to your budget $B$.

Answer 2

It appears that the original statement is essentially a slight generalization of the Knapsack Problem since you assume your functions $\text{Clicks}(\cdot)$ and $\text{Cost}(\cdot)$ can be any monotonic functions, instead of the linear functions seen in the traditional Bounded Knapsack Problem assumes.

I think one can be sure that this is at least as hard as the Knapsack Problem. I don't know what values for $K$ and $N$ you have, but this can certainly be solved exactly using dynamic programming (DP). The main issues you may run into is if $N = O(2^K)$. If $N$ is instead polynomial in $K$, you should be able to solve this problem in polynomial time and space using DP pretty readily.