Editing Knapsack problem (section)

===Dominance relations===
Solving the unbounded knapsack problem can be made easier by throwing away items which will never be needed.  For a given item <math>i</math>, suppose we could find a set of items <math>J</math> such that their total weight is less than the weight of <math>i</math>, and their total value is greater than the value of <math>i</math>.  Then <math>i</math> cannot appear in the optimal solution, because we could always improve any potential solution containing <math>i</math> by replacing <math>i</math> with the set <math>J</math>.  Therefore, we can disregard the <math>i</math>-th item altogether.  In such cases, <math>J</math> is said to '''dominate''' <math>i</math>.  (Note that this does not apply to bounded knapsack problems, since we may have already used up the items in <math>J</math>.)

Finding dominance relations allows us to significantly reduce the size of the search space.  There are several different types of [[dominance relations]],<ref name="poirriez_et_all_2009" /> which all satisfy an inequality of the form:

<math>\qquad \sum_{j \in J} w_j\,x_j \ \le  \alpha\,w_i</math>, and <math>\sum_{j \in J} v_j\,x_j \ \ge \alpha\,v_i\,</math> for some <math>x \in Z _+^n </math>

where
<math>\alpha\in Z_+ \,,J\subsetneq N</math> and <math>i\not\in J</math>.  The vector <math>x</math> denotes the number of copies of each member of <math>J</math>.

;Collective dominance:  The <math>i</math>-th item is  '''collectively dominated''' by <math>J</math>, written as <math>i\ll J</math>, if the total weight of some combination of items in <math>J</math> is less than ''w<sub>i</sub>'' and their total value is greater than ''v<sub>i</sub>''.  Formally, <math>\sum_{j \in J} w_j\,x_j \ \le  w_i</math> and <math>\sum_{j \in J} v_j\,x_j \ \ge v_i</math> for some <math>x \in Z _+^n </math>, i.e. <math>\alpha=1</math>.  Verifying this dominance is computationally hard, so it can only be used with a dynamic programming approach.  In fact, this is equivalent to solving a smaller knapsack decision problem where <math>V = v_i</math>, <math>W = w_i</math>, and the items are restricted to <math>J</math>.
;Threshold dominance: The <math>i</math>-th item is '''threshold dominated'''  by <math>J</math>, written as <math>i\prec\prec J</math>, if some number of copies of <math>i</math> are dominated by <math>J</math>.  Formally, <math>\sum_{j \in J} w_j\,x_j \ \le  \alpha\,w_i</math>, and <math>\sum_{j \in J} v_j\,x_j \ \ge \alpha\,v_i\,</math> for some <math>x \in Z _+^n </math> and <math>\alpha\geq 1</math>.  This is a generalization of collective dominance, first introduced in<ref name="eduk2000"/> and used in the EDUK algorithm.  The smallest such <math>\alpha</math> defines the '''threshold''' of the item <math>i</math>, written  <math>t_i =(\alpha-1)w_i</math>.  In this case, the optimal solution could contain at most <math>\alpha-1</math> copies of <math>i</math>.
;Multiple dominance: The <math>i</math>-th item is  '''multiply dominated''' by a single item <math>j</math>, written as <math>i\ll_{m} j</math>, if <math>i</math> is dominated by some number of copies of <math>j</math>.  Formally, <math>w_j\,x_j \ \le  w_i</math>, and <math>v_j\,x_j \ \ge v_i</math> for some <math>x_j \in Z _+ </math> i.e. <math> J=\{j\}, \alpha=1,  x_j=\lfloor \frac{w_i}{w_j}\rfloor</math>. This dominance could be efficiently used during preprocessing because it can be detected relatively easily.
;Modular dominance: Let <math>b</math> be the ''best item'', i.e. <math>\frac{v_b}{w_b}\ge\frac{v_i}{w_i}\, </math> for all <math>i</math>.  This is the item with the greatest density of value. The <math>i</math>-th item is '''modularly dominated''' by a single item <math>j</math>, written as <math>i\ll_\equiv j</math>, if <math>i</math> is dominated by <math>j</math> plus several copies of <math>b</math>.  Formally, <math> w_j+tw_b \le w_i</math>, and  <math>v_j +tv_b \ge v_i </math> i.e. <math>J=\{b,j\}, \alpha=1,  x_b=t, x_j=1</math>.