Sequence Model Solution

 Dynamic Programming Examples - Sequence Model

This example describes a sequencing problem for a set of wells in an off-shore oil field. We use it here to show the possibility of solving sequencing problems with dynamic programming. The problem is addressed in the paper: Optimal Sequential Exploration: A Binary Learning Model, by J. Eric Bickel and James E. Smith, Decision Analysis, Vol 3, No. 1, March 2006. The complete problem description, the model and the solution technique are found the paper. Here we concentrate on solving the stochastic DP using Excel. We use the DP Models add-in to build the model. The model is solved with the DP solver add-in. The solution obtained with the add-in is the same as the solution given in the paper.

Problem Description

The following is a copy of the first paragraph of the paper that provides an introduction to the topic.

 "The motivation for this paper began with a consulting engagement for a client that wanted to prioritize its deep-water oil and gas exploration program. The client had grouped the oil and gas prospects into clusters it believed to be geologically dependent and wanted to understand how the results for one well change the chance of success for the remaining undrilled prospects and how this information should affect the drilling strategy. Given that the wells cost tens of millions of dollars to drill, an optimal drilling program could generate significant savings and make an otherwise unattractive exploration opportunity economically viable. Researchers exploring multiple related R&D projects face similar problems—given dependent projects, which projects should they pursue first?"

In the following we deal with the problem of sequencing the drilling of six wells. We characterize a successful well as wet, and an unsuccessful well as dry. Data concerning the wells is in Table 1. The Include column indicates whether a particular well should be included in the sequence. The p column indicates the marginal (unconditioned on the sequence) probability that the well will be wet. The EV|wet column provides the expected net present worth of the cash flow of a wet well, where the present worth value is computed at the time of drilling. The EV/dry column is the expected net present worth of a dry well. Since no future cash flows are projected from a dry well, this is the cost of drilling. The EV column is expected return for the well considered alone from the other wells. It is, computed by the formula:

EV = (p)*EV|wet + (1 - p)*EV|dry

 Table 1. Example Well Data Well Include p EV|wet EV|dry EV 1 1 0.35 60.00 -35.00 -1.75 2 1 0.49 15.00 -20.00 -2.85 3 1 0.53 30.00 -35.00 -0.55 4 1 0.83 8.00 -40.00 -0.16 5 1 0.33 40.00 -20.00 -0.20 6 1 0.18 80.00 -20.00 -2.00

In this problem we have the choice of drilling the well or not. Based on the EV values in the table, none of the wells should be drilled. There may be benefits to considering the wells in order, however. When wells are drilled in sequence, the probabilities of wet or dry of a particular well may be affected by the success or failure of wells drilled earlier in the sequence.

Estimating the conditional probabilities is a major topic of the Bickel/Smith paper, but here we do not attempt to explain it. Through a series of questions to company experts, the researchers were able to compute the joint probabilities of complete scenarios. These are repeated from the paper in the table below. A scenario indicates the results for all six wells. Each scenario is described by a vector of 6 binary variables, with 1 indicating a wet well and 0 a dry well. For example one scenario is that all six wells are dry as shown as the first entry of the list , (0, 0, 0, 0, 0, 0). The probability of this scenario is estimated by the methods in the paper to be 0.0343. There are 2^6 or 64 scenarios.

We seek a sequence of drilling the wells that yields the maximum expected net present worth of oil field. The solution is not a deterministic sequence that is specified before any wills are drilled. Rather, the solution is a sequential decision rule that specifies the next well to drill, given the results for the wells drilling previously. This is called a policy. For example, if the policy is to drill 3 first, the next well in the sequence depends on whether well 3 is wet or dry. If it well 3 is wet, the next well to drill might be well 6. If well 3 is dry, the policy might be to abandon the field and drill no more wells.

To find the optimum policy we use stochastic dynamic programming. We first use the DP Models add-in to model the problem, and then use the DP Solver add-into find the solution. We use the table below to find event probabilities.

Dynamic Programming Model

 To create the DP model, select Add Models from the DP Models menu. On the ensuing dialog choose the MDP option. That presents the dialog to the left. The model consists of states defined by six state variables, one action variable and one event variable. We discuss the elements below.

