The current paper presents an approach for generating cutting patterns of equal circular blanks processed with the shearing and punching process, which includes two stages. A guillotine machine divides the sheet into ...
详细信息
The current paper presents an approach for generating cutting patterns of equal circular blanks processed with the shearing and punching process, which includes two stages. A guillotine machine divides the sheet into strips at the first stage. A stamping press punches out the blanks from the strips at the second stage. Normal patterns consisting of orthogonal strips are proposed and four dynamic programming algorithms for generating them are presented. The first two algorithms deal with the unconstrained problem in which there is no constraint on the number of blanks included in a pattern, and the last two deal with the constrained problem in which the blank demand must be met exactly. The computational results indicate that the algorithms are efficient in both computation time and material utilization.
The purpose of this paper is to describe the application of the notion of viscosity solutions to solve the Hamilton-Jacobi-Bellman (HJB) equation associated with an important class of optimal control problems for quan...
详细信息
The purpose of this paper is to describe the application of the notion of viscosity solutions to solve the Hamilton-Jacobi-Bellman (HJB) equation associated with an important class of optimal control problems for quantum spin systems. The HJB equation that arises in the control problems of interest is a first-order nonlinear partial differential equation defined on a Lie group. Hence we employ recent extensions of the theory of viscosity solutions to Riemannian manifolds in order to interpret possibly non-differentiable solutions to this equation. Results from differential topology on the triangulation of manifolds are then used develop a finite difference approximation method for numerically computing the solution to such problems. The convergence of these approximations is proven using viscosity solution methods. In order to illustrate the techniques developed, these methods are applied to an example problem. (C) 2011 Elsevier B.V. All rights reserved.
In this paper, a sleeping mode control for low power wireless node, that is, pico base station (PBS) in heterogeneous networks, is proposed to save energy cost with adaptation to the time-varying traffic load. By form...
详细信息
In this paper, a sleeping mode control for low power wireless node, that is, pico base station (PBS) in heterogeneous networks, is proposed to save energy cost with adaptation to the time-varying traffic load. By formulating the sleep mode control problem into the framework of a standard 0/1 knapsack problem, then a dynamic programming scheme for solving the sleeping on/off mode for PBS in heterogeneous networks was investigated. The complexity of the proposed scheme is only in linear order instead of exponential complexity with conventional scheme. Furthermore, the proposed algorithm is verified in dynamic traffic environment, which consists of two kinds of hot-spot area covered by PBSs. The simulation results show that the proposed scheme can effectively save the system energy consumption during the period of low traffic load. Copyright (C) 2015 John Wiley & Sons, Ltd.
The cruise industry has maintained a steady growth in the past 20 years. Due to the large number of cruise passengers and regulations on sea environment protection, determining at which ports to dispose of the waste g...
详细信息
The cruise industry has maintained a steady growth in the past 20 years. Due to the large number of cruise passengers and regulations on sea environment protection, determining at which ports to dispose of the waste generated onboard a cruise ship is a key decision to reduce the cost for a cruise company. We address four versions of the problem: the cruise itinerary is either static or dynamic and the amount of waste generated on each voyage leg is either deterministic or stochastic. We propose a polynomial-time solution algorithm for the static deterministic model, and the idea of the algorithm can also be used to solve the static stochastic model and the dynamic deterministic model. Second, we identify the structure of the optimal policy to the dynamic stochastic problem, based on which an efficient dynamic programming algorithm is developed. Extensive numerical experiments derived from problems of real-case scales demonstrate the efficiency of the proposed algorithms. (C) 2017 Elsevier Ltd. All rights reserved.
作者：
Akutsu, TUniv Tokyo
Inst Med Sci Ctr Human Genome Minato Ku Tokyo 1088639 Japan
This paper shows simple dynamic programming algorithms for RNA secondary structure pre diction with pseudoknots. For a basic version of the problem (i.e., maximizing the number of base pairs), this paper presents an O...
详细信息
This paper shows simple dynamic programming algorithms for RNA secondary structure pre diction with pseudoknots. For a basic version of the problem (i.e., maximizing the number of base pairs), this paper presents an O(n(4)) time exact algorithm and an O(n(4-delta)) time approximation algorithm. The latter one outputs, for most RNA sequences, a secondary structure in which the number of base pairs is at least 1 - epsilon of the optimal, where epsilon,delta are any constants satisfying 0
This paper presents results achieved by an implementation of dynamic programming as power quality control logic on electrical distribution in unbalanced medium-voltage systems. This control system intends distributors...
详细信息
This paper presents results achieved by an implementation of dynamic programming as power quality control logic on electrical distribution in unbalanced medium-voltage systems. This control system intends distributors to optimize quality indicators and generation costs operation. The aim is to improve energetic efficiency by reducing additional network losses produced by imbalance. Besides it intends to profit the capacity of transmission and distribution network and control the spread of the imbalance index. For this purpose, we worked on a real distribution system of EPEC enterprise of the Province of Cordoba, Argentina, by modeling its actual behavior by the ATP/EMTP software. It then builds using MATLAB, a platform for control and an algorithm is developed to process information to control and adjust the system under the new operating conditions. We conclude that the final results show the ability to control, regulate and reduce the imbalance optimizing the Distributed Generation income. Finally we present up to date achievements.
Numerical dynamic programming algorithms typically use Lagrange data to approximate value functions over continuous states. Hermite data can be easily obtained from solving the Bellman equation and used to approximate...
详细信息
Numerical dynamic programming algorithms typically use Lagrange data to approximate value functions over continuous states. Hermite data can be easily obtained from solving the Bellman equation and used to approximate the value functions. We illustrate the use of Hermite data with one-, three-, and six-dimensional examples. We find that Hermite approximation improves the accuracy in value function iteration (VFI) by one to three digits using little extra computing time. Moreover, VFI with Hermite approximation is significantly faster than VFI with Lagrange approximation for the same accuracy, and this advantage increases with the dimension of the continuous states.
We present a highly effective dynamic programming driven memetic algorithm for the Steiner tree problem with revenues, budget, and hop constraints (STPRBH), which aims at determining a subtree of an undirected graph, ...
详细信息
We present a highly effective dynamic programming driven memetic algorithm for the Steiner tree problem with revenues, budget, and hop constraints (STPRBH), which aims at determining a subtree of an undirected graph, so as to maximize the collected revenue, subject to both budget and hop constraints. The main features of the proposed algorithm include a probabilistic constructive procedure to generate initial solutions, a neighborhood search procedure using dynamic programming to significantly speed up neighborhood exploration, a backbone-based crossover operator to generate offspring solutions, as well as a quality-and-distance updating strategy to manage the population. Computational results based on four groups of 384 well-known benchmarks demonstrate the value of the proposed algorithm, compared to the state of the art approaches. In particular, for the 56 most challenging instances with unknown optima, our algorithm succeeds in providing 45 improved best known solutions within a short computing time. We additionally provide results for a group of 30 challenging instances that are introduced in the paper. We provide a complexity analysis of the proposed algorithm and study the impact of some ingredients on the performance of the algorithm.
Inference of Markov networks from finite sets of sample strings is formulated using dynamic programming. Strings are installed in a network sequentially via optimal string-to-network alignments computed with a dynamic...
详细信息
Inference of Markov networks from finite sets of sample strings is formulated using dynamic programming. Strings are installed in a network sequentially via optimal string-to-network alignments computed with a dynamic programming matrix, the cost function of which uses relative frequency estimates of transition probabilities to emphasize landmark substrings common to the sample set. Properties of an inferred network are described and the method is illustrated with artificial data and with data representing banded human chromosomes.
Two new algorithms recently proved to outperform all previous methods for the exact solution of the 0-1 Knapsack Problem. This paper presents a combination of such approaches, where, in addition, valid inequalities ar...
详细信息
Two new algorithms recently proved to outperform all previous methods for the exact solution of the 0-1 Knapsack Problem. This paper presents a combination of such approaches, where, in addition, valid inequalities are generated and surrogate relaxed, and a new initial core problem is adopted. The algorithm. is able to solve all classical test instances, with up to 10,000 variables, in less than 0.2 seconds on a HP9000-735/99 computer. The C language implementation of the algorithm is available on the internet.
暂无评论