Ship-pack optimization in a two-echelon distribution system

In large distribution systems, distribution centers (DC) deliver some merchandize to their retail stores in size-specific packages, also called ship-packs. These ship-packs include cases (e.g., cartons containing 24 or 48 units), inners (packages of 6 or 8 units) or eaches (individual units). For each Stock Keeping Unit (SKU), a retailer can decide which of these ship-pack options to use when replenishing its retail stores. Working with a major US retailer, we have developed a cost model that balances DC handling costs, store handling costs and inventory-related costs at both the DC and the stores, and therefore can help to determine the optimum warehouse ship-pack for each SKU. We implement our model for a sample of 529 SKUs, and show that by changing ship-pack size for about 30 SKUs, the retailer can reduce its total cost by 0.3% - 0.4%. Interestingly, we find that most of the cost savings occurs at the DC level.     

A note on “A LP-based heuristic for a time-constrained routing problem”

In their paper, Avella et al. (2006) investigate a time-constrained routing problem. The core of the proposed solution approach is a large-scale linear program that grows both row- and column-wise when new variables are introduced. Thus, a column-and-row generation algorithm is proposed to solve this linear program optimally, and an optimality condition is presented to terminate the column-and-row generation algorithm. We demonstrate by using Lagrangian duality that this optimality condition is incorrect and may lead to a suboptimal solution at termination.     

An Extended Ant Colony Algorithm and Its Convergence Analysis

In this work, we propose a stochastic algorithm for solving combinatorial optimization problems. The procedure is formulated within the Ant Colony Optimization (ACO) framework, and extends the so-called Graph-based Ant System with time-dependent evaporation factor, (GBAS/tdev) studied in Gutjahr (2002). In particular, we consider an ACO search procedure which also takes into account the objective function value. We provide a rigorous theoretical study on the convergence of the proposed algorithm. Further, for a toy example, we compare by simulation the rate of convergence of the proposed algorithm with those from the Random Search (RS) and from the corresponding procedure in Gutjahr (2002).AMS 2000 Subject Classification: 9OC15, 9OC27     

The <Emphasis Type="Italic">K</Emphasis>th-Best Approach for Linear Bilevel Multi-follower Programming

The majority of research on bilevel programming has centered on the linear version of the problem in which only one leader and one follower are involved. This paper addresses linear bilevel multi-follower programming (BLMFP) problems in which there is no sharing information among followers. It explores the theoretical properties of linear BLMFP, extends the Kth-best approach for solving linear BLMFP problems and gives a computational test for this approach.     

Parallel solvers for the depletion region identification in metal semiconductor field effect transistors

In this work we are interested in a sufficiently accurate approximation of the steady-state potentials in a Metal Semiconductor Field Effect Transistor (MESFET), which can be obtained with the so-called depletion region approximation (see [5]). We propose a robust method based on the shape optimization techniques to analyze and compute the depletion boundary as a function of the applied voltage and the geometry material properties of the device. During the optimization process several intermediate direct problems are solved using the boundary element method (BEM). To accelerate the solutions of of these systems we use a strategy of subdividing the domain into a number of smaller subdomains [11,9]. The scheme is iterative and each subdomain is handled by a separate node in parallel. Test runs comparing the performance of the parallel with the serial code, and other numerical discussions are presented. AMS subject classification 65N55, 65N38, 65K10, 78A55. A. Nachaoui: Corresponding author.     

Objective Function Features Providing Barriers to Rapid Global Optimization

The purposes of this discussion paper are twofold. First, features of an objective function landscape which provide barriers to rapid finding of the global optimum are described. Second, stochastic algorithms are discussed and their performance examined, both theoretically and computationally, as the features change. The paper lays a foundation for the later findings paper.     

Variance reduction in sample approximations of stochastic programs

This paper studies the use of randomized Quasi-Monte Carlo methods (RQMC) in sample approximations of stochastic programs. In numerical integration, RQMC methods often substantially reduce the variance of sample approximations compared to Monte Carlo (MC). It seems thus natural to use RQMC methods in sample approximations of stochastic programs. It is shown, that RQMC methods produce epi-convergent approximations of the original problem. RQMC and MC methods are compared numerically in five different portfolio management models. In the tests, RQMC methods outperform MC sampling substantially reducing the sample variance and bias of optimal values in all the considered problems.     

An Inexact Newton Method Derived from Efficiency Analysis

We consider solving an unconstrained optimization problem by Newton-PCG like methods in which the preconditioned conjugate gradient method is applied to solve the Newton equations. The main question to be investigated is how efficient Newton-PCG like methods can be from theoretical point of view. An algorithmic model with several parameters is established. Furthermore, a lower bound of the efficiency measure of the algorithmic model is derived as a function of the parameters. By maximizing this lower bound function, the parameters are specified and therefore an implementable algorithm is obtained. The efficiency of the implementable algorithm is compared with Newtons method by theoretical analysis and numerical experiments. The results show that this algorithm is competitive.Mathematics Subject Classification: 90C30, 65K05.This work was supported by the National Science Foundation of China Grant No. 10371131, and Hong Kong Competitive Earmarked Research Grant CityU 1066/00P from Hong Kong University Grant Council     

A Revision of the Trapezoidal Branch-and-Bound Algorithm for Linear Sum-of-Ratios Problems

In this paper, we point out a theoretical flaw in Kuno [(2002)Journal of Global Optimization 22, 155–174] which deals with the linear sum-of-ratios problem, and show that the proposed branch-and-bound algorithm works correctly despite the flaw. We also note a relationship between a single ratio and the overestimator used in the bounding operation, and develop a procedure for tightening the upper bound on the optimal value. The procedure is not expensive, but the revised algorithms incorporating it improve significantly in efficiency. This is confirmed by numerical comparisons between the original and revised algorithms. The author was partially supported by the Grand-in-Aid for Scientific Research (C)(2) 15560048 from the Japan Society for the Promotion of Science.     

自反Banach空间中锥线性优化问题初始——对偶目标函数水平集的几何性质

讨论自反Banach空间中的原——对偶锥线性优化问题的目标函数水平集的几何性质．在自反Banach空间中,证明了原目标函数水平集的最大模与对偶目标函数水平集的最大内切球半径几乎是成反比例的．