Optimal empty vehicle repositioning and fleet-sizing for two-depot service systems

This paper considers the problem of determining optimal control policies for empty vehicle repositioning and fleet-sizing in a two-depot service system with uncertainties in loaded vehicle arrival at depots and repositioning times for empty vehicles in the fleet. The objective is to minimise the sum of the costs incurred by vehicle maintenance, empty vehicle repositioning and vehicle leasing. A novel integrated model is presented. The optimal empty repositioning policy for a particular fleet size is shown to be of the threshold control type. The explicit form of the cost function under such threshold controls is obtained. The optimal threshold values and fleet-size are then derived. Numerical examples are given to demonstrate the results.     

Supply chain design under uncertainty using sample average approximation and dual decomposition

We present a supply chain design problem modeled as a sequence of splitting and combining processes. We formulate the problem as a two-stage stochastic program. The first-stage decisions are strategic location decisions, whereas the second stage consists of operational decisions. The objective is to minimize the sum of investment costs and expected costs of operating the supply chain. In particular the model emphasizes the importance of operational flexibility when making strategic decisions. For that reason short-term uncertainty is considered as well as long-term uncertainty. The real-world case used to illustrate the model is from the Norwegian meat industry. We solve the problem by sample average approximation in combination with dual decomposition. Computational results are presented for different sample sizes and different levels of data aggregation in the second stage.     

Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications

Inspired by a recent work by Alexander et al. (J Bank Finance 30:583–605, 2006) which proposes a smoothing method to deal with nonsmoothness in a conditional value-at-risk problem, we consider a smoothing scheme for a general class of nonsmooth stochastic problems. Assuming that a smoothed problem is solved by a sample average approximation method, we investigate the convergence of stationary points of the smoothed sample average approximation problem as sample size increases and show that w.p.1 accumulation points of the stationary points of the approximation problem are weak stationary points of their counterparts of the true problem. Moreover, under some metric regularity conditions, we obtain an error bound on approximate stationary points. The convergence result is applied to a conditional value-at-risk problem and an inventory control problem.      

Logarithmic sample bounds for Sample Average Approximation with capacity- or budget-constraints

Sample Average Approximation (SAA) is used to approximately solve stochastic optimization problems. In practice, SAA requires much fewer samples than predicted by existing theoretical bounds that ensure the SAA solution is close to optimal. Here, we derive new sample-size bounds for SAA that, for certain problems, are logarithmic (existing bounds are polynomial) in problem dimension. Notably, our new bounds provide a theoretical explanation for the success of SAA for many capacity- or budget-constrained optimization problems.     

Sample average approximation of expected value constrained stochastic programs

We propose a sample average approximation (SAA) method for stochastic programming problems with expected value constraints. Such problems arise, for example, in portfolio selection with constraints on conditional value-at-risk (CVaR). We provide a convergence analysis and a statistical validation scheme for the proposed method.     

Stochastic mathematical programs with equilibrium constraints,modelling and sample average approximation

In this article, we discuss the sample average approximation (SAA) method applied to a class of stochastic mathematical programs with variational (equilibrium) constraints. To this end, we briefly investigate the structure of both–the lower level equilibrium solution and objective integrand. We show almost sure convergence of optimal values, optimal solutions (both local and global) and generalized Karush–Kuhn–Tucker points of the SAA program to their true counterparts. We also study uniform exponential convergence of the sample average approximations, and as a consequence derive estimates of the sample size required to solve the true problem with a given accuracy. Finally, we present some preliminary numerical test results.     

Short-term liner ship fleet planning with container transshipment and uncertain container shipment demand

This paper proposes a short-term liner ship fleet planning problem by taking into account container transshipment and uncertain container shipment demand. Given a liner shipping service network comprising a number of ship routes, the problem is to determine the numbers and types of ships required in the fleet and assign each of these ships to a particular ship route to maximize the expected value of the total profit over a short-term planning horizon. These decisions have to be made prior to knowing the exact container shipment demand, which is affected by some unpredictable and uncontrollable factors. This paper thus formulates this realistic short-term planning problem as a two-stage stochastic integer programming model. A solution algorithm, integrating the sample average approximation with a dual decomposition and Lagrangian relaxation approach, is then proposed. Finally, a numerical example is used to evaluate the performance of the proposed model and solution algorithm.     

Accelerated sample average approximation method for two-stage stochastic programming with binary first-stage variables

This paper proposes an accelerated solution method to solve two-stage stochastic programming problems with binary variables in the first stage and continuous variables in the second stage. To develop the solution method, an accelerated sample average approximation approach is combined with an accelerated Benders’ decomposition algorithm. The accelerated sample average approximation approach improves the main structure of the original technique through the reduction in the number of mixed integer programming problems that need to be solved. Furthermore, the recently accelerated Benders’ decomposition approach is utilized to expedite the solution time of the mixed integer programming problems. In order to examine the performance of the proposed solution method, the computational experiments are performed on developed stochastic supply chain network design problems. The computational results show that the accelerated solution method solves these problems efficiently. The synergy of the two accelerated approaches improves the computational procedure by an average factor of over 42%, and over 12% in comparison with the original and the recently modified methods, respectively. Moreover, the betterment of the computational process increases substantially with the size of the problem.     

Capacity allocation problem with random demands for the rail container carrier

