Abstract:Simplex algorithm is a classical algorithm for solving linear programming problems (LP). The most time-consuming module of simplex algorithm is the algorithm for calculating the inverse matrix of the matrix. The network simplex algorithm is a special version of the simplex algorithm, which uses a spanning tree basis to solve linear programming problems with pure network form more efficiently.

This article is shared from Huawei Cloud Community “Brief Introduction to Network Simplicity Algorithm”, originally written by: Yun Xiaofan.

preface

Simplex algorithm is a classical algorithm for solving linear programming problems (LP). The most time-consuming module of simplex algorithm is the algorithm for calculating the inverse matrix of the matrix. The network simplex algorithm is a special version of the simplex algorithm, which uses a spanning tree basis to solve linear programming problems with pure network form more efficiently. Such an LP problem can be modeled using a formula on a directed graph as a minimum-cost flow problem.

Network Simplicity refers to the following form of LP problem:

Where, each column contains only one 1 and one minus 1, and all other coefficients are 0. Here’s an example:

This problem can be viewed as a graph of a Minimum Cost Flow problem. Graph G= (V,E), vertex V represents the row (constraint), edge E represents the column (variable), for A column in matrix A, row I has A 1, row k has A -1, represents an edge in graph G (I, K).

For the above example, it can be represented by the following:

The network flow problem satisfies Hoffman&Gale’s conditions, so integer solutions can be guaranteed.

Correlation matrix:

For the association matrix A of G= (V,E), it can be expressed as:

The association matrix in the above example can be expressed as:

Path:



Connected graph: Any two vertices in the graph have paths. Spanning tree: A subgraph T of graph G containing all vertices in graph G. Rank (A)=n-1, n = number of nodes

Let’s add A new variable, w, and add A new column to A

∈ {1, 2, r… N}, w=0, then LP model is:

R is called the root vertex and W is called the root edge going nowhere.

For the example above, let’s say you choose the root node r=2

A graph G is the incidence matrix, T is A spanning tree of G, (A │ e_r) base B = e_r ∪ {a_e | e ∈ T}

Simplex algorithm:





We can traverse from the root node in order to get y2=0, y1-y2=1, y1-y3=10, i.e. traverse basis 5, basis 1, and basis 4 in order

Pseudocode :(recursive)

Solve (Vertex P,Tree S){// P is the root node of the Tree S

Vertex v=root(S);

if(v==r) y[r]=c[w];

Else if ((p, v) ∈ E y = y [v] [p] – [(p, v)] c;

else y[v]=y[p]+c[(v,p)];

solve(v,S.left());

solve(v,S.right());

}

References: https://www.cs.upc.edu/~erodr…

Click on the attention, the first time to understand Huawei cloud fresh technology ~