Application of linear convolution criteria algorithm for finding effective solutions in vector problem of discrete optimization
The article examines ways to solve the problem of finding effective solutions for a vector problem of discrete optimization among the algorithms of linear convolution of criteria (LCC) and suggests the necessary condition, as well as a number of sufficient conditions of such solvability. It also provides the necessary and sufficient condition of solvability for the case of two-criterion problem. The article proposes an algorithm (with complexity estimation) that allows reducing any vector trajectory problem with a certain criterion and several MINMAX (the bottleneck criterion) and MINMIN criteria to an equivalent problem (with the same Pareto set) but solvable by the LÑC. The cases when the complexity estimation of the reduction is polynomial respectfully to the dimension of the problem are specified.