Search results for "DYNAMIC PROGRAMMING"
showing 10 items of 61 documents
Fixed point theorems for non-self mappings in symmetric spaces under φ-weak contractive conditions and an application to functional equations in dyna…
2014
In this paper, we prove some common fixed point theorems for two pairs of non-self weakly compatible mappings enjoying common limit range property, besides satisfying a generalized phi-weak contractive condition in symmetric spaces. We furnish some illustrative examples to highlight the realized improvements in our results over the corresponding relevant results of the existing literature. We extend our main result to four finite families of mappings in symmetric spaces using the notion of pairwise commuting mappings. Finally, we utilize our results to discuss the existence and uniqueness of solutions of certain system of functional equations arising in dynamic programming.
Quantized Dissensus in Networks of Agents subject to Death and Duplication
2012
Dissensus is a modeling framework for networks of dynamic agents in competition for scarce resources. Originally inspired by biological cells behaviors, it fits also marketing, finance and many other application areas. Competition is often unstable in the sense that strong agents, those having access to large resources, gain more and more resources at the expense of weak agents. Thus, strong agents duplicate when reaching a critical amount of resources, whereas weak agents die when loosing all their resources. To capture all these phenomena we introduce systems with a discrete time gossip and unstable state dynamics interrupted by discrete events affecting the network topology. Invariancy o…
Swing options in commodity markets: a multidimensional Lévy diffusion model
2013
Author's version of an article in the journal: Mathematical Methods of Operations Research. Also available from the publisher at: http://dx.doi.org/10.1007/s00186-013-0452-7 We study valuation of swing options on commodity markets when the commodity prices are driven by multiple factors. The factors are modeled as diffusion processes driven by a multidimensional Lévy process. We set up a valuation model in terms of a dynamic programming problem where the option can be exercised continuously in time. Here, the number of swing rights is given by a total volume constraint. We analyze some general properties of the model and study the solution by analyzing the associated HJB-equation. Furthermo…
Parameter Matching Analysis of Hydraulic Hybrid Excavators Based on Dynamic Programming Algorithm
2013
Published version of an article in the journal: Journal of Applied Mathematics. Also available from the publisher at: http://dx.doi.org/10.1155/2013/615608 Open Access In order to meet the energy saving requirement of the excavator, hybrid excavators are becoming the hot spot for researchers. The initial problem is to match the parameter of each component, because the system is tending to be more complicated due to the introduction of the accumulator. In this paper, firstly, a new architecture is presented which is hydraulic hybrid excavator based on common pressure rail combined switched function (HHES). Secondly, the general principle of dynamic programming algorithm (DPA) is explained. T…
Realizing Undelayed N-step TD prediction with neural networks
2010
There exist various techniques to extend reinforcement learning algorithms, e.g., eligibility traces and planning. In this paper, an approach is proposed, which combines several extension techniques, such as using eligibility-like traces, using approximators as value functions and exploiting the model of the environment. The obtained method, ‘Undelayed n-step TD prediction’ (TD-P), has produced competitive results when put in conditions of not fully observable environment.
Longest Common Subsequence from Fragments via Sparse Dynamic Programming
1998
Sparse Dynamic Programming has emerged as an essential tool for the design of efficient algorithms for optimization problems coming from such diverse areas as Computer Science, Computational Biology and Speech Recognition [7,11,15]. We provide a new Sparse Dynamic Programming technique that extends the Hunt-Szymanski [2,9,8] paradigm for the computation of the Longest Common Subsequence (LCS) and apply it to solve the LCS from Fragments problem: given a pair of strings X and Y (of length n and m, resp.) and a set M of matching substrings of X and Y, find the longest common subsequence based only on the symbol correspondences induced by the substrings. This problem arises in an application t…
Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem
2014
Finding differentially regulated subgraphs in a biochemical network is an important problem in bioinformatics. We present a new model for finding such subgraphs which takes the polarity of the edges (activating or inhibiting) into account, leading to the problem of finding a connected subgraph induced by \(k\) vertices with maximum weight. We present several algorithms for this problem, including dynamic programming on tree decompositions and integer linear programming. We compare the strength of our integer linear program to previous formulations of the \(k\)-cardinality tree problem. Finally, we compare the performance of the algorithms and the quality of the results to a previous approac…
Dynamic programming for 2-D discrete linear systems
1989
The authors calculate the optimal control of 2-D discrete linear systems using a dynamic programming method. It is assumed that the system is described with Roesser's state-space equations for which a 2-D sequence of inputs minimizing the given performance criterion is calculated. The method is particularly suitable for problems with bounded states and controls, although it can also be applied for unbounded cases. One numerical example is given. >
A computational study of LP-based heuristic algorithms for two-dimensional guillotine cutting stock problems
2002
In this paper we develop and compare several heuristic methods for solving the general two-dimensional cutting stock problem. We follow the Gilmore-Gomory column generation scheme in which at each iteration a new cutting pattern is obtained as the solution of a subproblem on one stock sheet. For solving this subproblem, in addition to classical dynamic programming, we have developed three heuristic procedures of increasing complexity, based on GRASP and Tabu Search techniques, producing solutions differing in quality and in time requirements. In order to obtain integer solutions from the fractional solutions of the Gilmore-Gomory process, we compare three rounding procedures, rounding up, t…
In-Depth Analysis of Pricing Problem Relaxations for the Capacitated Arc-Routing Problem
2015
Recently, Bode and Irnich [Bode C, Irnich S (2012) Cut-first branch-and-price-second for the capacitated arc-routing problem. Oper. Res. 60(5):1167–1182] presented a cut-first branch-and-price-second algorithm for solving the capacitated arc-routing problem (CARP). The fundamental difference to other approaches for exactly solving the CARP is that the entire algorithm works directly on the typically sparse underlying graph representing the street network. This enables the use of highly efficient dynamic programming-based pricing algorithms to solve the column-generation subproblem also known as the pricing problem. The contribution of this paper is the in-depth analysis of the CARP pricing…