I was trying to apply Dantzig Decomposition followed by Column Generation. The following is how I was taught.
\begin{array}{l}
\text { Minimize }-10 x_1-2 x_{2}-4 x_{3} \\
\text { subject to: } x_{1}+x_{3} \leq 15 \text{........ I}\\
x_{1}+2 x_{2} \leq 10 \text{........II}\\
2 x_{3}+x_{4} \leq 20 \text{........III}
\end{array}
Considering I as the link constraint and II as a constraint for segment 1 and III for segment 2
Next we trasform the lp for convex combination of extreme points from the disjoint constraints
$c=\left[\begin{array}{llll}
-10 & -2 & -4 & 0
\end{array}\right], A=\left[\begin{array}{lll}
1 & 0 & 1 & 0
\end{array}\right]$
\begin{equation}\begin{aligned}
M_{\text {inimize }} & \sum \lambda_{j} C X_{j} \\
& \sum \lambda_{j} A X_{j}+s=15 \text{.....IV} \\
& \sum \lambda_{j}=1 \text{.....V}
\end{aligned}\end{equation}
Let $\pi_1 and \pi_2$ be the dual variables associated with IV and V respectively.
where $X_j$ is corner point for I and II \begin{equation}\begin{array}{l} \text { Initial Solution} =>X_{1}=[0 \quad 0 \quad 0 \quad 0], \lambda_{1}=1 \\ \quad \text { Basis } \rightarrow s_{1} , \lambda_{1} \end{array}\end{equation}
\begin{equation}\begin{array}{c|cc|c} & s & \lambda_{1} & R_{15} \\ \hline s & 1 & 0 & 15 \\ \lambda_{1} & 0 & 1 & 1 \\ \hline z_j-c_{j} & 0 & 0 & 0 \end{array}\end{equation}
Next, we check which $\lambda_j$ satisfies to ender into the basis: \begin{equation}\begin{array}{c} z_{i}-c_{j} \geqslant 0 \\ z_{j}=\pi P_{j} \end{array}\end{equation} where $\pi$ is the dual vector, $P_j $ is the entering column \begin{equation}P_{j}=\left[\begin{array}{c} A X_{j} \\ 1 \end{array}\right], C_{j}=C X_{j}\end{equation}
\begin{equation}\begin{array}{l} {\left[\pi_{1} \pi_{2}\right]\left[\begin{array}{c} A X_{j} \\ 1 \end{array}\right]-c x_{j} \geqslant 0} \\ \left(\pi_{1} A-c\right) x_{j}+\pi_{2} \geqslant 0 \\ \pi_{1}=0,\pi_{2}=0 \text{He said that in the absence of artificial variables, the values under the initial basis are the values for the dual variables.} \end{array}\end{equation}
New Objective: Maximize $-CX_j$,
where $X_j$ belongs to the corner points of I and II together.
Next, we decompose the objective into two subproblems.
First:
\begin{equation}\begin{array}{l}
\text { Maximize } x_{1}+2 x_{2} \\
\text{subject to}: x_{1}+2 x_{2} \leq 10
\end{array}\end{equation}
This gives $x_1=10,x_2=0, z=100$
Second:
\begin{equation}\begin{array}{l}
\text { Maximize }4 x_{3} \\
\text{subject to}: 2x_{3}+ x_{4} \leq 20
\end{array}\end{equation}
This gives $x_3=10,x_4=0, z=40$
$X_2 =[10 \quad 0 \quad 10 \quad 0]$
$Z=100+40=140$
\begin{equation}\begin{aligned}
\bar{P}_{2} &=B^{-1} P_{2} \\
&=P_{2} \text{ as B=I}\\
&=\left[\begin{array}{c}
AX_2 \\
1
\end{array}\right] \\
&=\left[\begin{array}{c}
20 \\
1
\end{array}\right]
\end{aligned}\end{equation}
\begin{equation}\begin{array}{c|ccc|cc} & s & \lambda_{1} & \lambda_{2} & \text { RHS } & \theta \\ \hline s & 1 & 0 & (20) & 15 & 15 / 20 \\ \lambda_{1} & 0 & 1 & 1 & 1 & 1 / 1 \\ \hline & 0 & 0 & 140 &0 & \end{array}\end{equation} With 20 as pivot, we get \begin{equation}\begin{array}{c|ccc|c} & s & \lambda_{1} & \lambda_{2} & RHS\\ \hline \lambda_2 & 1 / 20 & 0 & 1 & 15 / 20 \\ \lambda_{1} & -1 / 20 & 1 & 0 & 5 / 20 \\ \hline & -140 & 0 & 0 & -105 \end{array}\end{equation}
\begin{equation}\text { current sol }=\frac{15}{20}\left[\begin{array}{c}
0 \\
0 \\
0 \\
0
\end{array}\right]+\frac{5}{20}\left[\begin{array}{c}
10 \\
0 \\
10 \\
0
\end{array}\right]\end{equation}
The video lecture that I am following
I am facing trouble applying the same method to the same problem if all constraints are equality. I need to know how things change in the presence of artificial variables. Also, he took [0 0 0 0] as the initial solution which made things easy. In case we do not know any initial solution, we will have to add another artificial variable.
How do we get the values for the dual variables in the presence of artificial variables.
It would be really helpful if someone could show one iteration inline with the way I have shown.
PS. I don't have very in-depth knowledge of the simplex method so some of my doubts may be stupid.
