Nonserial dynamic programming and local decomposition algorithms in discrete programming

Arnold Neumaier (Arnold.Neumaierunivie.ac.at)
Oleg Shcherbina (Oleg.Shcherbinaunivie.ac.at)

Abstract: 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.

Keywords: nonserial dynamic programming, discrete programming, decomposition, local decomposition algorithms, tree-like structures

Category 1: Combinatorial Optimization

Category 2: Other Topics (Dynamic Programming )

Category 3: Integer Programming (0-1 Programming )

Citation: submitted

Download: [PDF]

Entry Submitted: 03/15/2006
Entry Accepted: 03/16/2006
Entry Last Modified: 03/25/2006

Modify/Update this entry