Multi-index transportation problems with $1$-nested structure

Consideration was given to the solution of the multi-index transportation problems of linear and integer-linear programming. It was proposed to use the approach based on studying the reducibility of the multi-index transportation problems to the problem of the minimal cost in the treelike network. It was proved that within the framework of the reduction scheme the condition for $1$-nesting of the multi-index problems is necessary and sufficient for reducibility to the problem of the minimal-cost flow problem on a treelike network. An algorithm was proposed to solve the $1$-nested multi-index problems requiring as many computer operations as the square of variables in the original problem.

Presented by the member of Editorial Board: A. A. Lazarev