A multi-parametric programming approach for multilevel hierarchical and decentralised optimisation problems

In this paper, we outline the foundations of a general global optimisation strategy for the solution of multilevel hierarchical and general decentralised multilevel problems, based on our recent developments on multi-parametric programming and control theory. The core idea is to recast each optimisation subproblem, present in the hierarchy, as a multi-parametric programming problem, with parameters being the optimisation variables belonging to the remaining subproblems. This then transforms the multilevel problem into single-level linear/convex optimisation problems. For decentralised systems, where more than one optimisation problem is present at each level of the hierarchy, Nash equilibrium is considered. A three person dynamic optimisation problem is presented to illustrate the mathematical developments.     

A new algorithm for multi-dimensional dynamic programming problems

The new algorithm presented here solves medium size multi-dimensional dynamic programming problems in a relatively short computational time with no fast-memory restraints. The algorithm converges to the global optimal solution under some differentiability and convexity assumptions.The procedure is to solve a succession of dynamic programming problems, the state sets of which are limited to only a very small subset of the original state space. The interrelated definition of state sets for successive subproblems facilitates an algorithmic convergence while moving the subsets to contain the optimal states at the end.     

A class of nonseparable dynamic programming problems

A solution procedure is proposed for a class of deterministic sequential decision problems whose objective functions are of the form f _n(x _n)+(g _n(x _n)) where is differentiable and either concave or convex. The procedure calls for the collaboration between dynamic programming and c-programming, and is demonstrated in our treatment of a minimum variance type problem.     

New approach for nonseparable dynamic programming problems

A general class of nonseparable dynamic problems is studied in a dynamic programming framework by introducingkth-order separability. The solution approach uses multiobjective dynamic programming as a separation strategy forkth-order separable dynamic problems. The theoretical grounding on which the optimal solution of the original nonseparable dynamic problem can be attained by a noninferior solution of the corresponding multiobjective dynamic programming problem is established. The relationship between the overall optimal Lagrangian multipliers and the stage-optimal Lagrangian multipliers and the relationship between the overall weighting vector and the stage weighting vector are explored, providing the basis for identifying the optimal solution of the original nonseparable problem from among the set of noninferior solutions generated by the envelope approach.This work was supported in part by NSF Grant No. CES-86-17984. The authors appreciate the comments from Dr. V. Chankong and the editorial work by Mrs. V. Benade and Dr. S. Hitchcock.     

Optimizing reserves in school choice: A dynamic programming approach

We introduce a new model of school choice with reserves in which asocial planner is constrained by a limited supply of reserve seats and tries to find the matching that is optimal according to a social welfare function. We construct the optimal distribution of reserves via a quartic-time dynamic programming algorithm. Due to the modular nature of the algorithm, the resulting mechanism is strategy-proof for reserve-eligible students.     

Intensional dynamic programming. A Rosetta stone for structured dynamic programming

We present intensional dynamic programming (IDP), a generic framework for structured dynamic programming over atomic, propositional and relational representations of states and actions. We first develop set-based dynamic programming and show its equivalence with classical dynamic programming. We then show how to describe state sets intensionally using any form of structured knowledge representation and obtain a generic algorithm that can optimally solve large, even infinite, MDPs without explicit state space enumeration. We derive two new Bellman backup operators and algorithms. In order to support the view of IDP as a Rosetta stone for structured dynamic programming, we review many existing techniques that employ either propositional or relational knowledge representation frameworks.     

Optimal control problems on manifolds: a dynamic programming approach

Dynamic programming identifies the value function of continuous time optimal control with a solution to the Hamilton-Jacobi equation, appropriately defined. This relationship in turn leads to sufficient conditions of global optimality, which have been widely used to confirm the optimality of putative minimisers. In continuous time optimal control, the dynamic programming methodology has been used for problems with state space a vector space. However there are many problems of interest in which it is necessary to regard the state space as a manifold. This paper extends dynamic programming to cover problems in which the state space is a general finite-dimensional C^∞ manifold. It shows that, also in a manifold setting, we can characterise the value function of a free time optimal control problem as a unique lower semicontinuous, lower bounded, generalised solution of the Hamilton-Jacobi equation. The application of these results is illustrated by the investigation of minimum time controllers for a rigid pendulum.     

A fuzzy programming approach for dynamic virtual hub location problem

Hub location problem has been used in transportation network to exploit economies of scale. For example, a controversial issue in the planning of air transportation networks is inclement weather or emergency conditions. In this situation, hub facilities would not be able to provide a good service to their spoke nodes temporarily. Thus, some other kinds of predetermined underutilized facilities in the network are used as virtual hubs to host some or all connections of original hubs to recover the incurred incapacitation and increase network flexibility and demand flow. In such an unexpected situation, it is not unreasonable to expect that some information be imprecise or vague. To deal with this issue, fuzzy concept is used to pose a more realistic problem. Here, we present a fuzzy integer liner programming approach to propose a dynamic virtual hub location problem with the aim of minimizing transportation cost in the network. We examine the effectiveness of our model using the well-known CAB data set.     

An analytical bound on the fleet size in vehicle routing problems: A dynamic programming approach

We present an analytical upper bound on the number of required vehicles for vehicle routing problems with split deliveries and any number of capacitated depots. We show that a fleet size greater than the proposed bound is not achievable based on a set of common assumptions. This property of the upper bound is proved through a dynamic programming approach. We also discuss the validity of the bound for a wide variety of routing problems with or without split deliveries.     