In this paper, we consider the formulation and heuristic algorithm for the capacity allocation problem with random demands in the rail container transportation. The problem is formulated as the stochastic integer programming model taking into account matches in supply and demand of rail container transportation. A heuristic algorithm for the stochastic integer programming model is proposed. The solution to the model is found by maximizing the expected total profit over the possible control decisions under the uncertainty of demands. Finally, we give numerical experiments to demonstrate the efficiency of the heuristic algorithm.     

A note on the sample average approximation method for stochastic mathematical programs with complementarity constraints

Meng and Xu (2006) [3] proposed a sample average approximation (SAA) method for solving a class of stochastic mathematical programs with complementarity constraints (SMPCCs). After showing that under some moderate conditions, a sequence of weak stationary points of SAA problems converge to a weak stationary point of the original SMPCC with probability approaching one at exponential rate as the sample size tends to infinity, the authors proposed an open question, that is, whether similar results can be obtained under some relatively weaker conditions. In this paper, we try to answer the open question. Based on the reformulation of stationary condition of MPCCs and new stability results on generalized equations, we present a similar convergence theory without any information of second order derivative and strict complementarity conditions. Moreover, we carry out convergence analysis of the regularized SAA method proposed by Meng and Xu (2006) [3] where the convergence results have not been considered.     

插值多项式在一重积分Wiener空间下的同时逼近平均误差

本文在加权L_p范数逼近意义下确定了基于第一类Chebyshev 结点组的Lagrange 插值多项式列在一重积分Wiener 空间下同时逼近平均误差的渐近阶. 结果显示在L_p范数逼近意义下Lagrange 插值多项式列的平均误差弱等价于相应的最佳逼近多项式列的平均误差. 同时, 当2≤p≤4 时,Lagrange 插值多项式列导数逼近的平均误差弱等价于相应的导数最佳逼近多项式列的平均误差. 作为对比, 本文也确定了相应的Hermite-Fejér 插值多项式列在一重积分Wiener空间下逼近的平均误差的渐近阶.     

A novel method for computing the Hilbert transform with Haar multiresolution approximation

In this paper, an algorithm for computing the Hilbert transform based on the Haar multiresolution approximation is proposed and the L²$L^2$-error is estimated. Experimental results show that it outperforms the library function ‘hilbert’ in Matlab (The MathWorks, Inc. 1994–2007). Finally it is applied to compute the instantaneous phase of signals approximately and is compared with three existing methods.     

The modified method of refined bounds for polyhedral approximation of convex polytopes

The modified method of refined bounds is proposed and experimentally studied. This method is designed to iteratively approximate convex multidimensional polytopes with a large number of vertices. Approximation is realized by a sequence of convex polytopes with a relatively small but gradually increasing number of vertices. The results of an experimental comparison between the modified and the original methods of refined bounds are presented. The latter was designed for the polyhedral approximation of multidimensional convex compact bodies of general type.     

A successive convex approximation method for multistage workforce capacity planning problem with turnover

Workforce capacity planning in human resource management is a critical and essential component of the services supply chain management. In this paper, we consider the planning problem of transferring, hiring, or firing employees among different departments or branches of an organization under an environment of uncertain workforce demands and turnover, with the objective of minimizing the expected cost over a finite planning horizon. We model the problem as a multistage stochastic program and propose a successive convex approximation method which solves the problem in stages and iteratively. An advantage of the method is that it can handle problems of large size where normally solving the problems by equivalent deterministic linear programs is considered to be computationally infeasible. Numerical experiments indicate that solutions obtained by the proposed method have expected costs near optimal.     

The use of the linear sampling method for obtaining super-resolution effects in Born approximation

A two-step reconstruction scheme is introduced to solve fixed frequency inverse scattering problems in Born approximation conditions. The aim of the approach is to achieve super-resolution effects by constraining the inversion method to exploit some a priori knowledge on the scatterer. Therefore, the first step is to apply the linear sampling method to the far-field data in order to obtain an estimate of the support of the inhomogeneity. The second step is to apply the projected Landweber method to the linearized scattering equation in order to obtain super-resolution effects via out-of-band extrapolation. The effectiveness of the approach, which has a rather wide applicability power, is tested in the case of a two-dimensional problem for some scatterers of simple geometry.     

The semi-analytical method for time-dependent wave problems with uncertainties

This paper provides a constructive procedure for the computation of approximate solutions of random time-dependent hyperbolic mean square partial differential problems. Based on the theoretical representation of the solution as an infinite random improper integral, obtained via the random Fourier transform method, a double approximation process is implemented. Firstly, a random Gauss-Hermite quadrature is applied, and then, the evaluations at the nodes of the integrand are approximated by using a random Störmer numerical method. Numerical results are illustrated with examples.     

A method of stochastic subgradients with complete feedback stepsize rule for convex stochastic approximation problems

A stochastic subgradient algorithm for solving convex stochastic approximation problems is considered. In the algorithm, the stepsize coefficients are controlled on-line on the basis of information gathered in the course of computations according to a new, complete feedback rule derived from the concept of regularized improvement function. Convergence with probability 1 of the method is established.This work was supported by Project No. CPBP/02.15.     

The method of p-harmonic approximation and optimal interior partial regularity for energy minimizing p-harmonic maps under the controllable growth condition

In this paper, we are concerned with the partial regularity for the weak solutions of energy minimizing p-harmonic maps under the controllable growth condition. We get the interior partial regularity by the p-harmonic approximation method together with the technique used to get the decay estimation on some Degenerate elliptic equations and the obstacle problem by Tan and Yan. In particular, we directly get the optimal regularity.