On Enumeration of Near to Best Solutions in Discrete and Dynamic Programming

We consider a new approach to enumeration of near-to-optimal solutions in discrete optimization problems. The main idea is to consider the processes that generate such solutions, and to describe possible operations with the processes. It allows us to construct a rather standard tool for enumeration in those optimization problems that may be solved with ideas of splitting of the set of admissible solutions (as in Branch-and-Bound) and recursion (as in Dynamic programming). As examples we consider the problems of shortest and the quickest paths in a graph, and the nonserial dynamic programming. Some experimental software were developed to check the ideas. It was described at the end of the paper. 1 Introduction The enumeration of solutions next after optimum is a natural generalization of an ordinary extremal problem in the case when the set of feasible solutions is discrete. The first algorithms of that kind were considered yet by W. Hoffman and R. Pavley [1] and by R. Bellman and R...