An algorithm for determining the optimal batch size

Translated from Issledovaniya po Prikladnoi Matematike, Kazan', No. 14, pp. 3–9, 1987.     

On a finite horizon production lot size inventory model for deteriorating items: An optimal solution

A generalized production lot size inventory model for deteriorating items over a finite planning horizon is considered. The demand, production, and deteriorating rates are assumed to be known and continuous functions of time. Shortages are allowed and completely backlogged. The conditions under which the system total cost attains its (unique) global minimum are derived. An example which illustrate the applicability of theoretical results is also introduced.     

非线性整数规划的一个近似算法

利用连续总体优化填充函数法的思想，本文设计了非线性整数规划的一个近似算法．首先，给出了非线性整数规划问题离散局部极小解的定义，设计了找离散局部极小解的局部搜索算法；其次，用所设计的局部搜索算法极小化填充函数来找比当前离散局部极小解好的解．本文的近似算法是直接法，且与连续总体优化的填充函数法相比，本文填充函数中的参数易于选取．数值试验表明，本文的近似算法是有效的．     

An approximate decomposition algorithm for convex minimization

For nonsmooth convex optimization, Robert Mifflin and Claudia Sagastizábal introduce a VU-space decomposition algorithm in Mifflin and Sagastizábal (2005) [11]. An attractive property of this algorithm is that if a primal-dual track exists, this algorithm uses a bundle subroutine. With the inclusion of a simple line search, it is proved to be globally and superlinearly convergent. However, a drawback is that it needs the exact subgradients of the objective function, which is expensive to compute. In this paper an approximate decomposition algorithm based on proximal bundle-type method is introduced that is capable to deal with approximate subgradients. It is shown that the sequence of iterates generated by the resulting algorithm converges to the optimal solutions of the problem. Numerical tests emphasize the theoretical findings.     

An optimal production-inventory model for deteriorating items with multiple-market demand

The global markets of today offer more selling opportunities to the deteriorating items’ manufacturers, but also pose new challenges in production and inventory planning. From a production management standpoint, opportunities to exploit the difference in the timing of the selling season between geographically dispersed markets for deteriorating items are important to improving a firm’s profitability. In this paper, we examined the above issue with an insightful production-inventory model of a deteriorating items manufacturer selling goods to multiple-markets with different selling seasons. We also provided a solution procedure to find the optimal replenishment schedule for raw materials and the optimal production plan for finished products. A numerical example was then used to illustrate the model and the solution procedure. Finally, sensitivity analysis of the optimal solution with respect to major parameters was carried out.     

An optimal algorithm for geometrical congruence

An algorithm is given which, in time O(n log n), determines all the Euclidean congruences (if any) between two n-point sets in 3-dimensional space. The algorithm is shown to be optimal to within a constant factor.     

Asymptotic behaviour and optimal word size for exact and approximate word matches between random sequences

The present work is concerned with a fast and accurate sequence comparison method: the count of the number of words of length k letters shared by two sequences, also known as the D2 statistic. We link recent theoretical advances in the characterization of D2 asymptotic distributions with applications to biological sequences. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

An optimal minimax algorithm

Computer game-playing programs repeatedly calculate minimax elements = min _i max _j M _ij of large pay off matricesM _ij . A straightforwardrow-by-row calculation of scans rows ofM _ij one at a time, skipping to a new row whenever an element is encountered that exceeds a current minimax. Anoptimal calculation, derived here, scans the matrix more erratically but finds after testing the fewest possible matrix elements. Minimizing the number of elements tested is reasonable when elements must be computed as needed by evaluating future game positions. This paper obtains the expected number of tests required when the elements are independent, identically distributed, random variables. For matrices 50 by 50 or smaller, the expected number of tests required by the row-by-row calculation can be at most 42% greater than the number for the optimal calculation. When the numbersR, C of rows and columns are very large, both calculations require an expected number of tests nearRC/InR.     

An approximate waves-bordering algorithm for adaptive finite elements analysis

In this paper an Approximate Waves-Bordering algorithm (AWB) is presented. It computes the finite elements linear system solution-update after a refinement/unrefinement step. This is done taking into consideration only the equations that correspond to the nodes whose solution is modified above a certain tolerance and it appears to be very efficient. The algorithm considers an increasing set of equations that updates recursively and stops when the norm of the residual has gone under a user-defined threshold. This revised version was published online in June 2006 with corrections to the Cover Date.     

An extended algorithm for optimal product positioning

