A variable neighborhood search for the network design problem with relays

Given a set of commodities to be routed over a network, the network design problem with relays involves selecting a route for each commodity and determining the location of relays where the commodities must be reprocessed at certain distance intervals. We propose a hybrid approach based on variable neighborhood search. The variable neighborhood algorithm searches for the route for each commodity and the optimal relay locations for a given set of routes are determined by an implicit enumeration algorithm. We show that dynamic programming can be used to determine the optimal relay locations for a single commodity. Dynamic programming is embedded into the implicit enumeration algorithm to solve the relay location problem optimally for multiple commodities. The special structure of the problem is leveraged for computational efficiency. In the variable neighborhood search algorithm, the routes of the current solution are perturbed and reconstructed to generate neighbor solutions using random and greedy construction heuristics. Computational experiments on three sets of problems (80 instances) show that the variable neighborhood search algorithm with optimal relay allocations outperforms all existing algorithms in the literature.     

An extremal constrained routing problem with internal losses

We consider the following problem: one has to visit a finite number of sets and perform certain work on each of them. The work is accompanied by certain (internal) losses. Themovements from some set to another one are constrained and accompanied by external (aggregated additively) losses. We propose a “through” variant of the dynamic programming method, formulate an equivalent reconstruction problem, and develop an optimal algorithm based on an efficient dynamic programming algorithm.     

A linear programming-based optimization algorithm for solving nonlinear programming problems

In this paper a linear programming-based optimization algorithm called the Sequential Cutting Plane algorithm is presented. The main features of the algorithm are described, convergence to a Karush–Kuhn–Tucker stationary point is proved and numerical experience on some well-known test sets is showed. The algorithm is based on an earlier version for convex inequality constrained problems, but here the algorithm is extended to general continuously differentiable nonlinear programming problems containing both nonlinear inequality and equality constraints. A comparison with some existing solvers shows that the algorithm is competitive with these solvers. Thus, this new method based on solving linear programming subproblems is a good alternative method for solving nonlinear programming problems efficiently. The algorithm has been used as a subsolver in a mixed integer nonlinear programming algorithm where the linear problems provide lower bounds on the optimal solutions of the nonlinear programming subproblems in the branch and bound tree for convex, inequality constrained problems.     

Revised simplex algorithm for finite Markov decision processes

We introduce a revised simplex algorithm for solving a typical type of dynamic programming equation arising from a class of finite Markov decision processes. The algorithm also applies to several types of optimal control problems with diffusion models after discretization. It is based on the regular simplex algorithm, the duality concept in linear programming, and certain special features of the dynamic programming equation itself. Convergence is established for the new algorithm. The algorithm has favorable potential applicability when the number of actions is very large or even infinite.     

连续型动态规划的新算法研究

提出了求解一维连续型动态规划问题的自创算法----离散近似迭代法,并结合双收敛方法求解多维连续型动态规划问题. 该算法的基本思路为：在给定其它状态向
量序列的基础上,每次对一个状态变量序列进行离散近似迭代,并找出该状态变量的最优序列,直到所有状态向量序列都检查完.当模型为非凸非凹动态规划时,
证明了该算法的收敛性.当模型为凸动态规划时,证明了该算法的线性收敛性. 最后,以一个具体算例验证了该模型和算法的有效性.     

随机活动工期下求解资源约束项目最大期望净现值的动态调度算法

本文研究了随机活动工期下如何调度资源约束项目使得项目的期望净现值最大。首先对问题进行了界定,建立了相应的优化模型,其次针对问题的特点设计了一种动态规划算法。在算法设计的过程中,本文通过对项目网络图结构及不同状态最优值之间关系的分析,优化了动态规划算法状态的生成过程及状态最优值的求解过程,从而加快了算法的求解。使用随机生成的540个不同规模、不同结构的仿真案例对算法的有效性进行了验证,并分析了项目网络特征对算法效率的影响。实验发现：项目的次序强度对算法所需时间有着较大的影响,随着项目次序强度的减小,生成的状态数量会增加,从而计算时间也会增加。本文的研究可以为不确定环境下的项目调度提供决策支持。     

