Differential dynamic programming methods for solving bang-bang control problems

Differential dynamic programming is a technique, based on dynamic programming rather than the calculus of variations, for determining the optimal control function of a nonlinear system. Unlike conventional dynamic programming where the optimal cost function is considered globally, differential dynamic programming applies the principle of optimality in the neighborhood of a nominal, possibly nonoptimal, trajectory. This allows the coefficients of a linear or quadratic expansion of the cost function to be computed in reverse time along the trajectory: these coefficients may then be used to yield a new improved trajectory (i.e., the algorithms are of the "successive sweep" type). A class of nonlinear control problems, linear in the control variables, is studied using differential dynamic programming. It is shown that for the free-end-point problem, the first partial derivatives of the optimal cost function are continuous throughout the state space, and the second partial derivatives experience jumps at switch points of the control function. A control problem that has an aualytic solution is used to illustrate these points. The fixed-end-point problem is converted into an equivalent free-end-point problem by adjoining the end-point constraints to the cost functional using Lagrange multipliers: a useful interpretation for Pontryagin's adjoint variables for this type of problem emerges from this treatment. The above results are used to devise new second- and first-order algorithms for determining the optimal bang-bang control by successively improving a nominal guessed control function. The usefulness of the proposed algorithms is illustrated by the computation of a number of control problem examples.     

求解随机时变背包问题的精确算法与进化算法

随机时变背包问题(RTVKP)是一种新的动态背包问题,也是一种新的动态组合优化问题,目前它的求解算法主要是动态规划的精确算法、近似算法和遗传算法.本文首先利用动态规划提出了一个求解RTVKP问题的新精确算法,对算法时间复杂度的比较结果表明:它比已有的精确算法更适于求解背包载重较大的一类RTVKP实例.然后,分别基于差分演化和粒子群优化与贪心修正策略相结合,提出了求解RTVKP问题的两个进化算法.对5个RTVKP实例的数值计算结果比较表明: 精确算法一般不宜求解大规模的RTVKP实例,而基于差分演化、粒子群优化和遗传算法与贪心修正策略相结合的进化算法却不受实例规模与数据大小的影响,对于振荡频率大且具有较大数据的大规模RTVKP实例均能求得的一个极好的近似解.     

Algorithms for the boundary selection problem

User-oriented clustering schemes enable the classification of documents based upon the user's perception of the similarity between documents, rather than on some similarity function presumed by the designer to represent the user's criteria. In an earlier paper it was shown that such a classification scheme can be developed in two stages. The first stage involves the accumulation of relevance judgements provided by users,vis-à-vis past query instances, into a suitable structure. The second stage consists of cluster identification. When the structure chosen, in the first stage, for the accumulation of corelevance characteristics of documents is a straight line, the second stage can be formulated as a function optimization problem termed the Boundary Selection Problem (BSP). A branch-and-bound algorithm with a good bounding function is developed for the BSP. Although significant pruning is achieved due to the bounding function, the complexity is still high for a problem of a large size. For such a problem a heuristic that divides it into a number of subproblems, each being solved by a branch-and-bound approach, is developed. Then the overall problem is mapped to an integer knapsack problem and solved by the use of dynamic programming. The tradeoff between accuracy and complexity can be controlled, giving the user a preference of one over the other. Assuming that the heuristic which divides the overall problem introduces no errors and is given sufficient time, the branch and bound with dynamic programming (BBDP) approach will converge to the optimal solution. Two other heuristic approaches, one with the application of a polynomial dynamic programming algorithm and the other which works in a greedy way, are also proposed for the BSP and an experimental comparison of all these approaches is provided. Experimental results indicate that all proposed algorithms show better performance compared with the existing algorithm.     

Lagrangian bounds for just-in-time job-shop scheduling

We study the job-shop scheduling problem with earliness and tardiness penalties. We describe two Lagrangian relaxations of the problem. The first one is based on the relaxation of precedence constraints while the second one is based on the relaxation of machine constraints. We introduce dedicated algorithms to solve the corresponding dual problems. The second one is solved by a simple dynamic programming algorithm while the first one requires the resolution of an NP-hard problem by branch and bound. In both cases, the relaxations allow us to derive lower bounds as well as heuristic solutions. We finally introduce a simple local search algorithm to improve the best solution found. Computational results are reported.     

命令式动态规划类算法程序推导及机械化验证

动态规划是一种递归求解问题最优解的方法,主要通过求解子问题的解并组合这些解来求解原问题.由于其子问题之间存在大量依赖关系和约束条件,所以验证过程繁琐,尤其对命令式动态规划类算法程序正确性验证是一个难点.基于动态规划类算法Isabelle/HOL函数式建模与验证,通过证明命令式动态规划类算法程序与其的等价性,避免证明正确性时处理复杂的依赖关系和约束条件,提出命令式动态规划类算法程序设计框架及其机械化验证.首先,根据动态规划类算法的优化方法(备忘录方法)和性质(最优子结构性质和子问题重叠性质)描述问题规约、归纳递推关系式和形式化构造出循环不变式,并且基于递推关系式生成IMP (Minimalistic Imperative Programming Language)代码;其次,将问题规约、循环不变式和生成的IMP代码输入VCG (Verification Condition Generator),自动生成正确性的验证条件;然后,在Isabelle/HOL定理证明器中对验证条件进行机械化验证.算法首先设计为命令式动态规划类算法的一般形式,并进一步实例化得到具体算法.最后,例证了所提框架的有效性,为动态规划类算法的自动化推导和验证提供参考价值.     

