Solution of multistage decision making problem through dynamic programming

Dynamic programming is an optimization approach that transforms a complex problem into a sequence of simpler problems; its essential characteristic is the multistage nature of the optimization procedure. More so than the optimization techniques described previously, dynamic programming provides a general framework for analyzing many problem types. Within this framework a variety of optimization techniques can be employed to solve particular aspects of a more general formulation. Usually creativity is required before we can recognize that a particular problem can be cast effectively as a dynamic program; and often subtle insights are necessary to restructure the formulation so that it can be solved effectively.

Illustrations explain the paper; they do not show study data.

AI-generated illustration

↗ Enlarge

Iterative Problem ExpansionClose ×

AI-generated conceptual illustration (A series of interlocking geometric 3D cubes representing computational problem blocks). It explains the idea and does not show study data.

Open full-size image ↗

Introduction

The dynamic programming approach for solving multistage decision-making problems is presented. A general formulation is given followed by models of deterministic, stochastic, and adaptive versions of a particular multistage decision-making problem. The dynamic programming approach for solving multistage decision-making problems is presented. A general formulation is given followed by models of deterministic, stochastic, and adaptive versions of a particular multistage decision-making problem. Dynamic programming is a useful mathematical technique for making a sequence of interrelated decisions. It provides a systematic procedure for determining the optimal combination of decisions. In contrast to linear programming, there does not exist a standard mathematical formulation of "the" dynamic programming problem. Rather, dynamic programming is a general type of approach to problem solving, and the particular equations used must be developed to fit each situation. Therefore, a certain degree of ingenuity and insight into the general structure of dynamic programming problems is required to recognize when and how a problem can be solved by dynamic programming procedures. These abilities can best be developed by an exposure to a wide variety of dynamic programming applications and a study of the characteristics that are common to all these situations.

Review of Literatures

The key underlying philosophy behind the robust optimization modelling paradigm is that, in many practical situations, a complete stochastic description of the uncertainty may not be available. Instead, one may only have information with less detailed structure, such as bounds on the magnitude of the uncertain quantities or rough relations linking multiple unknown parameters. In such cases, one may be able to describe the unknowns by specifying a set in which all realizations should lie, the so-called "uncertainty set". The decision maker then seeks to ensure that the constraints in the problem remain feasible for any possible realization, while optimizing an objective that protects against the worst possible outcome. In its original form, proposed by [1][2] , robust optimization was mostly concerned with linear programming problems in which the data was inexact. Because of the column-wise structure of the uncertainty considered, the robust optimization problem amounted to taking the worst case for each parameter, which was very conservative and therefore limited its adoption by the operations research community, until new research efforts in the late 1990s devised approaches to control the degree of conservatism of the solution. The sequence of papers by [3][4][5][6][7] , [8][9] , followed by [1012] considerably generalized the earlier framework, by extending it to other classes of convex optimization problems beyond linear programming (quadratic, conic and semidefinite programs), as well as more complex descriptions of the uncertainty (intersections of ellipsoidal uncertainty sets, uncertainty sets with budgets of uncertainty, etc). A key feature of these papers was that the uncertainty set was cantered at the nominal value of the uncertain parameters and that the size of the set could be controlled by the decision maker to capture his level of aversion to ambiguity.

Robust Multi-Stage Decision Making

The stagecoach problem is a problem specially constructed1 to illustrate the features and to introduce the terminology of dynamic programming. It concerns a mythical fortune seeker in Missouri who decided to go west to join the gold rush in California during the mid-19th century. The journey would require traveling by stagecoach through unsettled country where there was serious danger of attack by marauders, Although his starting point and destination were fixed, he had considerable choice as to which states (or territories that subsequently became states) to travel through en route. Fortunately, dynamic programming provides a solution with much less effort than exhaustive enumeration. (The computational savings are enormous for larger versions of this problem.) Dynamic programming starts with a small portion of the original problem and finds the optimal solution for this smaller problem. It then gradually enlarges the problem, finding the current optimal solution from the preceding one, until the original problem is solved in its entirety. For the stagecoach problem, we start with the smaller problem where the fortune seeker has nearly completed his journey and has only one more stage (stagecoach run) to go. The obvious optimal solution for this smaller problem is to go from his current state (whatever it is) to his ultimate destination (state J). At each subsequent iteration, the problem is enlarged by increasing by 1 the number of stages left to go to complete the journey. For this enlarged problem, the optimal solution for where to go next from each possible state can be found relatively easily from the results obtained at the preceding iteration. The details involved in implementing this approach follow

