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$$
Best Answer
I'd prefer writing the primal problem (in the canonical form) in this way because it's more concise.
\begin{equation} \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} \end{equation}
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{equation} \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} \end{equation}
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}