Staffing call centers under arrival-rate uncertainty with Bayesian updates

We consider the problem of staffing service centers with quality-of-service constraints. We focus on the case where the arrival rates are uncertain. We introduce formulations that handle staffing decisions made over two decision periods, minimizing the staffing costs over the stages while satisfying a service quality constraint on the second stage operation. A Bayesian update is used to obtain the second-stage arrival-rate distribution based on the first stage prior arrival-rate distribution and the observations in the first stage.     

Robust linear optimization under general norms

We explicitly characterize the robust counterpart of a linear programming problem with uncertainty set described by an arbitrary norm. Our approach encompasses several approaches from the literature and provides guarantees for constraint violation under probabilistic models that allow arbitrary dependencies in the distribution of the uncertain coefficients.     

On the interaction between retrials and sizing of call centers

This paper models a call center as a Markovian queue with multiple servers, where customer impatience, and retrials are modeled explicitly. The model is analyzed as a continuous time Markov chain. The retrial phenomenon is explored numerically using a real example, to demonstrate the magnitude it can take and to understand its sensitivity to various system parameters. The model is then used to assess the impact of disregarding existing retrials in the staffing of a call center. It is shown that ignoring retrials can lead to under-staffing or over-staffing with respect to the optimal, depending on the forecasting assumptions being made.     

Robust economic order quantity models

In this paper, we study the classical economic order quantity (EOQ) model under significant. In particular, the problem under consideration is the economic order quantity model with the input data of the demand rate, the order cost, and the holding cost rate being uncertain. A robustness approach based on scenario characterization of the input data is adopted to describe the uncertainties. The aim of the approach is to find an inventory policy that performs well under all realizable input data scenarios. An efficient linear time algorithm is devised to find the robust decisions. Analytical results are obtained for the case where input data are defined in continuous intervals. Comparisons on performances between the robust decisions and the stochastic optimization decisions are conducted. The results demonstrate the advantages of robustness approach.     

On the convergence of the method of analytic centers when applied to convex quadratic programs

This work examines the method of analytic centers of Sonnevend when applied to solve generalized convex quadratic programs — where also the constraints are given by convex quadratic functions. We establish the existence of a two-sided ellipsoidal approximation for the set of feasible points around its center and show, that a simple (zero order) algorithm starting from an initial center of the feasible set generates a sequence of strictly feasible points whose objective function values converge to the optimal value. Concerning the speed of convergence it is shown that an upper bound for the gap in between the objective function value and the optimal value is reduced by a factor of with iterations wherem is the number of inequality constraints. Here, each iteration involves the computation of one Newton step. The bound of Newton iterations to guarantee an error reduction by a factor of in the objective function is as good as the one currently given forlinear programs. However, the algorithm considered here is of theoretical interest only, full efficiency of the method can only be obtained when accelerating it by some (higher order) extrapolation scheme, see e.g. the work of Jarre, Sonnevend and Stoer.This work was supported by the Deutsche Forschungsgemeinschaft, Schwerpunktprogramm für anwendungsbezogene Optimierung und Steuerung.     

LMI Approach to Robust Model Predictive Control

This paper introduces a new approach to robust model predictive control (MPC) based on conservative approximations to semi-infinite optimization using linear matrix inequalities (LMIs). The method applies to problems with convex quadratic costs, linear and convex quadratic constraints, and linear predictive models with bounded uncertainty. If the MPC optimization problem is feasible at the initial control step (the first application of the MPC optimization), it is shown that the MPC optimization problems will be feasible at all future time steps and that the controlled system will be closed-loop stable. The method is illustrated with a solenoid control example. The authors thank the anonymous reviewers for suggestions that improved the presentation of this work. The work was supported in part by the EPRI/DoD Complex Interactive Networks/Systems Initiative under Contract EPRI-W08333-05 and by the US Army Research Office Contract DAAD19-01-1-0485.     

Multipolar routing: where dynamic and static routing meet

Assuming that the traffic matrix belongs to a polytope, we describe a new routing paradigm where each traffic matrix is routed a combination of a number of extreme routings. This combination depends on the current traffic matrix. Multipolar routing can be seen as a generalization of both routing and robust static routing. Moreover, the time complexity of multipolar routing is under control since it depends on the number of poles (i.e. the number of extreme routings) which can be defined by the network planner     

Robust optimization for interactive multiobjective programming with imprecise information applied to R&D project portfolio selection

A multiobjective binary integer programming model for R&D project portfolio selection with competing objectives is developed when problem coefficients in both objective functions and constraints are uncertain. Robust optimization is used in dealing with uncertainty while an interactive procedure is used in making tradeoffs among the multiple objectives. Robust nondominated solutions are generated by solving the linearized counterpart of the robust augmented weighted Tchebycheff programs. A decision maker’s most preferred solution is identified in the interactive robust weighted Tchebycheff procedure by progressively eliciting and incorporating the decision maker’s preference information into the solution process. An example is presented to illustrate the solution approach and performance. The developed approach can also be applied to general multiobjective mixed integer programming problems.     

