Functional equations in dynamic programming.
Greedy algorithms for optimal computing of matrix chain products involving square dense and triangular matrices
This paper addresses a combinatorial optimization problem (COP), namely a variant of the (standard) matrix chain product (MCP) problem where the matrices are square and either dense (i.e. full) or lower/upper triangular. Given a matrix chain of length n, we first present a dynamic programming algorithm (DPA) adapted from the well known standard algorithm and having the same O(n3) complexity. We then design and analyse two optimal O(n) greedy algorithms leading in general to different optimal solutions...
Greedy algorithms for optimal computing of matrix chain products involving square dense and triangular matrices
This paper addresses a combinatorial optimization problem (COP), namely a variant of the (standard) matrix chain product (MCP) problem where the matrices are square and either dense (i.e. full) or lower/upper triangular. Given a matrix chain of length n, we first present a dynamic programming algorithm (DPA) adapted from the well known standard algorithm and having the same O(n3) complexity. We then design and analyse two optimal O(n) greedy algorithms leading in general to different optimal solutions...
Growth rates and average optimality in risk-sensitive Markov decision chains
In this note we focus attention on characterizations of policies maximizing growth rate of expected utility, along with average of the associated certainty equivalent, in risk-sensitive Markov decision chains with finite state and action spaces. In contrast to the existing literature the problem is handled by methods of stochastic dynamic programming on condition that the transition probabilities are replaced by general nonnegative matrices. Using the block-triangular decomposition of a collection...
Growth versus environment in dynamic models of capital accumulation.
High-performance simulation-based algorithms for an alpine ski racer's trajectory optimization in heterogeneous computer systems
Effective, simulation-based trajectory optimization algorithms adapted to heterogeneous computers are studied with reference to the problem taken from alpine ski racing (the presented solution is probably the most general one published so far). The key idea behind these algorithms is to use a grid-based discretization scheme to transform the continuous optimization problem into a search problem over a specially constructed finite graph, and then to apply dynamic programming to find an approximation...
Implantation et complexité des techniques de programmation dynamique dans les méthodes de confection de tournées et d'horaires
Integer Programming Formulation of the Bilevel Knapsack Problem
The Bilevel Knapsack Problem (BKP) is a hierarchical optimization problem in which the feasible set is determined by the set of optimal solutions of parametric Knapsack Problem. In this paper, we propose two stages exact method for solving the BKP. In the first stage, a dynamic programming algorithm is used to compute the set of reactions of the follower. The second stage consists in solving an integer program reformulation of BKP. We show that the...
Jedna úloha optimální obsluhy několika výrobních procesů s náhodnými parametry
La programmation dynamique de Bellman appliquée au calcul d'un câble électrique à plusieurs dérivations
Locally bounded k-colorings of trees
Given a tree T with n vertices, we show, by using a dynamic programming approach, that the problem of finding a 3-coloring of T respecting local (i.e., associated with p prespecified subsets of vertices) color bounds can be solved in O(n6p-1logn) time. We also show that our algorithm can be adapted to the case of k-colorings for fixed k.
Managing the Exploitation Life of the Mining Machinery for an Unlimited Duration of Time
Managing the Exploitation Life of the Mining Machinery for a Limited Duration of Time
Markov decision processes with time-varying discount factors and random horizon
This paper is related to Markov Decision Processes. The optimal control problem is to minimize the expected total discounted cost, with a non-constant discount factor. The discount factor is time-varying and it could depend on the state and the action. Furthermore, it is considered that the horizon of the optimization problem is given by a discrete random variable, that is, a random horizon is assumed. Under general conditions on Markov control model, using the dynamic programming approach, an optimality...
Metóda dynamického programovania v dynamickej optimalizácii sústav s minimálnou dobou riadenia
Nash equilibrium payoffs for stochastic differential games with reflection
In this paper, we investigate Nash equilibrium payoffs for nonzero-sum stochastic differential games with reflection. We obtain an existence theorem and a characterization theorem of Nash equilibrium payoffs for nonzero-sum stochastic differential games with nonlinear cost functionals defined by doubly controlled reflected backward stochastic differential equations.
New complexity results for time-constrained dynamical optimal path problems.
Nonserial dynamic programming for optimal register assignment
Object library of algorithms for dynamic optimization problems: benchmarking SQP and nonlinear interior point methods
The main purpose of this paper is to describe the design, implementation and possibilities of our object-oriented library of algorithms for dynamic optimization problems. We briefly present library classes for the formulation and manipulation of dynamic optimization problems, and give a general survey of solver classes for unconstrained and constrained optimization. We also demonstrate methods of derivative evaluation that we used, in particular automatic differentiation. Further, we briefly formulate...