Discrete allocation of a linear resource according to a sum-of-products objective

The allocation of a linear resource according to the sum of the returns from independent activities is considered. The return from each activity is given by a product of concave and nondecreasing functions of a single allocation variable. The model can be used, for instance, to describe probabilities of success of several serial tasks, into which an activity is subdivided. An incremental algorithm is defined and conditions are given for the algorithm to generate an optimal solution; otherwise, the problem is solved by a two-step procedure involving the incremental maximization of the return corresponding to a single activity and the combination of the activities by dynamic programming. Examples are given of problems solvable and not solvable by the incremental algorithm.     

三维弹塑性结构下限分析的边界元方法

基于极限分析的下限定理,建立了用常规边界元方法进行三维理想弹塑性结构极限分析的求解算法.下限分析所需的弹性应力场可直接由边界元方法求得.所需的自平衡应力场由一组带有待定系数的自平衡应力场基矢量的线性组合进行模拟,这些自平衡应力场基矢量由边界元弹塑性迭代计算得到.下限分析问题最终被归结为一系列未知变量较少的非线性数学规划子问题并通过复合形法进行求解.给出的计算结果表明该算法有较高的精度和计算效率.     

Book review of Orthogonal Systems and Convolution Operators,Operator Theory: Advances and Applications,Robert L. Ellis and Israel Gohberg,Birkhäuser Verlag,Basel-Boston-Berlin 2003, Volume 140. ISBN 3-7643-6929-9.

In this note we investigate a time-discrete stochastic dynamic programming problem with countable state and action spaces. We introduce an approximation procedure for a numerical solution by decomposition of the state and also of the action space. The minimal value functions and the optimal policies of the Markovian Decision .Processes constructed by clustering of both spaces are calculated by dynamic programming. Bounds for the minimal value functions will be obtained and convergence theorems are proved.     

Inequalities involving partial derivatives

This paper presents a method for obtaining closed form solutions to serial and nonserial dynamic programming problems with quadratic stage returns and linear transitions. Global parametric optimum solutions can be obtained regardless of the convexity of the stage returns. The closed form solutions are developed for linear, convex, and nonconvex quadratic returns, as well as the procedure for recursively solving each stage of the problem. Dynamic programming is a mathematical optimization technique which is especially powerful for certain types of problems. This paper presents a procedure for obtaining analytical solutions to a class of dynamic programming problems. In addition, the procedure has been programmed on the computer to facilitate the solution of large problems.     

Constrained two-dimensional cutting: an improvement of Christofides and Whitlock's exact algorithm

Christofides and Whitlock have developed a top-down algorithm which combines in a nice tree search procedure Gilmore and Gomory's algorithm and a transportation routine called at each node of the tree for solving exactly the constrained two-dimensional cutting problem. Recently, another bottom-up algorithm has been developed and reported as being more efficient. In this paper, we propose a modification to the branching strategy and we introduce the one-dimensional bounded knapsack in the original Christofides and Whitlock algorithm. Then, by exploiting dynamic programming properties we obtain good lower and upper bounds which lead to significant branching cuts, resulting in a drastic reduction of calls of the transportation routine. Finally, we propose an incremental solution of the numerous generated transportation problems. The resulting algorithm reveals superior performance to other known algorithms.     

The coordinated replenishment dynamic lot-sizing problem with quantity discounts

In the classical coordinated replenishment dynamic lot-sizing problem, the primary motivation for coordination is in the presence of the major and minor setup costs. In this paper, a separate element of coordination made possible by the offer of quantity discounts is considered. A mathematical programming formulation for the extended problem under the all-units discount price structure and the incremental discount price structure is provided. Then, using variable redefinitions, tighter formulations are presented in order to obtain tight lower bounds for reasonable size problems. More significantly, as the problem is NP-hard, we present an effective polynomial time heuristic procedure, for the incremental discount version of the problem, that is capable of solving reasonably large size problems. Computational results for the heuristic procedure are reported in the paper.     

Incremental analysis for MCDM with an application to group TOPSIS

