Shift-and-merge technique for the DP solution of the time-constrained backpacker problem

We formulate the time-constrained backpacker problem as an extension of the classical knapsack problem (KP), where a ‘backpacker’ travels from a origin to a destination on a directed acyclic graph, and collects items en route within the capacity of his knapsack and within a fixed time limit. We present a dynamic programming (DP) algorithm to solve this problem to optimality, and a ‘shift-and-merge’ DP algorithm to solve larger instances. The latter is an extension of the list-type DP, which has been successful for one-dimensional KPs, to the two-dimensional case. Computational experiments on a series of instances demonstrate advantage of the shift-and-merge technique over commercial MIP solvers.     

Data mining for state space orthogonalization in adaptive dynamic programming

Dynamic programming (DP) is a mathematical programming approach for optimizing a system that changes over time and is a common approach for developing intelligent systems. Expert systems that are intelligent must be able to adapt dynamically over time. An optimal DP policy identifies the optimal decision dependent on the current state of the system. Hence, the decisions controlling the system can intelligently adapt to changing system states. Although DP has existed since Bellman introduced it in 1957, exact DP policies are only possible for problems with low dimension or under very limiting restrictions. Fortunately, advances in computational power have given rise to approximate DP (ADP). However, most ADP algorithms are still computationally-intractable for high-dimensional problems. This paper specifically considers continuous-state DP problems in which the state variables are multicollinear. The issue of multicollinearity is currently ignored in the ADP literature, but in the statistics community it is well known that high multicollinearity leads to unstable (high variance) parameter estimates in statistical modeling. While not all real world DP applications involve high multicollinearity, it is not uncommon for real cases to involve observed state variables that are correlated, such as the air quality ozone pollution application studied in this research. Correlation is a common occurrence in observed data, including sources in meteorology, energy, finance, manufacturing, health care, etc.ADP algorithms for continuous-state DP achieve an approximate solution through discretization of the state space and model approximations. Typical state space discretizations involve full-dimensional grids or random sampling. The former option requires exponential growth in the number of state points as the state space dimension grows, while the latter option is typically inefficient and requires an intractable number of state points. The exception is computationally-tractable ADP methods based on a design and analysis of computer experiments (DACE) approach. However, the DACE approach utilizes ideal experimental designs that are (nearly) orthogonal, and a multicollinear state space will not be appropriately represented by such ideal experimental designs. While one could directly build approximations over the multicollinear state space, the issue of unstable model approximations remains unaddressed. Our approach for handling multicollinearity employs data mining methods for two purposes: (1) to reduce the dimensionality of a DP problem and (2) to orthogonalize a multicollinear DP state space and enable the use of a computationally-efficient DACE-based ADP approach. Our results demonstrate the risk of ignoring high multicollinearity, quantified by high variance inflation factors representing model instability. Our comparisons using an air quality ozone pollution case study provide guidance on combining feature selection and feature extraction to guarantee orthogonality while achieving over 95% dimension reduction and good model accuracy.     

A Markov Decision Problem Approach to Goal Attainment

A new Markov decision problem (MDP)-based method for managing goal attainment (GA), which is the process of planning and controlling actions that are related to the achievement of a set of defined goals in the presence of resource and time constraints, is proposed. Specifically, we address the problem as one of optimally selecting a sequence of actions to transform the system and/or its environment from an initial state to a desired state. We begin with a method of explicitly mapping an action-GA graph to an MDP graph and developing a dynamic programming (DP) recursion to solve the MDP problem. For larger problems having exponential complexity with respect to the number of goals, we propose guided search algorithms such as AO*, AO_epsiv*, and greedy search techniques, whose search power rests on the efficiency of their heuristic evaluation functions (HEFs). Our contribution in this part stems from the introduction of a new problem-specific HEF to aid the search process. We demonstrate reductions in the computational costs of the proposed techniques through performance comparison with standard DP techniques. We conclude this paper with a method to address situations in which alternative strategies (e.g., second best) are required. The new extended AO* algorithm identifies alternative control sequences for attaining the organizational goals.     

Logarithmic Barrier Decomposition Methods for Semi-infinite Programming

A computational study of some logarithmic barrier decomposition algorithms for semi-infinite programming is presented in this paper. The conceptual algorithm is a straightforward adaptation of the logarithmic barrier cutting plane algorithm which was presented recently by den Hartog et al. ( Annals of Operations Research , 58 , 69–98, 1995), to solve semi-infinite programming problems. Usually decomposition (cutting plane methods) use cutting planes to improve the localization of the given problem. In this paper we propose an extension which uses linear cuts to solve large scale, difficult real world problems. This algorithm uses both static and (doubly) dynamic enumeration of the parameter space and allows for multiple cuts to be simultaneously added for larger/difficult problems. The algorithm is implemented both on sequential and parallel computers. Implementation issues and parallelization strategies are discussed and encouraging computational results are presented.     

