GDDP: Generalized Dual Dynamic Programming Theory

This document presents theoretical considerations about the solution of dynamic optimization problems integrating the Benders Theory, the Dynamic Programming approach and the concepts of Control Theory. The so called Generalized Dual Dynamic Programming Theory (GDDP) can be considered as an extension of two previous approaches known as Dual Dynamic Programming (DDP): The first is the work developed by Pereira and Pinto [3–5], which was revised by Velásquez and others [8,9]. The second is the work developed by Read and others [2,6,7].     

Decision making and card collecting

^** D.K.Smith{at}exeter.ac.uk Collecting a set of different, yet similar, items is a popularhobby. The "coupon collector's problem" is concerned with thenumber of items which must be obtained, one at a time, in orderto complete the set, assuming that the collector is samplingfrom an infinite population where each item has a known probabilityof being found. In recent years, manufacturers have chosen toproduce the items in sealed packets which contain more thanone item, and possibly items from more than one set. This paperconsiders the problem of collecting items in packets, and thedecision problem faced by a collector who is offered the chanceto buy several packets at a discount. Dynamic programming isused to determine when it is worthwhile to purchase in bulk,for various sets and packets, as a function of the discountrate. Finally, mention is made of the other player in the transaction,the card manufacturer, who is also a decision-maker.     

动态模糊规划模型的构建及应用

常规规划模型通常存在如下两种缺陷:首先,它的目标系数及约束条件都是在硬性限制下的确定值,因而在建模方面弹性小、硬度大;其次,它的目标系数与时间无关,因此不能有效地刻划时时刻刻变化着的目标系数,而动态模糊规划模型可以有效地解决上述缺陷.首先应用模糊动态AHP确定目标系数;然后根据L-R模糊数的强序关系准则,将动态模糊规划模型分解为最优与最劣两个模糊规划模型;再根据以α水平截集为基础的求解方法,将上述两个模型进行相应的转换,建立具有风险分析功能的动态模糊规划模型;最后将其应用到一个实际算例中,收到较好的结果.     

Domain Decomposition of Optimal Control Problems for Dynamic Networks of Elastic Strings

We consider optimal control problems related to exact- and approximate controllability of dynamic networks of elastic strings. In this note we concentrate on problems with linear dynamics, no state and no control constraints. The emphasis is on approximating target states and velocities in part of the network using a dynamic domain decomposition method (d³m) for the optimality system on the network. The decomposition is established via a Uzawa-type saddle-point iteration associated with an augmented Lagrangian relaxation of the transmission conditions at multiple joints. We consider various cost functions and prove convergence of the infinite dimensional scheme for an exemplaric choice of the cost. We also give numerical evidence in the case of simple exemplaric networks.     

Learing from each other in a duopoly: Numerical approach

We consider a price-setting duopoly producing differentiated goods, where the players can learn by doing and from each other. The unit production cost is modelled as a decreasing function of accumulated knowledge. The game is noncooperative, played in a discrete time over an infinite horizon. Feedback Nash equilibrium strategies are sought. An algorithm to compute such equilibria is given, and ressults of numerical experiments concerned with symmetric and asymmetric duopolies are reported.This research was supported by the Natural Sciences and Engineering Research Council of Canada and the Centre d'Études en Administration Internationale, École des Hautes Études commerciales, Montréal, Canada. The authors wish to thank an anonymous referee for very helpful comments.     

Dynamic Pricing via Dynamic Programming<Superscript>1</Superscript>

This article specifies an efficient numerical scheme for computing optimal dynamic prices in a setting where the demand in a given period depends on the price in that period, cumulative sales up to the current period, and remaining market potential. The problem is studied in a deterministic and monopolistic context with a general form of the demand function. While traditional approaches produce closed-form equations that are difficult to solve due to the boundary conditions, we specify a computationally tractable numerical procedure by converting the problem to an initial-value problem based on a dynamic programming formulation. We find also that the optimal price dynamics preserves certain properties over the planning horizon: the unit revenue is linearly proportional to the demand elasticity of price; the unit revenue is constant over time when the demand elasticity is constant; and the sales rate is constant over time when the demand elasticity is linear in the price. ¹We acknowledge professor robert e. kalaba for initiating this work and suggesting solution methods.     

Corruption dynamics in democratic societies

This paper investigates the dynamics of corruption at the top (i.e., by politicians). For this purpose a dynamic, politico-economic framework is developed and analyzed. A particular feature of this investigation is an analytical characterization of the dynamic properties of the system. This allows one to interpret these properties in terms of economic and institutional parameters. As an example, the framework is applied to simulate Italian history from 1948 to today. © 1998 John Wiley & Sons, Inc.     

2.3. Methodology of OR