Model Elements

 The state definition has six variables corresponding to the six wells. Each variable takes on three values, -1, 0 and 1. The value -1 indicates that the well has not yet been drilled. The 0 value means that the well has been drilled and found to be dry. The 1 value means that the well has been drilled and found to be wet. The count row indicates that there are 729 feasible state vectors. Cell E17 holds logical conditions that determine if a given state is feasible. For this problem only the variable bounds determine feasibility, so cell E17 is set to TRUE. The range labeled Include is provided to restrict the wells to be considered. A value of 0 would indicate that the associated well would not be drilled. All wells are included for this example. State names are determined in cell L20. An underline indicates that the well has not been drilled and 0 and 1 are used to show the results of drilling. States do not affect the objective value directly so row 21 has all zeros. A second state is shown for comparison. The states are enumerated by changing the index in E14. Each integer value represents a state. The index of 100 determines the state with wells 1, 3, and 5 not drilled. Well 2 is dry, well 4 is wet, and well 6 is dry. The action is described a single variable specifying the next well to drill. The example selects well 3. A value of 7 indicates that drilling is abandoned. The enumeration includes all 7 values of the action variable, but a logical expression in the feasibility cell (O17) restricts actions to the set of wells included in the problem and specified in the range F11:L11. The logical expression in O17 is: =INDEX(F11:L11,1,Well_DPM_Action)=1 The result is TRUE when the entry in the range corresponding to the action is equal to 1. Otherwise it is FALSE. Again the action has no direct effect on the NPW. The event vector has only two values, 0 representing dry and 1 representing wet. The event holds the NPW contribution and probability associated with the result. The NPW is the value at the time of drilling. The transition equations will further discount the value to the beginning of the study period. The probability of the wet result is computed from the scenario probabilities given in the table above. It is the probability of success of the well given the results of all drilling that occurred earlier in the sequence. The probability does not depend on the sequence of the wells, only on the set of drilled wells and whether they were wet or dry. This information is provided by the state variable. The example shown is for the state with no drilled wells, so the probability of the wet result for well 3 is simply the marginal probability from table 1. The NPW contribution is from Table 1. The same event for the state S_0_1_0 is shown at the left. Note that the conditional probability of well 3 being wet has been changed by the state. This probability depends on the scenario probability data given earlier. The formulas providing this result are on the worksheet for this example.

 Clicking the List States button at the top of the page, creates the list shown in part to the left. Including the Final state at the bottom of the list there are 730 entries on the list. This list and all the other lists described on this page are on the worksheet named Well Lists.

Decisions

Two decision subsets are defined in the model. The first describes the set of actions regarding drilling a well, as indicated by the upper bound of 6 on the action variable for the Decision 1 subset. The logical cell O39 is interesting because it only allows actions on wells not yet drilled. The logical expression implementing this is:

=INDEX(F35:L35,Well_DPM_DecAction)=-1

The range (F35:L35) holds the state vector plus a cell that represents the Quit decision. Cell P35 has the name "Well_DPM_DecAction". The expression allows only wells that have a -1 in the corresponding state vector. Cell L35 is included so the expression will not generate an error for action 7, Quit. Errors occurring with the INDEX function cause the program to prematurely terminate.

The second Decision subset is only for action 7, Quit. That action is identified as an Exit state with the value TRUE in Z46.

 Clicking the List Elements button at the top of the page, creates the Decision and Transition lists. The decision list combines feasible states with feasible actions to obtain feasible decisions. The first six decisions are for the state with no wells drilled. As drilling results are added, the number of feasible decisions decrease. There are 2188 decisions for this model.

Transitions

The transitions move the system from the current state to a new state. The new state depends on the current state, the action, and the event. The transition is affected through the Change State range in row 61. The equation in cell F61, refers to the action and event. When the cell represents the current action, the state is changed by adding +2 for a wet well and +1 for a dry well. The formula uses the Excel IF function.

=IF(Well_DPM_TransAction=F60,Well_DPM_TransEvent+1,0)

The objective term is reflected in cell Z57 and the probability of the event is in Z58.

 The program combines all feasible decisions with each of the event possibilities to obtain the Transition List. The first few and last few transitions are shown at the left. There are 3646 feasible transitions.
We see at the end of the list, the Final State. The final state has a transition that returns to itself. Except for the final state the transitions from all states go to a state with a greater index. This kind of state network is called an acyclic network because there can be no cycle leading from one state back to itself.

Summary

This particular model is for the well sequencing problem, but many of its features could be adapted to other sequencing problems. It is a fairly large problem for our Excel DP Solver, but once constructed it is solved readily. We discuss the solution on the next page.

Operations Research Models and Methods
Internet
by Paul A. Jensen