Test sequencing algorithms with unreliable tests

In this paper, we consider imperfect test sequencing problems under a single fault assumption. This is a partially observed Markov decision problem (POMDP), a sequential multistage decision problem wherein a failure source must be identified using the results of imperfect tests at each stage. The optimal solution for this problem can be obtained by applying a continuous-state dynamic programming (DP) recursion. However, the DP recursion is computationally very expensive owing to the continuous nature of the state vector comprising the probabilities of faults. In order to alleviate this computational explosion, we present an efficient implementation of the DP recursion. We also consider various problems with special structure (parallel systems) and derive closed form solutions/index-rules without having to resort to DP. Finally, we present various top-down graph search algorithms for problems with no special structure, including multistep DP, multistep information heuristics, and certainty equivalence algorithms     

A traveling salesman problem with pickups and deliveries,time windows and draft limits: Case study from chemical shipping

This paper introduces and studies a real in-port ship routing and scheduling problem faced by chemical shipping companies. We show that this problem can be modeled as a Traveling Salesman Problem with Pickups and Deliveries, Time Windows and Draft Limits (TSPPD-TWDL). We propose a mathematical formulation for the TSPPD-TWDL and suggest a solution method based on forward dynamic programming (DP) to solve the problem. A set of label extension rules are also proposed to accelerate and enhance the performance of the algorithm. Computational studies show that the label extension rules are essential to the DP-algorithm, and the proposed solution method is able to solve real-sized in-port routing and scheduling problems in chemical shipping efficiently.     

Neural networks for nonlinear state estimation

Estimating the state of a nonlinear stochastic system (observed through a nonlinear noisy measurement channel) has been the goal of considerable research to solve both filtering and control problems. In this paper, an original approach to the solution of the optimal state estimation problem by means of neural networks is proposed, which consists in constraining the state estimator to take on the structure of a multilayer feedforward network. Both non-recursive and recursive estimation schemes are considered, which enable one to reduce the original functional problem to a nonlinear programming one. As this reduction entails approximations for the optimal estimation strategy, quantitative results on the accuracy of such approximations are reported. Simulation results confirm the effectiveness of the proposed method.     

Computational performance of basic state reduction based dynamic programming algorithms for bi-objective 0–1 knapsack problems

This paper studies a group of basic state reduction based dynamic programming (DP) algorithms for the multi-objective 0–1 knapsack problem (MKP), which are related to the backward reduced-state DP space (BRDS) and forward reduced-state DP space (FRDS). The BRDS is widely ignored in the literature because it imposes disadvantage for the single objective knapsack problem (KP) in terms of memory requirements. The FRDS based DP algorithm in a general sense is related to state dominance checking, which can be time consuming for the MKP while it can be done efficiently for the KP. Consequently, no algorithm purely based on the FRDS with state dominance checking has ever been developed for the MKP. In this paper, we attempt to get some insights into the state reduction techniques efficient to the MKP. We first propose an FRDS based algorithm with a local state dominance checking for the MKP. Then we evaluate the relative advantage of the BRDS and FRDS based algorithms by analyzing their computational time and memory requirements for the MKP. Finally different combinations of the BRDS and FRDS based algorithms are developed on this basis. Numerical experiments based on the bi-objective KP instances are conducted to compare systematically between these algorithms and the recently developed BRDS based DP algorithm as well as the existing FRDS based DP algorithm without state dominance checking.     

A dynamic programming approach to trajectory planning of robotic manipulators

This paper presents a solution to the problem of minimizing the cost of moving a robotic manipulator along a specified geometric path subject to input torque/force constraints, taking the coupled, nonlinear dynamics of the manipulator into account. The proposed method uses dynamic programming (DP) to find the positions, velocities, accelerations, and torques that minimize cost. Since the use of parametric functions reduces the dimension of the state space from2nfor ann- jointed manipulator, to two, the DP method does not suffer from the "curse of dimensionality." While maintaining the elegance of our previous trajectory planning method, we have developed the DP method for the general case where 1) the actuator torque limits are dependent on one another, 2) the cost functions can have an arbitrary form, and 3) there are constraints on the jerk, or derivative of the acceleration. Also, we have shown that the DP solution converges as the grid size decreases. As numerical examples, the trajectory planning method is simulated for the first three joints of the PACS arm, which is a cylindrical arm manufactured by the Bendix Corporation.     

A Comparative Analysis of Various Optimization Models for Electricity Capacity Expansion

