A mathematical programming approach for improving the robustness of least sum of absolute deviations regression

This paper discusses a novel application of mathematical programming techniques to a regression problem. While least squares regression techniques have been used for a long time, it is known that their robustness properties are not desirable. Specifically, the estimators are known to be too sensitive to data contamination. In this paper we examine regressions based on Least‐sum of Absolute Deviations (LAD) and show that the robustness of the estimator can be improved significantly through a judicious choice of weights. The problem of finding optimum weights is formulated as a nonlinear mixed integer program, which is too difficult to solve exactly in general. We demonstrate that our problem is equivalent to a mathematical program with a single functional constraint resembling the knapsack problem and then solve it for a special case. We then generalize this solution to general regression designs. Furthermore, we provide an efficient algorithm to solve the general nonlinear, mixed integer programming problem when the number of predictors is small. We show the efficacy of the weighted LAD estimator using numerical examples. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Expected time delay in multi‐item inventory systems with correlated demands

This paper considers multi‐item inventory systems where a customer order may require several different items (i.e., demands are correlated across items) and customer satisfaction is measured by the time delays seen by the customers. Most inventory models on time delay in the literature assume each demand only requires one item (i.e., demands are not correlated across items or are independent). In this paper, we derive an exact expression for the expected total time delay. We show that when items are actually correlated, assuming items are independent leads to an overestimate of the total time delay. However, (1) it is extremely difficult in practice to obtain the demand information for all demand types (especially in a system with tens of thousands of part numbers), and (2) the problem becomes too complicated to be of practical interest when the correlation is considered. We then explore the possibility of including the demand information partially and develop bounds for the time delays. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 671–688, 1999     

Resequencing with parallel queues to minimize the maximum number of items in the overflow area

This article treats an elementary optimization problem, where an inbound stream of successive items is to be resequenced with the help of multiple parallel queues in order to restore an intended target sequence. Whenever early items block the one item to be currently released into the target sequence, they are withdrawn from their queue and intermediately stored in an overflow area until their actual release is reached. We aim to minimize the maximum number of items simultaneously stored in the overflow area during the complete resequencing process. We met this problem in industry practice at a large German automobile producer, who has to resequence containers with car seats prior to the assembly process. We formalize the resulting resequencing problem and provide suited exact and heuristic solution algorithms. In our computational study, we also address managerial aspects such as how to properly avoid the negative effects of sequence alterations. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 401–415, 2016     

D-S 证据理论应用中的一种图解方法

D-S证据理论是对概率论的进一步扩充,在多传感器数据融合中,有着广泛的应用.当利用D-S合成公式进行融合时,由于需计算的项数较多且不易直接判定具体该有哪些项,容易造成漏项或错项,引起计算错误.提出了一种直观、简单的图解法,可使需计算的项一目了然.     

Some approximations in multi-item,multi-echelon inventory systems for recoverable items

The optimization problem as formulated in the METRIC model takes the form of minimizing the expected number of total system backorders in a two-echelon inventory system subject to a budget constraint. The system contains recoverable items – items subject to repair when they fail. To solve this problem, one needs to find the optimal Lagrangian multiplier associated with the given budget constraint. For any large-scale inventory system, this task is computationally not trivial. Fox and Landi proposed one method that was a significant improvement over the original METRIC algorithm. In this report we first develop a method for estimating the value of the optimal Lagrangian multiplier used in the Fox-Landi algorithm, present alternative ways for determining stock levels, and compare these proposed approaches with the Fox-Landi algorithm, using two hypothetical inventory systems – one having 3 bases and 75 items, the other 5 bases and 125 items. The comparison shows that the computational time can be reduced by nearly 50 percent. Another factor that contributes to the higher requirement for computational time in obtaining the solution to two-echelon inventory systems is that it has to allocate stock optimally to the depot as well as to bases for a given total-system stock level. This essentially requires the evaluation of every possible combination of depot and base stock levels – a time-consuming process for many practical inventory problems with a sizable system stock level. This report also suggests a simple approximation method for estimating the optimal depot stock level. When this method was applied to the same two hypotetical inventory systems indicated above, it was found that the estimate of optimal depot stock is quite close to the optimal value in all cases. Furthermore, the increase in expected system backorders using the estimated depot stock levels rather than the optimal levels is generally small.     