The study aims to exploit incremental analysis or marginal analysis to overcome the drawbacks of ratio scales utilized in various multi-criteria or multi-attribute decision making (MCDM/MADM) techniques. In the proposed 11-step procedure, multiple criteria of alternatives are first reorganized as two categories – benefits and costs – and decision information will be manipulated separately. The performances of alternatives are then evaluated on their incremental benefit–cost ratio, and the rank can be obtained by applying the group TOPSIS (technique for order preference by similarity to ideal solution) model (Shih et al., 2007). Two representations of cost, i.e., a cost index and utility index, are proposed in the model to better-fit real-world situations. In addition, some considerations on costs and input–output relations are also discussed in order to understand the essentials of incremental analysis. In the final part, a case of robot selection demonstrates the suggested model to be both robust and efficient in a group decision-making environment.     

Flexible solutions to systems of linear inequalities

In this paper we present two methods for calculating solutions to a system of linear inequalities which have certain prescribed distance properties to the constraints (referred to as flexibility properties). The first method (based on the calculation of the centre of an inscribed sphere, which is a well-known problem in linear programming) allows changes in the solution in any direction over a certain distance without becoming infeasible. The second method consists in the calculation of a solution with flexibility properties with respect to a prescribed coordinate system. It comprises an iterative procedure inside the area of feasible solutions using simple arithmetic operations. The major part of the paper will be devoted to the second method, since it is new and has attractive properties. Both methods are particularly applicable to the analysis of linear programming models with uncertain and inaccurate constraint parameters and in cases where operational adjustments are desired.     

Optimum control laws in a non-autonomous dynamic model of a gas field

A model of gas field development described as a nonlinear optimum control problem with an infinite planning horizon is considered. The Pontryagin maximum principle is used to solve it. The theorem on sufficient optimumity conditions in terms of constructions of the Pontryagin maximum principles is used to substantiate the optimumity of the extremal solution. A procedure for constructing the optimum solution by dynamic programming is described and is of some methodological interest. The obtained optimum solution is used to construct the Bellman function. Reference is made to a work containing an economic interpretation of the problem.     

Dynamic programming: An interactive approach

An interactive approach to the formulation, modeling, analysis, and solution of discrete deterministic dynamic programming problems is presented. The approach utilizes APL both as the mathematical and the programming language. The interactive capabilities of APL and the simple one-to-one correspondence between the programming and the mathematical language provide an extremely convenient environment for dynamic programming investigations in general and for teaching/learning purposes in particular. The approach is illustrated by a simple model and a numerical example.     

Portfolio optimization in a Lévy market with intertemporal substitution and transaction costs

We investigate an infinite horizon investment-consumption model in which a single agent consumes and distributes her wealth between a risk-free asset (bank account) and several risky assets (stocks) whose prices are governed by Lévy (jump-diffusion) processes. We suppose that transactions between the assets incur a transaction cost proportional to the size of the transaction. The problem is to maximize the total utility of consumption under Hindy-Huang-Kreps intertemporal preferences. This portfolio optimisation problem is formulated as a singular stochastic control problem and is solved using dynamic programming and the theory of viscosity solutions. The associated dynamic programming equation is a second order degenerate elliptic integro-differential variational inequality subject to a state constraint boundary condition. The main result is a characterization of the value function as the unique constrained viscosity solution of the dynamic programming equation. Emphasis is put on providing a framework that allows for a general class of Lévy processes. Owing to the complexity of our investment-consumption model, it is not possible to derive closed form solutions for the value function. Hence, the optimal policies cannot be obtained in closed form from the first order conditions for the dynamic programming equation. Therefore, we have to resort to numerical methods for computing the value function as well as the associated optimal policies. In view of the viscosity solution theory, the analysis found in this paper will ensure the convergence of a large class of numerical methods for the investment-consumption model in question.     

Pseudospectral Chebyshev Optimal Control of Constrained Nonlinear Dynamical Systems

A pseudospectral method for generating optimal trajectories of linear and nonlinear constrained dynamic systems is proposed. The method consists of representing the solution of the optimal control problem by an mth degree interpolating polynomial, using Chebyshev nodes, and then discretizing the problem using a cell-averaging technique. The optimal control problem is thereby transformed into an algebraic nonlinear programming problem. Due to its dynamic nature, the proposed method avoids many of the numerical difficulties typically encountered in solving standard optimal control problems. Furthermore, for discontinuous optimal control problems, we develop and implement a Chebyshev smoothing procedure which extracts the piecewise smooth solution from the oscillatory solution near the points of discontinuities. Numerical examples are provided, which confirm the convergence of the proposed method. Moreover, a comparison is made with optimal solutions obtained by closed-form analysis and/or other numerical methods in the literature.     

