93-64 On enumeration of near to best solutions in discrete and dynamic programming

DIMACS TR: 93-64

On enumeration of near to best solutions in discrete and dynamic programming

Author: Joseph V. Romanovsky

ABSTRACT
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.

The preliminary set of operations is proposed in the paper. This set allows ones to construct a rather standard tool for enumeration in those optimization problems that may be solved with ideas of splitting (as in Branch-and-Bound) and recursion (as in Dynamic programming).

As examples we considered the problems of shortest and the quickest paths in a graph, and the non-serial dynamic programming.

Some experimenal software were developed to check the ideas. It was described at the end of the paper.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-64.ps

DIMACS Home Page