An Efficient Substitution Method for Sparse Min-Max Problems Arising in Call Centers

摘要

The staffing and scheduling problems in call centers are often transferred into minimax problems with a finite number of functions whose Hessian matrices are often sparse, i.e., there are many zero-elements in these matrices. In this paper We present an efficient substitution algorithm for solving it. This method combines a secant method with a finite difference method and employs the sparsity of the Hessian matrices to reduce the gradient evaluations as efficiently as possible in forming quadratic approximations to the functions. By this technique we can reduce the number of gradient evaluations required by the substitution method by m, the number of functions, at every iteration. Without strict complementarity, local and global convergence is proven and q-superlinear convergence results and r-convergence rate estimates show that the method has a good convergence property. Our numerical tests show that the algorithm is robust and quite effective, and that its performance is comparable to or better than that of other algorithms available.