Exercise 6.8

Question

Consider the Dantzig-Wolfe decomposition method and suppose
that we are at a basic feasible solution to the master problem. \
(a) Show that at least one of the variables $\lambda_1^j$ must be a basic variable. \
(b) Let $r_1$ be the current value of the simplex multiplier associated with the
first convexity constraint (6.12), and let $z_1$ be the optimal cost in the first
subproblem. Show that $z_1 \leq r_1$ .

Aqa Arman · Accepted Answer

(a) Considering the convexity constraint, $\dispalystyle \sum_{i=1}^N \lambda_1^i=1$, there is at least a j such that $\lambda_1^j > 0$. \
(b) We know that $\overbar{c)_B = 0$. According to (a), there exists a j such that $\lambda_1^j$ is basic. Then we have: \ 
$0=\overbar(c)($\lambda_1^j)=(c_1^{\prime}-q^{\prime}D_1)x_1^j - r_1 \implies (c_1^{\prime}-q^{\prime}D_1)x_1^jj= r_1$. \
On the other hand $x_1^j$ is a vertex of $P_1$. So $x_1^j\in P$. Using optimality of $z_1$ we have: \
$z_1 \leq (c_1^{\prime}-q^{\prime}D_1)x_1^j = r_1 \implies z_1 \leq r_1$.

Exercise 6.8

Answers

Comments

Exercise 6.8

Answers

Comments

Add answer