A compact labeling scheme for series-parallel graphs

A linear time labeling algorithm is presented for series-parallel graphs. The labels enable us to efficiently implement dynamic programming algorithms for sequencing problems with series-parallel precedence constraints. The labeling scheme can also be used to efficiently count and generate the initial sets, terminal sets and independent sets in transitive series-parallel digraphs and to provide a characterization of the maximal independent sets in transitive digraphs.     

Dynamic Programming Method for Constrained Discrete-Time Optimal Control

A dynamic programming method is presented for solving constrained, discrete-time, optimal control problems. The method is based on an efficient algorithm for solving the subproblems of sequential quadratic programming. By using an interior-point method to accommodate inequality constraints, a modification of an existing algorithm for equality constrained problems can be used iteratively to solve the subproblems. Two test problems and two application problems are presented. The application examples include a rest-to-rest maneuver of a flexible structure and a constrained brachistochrone problem.     

Semi-Infinite Programming Approach to Continuously-Constrained Linear-Quadratic Optimal Control Problems

Consider the class of linear-quadratic (LQ) optimal control problems with continuous linear state constraints, that is, constraints imposed on every instant of the time horizon. This class of problems is known to be difficult to solve numerically. In this paper, a computational method based on a semi-infinite programming approach is given. The LQ optimal control problem is formulated as a positive-quadratic infinite programming problem. This can be done by considering the control as the decision variable, while taking the state as a function of the control. After parametrizing the decision variable, an approximate quadratic semi-infinite programming problem is obtained. It is shown that, as we refine the parametrization, the solution sequence of the approximate problems converges to the solution of the infinite programming problem (hence, to the solution of the original optimal control problem). Numerically, the semi-infinite programming problems obtained above can be solved efficiently using an algorithm based on a dual parametrization method.     

Lipschitz continuous dynamic programming with discount II

We construct an alternative theoretical framework for stochastic dynamic programming which allows us to replace concavity assumptions with more flexible Lipschitz continuous assumptions. This framework allows us to prove that the value function of stochastic dynamic programming problems with discount is Lipschitz continuous in the presence of nonconcavities in the data of the problem. Our method allows us to treat problems with noninterior optimal paths. We also describe a discretization algorithm for the numerical computation of the value function, and we obtain the rate of convergence of this algorithm.     

Optimal control problems on manifolds: a dynamic programming approach

Dynamic programming identifies the value function of continuous time optimal control with a solution to the Hamilton-Jacobi equation, appropriately defined. This relationship in turn leads to sufficient conditions of global optimality, which have been widely used to confirm the optimality of putative minimisers. In continuous time optimal control, the dynamic programming methodology has been used for problems with state space a vector space. However there are many problems of interest in which it is necessary to regard the state space as a manifold. This paper extends dynamic programming to cover problems in which the state space is a general finite-dimensional C^∞ manifold. It shows that, also in a manifold setting, we can characterise the value function of a free time optimal control problem as a unique lower semicontinuous, lower bounded, generalised solution of the Hamilton-Jacobi equation. The application of these results is illustrated by the investigation of minimum time controllers for a rigid pendulum.     

Numerical Solutions to the Bellman Equation of Optimal Control

In this paper, we present a numerical algorithm to compute high-order approximate solutions to Bellman’s dynamic programming equation that arises in the optimal stabilization of discrete-time nonlinear control systems. The method uses a patchy technique to build local Taylor polynomial approximations defined on small domains, which are then patched together to create a piecewise smooth approximation. The numerical domain is dynamically computed as the level sets of the value function are propagated in reverse time under the closed-loop dynamics. The patch domains are constructed such that their radial boundaries are contained in the level sets of the value function and their lateral boundaries are constructed as invariant sets of the closed-loop dynamics. To minimize the computational effort, an adaptive subdivision algorithm is used to determine the number of patches on each level set depending on the relative error in the dynamic programming equation. Numerical tests in 2D and 3D are given to illustrate the accuracy of the method.     

SOLVING DYNAMIC WILDLIFE RESOURCE OPTIMIZATION PROBLEMS USING REINFORCEMENT LEARNING