Parallel Algorithms for Dynamic Programming Recurrences with More Than O(1) Dependency

We study the parallel computation of dynamic programming. We consider four important dynamic programming problems which have wide application, and that have been studied extensively in sequential computation: (1) the 1D problem, (2) the gap problem, (3) the parenthesis problem, and (4) the RNA problem. The parenthesis problem has fast parallel algorithms; almost no work has been done for parallelizing the other three. We present a unifying framework for the parallel computation of dynamic programming recurrences with more than O(1) dependency. We use two well-known methods, the closure method and the matrix product method, as general paradigms for developing parallel algorithms. Combined with various techniques, they lead to a number of new results. Our main results are optimal sublinear-time algorithms for the 1D, parenthesis, and RNA problems.     

Reinforcement learning for resource allocation in LEO satellite networks.

In this paper, we develop and assess online decision-making algorithms for call admission and routing for low Earth orbit (LEO) satellite networks. It has been shown in a recent paper that, in a LEO satellite system, a semi-Markov decision process formulation of the call admission and routing problem can achieve better performance in terms of an average revenue function than existing routing methods. However, the conventional dynamic programming (DP) numerical solution becomes prohibited as the problem size increases. In this paper, two solution methods based on reinforcement learning (RL) are proposed in order to circumvent the computational burden of DP. The first method is based on an actor-critic method with temporal-difference (TD) learning. The second method is based on a critic-only method, called optimistic TD learning. The algorithms enhance performance in terms of requirements in storage, computational complexity and computational time, and in terms of an overall long-term average revenue function that penalizes blocked calls. Numerical studies are carried out, and the results obtained show that the RL framework can achieve up to 56% higher average revenue over existing routing methods used in LEO satellite networks with reasonable storage and computational requirements.     

Optimal portfolio selection in a Lévy market with uncontrolled cash flow and only risky assets

This article considers an investor who has an exogenous cash flow evolving according to a Lévy process and invests in a financial market consisting of only risky assets, whose prices are governed by exponential Lévy processes. Two continuous-time portfolio selection problems are studied for the investor. One is a benchmark problem, and the other is a mean-variance problem. The first problem is solved by adopting the stochastic dynamic programming approach, and the obtained results are extended to the second problem by employing the duality theory. Closed-form solutions of these two problems are derived. Some existing results are found to be special cases of our results.     

图像拼接的改进算法

图像拼接在制作全景图的过程中具有重要作用，但是现有的方法不能很好地处理鬼影和曝光差异，针对存在的问题，提出了一种实现图像拼接的算法．首先利用动态规划的方法在要进行拼接的图像中找到一条最佳的缝合线，然后利用多分辨率技术进行拼接，解决了鬼影和曝光差异。     

Dynamic programming algorithms for the Zero-One Knapsack Problem

New dynamic programming algorithms for the solution of the Zero-One Knapsack Problem are developed. Original recursive procedures for the computation of the Knapsack Function are presented and the utilization of bounds to eliminate states not leading to optimal solutions is analyzed. The proposed algorithms, according to the nature of the problem to be solved, automatically determine the most suitable procedure to be employed. Extensive computational results showing the efficiency of the new and the most commonly utilized algorithms are given. The results indicate that, for difficult problems, the algorithms proposed are superior to the best branch and bound and dynamic programming methods.     

A design methodology for synthesizing parallel algorithms and architectures

In this paper, a design methodology for synthesizing efficient parallel algorithms and VLSI architectures is presented. A design process starts with a problem definition specified in the parallel programming language Crystal and is followed by a series of program transformations in Crystal, each aiming at optimizing the target design for a specific purpose. To illustrate the design methodology, a set of design methods for deriving systolic algorithms and architectures is given and the use of these methods in the design of a dynamic programming solver is described. The design methodology, together with this particular set of design methods, can be viewed as a general theory of systolic designs (or multidimensional pipelines). The fact that Crystal is a general purpose language for parallel programming allows new design methods and synthesis techniques, properties and theorems about problems in specific application domains, and new insights into any given problem to be integrated readily within the existing design framework.     

A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time