Several optimization models have been proposed in the literature to solve the project selection, timing and sequencing problem. Models based on dynamic programming (DP) such as embebed state DP, objective space DP, and others have been used to solve the capacity expansion problem. Also models based on mixed integer linear programming using Benders decomposition theory, and heuristic rules have been proposed to solve that problem. In this paper these models are analyzed and compared from the theoretical point of view. All the reviewed models are then compared using them to define the minimum cost expansion of the Colombian electric sector. The Colombian interconnected electric generation system has about 10,000 MW of installed capacity with a generation composition of 80% hydro-generation plants and 20% thermo-generation plants. the expansion planning of the system has been carried out at a national level using simulation and optimization techniques. All these techniques are reviewed and discussed in this paper. Some conclusions and recommendations are finally presented.     

Approximate Dynamic Programming for Stochastic Resource Allocation Problems

A stochastic resource allocation model, based on the principles of Markov decision processes (MDPs), is proposed in this paper. In particular, a general-purpose framework is developed, which takes into account resource requests for both instant and future needs. The considered framework can handle two types of reservations (i.e., specified and unspecified time interval reservation requests), and implement an overbooking business strategy to further increase business revenues. The resulting dynamic pricing problems can be regarded as sequential decision-making problems under uncertainty, which is solved by means of stochastic dynamic programming (DP) based algorithms. In this regard, Bellman’s backward principle of optimality is exploited in order to provide all the implementation mechanisms for the proposed reservation pricing algorithm. The curse of dimensionality, as the inevitable issue of the DP both for instant resource requests and future resource reservations, occurs. In particular, an approximate dynamic programming (ADP) technique based on linear function approximations is applied to solve such scalability issues. Several examples are provided to show the effectiveness of the proposed approach.      

构造移动通信中降低能耗的前缀码的动态规划加速

动态规划是一种常用的寻找问题最优解的算法设计方案。当将动态规划中的各个子问题考虑成有向图上的节点时,我们可以将动态规划看作是一个有向无圈图。一些问题的动态规划的有向无圈图有着特殊的结构,我们可以利用这些结构加速动态规划。本文考虑了一种从基站将能源"转移"到移动通信宿主的二进制编码方案构造时采用的动态规划。移动通信中,常常需要考虑优化通信编码方案来降低移动通信宿主的能耗。本文研究的编码方案通过以下方式降低能耗:基站猜测移动通信宿主所要发出的信息并询问宿主,而宿主则在一定的情况下才做出回应,以此来降低宿主发送信息的能耗。对于有n个单词的编码,我们的算法比之前提出的算法降低了O(n2)的时间复杂度。     

Properties of a Level Set Algorithm for the Visibility Problems

We study an implicit visibility formulation and show that the corresponding closed form formula satisfies a dynamic programming principle, and is the viscosity solution of a Hamilton-Jacobi type equation involving jump discontinuities in the Hamiltonian. We derive the corresponding discretization in multi-dimensions and prove convergence of the corresponding numerical approximations. Finally, we introduce a generalization of the original Hamilton-Jacobi equation and the corresponding discretization that can be solved efficiently using either the fast sweeping or the fast marching methods. Thus, the visibility of an observer in non-constant media can be computed. We also introduce a specialization of the algorithms for environments in which occluders are described by the graph of a function.     

Parallel dynamic programming on clusters of workstations

The standard DP (dynamic programming) algorithms are limited by the substantial computational demands they put on contemporary serial computers. In this work, the theory behind the solution to serial monadic dynamic programming problems highlights the theory and application of parallel dynamic programming on a general-purpose architecture (cluster or network of workstations). A simple and well-known technique, message passing, is considered. Several parallel serial monadic DP algorithms are proposed, based on the parallelization in the state variables and the parallelization in the decision variables. Algorithms with no interpolation are also proposed. It is demonstrated how constraints introduce load unbalance which affect scalability and how this problem is inherent to DP.     

Least squares approximate policy iteration for learning bid prices in choice-based revenue management

We consider the revenue management problem of capacity control under customer choice behavior. An exact solution of the underlying stochastic dynamic program is difficult because of the multi-dimensional state space and, thus, approximate dynamic programming (ADP) techniques are widely used. The key idea of ADP is to encode the multi-dimensional state space by a small number of basis functions, often leading to a parametric approximation of the dynamic program’s value function. In general, two classes of ADP techniques for learning value function approximations exist: mathematical programming and simulation. So far, the literature on capacity control largely focuses on the first class.In this paper, we develop a least squares approximate policy iteration (API) approach which belongs to the second class. Thereby, we suggest value function approximations that are linear in the parameters, and we estimate the parameters via linear least squares regression. Exploiting both exact and heuristic knowledge from the value function, we enforce structural constraints on the parameters to facilitate learning a good policy. We perform an extensive simulation study to investigate the performance of our approach. The results show that it is able to obtain competitive revenues compared to and often outperforms state-of-the-art capacity control methods in reasonable computational time. Depending on the scarcity of capacity and the point in time, revenue improvements of around 1% or more can be observed. Furthermore, the proposed approach contributes to simulation-based ADP, bringing forth research on numerically estimating piecewise linear value function approximations and their application in revenue management environments.     

