Knapsack problem with setups (KPS)

Catalogue of combinatorial problems · Knapsack problems · Catalogue (PDF)

Definition 1: Knapsack problem with setups

Given:

1. a knapsack of capacity \(c \in \Z_{\ge 1}\),

2. a set \(\mathscr{I} = \{1,2,\dots,n\}\) of \(n\) items,

3. the set of items is partitioned into \(q \in \Z_{\ge 2}\) classes,

4. for each class \(h \in \{1,2,\dots,q\}\), the subset \(\mathscr{J}_h \subseteq \mathscr{I}\) contains the items of that class, with an associated setup cost \(f_h \in \Z_{\ge 1}\) and a setup weight \(s_h \in \Z_{\ge 1}\),

5. for each item \(j \in \mathscr{I}\), a revenue \(p_j \in \Z_{\ge 1}\) and a weight \(w_j \in \Z_{\ge 1}\),

the Knapsack Problem with Setups (KPS) asks to decide which items to insert into the knapsack, so that the total weight of the selected items plus the setup weights of their classes does not exceed the knapsack capacity, and the total revenue of the selected items minus the setup costs of their classes is maximized.

Assumptions

• We make the following assumptions:

  1. Each class contains at least one item. Formally:

     \[ \mathscr{J}_h \neq \emptyset \qquad \forall\, h\in\{1,2,\dots,q\}. \]

  2. Each item can fit into the knapsack together with the setup weight of its class (otherwise, it can never be selected). Formally:

     \[ w_j + s_h \le c \qquad \forall\, h\in\{1,2,\dots,q\},\ \forall\, j\in \mathscr{J}_h. \]

What the course does on this problem

Technique	Where
Definition	Ch. 2 «Knapsack problems»
Formulations	Ch. 9 «Formulations of knapsack problems»
Dynamic programming	Ch. 16 «Principles of dynamic programming»; Ch. 23 «DP for the knapsack problem with setups»
Exercises	Exercise 9.12; Ch. 23 (5 exercises)