[Math] the restriction matrix used for in the stepping stone method

linear programmingnetwork-flow

Let's say that we want to solve a classic transportation problem without capacities using the stepping stone method. (Problem definition: A bipartite graph with supply nodes a1m, demand nodes b1…bn, and costs wij for the transport of goods from ai to bj. Find a flow which satisfies the demand of all b nodes at minimal cost).

The first sentence in the chapter on the stepping stone method in the script is:

 The restriction matrix T of the equations Tx=(a,b)T of the linear 
program has the following structure: 

matrix

Then the text goes on to prove some lemmas about the subsets of independent columns in the restriction matrix. The matrix isn't mentioned after that, and it isn't used in the example. I couldn't find another source explaining it, and the textbook (Combinatorial optimization by Korte and Vygen) doesn't even mention the stepping stone method.

What I don't understand is: What do the rows and columns in this restriction matrix represent? Why are we interested in the amount of independent columns in it? And how is it used in the stepping stone method?

Best Answer

  1. The rows represent the supply and demand nodes. The columns represent the decision variables $x_{ij}$; i.e., how much you send from supply node $i$ to demand node $j$. That's why there are $m+n$ rows and $mn$ columns. The matrix itself is the coefficient matrix for the constraints in the (balanced) transportation problem; in other words, the left-hand side coefficients of the constraints $$\sum_{j=1}^n x_{ij} = s_i, \text{ for each supply node $i$;}$$ $$\sum_{i=1}^m x_{ij} = d_j, \text{ for each demand node $j$}.$$ These come from the assumption that all supply is shipped and all demand is met.

  2. There's a redundant constraint: If you know that all but one of the supply and demand constraints have been satisfied, then the other one must be satisfied as well in order for all supply to be shipped and all demand to be met. In linear algebra terminology, this means that the constraint matrix has rank $m+n-1$ or that it has $m+n-1$ linearly independent columns. We are interested in this because this means that there are $m+n-1$ basic variables in each iteration of the simplex method rather than the $m+n$ basic variables we would normally get with a constraint matrix that has $m+n$ rows and $mn$ columns.

  3. With respect to the stepping stone method, this means that there are only $m+n-1$ circled numbers in the tableau (i.e., flows in the basis, or basic variables) rather than the $m+n$ one would normally expect. It doesn't affect the loops generated or the net effects of the loops, however. If you use the modified distribution method, though, this also means that one of the $m + n$ dual variables $u_i$ and $v_j$ is a free variable. So you can choose a value for one of those variables that makes the subsequent calculations of $c_{ij} - u_i - v_j$ for each nonbasic variable easier. It's common, as in the example in the link, to choose one of $u_i$ or $v_j$ to be $0$.

Related Question