Formulation

Let the decision variables xn (n 1, 2, 3, 4) be the immediate destination on stage n (the nth stagecoach run to be taken). Thus, the route selected is A x1 x2 x3 x4, where x4 J. Let fn(s, xn) be the total cost of the best overall policy for the remaining stages, given that the fortune seeker is in state s, ready to start stage n, and selects xn as the immediate destination. Given s and n, let xn * denote any value of xn (not necessarily unique) that minimizes fn(s, xn), and let f n * (s) be the corresponding minimum value of fn(s, xn). Thus, f n *(s) min fn(s, xn) fn(s, xn *), xn where

Solution Procedure

When the fortune seeker has only one more stage to go (n 4), his route thereafter is determined entirely by his current state s (either H or I) and his final destination x4 J, so the route for this final stagecoach run is s J. Therefore, since f 4 *(s) f4(s, J) cs, J, the immediate solution to the n 4 problem is When the fortune seeker has two more stages to go (n 3), the solution procedure requires a few calculations. For example, suppose that the fortune seeker is in state F. Then, as depicted below, he must next go to either state H or I at an immediate cost of cF,H 6 or cF,I 3, respectively. If he chooses state H, the minimum additional cost after he reaches there is given in the preceding table as f 4 *(H) 3, as shown above the H node in the diagram. Therefore, the total cost for this decision is 6 3 9. If he chooses state I instead, the total cost is 3 4 7, which is smaller. Therefore, the optimal choice is this latter one, x3 * I, because it gives the minimum cost f 3 *(F) 7. 536 11 D Similar calculations need to be made when you start from the other two possible states s E and s G with two stages to go.

Proceeding both graphically and algebraically [combining cij and f 4 *(s) values], to verify the following complete results for the n 3 problem.

1. Falk JE. Exact solutions of inexact linear programs. Operations Research. 1976; 24(4):783-787.
2. Soyster AL. Technical Note-Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming. Operations Research. 1973; 21(5):1154-1157.
3. Ben-Tal A, Nemirovski A. Robust convex optimization. Mathematics of Operations Research. 1998; 23(4):769805.
4. Ben-Tal A, Nemirovski A. Robust solutions of uncertain linear programs. Operations Research Letters. 1999; 25:1-13.
5. Ben-Tal A, Nemirovski A. Robust solutions of linear programming problems contaminated with uncertain data. Mathematical Programming, Series A. 2000; 88(3):411-424.
6. Ben-Tal A, Nemirovski A. Robust optimization - methodology and applications. Mathematical Programming. 2002; 92(3):453-480.
7. Ben-Tal A, Nemirovski A, Roos C. Robust solutions of uncertain quadratic and conic-quadratic problems. SIAM Journal on Optimization. 2002; 13(2):535-560.
8. El-Ghaoui L, Lebret H. Robust solutions to least-squares problems with uncertain data. SIAM Journal on Matrix Analysis and Applications. 1997; 18(4):1035-1064.
9. El-Ghaoui L, Oustry F, Lebret H. Robust solutions to uncertain semidefinite programs. SIAM Journal on Optimization. 1998; 9(1):33-52.
10. Bertsimas D, Pachamanova D, Sim M. Robust linear optimization under general norms. Operations Research Letters. 2004; 32(6):510-516.
11. Bertsimas D, Sim M. Robust discrete optimization and network flows. Mathematical Programming. 2003; 98(13):49-71.
12. Bertsimas D, Sim M. The price of robustness. Operations Research. 2004; 52(1):35-53.