دانلود رایگان ترجمه مقاله روشی نیمه مدولار برای برنامه نویسی پویای گسسته (نشریه الزویر 1995)

روشی نیمه مدولار برای برنامه نویسی پویای گسسته

A submodular approach to discrete dynamic programming

Abstract

Submodular functions are playing an increasing role in analyzing many discrete optimization problems. The purpose of this paper is to continue the trend by using submodular functions and their properties to develop a duality for discrete dynamic programming.

1 Introduction

Duality is one of the most elegant concepts and one of the important computational tools in mathematics. Duality’s contributions to analysis and optimization are many. However, as a result of the recursive nature of dynamic programming (DP), duality results for DP are quite limited.

Bellman [1,2] was the first to introduce a duality concept in dynamic programming. Bellman [1] used Lagrange multipliers to reduce the state space. This in itself does not result in a general duality theory for DP. However, this concept, which was later generalized by Everett [4], has played an increasingly important role in discrete optimization vis-a-vis Lagrangian relaxation.

Dinkle and Peterson [3] developed a duality theory for the class of dynamic programming problems that have convex return functions and linear transition functions through the use of generalized geometric programming duality. In their approach, Dinkle and Peterson viewed the primal and dual problems in terms of orthogonal spaces. This approach is not without possible drawbacks. As Rockafellar [9,10] noted, it may not be a very effective scheme since it doesn’t always lead to unambiguous Lagrangians. It also does not provide the most natural setting for the study of the optimal value functions and it could create a conceptual stumbling block in application if there is not an obvious subspace at hand. Klein and Morin [6,7] overcame this problem with a more general approach using conjugate functions. Aside from the previously mentioned results and the fact that numerous other authors have provided tantalizing hints, a general duality theory for dynamic programming does not appear to have been developed to date.

We will look at the shortest route problem on a directed acyclic network which is the prototype problem for Dynamic Programming (DP). In this paper we will show how a duality can be achieved for the DP formulation of the shortest route problem.