Multi‐index transport problems with decomposition structure

Consideration was given to the multi‐index problems of linear and integer linear programming of the transport type. An approach based on the study of reducibility of the multi‐index transport problems to that of seeking a flow on the network was proposed. For the multi‐index problems with decomposition structure, a reduction scheme enabling one to solve the original multi‐index problem using the cyclic decomposition of the minimum‐cost flow of the auxiliary flow problem was constructed. The developed method underlies the heuristic algorithm to solve the NP‐hard integer multi‐index problem with a system of constraints featuring decompositional properties and general cost matrix.