# How to derive the dual problem of Knapsack problem

Knapsack problem is $$\text{max} \, v^Tx$$ $$\text{s.t.} \, w^Tx \le W, \, \, 0\le x_i \le 1 \, \, (i=1,...,n)$$

This is equivalent to $$\text{min} \, -v^Tx$$ $$\text{s.t.} \, {\left[\begin{array}{r} w^T \\ I \end{array}\right]} x \le {\left[\begin{array}{r} W\\ e \end{array}\right]} , \, \, x\ge 0 , \, \, e=(1,...,1)^T$$

Convert this into standard canonical form. $$\text{min} \, -v^Tx$$ $$\text{s.t.} \, {\left[\begin{array}{r} w^T \\ I \end{array}\right]}+y= {\left[\begin{array}{r} W\\ e \end{array}\right]}$$ $$x, y \ge 0$$

$$= \text{min} \, -{\left[\begin{array}{r} v \\ 0 \end{array}\right]} ^T {\left[\begin{array}{r} x \\ y \end{array}\right]}$$ $$\text{s.t.} \, \, {\left(\begin{array}{rr} {\left[\begin{array}{r} w^T\\ I \end{array}\right]} & I \end{array}\right)} {\left[\begin{array}{r} x \\ y \end{array}\right]}= {\left[\begin{array}{r} W\\ e \end{array}\right]}$$ $$x, y \ge 0$$

How can I find the dual of this? I only know to solve up to here (I hope that upto here it is correct!).

Answer should be $$\text{min} \, Wt+\sum_{i=1}^{n} S_i$$ $$\text{s.t.} w_{i}t+S_i \ge v_i , \, (i=1,...,n)$$ $$t,s_1,...,s_n \ge 0$$

I want to do this by using the following definition. The Standard form of the linear program is $$\text{Min} \, C^{T} x$$ $$s.t. Ax=b$$ $$x\ge 0$$

Then the Dual is $$\text{Max}\, b^Ty$$ $$s.t. C-A^{T}y \ge 0$$

• When you convert the original primal problem to its standard form, you've used both $y$ and $s$ in the LPP. I think you mean the same variable. – GNUSupporter 8964民主女神 地下教會 Jan 9 '16 at 6:24
• Yes it is. I corrected it in my question. Thank you – Oily Jan 9 '16 at 6:30

1. If you know that the dual of the dual is the primal problem itself, you don't need to rewrite the max problem into the min one. Therefore, what's below the formulation of the LPP doesn't help to solve the problem. Anyways, good try.
2. It's possible that $\ge$ and $\le$ appear in the canonical form.

I'd prefer writing the primal problem (in the canonical form) in this way because it's more concise.

\begin{aligned} \max z = v^T x & \\ \text{s.t. } w^T x &\le W \\ Ix &\le \mathbf{e} \\ x &\ge 0 \end{aligned} \tag{*} \label{primal}

Here $\mathbf{e} = (1,1,\dots,1)^T \in \Bbb R^n$ and $W$ is a scalar. If you don't see why the answer follows from \eqref{primal}, you may write it clearer like this.

\begin{aligned} \max z = v^T x & \\ \text{s.t. } \begin{bmatrix} w^T \\ I \end{bmatrix} x &\le \begin{bmatrix} W \\ \mathbf{e} \end{bmatrix} \\ x &\ge 0 \end{aligned} \tag{#} \label{clear}

• The dual variable $t \in \Bbb R$ represents the first constraint (row) in \eqref{clear}.
• The dual variable $s = (S_1,S_2,\dots,S_n)^T \in \Bbb R^n$ represents the rest of the constraints in \eqref{clear}.

Therefore, the dual problem should be the last LPP stated in the OP.

\begin{align} \min Z = \begin{bmatrix} W \\ \mathbf{e} \end{bmatrix}^T \begin{bmatrix} t \\ s \end{bmatrix} & \\ \text{s.t. } \begin{bmatrix} w & I \end{bmatrix} \begin{bmatrix} t \\ s \end{bmatrix} &\ge v \\ t,s &\ge 0 \end{align}

Simplify this to

\begin{align} \min Z = W t + \mathbf{e}^T s & \\ \text{s.t. } w t + s &\ge v \\ t,s &\ge 0. \end{align}

Write it in terms of scalar decision variables.

\begin{align} \min Z = W t+\sum_{i=1}^{n} S_i & \\ \text{s.t. } w_{i}t+S_i &\ge v_i \, \forall i \in \{1,\dots,n\} \\ t,s_1,\dots,s_n &\ge 0 \, \forall i \in \{1,\dots,n\} \end{align}

Finding the dual from the standard form

Note that $W \in \Bbb R, x,e \in \Bbb R^n, y \in \Bbb R^{n+1}$. The original problem in standard form:

\begin{align} \min z = -\begin{bmatrix} v \\ 0 \end{bmatrix}^T \begin{bmatrix} x \\ y \end{bmatrix} & \\ \text{s.t. } \left(\begin{array}{rr} {\left[\begin{array}{r} w^T\\ I_n \end{array}\right]} & I_{n+1} \end{array}\right) \begin{bmatrix} x \\ y \end{bmatrix} &\ge \begin{bmatrix} W \\ e \end{bmatrix} \\ x,y &\ge 0 \end{align}

The dual is therefore

\begin{align} \max Z = \begin{bmatrix} W \\ e \end{bmatrix}^T \begin{bmatrix} t \\ s \end{bmatrix} & \\ \text{s.t. } -\begin{bmatrix} v \\ 0 \end{bmatrix} - \begin{bmatrix} \begin{bmatrix} w & I_n \end{bmatrix} \\ I_{n+1} \end{bmatrix} \begin{bmatrix} t \\ s \end{bmatrix} &\ge 0 \end{align}

Write it using one more $\ge$ sign.

\begin{align} \max Z = \begin{bmatrix} W \\ e \end{bmatrix}^T \begin{bmatrix} t \\ s \end{bmatrix} & \\ \text{s.t. } -v - \begin{bmatrix} w & I_n \end{bmatrix} \begin{bmatrix} t \\ s \end{bmatrix} &\ge 0 \\ -I_{n+1} \begin{bmatrix} t \\ s \end{bmatrix} &\ge 0 \end{align}

The last row means that $t,s \le 0$. Replace them by positive variables.

\begin{align} \min Z = Wt + e^T s & \\ \text{s.t. } wt + s &\ge v \\ t,s &\ge 0 \end{align}

• @user303643 They're equivalent. Yes, you can, but this makes your solution clumsy. To efficiently write down the dual problem, you may use a table for converting dual LPP. For example, see Table 4.1 of web.mit.edu/15.053/www/AMP-Chapter-04.pdf on p.141. – GNUSupporter 8964民主女神 地下教會 Jan 9 '16 at 5:54
• Thank you very much! Your answer is correct. But I want to use the standard form of the linear program. I have edited my question again in above. Could you please give me an answer for that? – Oily Jan 9 '16 at 6:12
• @user303643 OK, I'll try. I've really used "the standard form of the linear program" in your another question. I hope this helps. – GNUSupporter 8964民主女神 地下教會 Jan 9 '16 at 6:16
• Thank you very much for time and effort! – Oily Jan 9 '16 at 6:20
• @user303643 I've added a section for your edit. As you can see, writing the dual directly from the definition is more time-consuming than remembering the rules from a table, especially in test/exams. – GNUSupporter 8964民主女神 地下教會 Jan 9 '16 at 7:08