Similarity criteria for dynamic problems of combinatorial optimization

Akhanova Marina Anatolievna, Ovchinnikova Svetlana Valerievna, Terekhova Natalya Vladimirovna

The article describes the signs by which the similarity of dynamic tasks belonging to different classes is established. Those combinatorial optimization problems are considered dynamic, in which, when solving them, the existing information is produced, according to which the result is evaluated, and the optimal solution is found in stages with the calculation of partial sums of the objective function. The main signs of similarity for them is the change in the result of the solution in time and for its current reference the need to calculate a partial objective function. The process of their solution is described by a directed acyclic graph, and the partial values of the objective function change in time and are calculated in accordance with recursive rules. When finding their optimal values, the Bellman principle is fulfilled. Similarity properties are revealed that are characteristic of problems of this class and determine their universality, as a result of which the same method is used to solve them. To solve these problems, as a rule, dynamic programming is used. The analysis and use of the similarity property in combinatorial optimization makes it possible to bring unsolvable problems to solvable ones. Examples of some dynamic problems of combinatorial optimization are given.

Keywords:combinatorial optimization (CO), combinatorial configuration, dynamic problems, problem similarity, objective function.