Robust output feedback sliding mode control for uncertain discrete time systems

This paper proposes a robust output feedback controller for a class of uncertain discrete-time, multi-input multi-output, linear, systems. This method, which is based on the combination of discrete-time sliding mode control (DTSMC) and Kalman estimator, ensures the stability, robustness and an output tracking against the modeling uncertainties at large sampling periods. For this purpose, an appropriate structure is considered for sliding surface and the Lyapunov theory for the mismatched uncertain system is then used to design its parameter. This problem leads to solve a set of linear matrix inequalities. A new method is then proposed to reach the quasi-sliding mode and stay thereafter. Simulation studies show the effectiveness of the proposed method in the presence of parameter uncertainties and external disturbances at large sampling periods.     

A cone programming approach to the bilinear matrix inequality problem and its geometry

We discuss an approach for solving the Bilinear Matrix Inequality (BMI) based on its connections with certain problems defined over matrix cones. These problems are, among others, the cone generalization of the linear programming (LP) and the linear complementarity problem (LCP) (referred to as the Cone-LP and the Cone-LCP, respectively). Specifically, we show that solving a given BMI is equivalent to examining the solution set of a suitably constructed Cone-LP or Cone-LCP. This approach facilitates our understanding of the geometry of the BMI and opens up new avenues for the development of the computational procedures for its solution. Research supported in part by the National Science Foundation under Grant CCR-9222734.     

Robust Stabilization of Linear Systems with Delayed State and Control

Robust stabilization of linear systems with delays on both the state and control input is studied in this paper. Using an improved Lyapunov-Krasovskii functional, we establish new criteria that ensure the robust stability of the closed-loop system with memoryless state feedback controls. The generalized conditions are derived in terms of linear matrix inequalities (LMIs), allowing us to compute simultaneously the two bounds that characterize the exponential stability rate of the solution and can be easily solved by numerical algorithms. This work was supported by the National Basic Program in Natural Sciences. The authors thank the anonymous referees for valuable comments to improve the paper.     

工件具有任意尺寸的混合分批平行机排序问题的近似算法

本文考虑了工件具有任意尺寸且机器有容量限制的混合分批平行机排序问题。在该问题中, 一个待加工的工件集需在多台平行批处理机上进行加工。每个工件有它的加工时间和尺寸, 每台机器可以同时处理多个工件, 称为一个批, 只要这些工件尺寸之和不超过其容量; 一个批的加工时间等于该批中工件的最大加工时间和总加工时间的加权和; 目标函数是极小化最大完工时间。该问题包含一维装箱问题为其特殊情形, 为强NP-困难的。对此给出了一个$\left( {2 + 2\alpha+\alpha^{2}}\right)$-近似算法, 其中$\alpha$为给定的权重参数, 满足考虑了不同于Goldfarb和Iyengar （2003）的因子模型,通过横截面回归分析以及Fama-MacBeth估计构造了关于资产的平均收益向量和协方差矩阵的不确定性集合（置信区域）。基于这些不确定性集合以及Markowitz“均值-方差模型”的鲁棒投资组合问题,提出了多个鲁棒投资组合问题,并对应的推导出其等价的半正定规划形式,使得问题可以在多项式时间内求解。     

Adaptive and robust radiation therapy optimization for lung cancer

A previous approach to robust intensity-modulated radiation therapy (IMRT) treatment planning for moving tumors in the lung involves solving a single planning problem before the start of treatment and using the resulting solution in all of the subsequent treatment sessions. In this paper, we develop an adaptive robust optimization approach to IMRT treatment planning for lung cancer, where information gathered in prior treatment sessions is used to update the uncertainty set and guide the reoptimization of the treatment for the next session. Such an approach allows for the estimate of the uncertain effect to improve as the treatment goes on and represents a generalization of existing robust optimization and adaptive radiation therapy methodologies. Our method is computationally tractable, as it involves solving a sequence of linear optimization problems. We present computational results for a lung cancer patient case and show that using our adaptive robust method, it is possible to attain an improvement over the traditional robust approach in both tumor coverage and organ sparing simultaneously. We also prove that under certain conditions our adaptive robust method is asymptotically optimal, which provides insight into the performance observed in our computational study. The essence of our method – solving a sequence of single-stage robust optimization problems, with the uncertainty set updated each time – can potentially be applied to other problems that involve multi-stage decisions to be made under uncertainty.     

Vehicle routing with multiple deliverymen: Modeling and heuristic approaches for the VRPTW

In real life distribution of goods, relatively long service times may make it difficult to serve all requests during regular working hours. These difficulties are even greater if the beginning of the service in each demand site must occur within a time window and violations of routing time restrictions are particularly undesirable. We address this situation by considering a variant of the vehicle routing problem with time windows for which, besides routing and scheduling decisions, a number of extra deliverymen can be assigned to each route in order to reduce service times. This problem appears, for example, in the distribution of beverage and tobacco in highly dense Brazilian urban areas. We present a mathematical programming formulation for the problem, as well as a tabu search and an ant colony optimization heuristics for obtaining minimum cost routes. The performance of the model and the heuristic approaches are evaluated using instances generated from a set of classic examples from the literature.     

