The aim of this paper is to provide a dynamic programming formulation for the spanning tree problem (), which allows several instances of the classical to be addressed. The spanning tree structure is modelled with sta...
详细信息
The aim of this paper is to provide a dynamic programming formulation for the spanning tree problem (), which allows several instances of the classical to be addressed. The spanning tree structure is modelled with states and transition between states, defining a state-space. Several properties are shown and optimality conditions are given. Once the theoretical fundamentals of the proposed formulation are derived, the multi-objective spanning tree problem () is addressed. This problem arises in the telecommunications and transportation sectors. In these contexts, handling different criteria simultaneously plays a crucial role. The scientific literature provides several works that focus on the bi-objective version of the considered problem, in which only two criteria are taken into account. To the best of our knowledge, no works provide optimal methods to address the with an arbitrary number of objective functions. In this paper we extend the proposed dynamic programming formulation to model and solve the with criteria.
In this paper, we present a new numerical algorithm to find the optimal control for the general nonlinear lumped systems without state constraints. The dynamic programming-viscosity solution (DPVS) approach is develop...
详细信息
In this paper, we present a new numerical algorithm to find the optimal control for the general nonlinear lumped systems without state constraints. The dynamic programming-viscosity solution (DPVS) approach is developed and the numerical solutions of both approximate optimal control and trajectory are produced. To show the effectiveness and efficiency of new algorithm, we apply it to an optimal control problem of two types of drug therapies for human immunodeficiency virus (HIV)/acquired immune deficiency syndrome (AIDS). The quality of the obtained optimal control and the trajectory pair is checked through comparison with the costs under the arbitrarily selected different controls. The results illustrate the effectiveness of the algorithm.
Complex thermal behavior inhibits the advancement of three-dimensional (3D) very-large-scale-integration (VLSI) system designs, as it could lead to ultra-high temperature hotspots and permanent silicon device damage. ...
详细信息
Complex thermal behavior inhibits the advancement of three-dimensional (3D) very-large-scale-integration (VLSI) system designs, as it could lead to ultra-high temperature hotspots and permanent silicon device damage. This article introduces a new runtime thermal management strategy to effectively diffuse and manage heat throughout 3D chip geometry for a better throughput performance in networks on chip (NoC). This strategy employs a dynamic programming-based runtime thermal management (DPRTM) policy to provide online thermal regulation. Reactive and proactive adaptive schemes are integrated to optimize the routing pathways depending on the critical temperature thresholds and traffic developments. Also, when the critical system thermal limit is violated, an urgent throttling will take place. The proposed DPRTM is rigorously evaluated through cycle-accurate simulations, and results show that the proposed approach outperforms conventional approaches in terms of computational efficiency and thermal stability. For example, the system throughput using the DPRTM approach can be improved by 33% when compared to other adaptive routing strategies for a given thermal constraint. Moreover, the DPRTM implementation presented in this article demonstrates that the hardware overhead is insignificant. This work opens a new avenue for exploring the on-chip adaptability and thermal regulation for future large-scale and 3D many-core integrations.
Graphical representations of codes facilitate the design of computationally efficient decoding algorithms, This is an example of a general connection between dependency graphs, as arise in the representations of Marko...
详细信息
Graphical representations of codes facilitate the design of computationally efficient decoding algorithms, This is an example of a general connection between dependency graphs, as arise in the representations of Markov random fields, and the dynamic programming principle, We concentrate on two computational tasks: finding the maximum-likelihood codeword and finding its posterior probability, given a signal received through a noisy channel, These two computations lend themselves to a particularly elegant version of dynamic programming, whereby the decoding complexity is particularly transparent. We explore some codes and some graphical representations designed specifically to facilitate computation. We further explore a coarse-to-fine version of dynamic programming that can produce an exact maximum-likelihood decoding many orders of magnitude faster than ordinary dynamic programming.
In this paper we propose an algorithm for the constrained two-dimensional cutting stock problem (TDC) in which a single stock sheet has to be cut into a set of small pieces, while maximizing the value of the pieces cu...
详细信息
In this paper we propose an algorithm for the constrained two-dimensional cutting stock problem (TDC) in which a single stock sheet has to be cut into a set of small pieces, while maximizing the value of the pieces cut. The TDC problem is NP-hard in the strong sense and finds many practical applications in the cutting and packing area. The proposed algorithm is a hybrid approach in which a depth-first search using hill-climbing strategies and dynamic programming techniques are combined. The algorithm starts with an initial (feasible) lower bound computed by solving a series of single bounded knapsack problems. In order to enhance the first-level lower bound, we introduce an incremental procedure which is used within a top-down branch-and-bound procedure. We also propose some hill-climbing strategies in order to produce a good trade-off between the computational time and the solution quality. Extensive computational testing on problem instances from the literature shows the effectiveness of the proposed approach. The obtained results are compared to the results published by Alvarez-Valdes et al. (2002).
A new dynamic programming based algorithm is used for the long-term hydrothermal scheduling of multireservoir systems. The proposed method minimizes the sum of operation costs in two consecutive periods, formulating t...
详细信息
A new dynamic programming based algorithm is used for the long-term hydrothermal scheduling of multireservoir systems. The proposed method minimizes the sum of operation costs in two consecutive periods, formulating the hydrothermal scheduling problem as a function of reservoirs' water content in one period. No discretization of state and control variables is required. The proposed algorithm has smaller storage and computing time requirements than the dynamic programming - successive approximations (SA) method. The operation of an example multireservoir system is simulated indicating that the proposed method leads to lower operation costs than those of the SA method.
In this paper we consider the crew scheduling problem, that is the problem of assigning K crews to tasks with fixed start and finish times such that each crew does not exceed a limit on the total time it can spend wor...
详细信息
In this paper we consider the crew scheduling problem, that is the problem of assigning K crews to tasks with fixed start and finish times such that each crew does not exceed a limit on the total time it can spend working. This problem is formulated as a problem of finding K time limit constrained vertex disjoint paths which visit all vertices on a network. A lower bound for the problem is found via dynamic programming. This lower bound is improved via a Lagrangean based penalty procedure and subgradient optimisation. Computational results are given for a number of randomly generated problems involving between 50 and 500 tasks. (C) 1998 Elsevier Science Ltd. All rights reserved.
This paper aims to present a state-of-the-art review of recent development within the areas of dynamic programming and optimal control for vector-valued functions.
This paper aims to present a state-of-the-art review of recent development within the areas of dynamic programming and optimal control for vector-valued functions.
Bacterium genome plasticity can efficiently be studied by the long-range polymerase chain reaction (LR-PCR) technique: genomes of different strains are split into hundreds of short segments which, after LR-PCR amplifi...
详细信息
Bacterium genome plasticity can efficiently be studied by the long-range polymerase chain reaction (LR-PCR) technique: genomes of different strains are split into hundreds of short segments which, after LR-PCR amplification, are used to sketch profiles. The segments have to: (1) cover the entire genome;(2) overlap each other;and (3) be of nearly identical size. This paper addresses the problem of finding a list of segments satisfying these constraints 'as much as possible'. Two algorithms based on dynamic programming approach are presented. They differ on the optimization criteria for measuring the quality of the covering. The first considers the maximal deviation of the segment lengths relatively to an ideal length. The second automatically finds a segment length that minimizes the maximal deviation. Copyright (c) 2005 John Wiley & Sons, Ltd.
A simple yet effective approach is developed on the basis of dynamic programming (DP) as a means of objectively selecting and prioritizing sewerage projects within available funds and system capacity. The methodology ...
详细信息
A simple yet effective approach is developed on the basis of dynamic programming (DP) as a means of objectively selecting and prioritizing sewerage projects within available funds and system capacity. The methodology consists of two DP models: a collection system model with an embedded benefit assessment technique to identify areas for wastewater collection;and a transportation system model to select routes of wastewater conveyance. Unlike conventional benefit analysis, benefits in this approach are defined as changes in adverse environmental, public health, and other noneconomic consequences as a result of sewerage provisions. The approach is a useful decision tool for planning sewerage system expansion. The models are used to identify "best" sewerage expansion plans for Ensenada, Baja California, Mexico. Sixteen potential areas for sewerage expansion and three existing plants with additional wastewater treatment capacity are considered. DOI: 10.1061/(ASCE)WR.1943-5452.0000107. (C) 2011 American Society of Civil Engineers.
暂无评论