We provide two different neighborhood construction techniques for creating exponentially large neighborhoods that are searchable in polynomial time using dynamic programming. We illustrate both of these approaches on very large scale neighborhood search techniques for the traveling salesman problem. Our approaches are intended both to unify previously known results as well as to offer schemas for generating additional exponential neighborhoods that are searchable in polynomial time. The first approach is to define the neighborhood recursively. In this approach, the dynamic programming recursion is a natural consequence of the recursion that defines the neighborhood. In particular, we show how to create the pyramidal tour neighborhood, the twisted sequences neighborhood, and dynasearch neighborhoods using this approach. In the second approach, we consider the standard dynamic program to solve the TSP. We then obtain exponentially large neighborhoods by selecting a polynomially bounded number of states, and restricting the dynamic program to those states only. We show how the Balas and Simonetti neighborhood and the insertion dynasearch neighborhood can be viewed in this manner. We also show that one of the dynasearch neighborhoods can be derived directly from the 2-exchange neighborhood using this approach.

In ordert to increasing the capacity of stocking and integration in the process of optimizing the internal cost in steel industry. The cost of material profolio is usually being ignored during opmization. Experiences-based decision paten still being carried out in material profolio in this industry.Thus the Inventory and Manufacture cost are losing inadvertently. This study aims at obtaining the minimum material profolio cost so that we provide a model concerned with cost and element limitation of target product.Using dynamic programming into material-profolio decision making process. We divided material profolio into three steps, transforming the productive limitations into mathematic constrains,and implememting by software.The real-case data is given to estabilish the model database.Comparing our data with the real data,we found that with the approach, we significately reduced and the cost and variety of material profolio in different critiria

No description available.

No description available.

No description available.

Thesis (M.S.)--Oregon State University, 1993. / Typescript (photocopy). Includes bibliographical references (leaves 48-49). Also available on the World Wide Web.

Thesis (Ph. D.)--Drexel University, 2006. / Includes abstract and vita. Includes bibliographical references (leaves 92-97).

The investigation reported in this dissertation attempts to determine the feasibility of using a distance-based approach like compromise programming for discrete-time dynamic programming problems with multiple objectives. In compromise programming, a function measuring the distance from a generally infeasible ideal solution to the feasible set of the problem is the single objective acting as a surrogate for the set of multiple objectives. Since, in general, there is no single best solution to a multiple objective problem, a framework to generate a family of compromise solutions interactively on a computer is proposed. Various quantities relevant to dynamic compromise programming are defined in precise terms. Dynamic compromise programming problems are computationally difficult to solve because in order to make the distance function decomposable over stages, dimensionality of the state-space must be increased by the number of objectives. To generate compromise solutions, quasi-Newton differential dynamic programming (QDDP), a recently developed variable-metric method for discrete-time optimal control, was employed. QDDP is attractive because no second order or Hessian information is required as input. Instead, Hessian matrices are approximated by first order or gradient information. Since very little is known about its numerical properties, computational experiments were conducted on QDDP. A new strategy for updating Hessian matrix approximations was computationally tested. A constrained QDDP algorithm is proposed, computationally tested, and applied to solve a multiobjective dynamic programming problem with inequality constraints at each stage. The algorithm has the potential for application to the more general discrete-time optimal control problem with stage constraints. The framework for generating compromise solutions interactively was implemented for prototype problems. Because decision maker interaction is crucial in a multiple objective situation, special attention was paid towards developing a man-machine interface using on-screen windows. All implementation and computational testing were done on a UNIX based personal computer.

Multi-homing is a technology used by Internet Service Provider (ISP) to connect to the Internet via multiple networks. This connectivity enhances the network reliability and service quality of the ISP. However, using multi-networks may imply multiple costs on the ISP. To make full use of the underlying networks with minimum cost, a routing strategy is requested by ISPs. Of course, this optimal routing strategy depends on the pricing regime used by network providers. In this study we investigate a relatively new pricing regime – top-percentile pricing. Under top-percentile pricing, network providers divide the charging period into several fixed length time intervals and calculate their cost according to the traffic volume that has been shipped during the θ-th highest time interval. Unlike traditional pricing regimes, the network design under top-percentile pricing has not been fully studied. This paper investigates the optimal routing strategy in case where network providers charge ISPs according to top-percentile pricing. We call this problem the Top-percentile Traffic Routing Problem (TpTRP). As the ISP cannot predict next time interval’s traffic volume in real world application, in our setting up the TpTRP is a multi-stage stochastic optimisation problem. Routing decisions should be made at the beginning of every time period before knowing the amount of traffic that is to be sent. The stochastic nature of the TpTRP forms the critical difficulty of this study. In this paper several approaches are investigated in either the modelling or solving steps of the problem. We begin by exploring several simplifications of the original TpTRP to get an insight of the features of the problem. Some of these allow analytical solutions which lead to bounds on the achievable optimal solution. We also establish bounds by investigating several “naive” routing policies. In the second part of this work, we build the multi-stage stochastic programming model of the TpTRP, which is hard to solve due to the integer variables introduced in the calculation of the top-percentile traffic. A lift-and-project based cutting plane method is investigated in solving the SMIP for very small examples of TpTRP. Nevertheless it is too inefficient to be applicable on large sized instances. As an alternative, we explore the solution of the TpTRP as a Stochastic Dynamic Programming (SDP) problem by a discretization of the state space. This SDP model gives us achievable routing policies on small size instances of the TpTRP, which of course improve the naive routing policies. However, the solution approach based on SDP suffers from the curse of dimensionality which restricts its applicability. To overcome this we suggest using Approximate Dynamic Programming (ADP) which largely avoids the curse of dimensionality by exploiting the structure of the problem to construct parameterized approximations of the value function in SDP and train the model iteratively to get a converged set of parameters. The resulting ADP model with discrete parameter for every time interval works well for medium size instances of TpTRP, though it still requires too long to be trained for large size instances. To make the realistically sized TpTRP problem solvable, we improve on the ADP model by using Bezier Curves/Surfaces to do the aggregation over time. This modification accelerates the efficiency of parameter training in the solution of the ADP model, which makes the realistically sized TpTRP tractable.

The internet has facilitated music metadata production and distribution on an unprecedented scale. A contributing factor of this data deluge is a change in the authorship of this data from the expert few to the untrained crowd. The resulting unordered flood of imperfect annotations provides challenges and opportunities in identifying accurate metadata and linking it to the music audio in order to provide a richer listening experience. We advocate novel adaptations of Dynamic Programming for music metadata synchronisation, ranking and comparison. This thesis introduces Windowed Time Warping, Greedy, Constrained On-Line Time Warping for synchronisation and the Concurrence Factor for automatically ranking metadata. We begin by examining the availability of various music metadata on the web. We then review Dynamic Programming methods for aligning and comparing two source sequences whilst presenting novel, specialised adaptations for efficient, realtime synchronisation of music and metadata that make improvements in speed and accuracy over existing algorithms. The Concurrence Factor, which measures the degree in which an annotation of a song agrees with its peers, is proposed in order to utilise the wisdom of the crowds to establish a ranking system. This attribute uses a combination of the standard Dynamic Programming methods Levenshtein Edit Distance, Dynamic Time Warping, and Longest Common Subsequence to compare annotations. We present a synchronisation application for applying the aforementioned methods as well as a tablature-parsing application for mining and analysing guitar tablatures from the web. We evaluate the Concurrence Factor as a ranking system on a largescale collection of guitar tablatures and lyrics to show a correlation with accuracy that is superior to existing methods currently used in internet search engines, which are based on popularity and human ratings.