Interference-Based Dynamic Pricing for WCDMA Networks Using Neurodynamic Programming

We study the problem of optimal integrated dynamic pricing and radio resource management, in terms of resource allocation and call admission control, in a WCDMA network. In such interference-limited network, one's resource usage also degrades the utility of others. A new parameter noise rise factor, which indicates the amount of interference generated by a call, is suggested as a basis for setting price to make users accountable for the congestion externality of their usage. The methods of dynamic programming (DP) are unsuitable for problems with large state spaces due to the associated ldquocurse of dimensionality.rdquo To overcome this, we solve the problem using a simulation-based neurodynamic programming (NDP) method with an action-dependent approximation architecture. Our results show that the proposed optimal policy provides significant average reward and congestion improvement over conventional policies that charge users based on their load factor.     

Motion strategies for exploration and map building under uncertainty with multiple heterogeneous robots

In this paper, we present a multi-robot exploration strategy for map building. We consider an indoor structured environment and a team of robots with different sensing and motion capabilities. We combine geometric and probabilistic reasoning to propose a solution to our problem. We formalize the proposed solution using stochastic dynamic programming (SDP) in states with imperfect information. Our modeling can be considered as a partially observable Markov decision process (POMDP), which is optimized using SDP. We apply the dynamic programming technique in a reduced search space that allows us to incrementally explore the environment. We propose realistic sensor models and provide a method to compute the probability of the next observation given the current state of the team of robots based on a Bayesian approach. We also propose a probabilistic motion model, which allows us to take into account errors (noise) on the velocities applied to each robot. This modeling also allows us to simulate imperfect robot motions, and to estimate the probability of reaching the next state given the current state. We have implemented all our algorithms and simulations results are presented.     

Constructing a unifying theory of dynamic programming DCOP algorithms via the generalized distributive law

In this paper we propose a novel message-passing algorithm, the so-called Action-GDL, as an extension to the generalized distributive law (GDL) to efficiently solve DCOPs. Action-GDL provides a unifying perspective of several dynamic programming DCOP algorithms that are based on GDL, such as DPOP and DCPOP algorithms. We empirically show how Action-GDL using a novel distributed post-processing heuristic can outperform DCPOP, and by extension DPOP, even when the latter uses the best arrangement provided by multiple state-of-the-art heuristics.     

Classifying molecular sequences using a linkage graph with their pairwise similarities

This paper presents a method for classifying a large and mixed set of uncharacterized sequences provided by genome projects. As the measure of sequence similarity, we use similarity score computed by a method based on the dynamic programming (DP), such as the Smith-Waterman local alignment algorithm. Although comparison by DP based method is very sensitive, when given sequences include a family of sequences that are much diverged in evolutionary process, similarity among some of them may be hidden behind spurious similarity of some unrelated sequences. Also the distance derived from the similarity score may not be metric (i.e., triangle inequality may not hold) when some sequences have multi-domain structure. To cope with these problems, we introduce a new graph structure called p-quasi complete graph for describing a family of sequences with a confidence measure. We prove that a restricted version of the p-quasi complete graph problem (given a positive integer k, whether a graph contains a 0.5-quasi complete subgraph of which size k or not) is NP-complete. Thus we present an approximation algorithm for classifying a set of sequences using p-quasi complete subgraphs. The effectiveness of our method is demonstrated by the result of classifying over 4000 protein sequences on the Escherichia coli genome that was completely determined recently.     

A dynamic programming approach to GA-based heuristic for multi-period CF problems

In this paper we have introduced a multi-period cell formation (CF) model which is more computationally challenging than the most comprehensive CF models in the literature. A dynamic programming (DP) based approach coupled with GA-based heuristic is proposed to solve the multi-period problem. Since, the introduced dynamic programming is general and can be applied to any GA-based heuristic with full rejuvenation cycles to solve the multi-period part of the model, we focused only on the DP approach in this paper but have explained the interface with the GA-based heuristic. Illustrative example has been provided that clarifies the application of DP-heuristic. The performance of the DP-heuristic has been evaluated against LINGO and multi period GA-based heuristic.