We investigate the problem of scheduling n jobs in s-stage hybrid flowshops with parallel identical machines at each stage. The objective is to find a schedule that minimizes the sum of weighted completion times of the jobs. This problem has been proven to be NP-hard. In this paper, an integer programming formulation is constructed for the problem. A new Lagrangian relaxation algorithm is presented in which precedence constraints are relaxed to the objective function by introducing Lagrangian multipliers, unlike the commonly used method of relaxing capacity constraints. In this way the relaxed problem can be decomposed into machine type subproblems, each of which corresponds to a specific stage. A dynamic programming algorithm is designed for solving parallel identical machine subproblems where jobs may have negative weights. The multipliers are then iteratively updated along a subgradient direction. The new algorithm is computationally compared with the commonly used Lagrangian relaxation algorithms which, after capacity constraints are relaxed, decompose the relaxed problem into job level subproblems and solve the subproblems by using the regular and speed-up dynamic programming algorithms, respectively. Numerical results show that the new Lagrangian relaxation method produces better schedules in much shorter computation time, especially for large-scale problems.     

Analysis of integer programming formulations of clustering problems

Five different integer programming formulations of the clustering problem are discussed. Three new heuristic algorithms for solving these problems are presented. Some of the existing algorithms are generalized. The relevance of integer programming and combinatorial theory to cluster analysis is discussed. Many other applicable algorithms are listed.     

Alattin: mining alternative patterns for defect detection

To improve software quality, static or dynamic defect-detection tools accept programming rules as input and detect their violations in software as defects. As these programming rules are often not well documented in practice, previous work developed various approaches that mine programming rules as frequent patterns from program source code. Then these approaches use static or dynamic defect-detection techniques to detect pattern violations in source code under analysis. However, these existing approaches often produce many false positives due to various factors. To reduce false positives produced by these mining approaches, we develop a novel approach, called Alattin, that includes new mining algorithms and a technique for detecting neglected conditions based on our mining algorithm. Our new mining algorithms mine patterns in four pattern formats: conjunctive, disjunctive, exclusive-disjunctive, and combinations of these patterns. We show the benefits and limitations of these four pattern formats with respect to false positives and false negatives among detected violations by applying those patterns to the problem of detecting neglected conditions.     

Stability Analysis of Constrained Nonlinear Model Predictive Control with Terminal Weighting

This paper investigates stability of model predictive control (MPC) for nonlinear constrained systems. New stability results for the MPC algorithms with terminal weighting are proposed using the dynamic programming method, which gives new criteria for choosing state, control and terminal weighting in the performance index to achieve stability of MPC algorithms. Illustrative examples are given to show that by combining this condition with existing ones, much less conservative results can be generated.     

Knowledge based approach to machine cell layout

In this paper, the machine cell layout problem is examined. A new methodology for solving the problem is proposed. The methodology involves three stages. In the first stage, an algorithm suitable for solving the machine grouping problem is utilized. In the second and third stages, mathematical programming models of the machine cell and machine layout problems are formulated and solved using suitable algorithms. The development of a knowledge based system which uses models and algorithms for solving the machine grouping and layout problems, is also outlined.     

Fixed channel assignment using new dynamic programming approach in cellular radio networks

In this paper, we propose a new approach to the fixed channel assignment problem by modifying the dynamic programming technique. This new strategy extends the already known dynamic programming so that the channel assignment solutions can be obtained. There is no need to have an initial random solution for convergence. One of the questions in the fixed channel assignment is the minimum bandwidth, which is usually unknown; the new strategy can obtain this lower bound. Parallel processing can be implemented over the proposed algorithm. The existing fixed channel assignment methods do not have all these in one place. The performance of modified dynamic programming (MDP) is evaluated by computer simulation, applied to seven well-known benchmark problems on channel assignment. The channel assignment strategies results shows that required bandwidths of modified dynamic programming are closely match or sometimes better than the algorithms that we have investigated.     

Implementation and analysis of alternative algorithms for generalized shortest path problems

This paper addresses a special class of deterministic dynamic programming problems which can be formulated as a generalized network problem. Because of the similarities between this class of dynamic programming problems and shortest path problems, we are naming it the Generalized Shortest Path problem. A new primal extreme point algorithm and a new special dual algorithm are proposed here. While researchers have presented a variety of algorithms to solve this class of problems, there has been no comuptational analysis of these algorithms. An in-depth computational analysis is performed to determine the most efficient set of rules for implementing the algorithms of this paper.     

时间约束调度中功能单元的下限估算

针对高层次综合中时间约束下的调度问题,提出了对功能单元的2种下限估算算法：单位长度调度法和最大网络流法．其主要思想是将原调度问题的不同约束放松,得到多项式可解的新问题,并使得新问题的最优解是原调度问题的下限值．将2种算法与已有的最小重叠法和整数线性规划给出的最优解做了理论和实验上的比较．实验结果表明：2种估算算法运行时间合理,并且单位长度调度法比最小重叠法更准确．最后总结了各种约束对下限估算准确性的影响．     

无线网络中需求驱动的动态频谱分配

研究无线网络中协同动态频谱接入模型下的动态频谱分配问题,在考虑基站频谱需求的基础上,将物理干扰模型下的动态频谱分配问题建模为一个非线性优化问题。通过将非线性优化问题转换为线性规划问题,提出一种无线网络中需求驱动的动态频谱分配算法,计算初始频谱分配,并应用迭代增强算法为节点添加多余信道。仿真结果表明,该算法在有效频谱利用率和平均满意度上都优于现有算法。