I am studying Chapter 7 (Network Flow Problems) of the book Introduction to Linear Optimization by Bertsimas and Tsitsiklis. On page 286 the authors briefly describe a way to deal with the initialization of the minimum cost network flow problem:
In the case where finding an initial basic feasible solution is difficult, we may need to form and solve an auxiliary problem. For example, for each pair of source and sink nodes, we may introduce an auxiliary arc; finding a basic feasible solution in the presence of these arcs is straightforward. Furthermore, if the unit costs $c_{ij}$ of the auxiliary arcs are chosen large enough, solving the auxiliary problem is equivalent to solving the original problem.
A minimum cost network flow problem takes the following form. A network is a directed graph $G=(\mathcal{N},\mathcal{A})$ together with some additional numerical information, including $b_i$ representing the supply to (if $b_i>0$) or demand of (if $b_i<0$) each node $i\in\mathcal{N}$, nonnegative numbers $u_{ij}$ representing the capacity of each arc $(i,j)\in\mathcal{A}$, and numbers $c_{ij}$ representing the cost per unit flow along arc $(i,j)$. The minimum cost network flow problem is $$ \begin{align*} \min&\quad\sum_{(i,j)\in\mathcal{A}}c_{ij}f_{ij} \\ \text{s.t.}&\quad b_i+\sum_{\{j\in\mathcal{N}:(j,i)\in\mathcal{A}\}}f_{ji}=\sum_{\{j\in\mathcal{N}:(i,j)\in\mathcal{A}\}}f_{ij},\quad\forall\,i\in\mathcal{N} \\ &\quad 0\le f_{ij}\le u_{ij},\quad\forall\,(i,j)\in\mathcal{A}, \end{align*} $$ where the decision variable $f_{ij}$ represents the amount of flow along arc $(i,j)$.
My question: Why do the authors say it is straightforward to find a basic feasible solution in the presence of these arcs?
In my understanding, this method resembles the big-$M$ method for general linear programming: we introduce auxiliary variables $y$ in the constraints and add $M\sum_jy_j$ to the objective, and then the initial basic variables are $y$. However, I don't see how the same trick extends to the network flow problem. Intuitively, I need to pick some nonzero auxiliary arcs and also some arcs between nodes with zero supply and demand, and these arcs need to form a tree. Is there a general procedure to do this?