Optimal product positioning in an attribute space has been formulated according to the axiom of choice as a mixed integer nonlinear programming problem. To solve it, Albers and Brockhoff have designed the special purpose algorithm PROPOSAS. It works under simplified assumptions: Euclidean metric, equally weighted dimensions of the attribute space and equal sales per customer. The following article shows that the basic ideas of PROPOSAS are flexible enough to be expanded to cover a weighted Minkowski-metric as well as different revenues from the customers. Furthermore, the calculation of a new upper bound is described which reduces CPU-time considerably.     

An optimal contour algorithm for iso-oriented rectangles

Given a set of n iso-oriented rectangles in 2-space we describe an algorithm which determines the contour of their union in O(n log n + p) time and O(n + p) space, where p is the number of edges in the contour. This performance is time-optimal. The space requirements are the same as in the best previously known algorithm. We achieve this by introducing a new data structure, the contracted segment tree, which is a non-trivial modification of the well known segment tree. If only the pieces of the contour are to be reported then this approach yields a time- and space-optimal algorithm.     

An adaptive parameter approach for an approximate solution of optimal control problems

In this paper, we consider a class of nonlinear optimal control problems (Bolza-problems) with constraints of the control vector, initial and boundary conditions of the state vectors. The time interval is fixed. Our approach to parametrize both the state functions and the control functions is described by general piecewise polynomials with unknown coefficients (parameters), where a fixed partition of the time interval is used. Here each of these functions in a suitable way individually will be approximated by such polynomials. The optimal control problem thus is reduced to a mathematical programming problem for these parameters. The existence of an optimal solution is assumed. Convergence properties of this method are not considered in this paper.     

An optimal replenishment policy for deteriorating items with time-varying demand and partial backlogging

Recently, Papachristos and Skouri developed an inventory model in which unsatisfied demand is partially backlogged at a negative exponential rate with the waiting time. In this article, we complement the shortcoming of their model by adding not only the cost of lost sales but also the non-constant purchase cost.     

An approximate solution algorithm for the one-dimensional online median problem

The online median problem consists in finding a sequence of incremental solutions of the k-median problem with k increasing. A particular case of the problem is considered: the clients and facilities are located on the real line. The best algorithm available for the one-dimensional case has competitive ratio 8. We give an improved 5.83-competitive algorithm.     

An approximate algorithm for prognostic modelling using condition monitoring information

Established condition based maintenance modelling techniques can be computationally expensive. In this paper we propose an approximate methodology using extended Kalman-filtering and condition monitoring information to recursively establish a conditional probability density function for the residual life of a component. The conditional density is then used in the construction of a maintenance/replacement decision model. The advantages of the methodology, when compared with alternative approaches, are the direct use of the often multi-dimensional condition monitoring data and the on-line automation opportunity provided by the computational efficiency of the model that potentially enables the simultaneous condition monitoring and associated inference for a large number of components and monitored variables. The methodology is applied to a vibration monitoring scenario and compared with alternative models using the case data.     

An approximate algorithm for a high-multiplicity parallel machine scheduling problem

We consider a high-multiplicity parallel machine scheduling problem where the objective is to minimize the weighted sum of completion times. We suggest an approximate algorithm and we prove that it is asymptotically exact. The algorithm exploits a convex quadratic relaxation of the problem to fix a partial schedule, consisting of most jobs, and then assigns the residual jobs following a simple and general rule. The quality of the obtained solution is evidenced by some numerical tests.     

An approximate subgradient algorithm for unconstrained nonsmooth,nonconvex optimization

In this paper a new algorithm for minimizing locally Lipschitz functions is developed. Descent directions in this algorithm are computed by solving a system of linear inequalities. The convergence of the algorithm is proved for quasidifferentiable semismooth functions. We present the results of numerical experiments with both regular and nonregular objective functions. We also compare the proposed algorithm with two different versions of the subgradient method using the results of numerical experiments. These results demonstrate the superiority of the proposed algorithm over the subgradient method.      

An efficient gradient method with approximate optimal stepsize for large-scale unconstrained optimization

In this paper, we introduce a new concept of approximate optimal stepsize for gradient method, use it to interpret the Barzilai-Borwein (BB) method, and present an efficient gradient method with approximate optimal stepsize for large unconstrained optimization. If the objective function f is not close to a quadratic on a line segment between the current iterate x _k and the latest iterate x _k?1, we construct a conic model to generate the approximate optimal stepsize for gradient method if the conic model is suitable to be used. Otherwise, we construct a new quadratic model or two other new approximation models to generate the approximate optimal stepsize for gradient method. We analyze the convergence of the proposed method under some suitable conditions. Numerical results show the proposed method is very promising.