One of perspective ways to exploit sparsity in the dependency graph of an optimization problem as J.N. Hooker stressed is nonserial dynamic programming (NSDP) which allows to compute solution in stages, each of them uses results from previous stages. The class of discrete optimization problems with the block-tree-structure matrix of constraints is considered. Nonserial dynamic programming (NSDP) algorithm for the solution of this class of problems is proposed. Properties of NSDP algorithm for the solution of the problems of this class are investigated.
Citation
submitted
Article
View Nonserial dynamic programming and local decomposition algorithms in discrete programming