Optimization of Discrete-Continuous Dynamic Systems Based on Disjunctive Programming

In this contribution, a novel approach for the modeling and optimization of discrete-continuous dynamic systems based on a disjunctive problem formulation is proposed. It will be shown that a disjunctive model representation, which constitutes an alternative to mixed-integer model formulations, provides a very flexible and intuitive way to formulate discrete-continuous dynamic optimization problems. Moreover, the structure and properties of the disjunctive process models can be exploited for an efficient and robust numerical solution by applying generalized disjunctive programming techniques. The proposed modeling and optimization approach will be illustrated by means of an optimal control problem that embeds a linear discretecontinuous dynamic system. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Analysis of a time discretization for an implicit variational inequality modelling dynamic contact problems with friction

Some dynamic contact problems with friction can be formulated as an implicit variational inequality. A time discretization of such an inequality is given here, thus giving rise to a so‐called incremental solution. The convergence of the incremental solution is established, and then the limit is shown to be the unique solution of the variational inequality. This paper contains therefore not only some new results concerning the numerical aspect of some models of contact and friction but also a constructive existence result. Copyright © 2001 John Wiley & Sons, Ltd.     

A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size

We consider a two-dimensional cutting stock problem where stock of different sizes is available, and a set of rectangular items has to be obtained through two-staged guillotine cuts. We propose a heuristic algorithm, based on column generation, which requires as its subproblem the solution of a two-dimensional knapsack problem with two-staged guillotines cuts. A further contribution of the paper consists in the definition of a mixed integer linear programming model for the solution of this knapsack problem, as well as a heuristic procedure based on dynamic programming. Computational experiments show the effectiveness of the proposed approach, which obtains very small optimality gaps and outperforms the heuristic algorithm proposed by Cintra et al. [3].     

A recurrence method for a special class of continuous time linear programming problems

This article studies a numerical solution method for a special class of continuous time linear programming problems denoted by (SP). We will present an efficient method for finding numerical solutions of (SP). The presented method is a discrete approximation algorithm, however, the main work of computing a numerical solution in our method is only to solve finite linear programming problems by using recurrence relations. By our constructive manner, we provide a computational procedure which would yield an error bound introduced by the numerical approximation. We also demonstrate that the searched approximate solutions weakly converge to an optimal solution. Some numerical examples are given to illustrate the provided procedure.     

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.     

Modeling and numerical analysis of the thread rolling process

The paper presents the physical and mathematical models of deformations (displacements and strains) and the stress in the cold process of the thread rolling. The process is considered as a geometrical and physical nonlinear, initial as well as a boundary value problem. The phenomena of a typical incremental step were described using a step-by-step incremental procedure, in the updated Lagrangian formulation. The state of strains was described by Green-Lagrange's tensor, while the state of stress was described by the second symmetrical Pioli-Kirchhoff's tensor. The object was treated as an elastic (in the reversible zone) and visco-plastic body (in the non-reversible zone) with mixed hardening. The variational equation of the motion in three dimensions for this case was proposed. Then, the finite elements methods (FEM) and dynamic explicit method (DEM) were used to obtain the solution. In a numerical analysis, boundary condition for a displacement increment, was determined in the model investigation. The results of a numerical analysis were compared and verified in an experimental investigation. Examples of calculations of the influence of a friction coefficient on the state of the deformation and stress, and an example application for this method of thread rolling were presented. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A Decision Model for a Sequential Testing Problem in civil Engineering

A sequential decision problem in civil engineering is formulatedas a dynamic programming model. A set of theorems lead to amore efficient formulation, permitting the solution routineto be programmed on a microcomputer. The solution is printedin table fonn, directly providing a decision rule usable bythe foreman in the field. The paper illustrates a point whichis becoming increasingly apparent: the power and availabilityof portable computer systems are making many decision problemsamenable to on-site analysis using models based upon rigoroustheory.     

在寿命周期内具有抛物型需求的物品的最优补充模型

本文建立了在寿命周期内具有二次抛物需求的物品的一个确定型最优批量模型,提供了产生最优补充策略的一个简单的动态规划方法,用数字例子说明了该模型的求解过程,并出示了模型参数的灵敏度分析．