D-S证据理论应用中的一种验证方法

D-S证据理论是一种比概率论确定性弱的不确定性理论,它能将"不知道"和"不确定"两个认知学上的主要概念区别开来,在多传感器数据融合中具有广泛的应用前景.D-S证据理论在实际应用中却存在一个困难,当目标的个数较多时,需要计算的项数太多,容易造成漏项,引起计算错误.提出了一种确定计算项数的算法,作为验证计算结果的必要条件,并通过图解的方法找出需要计算的项.     

Optimization methods for large-scale multiechelon stockage problems

I examine the problem of determining inventory stockage levels and locations of different parts in a multiechelon system. This stockage problem is complicated by parts commonality—each part may be used by several different end items. Stockage levels and locations of each part affect the availability of end items that use the part, since an end item will be out of service if it requires a part that is not available. Of course, if the part is available at another nearby location, then the end item will be out of service for a shorter period of time. An essential feature of any model for this problem is constraints on operational availability of the end items. Because these constraints would involve nonconvex functions if the stockage levels were allowed to vary continuously, I formulate a 0–1 linear optimization model of the stockage problem. In this model, each part can be stocked at any of a number of prespecified levels at each echelon. The model is to minimize stockage cost of the selected items subject to the end-item availability constraints and limits on the total weight, volume, and number of different parts stocked at each echelon. Advantages and disadvantages of different Lagrangian relaxations and the simplex method with generalized upper-bounding capability are discussed for solving this stockage model.     

Scheduling with parallel processors and linear delay costs

This paper deals with the sequencing problem of minimizing linear delay costs with parallel identical processors. The theoretical properties of this m-machine problem are explored, and the problem of determining an optimum scheduling procedure is examined. Properties of the optimum schedule are given as well as the corresponding reductions in the number of schedules that must be evaluated in the search for an optimum. An experimental comparison of scheduling rules is reported; this indicates that although a class of effective heuristics can be identified, their relative behavior is difficult to characterize.     

(R.Q) inventory problem with unknown mean demand and learning

We address a single product, continuous review model with stationary Poisson demand. Such a model has been effectively studied when mean demand is known. However, we are concerned with managing new items for which only a Bayesian prior distribution on the mean is available. As demand occurs, the prior is updated and our control parameters are revised. These include the reorder point (R) and reorder quantity (Q). Deemer, taking a clue from some earlier RAND work, suggested using a model appropriate for known mean, but using a Compound Poisson distribution for demand rather than Poisson to reflect uncertainty about the mean. Brown and Rogers also used this approach but within a periodic review context. In this paper we show how to compute optimum reorder points for a special problem closely related to the problem of real interest. In terms of the real problem, subject to a qualification to be discussed, the reorder points found are upper bounds for the optimum. At the same time, the reorder points found can never exceed those found by the Compound Poisson (Deemer) approach. And they can be smaller than those found when there is no uncertainty about the mean. As a check, the Compound Poisson and proposed approach are compared by simulation.     

面向大规模交互数据空间划分的Voronoi图生成算法及应用

