TY - JOUR

T1 - The simplex algorithm for multicommodity networks

AU - Detlefsen, Nina

AU - Wallace, Stein W

PY - 2002

Y1 - 2002

N2 - We consider multicommodity network flow problems, where external flow is allowed to vary and where flows of individual commodities may be constrained. For this problem, we describe the simplex algorithm. The simplex algorithm is based upon the inverse of the basis matrix. We discuss an approach where we only have to invert a working matrix with dimension at most equal to the number of arcs in the network. The dimension is independent of the number of commodities. The reduced cost of a nonbasic variable is found only using the working matrix that is explicitly inverted and some simple network operations. We also discuss how to pivot in the working matrix. The focus is on the detailed interpretation of the network structures arising in terms of cycles for the individual commodities.

AB - We consider multicommodity network flow problems, where external flow is allowed to vary and where flows of individual commodities may be constrained. For this problem, we describe the simplex algorithm. The simplex algorithm is based upon the inverse of the basis matrix. We discuss an approach where we only have to invert a working matrix with dimension at most equal to the number of arcs in the network. The dimension is independent of the number of commodities. The reduced cost of a nonbasic variable is found only using the working matrix that is explicitly inverted and some simple network operations. We also discuss how to pivot in the working matrix. The focus is on the detailed interpretation of the network structures arising in terms of cycles for the individual commodities.

KW - multicommodity

KW - basis characterization

KW - simplex algorithm

KW - basis interpretation

U2 - 10.1002/net.10006

DO - 10.1002/net.10006

M3 - Journal article

VL - 39

SP - 15

EP - 28

JO - Networks

JF - Networks

SN - 0028-3045

IS - 1

ER -