A dynamic programming algorithm for the bilevel knapsack problem

We propose an efficient dynamic programming algorithm for solving a bilevel program where the leader controls the capacity of a knapsack, and the follower solves the resulting knapsack problem. We propose new recursive rules and show how to solve the problem as a sequence of two standard knapsack problems.     

Selecting preferred solutions in the minimax approach to dynamic programming problems under flexible constraints

Dynamic Programming is a powerful approach to the optimization of sequential or multistage decision processes, e.g., in planning or in system control. In this paper, we consider both theoretical and algorithmic issues in sequential decision processes under flexible constraints. Such processes must attain a given goal within some tolerance. Tolerances or preferences also apply to the values the decision variables may take or on the action chosen at each step. Such problems boil down to maximin optimization. Unfortunately, this approach suffers from the so-called “drowning effect” (lack of discrimination) and the optimality principle of dynamic programming is not always verified. In this context, we introduce a general framework for refined minimax optimization procedures in order to compare and select preferred alternatives. This framework encompasses already introduced methods such as LexiMin and DiscriMin, but it allows their extension to the comparison of vectors of unequal lengths. We show that these refined comparisons restore compatibility with the optimality principle, and that classical algorithms can be adapted to compute such preferred solutions, by exploiting existing results on idempotent semirings.     

A dynamic programming approach to constrained portfolios

This paper studies constrained portfolio problems that may involve constraints on the probability or the expected size of a shortfall of wealth or consumption. Our first contribution is that we solve the problems by dynamic programming, which is in contrast to the existing literature that applies the martingale method. More precisely, we construct the non-separable value function by formalizing the optimal constrained terminal wealth to be a (conjectured) contingent claim on the optimal non-constrained terminal wealth. This is relevant by itself, but also opens up the opportunity to derive new solutions to constrained problems. As a second contribution, we thus derive new results for non-strict constraints on the shortfall of intermediate wealth and/or consumption.     

A dynamic programming approach for batch sizing in a multi-stage production process with random yields

This paper proposes a dynamic programming approach to modeling and determining batch sizes in a single period, multi-stage production process with random yields for each stage. To improve the computational performance of the proposed approach, a statistical bound is developed. A key decision incorporated into the model is whether to continue onto the next stage of processing or to scrap the entire current batch of product. This decision is based on the expected total profit from the remaining items for processing following the removal of all defectives. The decisions involving the locations of test stations after stages are also incorporated into the modeling approach.     

Interactive fuzzy goal programming approach for bilevel programming problem

This paper presents an interactive fuzzy goal programming (FGP) approach for bilevel programming problems with the characteristics of dynamic programming (DP).     

Non-randomized policies for constrained Markov decision processes

This paper addresses constrained Markov decision processes, with expected discounted total cost criteria, which are controlled by non-randomized policies. A dynamic programming approach is used to construct optimal policies. The convergence of the series of finite horizon value functions to the infinite horizon value function is also shown. A simple example illustrating an application is presented.     

Solving shortest length least-squares problems via dynamic programming

If the matrixA is not of full rank, there may be many solutions to the problem of minimizing Ax–b overx. Among such vectorsx, the unique one for which x is minimum is of importance in applications. This vector may be represented asx=A ⁺ b. In this paper, the functional equation technique of dynamic programming is used to find the shortest solution to the least-squares problem in a sequential fashion. The algorithm is illustrated with an example.Our debt to the late Professor Richard Bellman is clear, and we wish to thank Professor Harriet Kagiwada for many stimulating conversations concerning least-squares problems over a long period of years.     

A parallel variable-metric dynamic programming algorithm

This paper presents a potentially parallel iterative algorithm for the solution of the unconstrainedN-stage decision problem of dynamic programming. The basis of the algorithm is the use of variable-metric minimization techniques to develop a quadratic approximation to the cost function at each stage. The algorithm is applied to various problems, and comparisons with other algorithms are made.This research forms part of the author's PhD program, and is supported by the Department of Scientific and Industrial Research of the New Zealand Government. The author is indebted to Dr. B. A. Murtagh, PhD supervisor, for his encouragement and support during the preparation of this paper.     

A dynamic programming algorithm for dynamic lot size models with piecewise linear costs

We propose a new algorithm for dynamic lot size models (LSM) in which production and inventory cost functions are only assumed to be piecewise linear. In particular, there are no assumptions of convexity, concavity or monotonicity. Arbitrary capacities on both production and inventory may occur, and backlogging is allowed. Thus the algorithm addresses most variants of the LSM appearing in the literature. Computational experience shows it to be very effective on NP-hard versions of the problem. For example, 48 period capacitated problems with production costs defined by eight linear segments are solvable in less than 2.5 minutes of Vax 8600 cpu time.     

NLPQL: A fortran subroutine solving constrained nonlinear programming problems

NLPQL is a FORTRAN implementation of a sequential quadratic programming method for solving nonlinearly constrained optimization problems with differentiable objective and constraint functions. At each iteration, the search direction is the solution of a quadratic programming subproblem. This paper discusses the organization of NLPQL, including the formulation of the subproblem and the information that must be provided by a user. A summary is given of the performance of different algorithmic options of NLPQL on a collection of test problems (115 hand-selected or application problems, 320 randomly generated problems). The performance of NLPQL is compared with that of some other available codes.