Multi-index transport problems with decomposition structure
L. G. Afraimovich · Automation and Remote Control · 2012
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.