We present and analyze a generalization of the standard decision analysis model of sequential decisionmaking under risk. The decision tree is assumed given and all probabilities are assumed to be known precisely. Utility values are assumed to be affine in an imprecisely known parameter. The affine form is sufficiently general to allow importance weights or the utility values themselves to be represented by the imprecise parameter. Parameter imprecision is described by set inclusion. A relation on all available alternatives is assumed given for each decision node. The intent of each (not necessarily complete) relation is to model the decisionmaker's directly expressed preferences among the available alternatives at the associated decision node. A numerical procedure is developed to determine the set of all strategies that may be optimal and the corresponding set of all possible parameter values. An example illustrates the procedure.     

Stochastic equilibrium programming for dynamic oligopolistic markets

This paper deals with the concept of stochastic equilibrium programming (SEP), which has recently been proposed for the modeling of imperfect competition on uncertain dynamic markets. We show that the equilibria computed via SEP correspond to an information structure, called S-adapted open-loop, which is not common in the dynamic game literature. We compare the single-player case with the many-player case using a simple two-stage dynamical system. An illustration of the use of the approach for the modeling of imperfect dynamic markets is also provided.This research was supported by FCAR, Québec, Canada, by CRSNG, Canada, by DG XII, European Commission, and by SPPS, Belgium.     

Discrete allocation of a linear resource according to a sum-of-products objective

The allocation of a linear resource according to the sum of the returns from independent activities is considered. The return from each activity is given by a product of concave and nondecreasing functions of a single allocation variable. The model can be used, for instance, to describe probabilities of success of several serial tasks, into which an activity is subdivided. An incremental algorithm is defined and conditions are given for the algorithm to generate an optimal solution; otherwise, the problem is solved by a two-step procedure involving the incremental maximization of the return corresponding to a single activity and the combination of the activities by dynamic programming. Examples are given of problems solvable and not solvable by the incremental algorithm.     

A heuristic algorithm for a dial-a-ride problem with time windows,multiple capacities,and multiple objectives

The paper describes a system for the solution of a static dial-a-ride routing and scheduling problem with time windows (DARPTW). The problem statement and initialization of the development project was made by the Copenhagen Fire-Fighting Service (CFFS). The CFFS needed a new system for scheduling elderly and disabled persons, involving about 50.000 requests per year. The problem is characterized by, among other things, multiple capacities and multiple objectives. The capacities refer to the fact that a vehicle may be equipped with e.g. normal seats, children seats or wheel chair places. The objectives relate to a number of concerns such as e.g. short driving time, high vehicle utilization or low costs. A solution algorithm REBUS based on an insertion heuristics was developed. The algorithm permits in a flexible way weighting of the various goals such that the solution reflects the user's preferences. The algorithm is implemented in a dynamic environment intended for on-line scheduling. Thus, a new request for service is treated in less than 1 second, permitting an interactive user interface.     

The elixir of life: using a maintenance, repair and replacement model based on virtual and operating age in the water industry

Processing equipment in the water industry is subject to decayand requires maintenance, repair and eventual replacement. Thechallenge of competition within the water industry and the accompanyingregulatory regime requires that actions be integrated and costeffective. This is an industry, which has considerable dataon the failure of its equipment, but until recently very fewmodels of the maintenance process have been built. This paper describes the context of this problem for cleanwater processing where the equipment is that required to purifywater. It proposes a model based on the virtual and operatingage of the components. The operating age reflects the true ageof the equipment while the virtual age allows for the cumulativeeffect of maintenance actions performed on the equipment. Themodel also allows for different types of equipment by describingdegradation by Cox's proportional hazards model. Thus the specialfeatures of the equipment and environment in which the equipmentoperates are described by a set of characteristics, which modifythe hazard rate of the failure time of the equipment. This approachusing Cox's model with virtual and operating age can be appliedto other processing industries including the gas industry andthe ‘dirty water’ side of the water industry. The model is formulated as a stochastic dynamic programmingor Markov decision process and the form of the optimal policyis determined. This shows that repair and replacement shouldonly be performed when the equipment has failed and describesgeneral conditions when replacement is appropriate. The optimalpolicy is calculated numerically using the value iteration algorithmfor a specific example based on data on failure.     

Building an Optimal Portfolio in Discrete Time in the Presence of Transaction Costs

Abstract

Portfolio theory covers different approaches to the construction of a portfolio offering maximum expected returns for a given level of risk tolerance where the goal is to find the optimal investment rule. Each investor has a certain utility for money which is reflected by the choice of a utility function. In this article, a risk averse power utility function is studied in discrete time for a large class of underlying probability distribution of the returns of the asset prices. Each investor chooses, at the beginning of an investment period, the feasible portfolio allocation which maximizes the expected value of the utility function for terminal wealth. Effects of both large and small proportional transaction costs on the choice of an optimal portfolio are taken into account. The transaction regions are approximated by using asymptotic methods when the proportional transaction costs are small and by using expansions about critical points for large transaction costs.     

