Search

Abstract. We present a perfect formulation for a single generator in the unit commitment problem, inspired by the dynamic programming approach taken by Frangioni and Gentile. This generator can have [...]

We present a novel method for deriving tight Monte Carlo confidence intervals for solutions of stochastic dynamic programming equations. Taking some approximate solution to the equation as an input, we construct pathwise recursions with a known bias. Suitably coupling the recursions for lower and upper bounds ensures that the method is applicable even when the dynamic program does not satisfy a comparison principle. We apply our method to three nonlinear option pricing problems, pricing under bilateral counterparty risk, under uncertain volatility, and under negotiated collateralization. Funding: Financial support by the Deutsche Forschungsgcmeinschaft under grant BE3933/5-1 is gratefully acknowledged. Keywords: stochastic dynamic programming * Monte Carlo * confidence bounds * option pricing, 1. Introduction We study the problem of computing Monte Carlo confidence intervals for solutions of discrete-time, finitehorizon stochastic dynamic programming equations. There is a random terminal value, and a nonlinear [...]

Abstract. Recent research on location-routing problems has been focusing on locating facilities as the starting and end point of routes. In this paper, we investigate a new type of location-routing [...]

Abstract. We study same-day delivery systems by formulating the dynamic dispatch waves problem (DDWP), which models a depot where delivery requests arrive dynamically throughout a service day. At any dispatch [...]

Abstract. We consider the problem of reinforcement learning over episodes of a finite-horizon deterministic system and as a solution propose optimistic constraint propagation (OCP), an algorithm designed to synthesize efficient [...]

We propose empirical dynamic programming algorithms for Markov decision processes. In these algorithms, the exact expectation in the Bellman operator in classical value iteration is replaced by an empirical estimate [...]

We study a class of stochastic target games where one player tries to find a strategy such that the state process almost surely reaches a given target, no matter which [...]

The theory of dynamic programming is formulated using finitely additive probability measures defined on sets of Arbitrary cardinality. Many results from the conventional countably additive theory generalize, and the proofs [...]

We study a constrained stochastic control problem with jumps; the jump times of the controlled process are given by a Poisson process. The cost functional comprises quadratic components for an [...]

We study the problem faced by a supplier deciding how to dynamically allocate limited capacity among a portfolio of customers who remember the fill rates provided to them in the past. A customer's order quantity is positively correlated with past fill rates. Customers differ from one another in their contribution margins, their sensitivities to the past, and in their demand volatilities. By analyzing and comparing policies that ignore goodwill with ones that account for it, we investigate when and how customer memory effects impact supplier profits. We develop an approximate dynamic programming policy that dynamically rationalizes the fill rates the firm provides to each customer. This policy achieves higher rewards than margin-greedy and Lagrangian policies and yields insights into how a supplier can effectively manage customer memories to its advantage. Key words: dynamic programming; approximate; behavioral operations; customer relationship management; capacity allocation History: Received January 10, 2012; accepted July 17, 2012, by Martin Lariviere, operations management. Published online in Articles in Advance December 19, 2012., 1. Introduction Whenever a firm doing business with a handful of customers (or customer segments) faces more demand than it can supply, it faces a tough choice. On the one [...]