传统Voronoi图对大量点集进行Voronoi划分时会产生Voronoi单元格数过多的现象,导致难以适用于地理信息系统、生物医学等诸多领域.为了解决这个问题,提出一种自适应基于密度的聚类算法(Density-Based Spatial Clustering of Applications with Noise,DBS...     

基于多目标的雷达组网传感器资源管理算法

在雷达组网系统的多目标跟踪过程中,当目标数量过多时,由于传感器资源不足,无法使用传统传感器的管理方法进行资源分配,且运算时间过长,不满足工程实际需求。针对以上问题,提出了一种新的多传感器多目标跟踪任务快速分配算法,该算法将跟踪目标个数和跟踪目标精度作为优化目标,首先按照设定的分配准则对传感器进行一次分配,最大化跟踪目标个数;然后利用一种基于传感器排序的启发式传感器分配方法进行二次分配,通过控制跟踪目标的协方差水平,使目标的跟踪精度尽量接近期望值。仿真结果表明,该算法能够在较短的时间内对多传感器进行有效快速地分配,既跟踪了更多的目标,又达到了期望目标的跟踪精度,并且在一定程度上控制资源消耗,减少系统的总耗能。     

Algorithms for the multi‐item multi‐vehicles dynamic lot sizing problem

We consider a two‐stage supply chain, in which multi‐items are shipped from a manufacturing facility or a central warehouse to a downstream retailer that faces deterministic external demand for each of the items over a finite planning horizon. The items are shipped through identical capacitated vehicles, each incurring a fixed cost per trip. In addition, there exist item‐dependent variable shipping costs and inventory holding costs at the retailer for items stored at the end of the period; these costs are constant over time. The sum of all costs must be minimized while satisfying the external demand without backlogging. In this paper we develop a search algorithm to solve the problem optimally. Our search algorithm, although exponential in the worst case, is very efficient empirically due to new properties of the optimal solution that we found, which allow us to restrict the number of solutions examined. Second, we perform a computational study that compares the empirical running time of our search methods to other available exact solution methods to the problem. Finally, we characterize the conditions under which each of the solution methods is likely to be faster than the others and suggest efficient heuristic solutions that we recommend using when the problem is large in all dimensions. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006.     

A closed-from approach for multi-item inventory grouping

The problem of optimally coordinating the replenishments of the many items in stock with one another is dealt with in this article. Specifically, it considers this coordination based on classifying the items into a few groups with common order cycles for all the items in a particular group. Assuming that the cumulative distribution by value of the inventory can be characterized by a Pareto function of the type f(n) = n/(an + b), (a, b > 0), it establishes that the optimal boundaries of the groups can be obtained as closed-form expressions by solving a system of simultaneous equations. The composition of the successive groups thus obtained is found to equipartition the total cost and to follow geometric sequences in relation to the number of items, the value of items, and the lengths of the order cycles. Graphs have been proposed to aid the implementation of the grouping scheme. Simple iterative schemes are outlined within the framework of the Pareto function to handle other relevant costs.     

A concave‐cost production planning problem with remanufacturing options

We focus on the concave‐cost version of a production planning problem where a manufacturer can meet demand by either producing new items or by remanufacturing used items. Unprocessed used items are disposed. We show the NP‐hardness of the problem even when all the costs are stationary. Utilizing the special structure of the extreme‐point optimal solutions for the minimum concave‐cost problem with a network flow type feasible region, we develop a polynomial‐time heuristic for the problem. Our computational study indicates that the heuristic is a very efficient way to solve the problem as far as solution speed and quality are concerned. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

The inventory packing problem

We study the problem of finding the minimum number of identical storage areas required to hold n items for which demand is known and constant. The replenishments of the items within a single storage area may be time phased so as to minimize the maximum total storage capacity required at any time. This is the inventory-packing problem, which can be considered as a variant of the well-known bin-packing problem, where one constraint is nonlinear. We study the worst-case performance of six heuristics used for that earlier problem since the recognition version of the inventory-packing problem is shown to be NP complete. In addition, we describe several new heuristics developed specifically for the inventory-packing problem, and also study their worst-case performance. Any heuristic which only opens a bin when an item will not fit in any (respectively, the last) open bin needs, asymptotically, no more than 25/12 (resp., 9/4) times the optimal number of bins. Improved performance bounds are obtainable if the range from which item sizes are taken is known to be restricted. Extensive computational testing indicates that the solutions delivered by these heuristics are, for most problems, very close to optimal in value.     

A three-echelon,multi-item model for recoverable items

The main objective of this paper is to develop a mathematical model for a particular type of three-echelon inventory system. The proposed model is being used by the Air Force to evaluate inventory investment requirements for alternative logistic structures. The system we will model consists of a group of locations, called bases, and a central depot. The items of concern in our analysis are called recoverable items, that is, items that can be repaired when they fail. Furthermore, each item has a modular or hierarchical design. Briefly, the model is used to determine the stock levels at each location for each item so as to achieve optimum inventory-system performance for a given level of investment. An algorithm for the computation of stock levels for each item and location is developed and illustrated. Some of the ways the model can be used are illustrated with Air Force data.     

The distribution of recoverable inventory items from a repair center when the number of consumption centers is large

This paper considers real-time decision rules for an inventory system where items are repaired than “used up.” The problem is to decide which user in the system has the greatest need for the newly available inventory items coming out of repair. The main result shows that two published approahes, the Transportation Time Look Ahead policy and METRIC, are optimal when the number of users gets large. A useful byproduct of the proof is a lower bound on the average backorder rate for a repair-inventory system of any size.     

Optimal disposal policies for a single-item inventory system with returns

We consider a single-item inventory system in which the stock level can increase due to items being returned as well as decrease when demands occur. Returned items can be repaired and then used to satisfy future demand, or they can be disposed of. We identify those inventory levels where disposal is the best policy. It is shown that this problem is equivalent to a problem of controlling a single-server queue. When the return and demand processes are both Poisson, we find the optimal policy exactly. When the demand and return processes are more general, we use diffusion approximations to obtain an approximate model, which is then solved. The approximate model requires only mean and variance data. Besides the optimal policy, the output of the models includes such characteristics as the operating costs, the purchase rate for new items, the disposal rate for returned items and the average inventory level. Several numerical examples are given. An interesting by-product of our investigation is an approximation for the steady-state behavior of the bulk GI/G/1 queue with a queue limit.     

The initial provisioning decision for insurance type items

Initial provisioning decisions (inventory stocking requirements) for low demand items often have to be made without much knowledge of what future demand rates will be. When the nature of an item is such that little demand for it is expected, the problem of whether to stock initially or risk not stocking the item is most critical. This report discusses this problem and presents decision procedures which can be used to handle this aspect of initial provisioning. The procedures relate an item's provisioning desirability to its provisioning characteristics, such as expected cost, expected resupply time, current information on its likely demand rate, and to an overall operating policy or criterion. The criterion function measures the total system degredation as a function of the events of having items out of stock when demand occurs. Several different policy functions are discussed and the provisioning decision rules which apply to each are presented. Demand rate information is handled through a Bayesian type approach. The decision rules presented in this report can be utilized to either determine stocking requirements within a budgetary constraint, or determine the relative stocking desirability on an item-by-item basis.     

一种基于混合搜索的高效Top-K最频繁模式挖掘算法

挖掘数据集中的Top-K最频繁模式具有重要意义.已有Top-K最频繁模式挖掘算法通常采用最频繁的k个项目作为初始项目,并将初始项目中频率最低的项目的支持度作为初始边界支持度.但实际组成Top-K最频繁模式的项目数目可能远少于k,从而制约了算法的效率.为此,提出了一种基于混合搜索方式的高效Top-K最频繁模式挖掘算法MTKFP.该算法首先利用宽度优先搜索获得少量的短项集,并利用短项集确定数目少于k的初始项目范围以及较高的初始边界支持度;然后利用深度优先搜索获得所有Top-K最频繁模式.实验表明,MTKFP算法所获得的初始项目数目至少低于已有算法70%,初始边界支持度高于已有算法;NTKFP算法的性能优于已有最好算法.