稳健资产负债管理最优化模型及实证分析

本文提出一种新的稳健资产负债模型最优化模型.该模型考虑了利率的不确定性对未来现金流、资金成本和资产收益率的影响.我们通过构建情景树反映未来的利率变化的情景结构.由于最优决策对利率的预测十分敏感,我们提出系数预测值可在一定误差范围内的稳健资产负债最优化模型.实证分析结果表明,从收益与风险均衡的角度看,稳健优化模型产生的保守解优于系数确定的优化模型产生的最优解.     

数据处理服务外包企业多层复合技能人力资源调配问题研究

服务外包是推进我国产业结构调整的重要方式。数据处理作为服务外包中基础业务之一,对人力依赖程度很高。企业只有合理有效安排员工生产才能及时处理并以低成本交付订单。文章以数据处理业务为研究背景,考虑订单加工整个流程和员工技能种类,建立两步多层复合技能人力调配分段模型。选取实地调研企业数据运用模型进行求解。结果表明了模型的有效性,对于有效提升企业接包能力,促进我国服务外包发展有重要意义。     

Robust weighted vertex p-center model considering uncertain data: An application to emergency management

This paper presents a generalized weighted vertex p-center (WVPC) model that represents uncertain nodal weights and edge lengths using prescribed intervals or ranges. The objective of the robust WVPC (RWVPC) model is to locate p facilities on a given set of candidate sites so as to minimize worst-case deviation in maximum weighted distance from the optimal solution. The RWVPC model is well-suited for locating urgent relief distribution centers (URDCs) in an emergency logistics system responding to quick-onset natural disasters in which precise estimates of relief demands from affected areas and travel times between URDCs and affected areas are not available. To reduce the computational complexity of solving the model, this work proposes a theorem that facilitates identification of the worst-case scenario for a given set of facility locations. Since the problem is NP-hard, a heuristic framework is developed to efficiently obtain robust solutions. Then, a specific implementation of the framework, based on simulated annealing, is developed to conduct numerical experiments. Experimental results show that the proposed heuristic is effective and efficient in obtaining robust solutions. We also examine the impact of the degree of data uncertainty on the selected performance measures and the tradeoff between solution quality and robustness. Additionally, this work applies the proposed RWVPC model to a real-world instance based on a massive earthquake that hit central Taiwan on September 21, 1999.     

Decomposition based and branch and bound global optimization approaches for the phase equilibrium problem

An increasingly popular approach when solving the phase and chemical equilibrium problem is to pose it as an optimization problem. However, difficulties are encountered due to the highly nonlinear nature of the models used to represent the behavior of the fluids, and because of the existence of multiple local solutions. This work shows how it is possible to guarantee -global solutions for a certain important class of the phase and chemical equilibrium problem, namely when the liquid phase can be modeled using neither the Non-Random Two-Liquid (NRTL) equation, or the UNIversal QUAsi Chemical (UNIQUAC) equation. Ideal vapor phases are easily incorporated into the global optimization framework. A numberof interesting properties are described which drastically alter the structure of the respective problems. For the NRTL equation, it is shown that the formulation can be converted into a biconvex optimization problem. The GOP algorithm of Floudas and Visweswaran [8, 9] can then be used to obtain -global solutions in this case. For the UNIQUAC equation, the new properties show how the objective function can be transformed into the difference of two convex functions (i.e. a D.C. programming problem is obtained), where the concave portion is separable. A branch and bound algorithm based on that of Falk and Soland [6] is used to guarantee convergence to an -global solution. Examples are presented which demonstrate the performance of both algorithms.     

Quantitative Robust Uncertainty Principles and Optimally Sparse Decompositions

In this paper we develop a robust uncertainty principle for finite signals in which states that, for nearly all choices such that

Robust optimization – methodology and applications

Robust Optimization (RO) is a modeling methodology, combined with computational tools, to process optimization problems in which the data are uncertain and is only known to belong to some uncertainty set. The paper surveys the main results of RO as applied to uncertain linear, conic quadratic and semidefinite programming. For these cases, computationally tractable robust counterparts of uncertain problems are explicitly obtained, or good approximations of these counterparts are proposed, making RO a useful tool for real-world applications. We discuss some of these applications, specifically: antenna design, truss topology design and stability analysis/synthesis in uncertain dynamic systems. We also describe a case study of 90 LPs from the NETLIB collection. The study reveals that the feasibility properties of the usual solutions of real world LPs can be severely affected by small perturbations of the data and that the RO methodology can be successfully used to overcome this phenomenon. Received: May 24, 2000 / Accepted: September 12, 2001?Published online February 14, 2002