Consider a network .N = (N, A) and associate with each arc e [member of] A a fixed cost ce for using arc e, an interval [[l.sub.e], [u.sub.e]] ([l.sub.e], [u.sub.e] [...]

Consumers become satiated with a product when purchasing too much too quickly. How much is too much and how quickly is too quickly depends on the characteristics of the product relative to the time interval between consumption periods. Knowing that, consumers allocate their budget to products that generate less satiation effects. Retailers should then choose to sell products that induce minimal satiation, but usually this is operationally more costly. To study this trade-off, we provide an analytical model based on utility theory that relates customer consumption to price and satiation, in the context of multiple competing retailers. We determine the purchasing pattern over time and provide an explicit expression to determine the consumption level in steady state. We derive market shares and show that they take the form of an attraction model in which the attractiveness depends on price and product satiation. We use this to analyze the competition between firms that maximize long-term average profit. We characterize the equilibrium under three scenarios: (i) price-only competition, (ii) product-only competition, and (iii) price and product competition. The results reveal the interplay between a key marketing lever (price) and the firm's ability to offer products that generate less satiation. In particular, we show that when a firm becomes more efficient at reducing satiation, its competitor may benefit if competition is on product only, but not if it is on price and product. We also find that when satiation effects are not managed, a firm's profit may be significantly reduced while a strategic competitor can largely benefit. Key words: utility preference; dynamic programming: deterministic, discrete time; marketing: product policy History: Received October 13, 2010; accepted October 15, 2011, by Yossi Aviv, operations management. Published online in Articles in Advance April 6, 2012., 1. Introduction For many products, consumers tend to make different purchasing decisions over time. For example, most people would usually avoid eating the exact same meal in the exact same [...]

We provide a practical methodology for solving the generalized joint replenishment (GJR) problem, based on a mathematical programming approach to approximate dynamic programming. We show how to automatically generate a [...]

This paper examines the problem of finding an optimal operating policy for Hydro-Quebec's Manicouagan River and Outardes River hydroelectric installations. The solution method is based on the sampling dynamic programming (SSDP) algorithm. We use a new hydrologic state variable to capture the inflows regime, and this variable is given by a linear combination of the snow water equivalent and soil moisture. In real-time operation, this variable is calculated by a hydrologic model and incorporated in the operating policy to calculate the water released at each power plant. The algorithm is compared to the lag-1 stochastic dynamic programming (SDP) already implemented at Hydro-Quebec, through a statistical analysis with a set of 40 synthetic historical inflow scenarios obtained by hydrologic modeling, using synthetic temperature and precipitation produced by a stochastic weather generator. The results of the analysis show that the SSDP operating policy is statistically superior to the operating policy of the lag-1 SDP model. The SSDP operating policy does not underestimate the volume of runoff occurring during the spring season contrary to SDP. Consequently, there is a reduction in the [hm.sup.3] of water spilled, while the average annual generation is increased. Key words: hydropower system, stochastic dynamic programming, sampling stochastic dynamic programming, snow water equivalent, soil moisture, operating policy, weather generator. Cet article etudie le probleme de trouver une politique optimale d'exploitation des centrales hydroelectriques d'Hydro-Quebec sur les rivieres Manicouagan et aux Outardes. La methode de resolution est basee sur l'algorithme de programmation dynamique stochastique par echantillonnage (SSDP--sampling stochastic dynamic programming). Nous utilisons une nouvelle variable de l'etat hydrologique pour saisir les debits entrants; cette variable est donnee par une combinaison lineaire de l'equivalent en eau de la neige et de l'eau dans le sol. Dans une exploitation en temps reel, cette variable est calculee par un modele hydrologique et incorporee dans la politique d'exploitation afin de calculer la quantite d'eau liberee par chaque centrale. L'algorithme est compare a la programmation dynamique stochastique (SDP--stochastic dynamic programming) lag-1 deja utilise a Hydro-Quebec par le truchement d'une analyse statistique d'un ensemble de 40 scenarios historiques de debits entrants obtenus par modelisation hydrologique utilisant une temperature et une precipitation artificielles produites par un generateur meteorologique stochastique. Les resultats de l' analyse montrent que la politique d'exploitation SSDP est superieure d'un point de vue statistique a la politique d'exploitation du modele SDP lag-1. Contrairement au SDP, la politique d'exploitation SSDP ne sous-estime pas le volume de ruissellement printanier. Ainsi, il y a reduction des [hm.sup.3] d' eau deverses tout en augmentant la moyenne annuelle produite. Mots-cles : systeme hydroelectrique, programmation stochastique dynamique, programmation dynamique stochastique d'echantillonnage, equivalent en eau de la neige, eau dans le sol, politique d'exploitation, generateur meteorologique. [Traduit par la Redaction], 1. Introduction The operation of a hydroelectric power system entails the solution of a stochastic optimization problem, and such a problem is difficult to solve for many reasons. First, the [...]

This paper considers the efficient exact computation of the counterpart of the Gittins index for a finite-horizon discrete-state bandit, which measures for each initial state the average productivity, given by [...]

Through recent technical advances, multiple resources can be connected to provide a computing grid for processing computationally intensive applications. We build on an approach, termed sequential grid computing, that takes [...]

We give a dynamic programming solution to the problem of scheduling scenes to minimize the cost of the talent. Starting from a basic dynamic program, we show a number of [...]

We consider a dynamic inventory (production) model with general convex order (production) costs and excess demand that can be accepted or refused by the firm. Excess demand that is accepted is backlogged and results in a backlog cost whereas demand that is refused results in a lost.sales charge. Endogenizing the sales decision is appropriate in the presence of general convex order costs so that the firm is not forced to backlog a unit whose subsequent satisfaction would reduce total profits. In each period, the firm must determine the optimal order and sales strategy. We show that the optimal policy is characterized by an optimal buy-up-to level that increases with the initial inventory level and an order quantity that decreases with the initial inventory level. More importantly, we show the optimal sales strategy is characterized by a critical threshold, a backlog limit, that dictates when to stop selling. This threshold is independent of the initial inventory level and the amount purchased. We investigate various properties of this new policy. As demand stochastically increases, the amount purchased increases but the amount backlogged decreases, reflecting a shift in the way excess demand is managed. We develop two regularity conditions, one that ensures some backlogs are allowed in each period, and another that ensures the amount backlogged is nondecreasing in the length of the planning horizon. We illustrate the buy-up-to levels in our model are bounded above by buy-up-to levels from the pure lost sales and pure backlogging models. We explore additional extensions using numerical experiments. Key words: inventory-production policies; dynamic programming; stochastic History: Received February 19, 2009; accepted July 31, 2010, by Yossi Aviv, operations management., 1. Introduction and Prior Literature Firms that produce inventory or buy large quantities of inventory sometimes incur increasing marginal unit costs. For example, this occurs when a firm buys inventory [...]

In this paper, we study the curfew planning problem (CPP) encountered by railroads for the maintenance of their railway tracks. The CPP is to design an optimal annual timetable to [...]

Communications between cells in large part drive tissue development and function, as well as disease-related processes such as tumorigenesis. Understanding the mechanistic bases of these processes necessitates quantifying specific molecules in adjacent cells or cell nuclei of intact tissue. However, a major restriction on such analyses is the lack of an efficient method that correctly segments each object (cell or nucleus) from 3-D images of an intact tissue specimen. We report a highly reliable and accurate semi-automatic algorithmic method for segmenting fluorescence-labeled cells or nuclei from 3-D tissue images. Segmentation begins with semi-automatic, 2-D object delineation in a user-selected plane, using dynamic programming (DP) to locate the border with an accumulated intensity per unit length greater that any other possible border around the same object. Then the two surfaces of the object in planes above and below the selected plane are found using an algorithm that combines DP and combinatorial searching. Following segmentation, any perceived

This paper presents the optimization and implementation of a relaxed dynamic programming (RDP) algorithm to generate a daily control scheduling for optimal or near-optimal air conditioner loads (ACLs). The conventional control mode for ACL includes demand control, cycling control, and timer control, to assist customers for saving electricity costs. The proposed load control scheduler (LCS) scheme supports any combination of these three control types to save costs optimally during the dispatch period. Microprocessor hardware techniques were applied to carry out the proposed strategy for realistic application. The Visual [C.sup.++] language was adopted as the developing tool to carry out the proposed work. Field tests of controlling air conditioners located in the campus of National Kaohsiung University of Applied Sciences, Kaohsiung, Taiwan, were tested on-site to demonstrate the effectiveness of the proposed load control strategy. The results show that interruptible load scheduling can reduce the system load effectively, and the load capacity reduced by the proposed load control strategy follows closely the trajectory of the peak load. Index Terms--Implementation, load control scheduler, optimization, relaxed dynamic programming.

A particular scheduling problem over a single machine is considered. Jobs belong to different classes, and two jobs belonging to the same class are considered as completely equivalent. A sequence of due dates is specified for each class of jobs, and the serviced jobs, for each class, are assigned to the due dates according to the EDD rule. The service time of any job of a given class has to be selected within an interval of possible values (the highest possible one being the nominal service time). A deviation of the actual service time from the nominal value determines a cost that has a linear dependence on such a deviation. The cost function to be minimized is the sum of the total (weighted) tardiness cost and the overall service time deviation cost. The decision variables are those concerning job sequencing (taking into account the equivalence of jobs of the same class) and service times. In this paper, a solution to this problem is provided in terms of closed-loop strategies. Index Terms--Controllable processing times, dynamic programming, manufacturing systems, optimal control, scheduling algorithms.

The understanding of drinking patterns leading to alcoholism has been hindered by an inability to unobtrusively measure ethanol consumption over periods of weeks to months in the community environment. An implantable ethanol sensor is under development using microelectromechanical systems technology. For safety and user acceptability issues, the sensor will be implanted subcutaneously and, therefore, measure peripheral-tissue ethanol concentration. Determining ethanol consumption and kinetics in other compartments from the time course of peripheral-tissue ethanol concentration requires sophisticated signal processing based on detailed descriptions of the relevant physiology. A statistical signal processing system based on detailed models of the physiology and using extended Kalman filtering and dynamic programming tools is described which can estimate the time series of ethanol concentration in blood, liver, and peripheral tissue and the time series of ethanol consumption based on peripheral-tissue ethanol concentration measurements. Index Terms--Bio-sensor, dynamic programming, ethanol consumption model, ethanol PBPK model, ethanol pharmacokinetics model, extended Kalman smoothing.

In this paper, the duality in differential form is developed between a 3D primal surface and its dual manifold formed by the surface's tangent planes, that is, each tangent plane of the primal surface is represented as a four-dimensional vector that constitutes a point on the dual manifold. The iterated dual theorem shows that each tangent plane of the dual manifold corresponds to a point on the original 3D surface, that is, the "dual" of the "dual" goes back to the "primal." This theorem can be directly used to reconstruct 3D surface from image edges by estimating the dual manifold from these edges. In this paper, we further develop the work in our original conference papers resulting in the robust differential dual operator. We argue that the operator makes good use of the information available in the image data by using both points of intensity discontinuity and their edge directions; we provide a simple physical interpretation of what the abstract algorithm is actually estimating and why it makes sense in terms of estimation accuracy; our algorithm operates on all edges in the images, including silhouette edges, self occlusion edges, and texture edges, without distinguishing their types (thus, resulting in improved accuracy and handling locally concave surface estimation if texture edges are present); the algorithm automatically handles various degeneracies; and the algorithm incorporates new methodologies for implementing the required operations such as appropriately relating edges in pairs of images, evaluating and using the algorithm's sensitivity to noise to determine the accuracy of an estimated 3D point. Experiments with both synthetic and real images demonstrate that the operator is accurate, robust to degeneracies and noise, and general for reconstructing free-form objects from occluding edges and texture edges detected in calibrated images or video sequences. Index Terms--3D reconstruction robust to degeneracies and noise, duality in differential form, dual manifold, multiview reconstruction, shape from silhouettes, shape from occlusions and textures, dynamic programming.

In cricket, a rain-affected pitch can make batting more difficult than normal. Several other conditions such as poor light or an initially lively pitch, may also result in difficulties for the batsmen. In this note, we refer to all of them as 'sticky wickets'. On sticky wickets, lower order batsmen are often sent into 'hold the fort' until conditions improve. In this paper, a stochastic dynamic programming model is used to examine the appropriateness of this policy. The model suggests that the tactic is often optimal when the sticky wicket persists until the end of the day's play, but not often when the sticky wicket is transitory. In some circumstances, it is worthwhile, on a normal wicket near the end of the day, to send in a lower order batsman to hold the fort (a night watchman): when the wicket is sticky, this tactic is even more worthwhile. Keywords: sports; cricket; dynamic programming; strategies

In this note, we show that min-max model predictive control (MPC) for linearly constrained polytopic systems with quadratic cost can be cast as a quadratically constrained quadratic program (QCQP). We use the rigorous closed loop formulation of min-max MPC, and show that any such min-max MPC problem with convex costs and constraints can be cast as a finite dimensional convex optimization problem, with the QCQP arising from quadratic costs as a special case. At the base of the proof is a lemma showing the convexity of the dynamic programming cost-to-go, which implies that the worst case on an infinite polytopic set is assumed on one of its finitely many vertices. As the approach is based on a scenario tree formulation, the number of variables in this problem grows exponentially with the horizon length. Fortunately, the QCQP is tree structured, and can thus be efficiently solved by specially tailored interior-point methods whose computational costs are linear in the number of variables. The new formulation as a tree sparse QCQP promises to facilitate online solution of the rigorous min-max MPC problem with quadratic costs. Index Terms--Constraints, convex programming, model predictive control (MPC), receding horizon control (RHC), robustness.

For applications such as behavior recognition it is important to maintain the identity of multiple targets, while tracking them in the presence of splits and merges, or occlusion of the targets by background obstacles. Here we propose an algorithm to handle multiple splits and merges of objects based on dynamic programming and a new geometric shape matching measure. We then cooperatively combine Kalman filter-based motion and shape tracking with the efficient and novel geometric shape matching algorithm. The system is fully automatic and requires no manual input of any kind for initialization of tracking. The target track initialization problem is formulated as computation of shortest paths in a directed and attributed graph using Dijkstra's shortest path algorithm. This scheme correctly initializes multiple target tracks for tracking even in the presence of clutter and segmentation errors which may occur in detecting a target. We present results on a large number of real world image sequences, where upto 17 objects have been tracked simultaneously in real-time, despite clutter, splits, and merges in measurements of objects. The complete tracking system including segmentation of moving objects works at 25 Hz on 352 x 288 pixei color image sequences on a 2.8-GHz Pentium-4 workstation. Index Terms--Data association, dynamic programming (DP), Kalman filtering, multitarget tracking (MTT), shape matching, split and merge.

In this note, non-smooth finite-time stabilization of nonlinear systems with parametric and dynamic uncertainties is investigated. To solve this problem, the input-to-state stability property is used to characterize unmeasured dynamic uncertainties. A constructive partial-state control design is proposed on the basis of involved combined use of Lyapunov, backstepping and input-to-state stability techniques. Under small-gain type local conditions, a solution for the finite-time regulation of a class of uncertain nonlinear systems is obtained. Index Terms--Dynamic uncertainties, finite-time convergence, input-to-state stability (ISS), nonsmooth feedback, parametric uncertainties.

We consider the constrained finite and infinite time optimal control problem for the class of discrete-time linear hybrid systems. When a linear performance index is used the finite and infinite time optimal solution is a piecewise affine state feedback control law. In this paper, we present algorithms that compute the optimal solution to both problems in a computationally efficient manner and with guaranteed convergence and error bounds. Both algorithms combine a dynamic programming exploration strategy with multiparametric linear programming and basic polyhedral manipulation. Index Terms--Constrained systems, discrete-time, dynamic programming, finite time, hybrid systems, infinite time, mnitiparametric linear program, optimal control, piecewise affine systems.

Contemporary wireless systems combine aspects of network theory such as scheduling, throughput, and delay as well as information theory aspects such as capacity, coding, and power control. Design of such systems requires joint optimization of both network and physical layers. In this paper, we analyze a single-user communication system composed of a transmitter preceded by a queue used for retransmissions, Gaussian block-fading channel, and a receiver. The system average delay is optimized by using combined power/rate control under average power constraints. Dynamic programming is used for calculating the optimized policies using numerical analysis as well as analytic analysis for asymptotically large buffer size. Asymptotic results are obtained for all combinations of fixed or variable power and rate controls. The most important result extends the "water-filling" result for systems with average delay constraint. Index Terms--Automatic repeat request (ARQ), average delay, block-fading channel, dynamic programming, power control, rate control, water filling.

We introduce an axiomatic definition of a conditional convex risk mapping and we derive its properties. In particular, we prove a representation theorem for conditional risk mappings in terms of [...]

The methods to integrate latent learning with dynamic programming under the Learning Classifier System (LCS) are described. The Modular Anticipatory Classifier System (MACS) is proposed as the latest model by showing some limitations of the formalism common to Anticipatory Classifier System (ACS) and Yet Another Classifier System (YACS).

The modes to find the preferred solutions in dynamic programming problems under flexible constraints are studied in the context of LexiMin or DescriMin procedures, and the viability of Bellman optimality principle and fundamental dynamic programming algorithms

Two new algorithms are presented and are compared with several algorithms from the literature. The new algorithms are for the segmentation of a white Gaussian-distributed time series with unknown but piecewise-constant variances.

This research reviews access control policies in multiserver loss queus in series tyical of telecommunications or computer networks. A proposed recursive method to resolve the problem involved dynamic programming on a set of reduced state spaces.

This research usees stochastic dynamic programming to determine the shortest route from source node to sink nodein stochastic dynamic networks. In applying this to the ship routing problem, the algorithm becomes exponentially complex.

We present a novel approach to finding a correspondence (alignment) between two curves. The correspondence is based on a notion of an alignment curve which treats both curves symmetrically, We then define a similarity metric based on the alignment curve using two intrinsic properties of the curve, namely, length and curvature. The optimal correspondence is found by an efficient dynamic-programming method both for aligning pairs of curve segments and pairs of closed curves, and is effective in the presence of a variety of transformations of the curve. Finally, the correspondence is shown in application to handwritten character recognition, prototype formation, and object recognition, and is potentially useful in other applications such as registration and tracking. Index Terms--Curve alignment, recognition, dynamic programming, prototypes, correspondence.

We analyze a dynamic programming (DP)-based track before detect (TBD) algorithm. By using extreme value theory we obtain explicit expressions for various performance measures of the algorithm such as probability of detection and false alarm. Our analysis has two advantages. First the unrealistic Gaussian and independence assumptions used in previous works are not required. Second, the probability of detection and false alarm curves obtained fit computer simulated performance results significantly more accurately than previously proposed analyses of the TBD algorithm.

Optimal and suboptimal beam scheduling algorithms for electronically scanned array tracking systems are discussed. A scheduling problem is formulated as a multiarm bandit problem involving hidden Markov models (HMM).

Research is presented concerning the use of stochastic programming methods which include the progressive hedging algorithm of Rockafellar and Wets. The use of the algorithm within a meta-heuristic framework is discussed.

Research is presented concerning the development of a method to determine the home positions of automated guided vehicles placed in a loop layout. The use of unidirectional and bidirectional flow systems is discussed.

Research is presented concerning the use of optimal parallel algorithms to resolve single resource allocation problems. The three parallel computing hardware solutions which were used to test the algorithms are discussed.

Research is presented concerning the development of an algorithm which is trellis-based and which enables the quantization of block coefficients to be made jointly. The experiments were conducted using H.263+ video codes.

A new method is presented that uses the Fritz-John technique for action elimination in complex dynamic programming problems.

This article discusses the use of probability to derive optimal strategies in the popular fantasy card game Magic: The Gathering. Topics include a brief description of the card game, probability algorithms, and dynamic programming.

The authors study the static assignment to M parallel, exponential, heterogeneous servers. Blocked customers are lost, while the objective is to minimize the average number of blocked customers. The problem is formulated as a stochastic control problem with partial observation, and an equivalent full observation problem is formulated. Numerical experiments are conducted and the structure of the optimal policies is studied. Index Terms - Dynamic programming, partially observed Markov decision processes, regular sequences, round robin, static assignments.