0

Suppose I have the following primal and dual problem

enter image description here

The restricted primal problem is

enter image description here

My question is, how do we know that $X_i \ge 0$ (which implies $\sum_{j\in J}a_{ij}x_j \le b_i$)?

Rufus
  • 215
  • If $X_i$ is an auxiliary variable, then the contraint without the auxiliary variable is still an equality: $\sum\limits_{j\in J}a_{ij}x_j \ \large{\color{red}{=}} \ b_i$. Next you add an auxiliary variable to obtain an initial solution: $X_i=b_i$ and $x_i=0 \ \forall \ \ i\in I$ // You add an auxiliary variable for every equality and every $\geq$-constraint. – callculus42 Feb 04 '22 at 01:36
  • @callculus42 So the reason we use $X_i \ge 0$ is because we start the search with $X_i = b_i$. This doesn't seem trivial / obvious... Is this algorithm dependent on this initial condition? – Rufus Feb 04 '22 at 23:18
  • 1
    Let say you have the constraint $x_1+x_2\geq 5$. Next you subtract an surplus (slack) variable to obtain an equality. $x_1+x_2-s_1=5$. At the initial solution we set $x_1=x_2=0$. So $s_1$ would be negative to fulfill the equality. But $s_1$ is non-negative by definition. Thus you have to add an artificial variable. $x_1+x_2-s_1+X_1=5$ Therefore the initial solution is this case is $(x_1,x_2,s_2,X_1)=(0,0,0,5)$. Yes, this is a part of the simplex algorithm. The case is similar for an equality-constraint. The decision variables ($x_i$) are 0 at the start. We have to add an artificial variable. – callculus42 Feb 05 '22 at 02:19
  • 1
    For more detailed information see here. – callculus42 Feb 05 '22 at 02:30
  • @callculus42 Thanks a lot! This helped greatly! Somehow I must've glossed over the part about initializing the simplex algorithm. – Rufus Feb 05 '22 at 20:36
  • You're welcome. If you have any further question, feel free to ask. – callculus42 Feb 05 '22 at 21:19

0 Answers0