A heuristic method for solving integer-valued decompositional multiindex problems

• DOI: 10.1134/s0005117914080013
• Publication Date: 2014-08-12T04:46:42Z
• Authors: L. G. Afraimovich
• Keywords: Heuristics

We consider NP-hard integer-valued multiindex problems of transportation type. We distinguish a subclass of polynomially solvable multiindex problems, namely multiindex problems with decomposition structure. We construct a general scheme for a heuristic method to solve a number of similar NP-hard decompositional multiindex problems. For one version of implementation for this scheme, we estimate its deviation from the optimum. We illustrate our results with the example of designing a class schedule.