On a class of dynamic programming problems whose optimal controls and states are independent of the future

When applying dynamic programming for optimal decision making one usually needs considerable knowledge about the future. This knowledge, e.g. about future functions and parameters, necessary to determine optimal control policies, however, is often not available and thus precludes the application of dynamic programming.In the present paper it is shown that for a certain class of dynamic programming problems the optimal control policy is independent of the future. To illustrate the results an application in inventory control is given and further applications in the theories of economic growth and corporate finance are listed in the references.     

A hybrid approach to discrete mathematical programming

The dynamic programming and branch-and-bound approaches are combined to produce a hybrid algorithm for separable discrete mathematical programs. Linear programming is used in a novel way to compute bounds. Every simplex pivot permits a bounding test to be made on every active node in the search tree. Computational experience is reported.     

The application of optimal control methodology to nonlinear programming problems

Dynamic programming techniques have proven to be more successful than alternative nonlinear programming algorithms for solving many discrete-time optimal control problems. The reason for this is that, because of the stagewise decomposition which characterizes dynamic programming, the computational burden grows approximately linearly with the numbern of decision times, whereas the burden for other methods tends to grow faster (e.g.,n ³ for Newton's method). The idea motivating the present study is that the advantages of dynamic programming can be brought to bear on classical nonlinear programming problems if only they can somehow be rephrased as optimal control problems.As shown herein, it is indeed the case that many prominent problems in the nonlinear programming literature can be viewed as optimal control problems, and for these problems, modern dynamic programming methodology is competitive with respect to processing time. The mechanism behind this success is that such methodology achieves quadratic convergence without requiring solution of large systems of linear equations.     

Multicriteria integer programming: A (hybrid) dynamic programming recursive approach

Dynamic programming recursive equations are used to develop a procedure to obtain the set of efficient solutions to the multicriteria integer linear programming problem. An alternate method is produced by combining this procedure with branch and bound rules. Computational results are reported.     

Lipschitz continuous dynamic programming with discount II

We construct an alternative theoretical framework for stochastic dynamic programming which allows us to replace concavity assumptions with more flexible Lipschitz continuous assumptions. This framework allows us to prove that the value function of stochastic dynamic programming problems with discount is Lipschitz continuous in the presence of nonconcavities in the data of the problem. Our method allows us to treat problems with noninterior optimal paths. We also describe a discretization algorithm for the numerical computation of the value function, and we obtain the rate of convergence of this algorithm.     

Integer programming approach to reactive scheduling in make-to-order manufacturing

New algorithms based on mixed integer programming formulations are proposed for reactive scheduling in a dynamic, make-to-order manufacturing environment. The problem objective is to update a long-term production schedule subject to service level and inventory constraints, whenever the customer orders are modified or new orders arrive. Different rescheduling policies are proposed, from a total reschedule of all remaining and unmodified customer orders to a non-reschedule of all such orders. In addition, a medium restrictive policy is considered for rescheduling only a subset of remaining customer orders awaiting material supplies. Numerical examples modeled after a real-world scheduling/rescheduling of customer orders in the electronics industry are presented and some results of computational experiments are reported.     

Optimality in transient markov chains and linear programming

It is shown how a discrete Markov programming problem can be transformed, using a linear program, into an equivalent problem from which the optimal decision rule can be trivially deduced. This transformation is applied to problems which have either transient probabilities or discounted costs.This research was supported by the National Research Council of Canada, Grant A7751.     

Contractivity of Bellman operator in risk averse dynamic programming with infinite horizon

The paper deals with a risk averse dynamic programming problem with infinite horizon. First, the required assumptions are formulated to have the problem well defined. Then the Bellman equation is derived, which may be also seen as a standalone reinforcement learning problem. The fact that the Bellman operator is contraction is proved, guaranteeing convergence of various solution algorithms used for dynamic programming as well as reinforcement learning problems, which we demonstrate on the value iteration and the policy iteration algorithms.     

Portfolio optimization in a Lévy market with intertemporal substitution and transaction costs

We investigate an infinite horizon investment-consumption model in which a single agent consumes and distributes her wealth between a risk-free asset (bank account) and several risky assets (stocks) whose prices are governed by Lévy (jump-diffusion) processes. We suppose that transactions between the assets incur a transaction cost proportional to the size of the transaction. The problem is to maximize the total utility of consumption under Hindy-Huang-Kreps intertemporal preferences. This portfolio optimisation problem is formulated as a singular stochastic control problem and is solved using dynamic programming and the theory of viscosity solutions. The associated dynamic programming equation is a second order degenerate elliptic integro-differential variational inequality subject to a state constraint boundary condition. The main result is a characterization of the value function as the unique constrained viscosity solution of the dynamic programming equation. Emphasis is put on providing a framework that allows for a general class of Lévy processes. Owing to the complexity of our investment-consumption model, it is not possible to derive closed form solutions for the value function. Hence, the optimal policies cannot be obtained in closed form from the first order conditions for the dynamic programming equation. Therefore, we have to resort to numerical methods for computing the value function as well as the associated optimal policies. In view of the viscosity solution theory, the analysis found in this paper will ensure the convergence of a large class of numerical methods for the investment-consumption model in question.     

A multi-parametric programming approach for constrained dynamic programming problems

In this work, we present a new algorithm for solving complex multi-stage optimization problems involving hard constraints and uncertainties, based on dynamic and multi-parametric programming techniques. Each echelon of the dynamic programming procedure, typically employed in the context of multi-stage optimization models, is interpreted as a multi-parametric optimization problem, with the present states and future decision variables being the parameters, while the present decisions the corresponding optimization variables. This reformulation significantly reduces the dimension of the original problem, essentially to a set of lower dimensional multi-parametric programs, which are sequentially solved. Furthermore, the use of sensitivity analysis circumvents non-convexities that naturally arise in constrained dynamic programming problems. The potential application of the proposed novel framework to robust constrained optimal control is highlighted.     

A dynamic programming approach to adjustable robust optimization

In this paper we consider the adjustable robust approach to multistage optimization, for which we derive dynamic programming equations. We also discuss this from the point of view of risk averse stochastic programming. We consider as an example a robust formulation of the classical inventory model and show that, like for the risk neutral case, a basestock policy is optimal.     

Optimal design of a membrane separation process using signomial programming

A multistage membrane separation process for hydrogen recovery is described and formulated as a signomial programming problem. Two different configurations are examined. A 3-stage and a 5-stage process design problem are solved. The optimal solution to these programs is computed from an initial point that does not satisfy the mass balance or transport constraints of the process, using a primal-based geometric programming code. Also examined is the sensitivity of the optimal solution to changes in purity requirements. In all cases, computation times are very reasonable ranging from 2 to 4 seconds of IBM 370/165 CPU time.     

Dynamic programming and minimum risk paths

This paper addresses the problem of computing minimum risk paths by taking as objective the expected accident cost. The computation is based on a dynamic programming formulation which can be considered an extension of usual dynamic programming models: path costs are recursively computed via functions which are assumed to be monotonic. A large part of the paper is devoted to analyze in detail this formulation and provide some new results. Based on the dynamic programming model a linear programming model is also presented to compute minimum risk paths. This formulation turns out to be useful in solving a biobjective version of the problem, in which also expected travel length is taken into consideration. This leads to define nondominated mixed strategies. Finally it is shown how to extend the basic updating device of dynamic programming in order to enumerate all nondominated paths.     

Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints

When vehicle routing problems with additional constraints, such as capacity or time windows, are solved via column generation and branch-and-price, it is common that the pricing subproblem requires the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the vertices. A common solution technique for this problem is dynamic programming. In this paper we illustrate how the basic dynamic programming algorithm can be improved by bounded bi-directional search and we experimentally evaluate the effectiveness of the enhancement proposed. We consider as benchmark problems the elementary shortest path problems arising as pricing subproblems in branch-and-price algorithms for the capacitated vehicle routing problem, the vehicle routing problem with distribution and collection and the capacitated vehicle routing problem with time windows.     

背包问题的两阶段动态规划算法

本文通过理论分析给出了背包问题的两阶段动态规划算法，用例题说明了其求解过程。在计算机上运用本文所述算法和背包问题的动态规划算法求解了大量例题。解题实践说明，对于大中型背包问题，两阶段动态规划算法由于只要求对少量变量进行排序而使解题时间大为缩短，是一种值得推荐的算法。     

Interactive fuzzy goal programming approach for bilevel programming problem

This paper presents an interactive fuzzy goal programming (FGP) approach for bilevel programming problems with the characteristics of dynamic programming (DP).     

Dynamic programming in stochastic control of systems with delay

We consider optimal control problems for systems described by stochastic differential equations with delay (SDDE). We prove a version of Bellman's principle of optimality (the dynamic programming principle) for a general class of such problems. That the class in general means that both the dynamics and the cost depends on the past in a general way. As an application, we study systems where the value function depends on the past only through some weighted average. For such systems we obtain a Hamilton-Jacobi-Bellman partial differential equation that the value function must solve if it is smooth enough. The weak uniqueness of the SDDEs we consider is our main tool in proving the result. Notions of strong and weak uniqueness for SDDEs are introduced, and we prove that strong uniqueness implies weak uniqueness, just as for ordinary stochastic differential equations.     

Shadow prices in nonconvex mathematical programming

In this paper a definition is proposed for the concept of shadow prices in nonconvex programming. For a nonlinear program with equality and inequality constraints, existence of these prices and bounds for their possible values are obtained under the Mangasarian—Fromowitz regularity condition. Their exact values and some continuity properties are obtained under the more restrictive linear independence regularity condition. A definition of equilibrium prices is also proposed. Under convexity assumptions, all definitions and results coincide with those already known on this subject in convex programming.This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant A-9273.     

Distributed asynchronous computation of fixed points

We present an algorithmic model for distributed computation of fixed points whereby several processors participate simultaneously in the calculations while exchanging information via communication links. We place essentially no assumptions on the ordering of computation and communication between processors thereby allowing for completely uncoordinated execution. We provide a general convergence theorem for algorithms of this type, and demonstrate its applicability to several classes of problems including the calculation of fixed points of contraction and monotone mappings arising in linear and nonlinear systems of equations, optimization problems, shortest path problems, and dynamic programming. This research was contacted at the M.I.T. Laboratory for Information and Decision Systems with partial support provided by the Defense Advanced Research Projects Agency under Grant No. ONR-N00014-75-C-1183.