ABSTRACT. An important technical component of natural resource management, particularly in an adaptive management context, is optimization. This is used to select the most appropriate management strategy, given a model of the system and all relevant available information. For dynamic resource systems, dynamic programming has been the de facto standard for deriving optimal state‐specific management strategies. Though effective for small‐dimension problems, dynamic programming is incapable of providing solutions to larger problems, even with modern microcomputing technology. Reinforcement learning is an alternative, related procedure for deriving optimal management strategies, based on stochastic approximation. It is an iterative process that improves estimates of the value of state‐specific actions based in interactions with a system, or model thereof. Applications of reinforcement learning in the field of artificial intelligence have illustrated its ability to yield near‐optimal strategies for very complex model systems, highlighting the potential utility of this method for ecological and natural resource management problems, which tend to be of high dimension. I describe the concept of reinforcement learning and its approach of estimating optimal strategies by temporal difference learning. I then illustrate the application of this method using a simple, well‐known case study of Anderson [1975], and compare the reinforcement learning results with those of dynamic programming. Though a globally‐optimal strategy is not discovered, it performs very well relative to the dynamic programming strategy, based on simulated cumulative objective return. I suggest that reinforcement learning be applied to relatively complex problems where an approximate solution to a realistic model is preferable to an exact answer to an oversimplified model.     

A heuristic for scheduling problems,especially for scheduling farm operations

Scheduling problems in agriculture are often solved using techniques such as linear programming (the multi-period formulation) and dynamic programming. But it is difficult to obtain an optimal schedule with these techniques for any but the smallest problems, because the model is unwieldly and much time is needed to solve the problem. Therefore, a new algorithm, a heuristic, has been developed to handle scheduling problems in agriculture. It is based on a search technique (i.e. hill-climbing) supported by a strong heuristic evaluation function. In this paper the heuristic performance is compared with dynamic programming. The heuristic offers near-optimal solutions and is much faster than the dynamic programming model. When tested against dynamic programming the difference in results was about 3%. This heuristic could probably also be applied in an industrial environment (e.g. agribusiness or road construction).     

The value iteration algorithm is not strongly polynomial for discounted dynamic programming

This note provides a simple example demonstrating that, if exact computations are allowed, the number of iterations required for the value iteration algorithm to find an optimal policy for discounted dynamic programming problems may grow arbitrarily quickly with the size of the problem. In particular, the number of iterations can be exponential in the number of actions. Thus, unlike policy iterations, the value iteration algorithm is not strongly polynomial for discounted dynamic programming.     

A dual dynamic programming for minimax optimal control problems governed by parabolic equation

In the article, minimax optimal control problems governed by parabolic equations are considered. We apply a new dual dynamic programming approach to derive sufficient optimality conditions for such problems. The idea is to move all the notions from a state space to a dual space and to obtain a new verification theorem providing the conditions, which should be satisfied by a solution of the dual partial differential equation of dynamic programming. We also give sufficient optimality conditions for the existence of an optimal dual feedback control and some approximation of the problem considered, which seems to be very useful from a practical point of view.     

Partially observable multistage stochastic programming

We propose a class of partially observable multistage stochastic programs and describe an algorithm for solving this class of problems. We provide a Bayesian update of a belief-state vector, extend the stochastic programming formulation to incorporate the belief state, and characterize saddle-function properties of the corresponding cost-to-go function. Our algorithm is a derivative of the stochastic dual dynamic programming method.     

Stochastic optimal control and algorithm of the trajectory of horizontal wells

This paper presents a nonlinear, multi-phase and stochastic dynamical system according to engineering background. We show that the stochastic dynamical system exists a unique solution for every initial state. A stochastic optimal control model is constructed and the sufficient and necessary conditions for optimality are proved via dynamic programming principle. This model can be converted into a parametric nonlinear stochastic programming by integrating the state equation. It is discussed here that the local optimal solution depends in a continuous way on the parameters. A revised Hooke–Jeeves algorithm based on this property has been developed. Computer simulation is used for this paper, and the numerical results illustrate the validity and efficiency of the algorithm.