The design of corporate tax structures

We consider the corporate tax structuring problem (TaxSP), a combinatorial optimization problem faced by firms with multinational operations. The problem objective is nonlinear and involves the minimization of the firm's overall tax payments i.e. the maximization of shareholder returns. We give a dynamic programming (DP) formulation of this problem including all existing schemes of tax-relief and income-pooling. We apply state space relaxation and state space descent to the DP recursions and obtain an upper bound to the value of optimal TaxSP solutions. This bound is imbedded in a B&B tree search to provide another exact solution procedure. Computational results from DP and B&B are given for problems up to 22 subsidiaries. For larger size TaxSPs we develop a heuristic referred to as the Bionomic Algorithm (BA). This heuristic is also used to provide an initial lower bound to the B&B algorithm. We test the performance of BA firstly against the exact solutions of TaxSPs solvable by the B&B algorithm and secondly against results obtained for large-size TaxSPs by Simulated Annealing (SA) and Genetic Algorithms (GA). We report results for problems of up to 150 subsidiaries, including some real-world problems for corporations based in the US and the UK. Support for this work was provided by the IST Framework 5 Programme of the European Union, Contract IST2000-29405, Eurosignal ProjectMathematics Subject Classification (2000): 90C39, 91B28     

On characterizations of the ordered field of real numbers

This self-contained note could find classroom use in an introductory course on analysis. It is proved that an ordered field F is complete (that is, order-isomorphic to the field of real numbers) if and only if each bounded monotonic sequence in F converges in F. Also established is the key tool that an ordered field is complete if and only if it is Archimedean and Cauchy-complete, along with a number of characterizations of Archimedean fields.     

Global Optimization with Nonlinear Ordinary Differential Equations

This paper examines global optimization of an integral objective function subject to nonlinear ordinary differential equations. Theory is developed for deriving a convex relaxation for an integral by utilizing the composition result defined by McCormick (Mathematical Programming 10, 147–175, 1976) in conjunction with a technique for constructing convex and concave relaxations for the solution of a system of nonquasimonotone ordinary differential equations defined by Singer and Barton (SIAM Journal on Scientific Computing, Submitted). A fully automated implementation of the theory is briefly discussed, and several literature case study problems are examined illustrating the utility of the branch-and-bound algorithm based on these relaxations.     

A fair and time‐consistent sharing of the joint exploitation payoff of a fishery

We consider the problem of efficiently managing a fishery where pollution externalities are present. The open‐access bionomic model is analyzed in an ‐player differential game framework with two‐state variables, that is, the fish stock and the pollution stock. We characterize the noncooperative feedback‐Nash equilibrium and cooperative solution, and define an egalitarian sharing rule to allocate the joint welfare maximizing payoff over an infinite time horizon, and show that this rule is time consistent. Recommendations for Resource Managers

• ● Cooperation in management of a fishery where pollution externalities are present yields a higher payoff over time as compared to the noncooperative behavior.
• ● The dividend of cooperation can be allocated among the fisherpersons according to an egalitarian sharing rule.
• ● This allocation is time‐consistent, that is, no player will be tempted to deviate from cooperation as time goes by, and the initial agreement is sustainable.

     

Efficient Sequential Quadratic Programming Implementations for Equality-Constrained Discrete-Time Optimal Control

Efficient sequential quadratic programming (SQP) implementations are presented for equality-constrained, discrete-time, optimal control problems. The algorithm developed calculates the search direction for the equality-based variant of SQP and is applicable to problems with either fixed or free final time. Problem solutions are obtained by solving iteratively a series of constrained quadratic programs. The number of mathematical operations required for each iteration is proportional to the number of discrete times N. This is contrasted by conventional methods in which this number is proportional to N ³. The algorithm results in quadratic convergence of the iterates under the same conditions as those for SQP and simplifies to an existing dynamic programming approach when there are no constraints and the final time is fixed. A simple test problem and two application problems are presented. The application examples include a satellite dynamics problem and a set of brachistochrone problems involving viscous friction.     

A note on an optimal choice problem

An item has probabilityp ₀ of not being workable. Before, going into use it has to be controlled by some deliberately chosen checksC _i which costsc _i 0,1in. Total checking costs must be not larger thanc ₀>0. It may happen that a check breaks a workable item, and failures may be overlooked. The problem is to determine an optimal sequence of checks subject to the cost constraints, such that the probability is maximized that an item leaving the checks is workable. In [1] this problem is solved by W. Stadje, but numerically the solution method only is applicable to problems of modest size.In this paper a simple reformulation of the original problem is presented. This first allows a simpler derivation of some of the results in [1]. Further, a dynamic programming algorithm is presented, which is pseudopolynomial, if costsc _i are integers. It then requiresO(n·c ₀) time.