Robust multi-echelon multi-period inventory control

We consider the problem of minimizing the overall cost of a supply chain, over a possible long horizon, under demand uncertainly which is known only crudely. Under such circumstances, the method of choice is Robust Optimization, in particular the Affinely Adjustable Robust Counterpart (AARC) method which leads to tractable deterministic optimization problems. The latter is due to a recent re-parametrization technique for discrete time linear control systems. In this paper we model, analyze and test an extension of the AARC method known as the Globalized Robust Counterpart (GRC) in order to control inventories in serial supply chains. A simulation study demonstrates the merit of the methods employed here, in particular, it shows that a good control law that minimizes cost achieves simultaneously good control of the bullwhip effect.     

Extending Scope of Robust Optimization: Comprehensive Robust Counterparts of Uncertain Problems

In this paper, we propose a new methodology for handling optimization problems with uncertain data. With the usual Robust Optimization paradigm, one looks for the decisions ensuring a required performance for all realizations of the data from a given bounded uncertainty set, whereas with the proposed approach, we require also a controlled deterioration in performance when the data is outside the uncertainty set. The extension of Robust Optimization methodology developed in this paper opens up new possibilities to solve efficiently multi-stage finite-horizon uncertain optimization problems, in particular, to analyze and to synthesize linear controllers for discrete time dynamical systems. Research was supported by the Binational Science Foundation grant #2002038     

到达不确定呼叫中心人员配置的鲁棒优化模型

针对呼叫中心实际运营中顾客到达不确定的特点,采用鲁棒离散优化方法,建立呼叫中心人员配置的鲁棒模型。利用对偶原理将鲁棒模型转换易于求解的线性鲁棒对等式,通过调节模型中的鲁棒参数来权衡鲁棒解的保守性与最优性之间的关系,计算模型中约束违背概率上限来表示鲁棒解的可靠性。通过现实呼叫中心数据算例,验证了模型的有效性,分析了不同鲁棒水平下各时间段服务人员配置规律,以及系统最小成本与违背概率之间的权衡关系。最后,对到达扰动系数进行了敏感性分析。     

Analyticity on circles for rational and real-analytic functions of two real variables

Conditions for rational and real-analytic functions of two real variables to be holomorphic are given in terms of holomorphic extendibility from families of circles. The first author was supported by the Israel Science Foundation, grant No. 279/02-1. The second author was partially supported by a grant from the Slovenian Ministry of Science and Technology. Both authors were supported by the Ministry of Science of Israel and the Ministry of Science and Technology of Slovenia, in the framework of the Program of Exchange by scientists.     

Complementarity and nondegeneracy in semidefinite programming

Primal and dual nondegeneracy conditions are defined for semidefinite programming. Given the existence of primal and dual solutions, it is shown that primal nondegeneracy implies a unique dual solution and that dual nondegeneracy implies a unique primal solution. The converses hold if strict complementarity is assumed. Primal and dual nondegeneracy assumptions do not imply strict complementarity, as they do in LP. The primal and dual nondegeneracy assumptions imply a range of possible ranks for primal and dual solutionsX andZ. This is in contrast with LP where nondegeneracy assumptions exactly determine the number of variables which are zero. It is shown that primal and dual nondegeneracy and strict complementarity all hold generically. Numerical experiments suggest probability distributions for the ranks ofX andZ which are consistent with the nondegeneracy conditions. Supported in part by the U.S. National Science Foundation grant CCR-9625955. Supported in part by U.S. National Science Foundation grant CCR-9501941 and the U.S. Office of Naval Research grant N00014-96-1-0704. Supported in part by U.S. National Science Foundation grant CCR-9401119.     

On the average performance of the adjustable RO and its use as an offline tool for multi-period production planning under uncertainty

Robust optimization (RO) is a distribution-free worst-case solution methodology designed for uncertain maximization problems via a max-min approach considering a bounded uncertainty set. It yields a feasible solution over this set with a guaranteed worst-case value. As opposed to a previous conception that RO is conservative based on optimal value analysis, we argue that in practice the uncertain parameters rarely take simultaneously the values of the worst-case scenario, and thus introduce a new performance measure based on simulated average values. To this end, we apply the adjustable RO (AARC) to a single new product multi-period production planning problem under an uncertain and bounded demand so as to maximize the total profit. The demand for the product is assumed to follow a typical life-cycle pattern, whose length is typically hard to anticipate. We suggest a novel approach to predict the production plan’s profitable cycle length, already at the outset of the planning horizon. The AARC is an offline method that is employed online and adjusted to past realizations of the demand by a linear decision rule (LDR). We compare it to an alternative offline method, aiming at maximum expected profit, applying the same LDR. Although the AARC maximizes the profit against a worst-case demand scenario, our empirical results show that the average performance of both methods is very similar. Further, AARC consistently guarantees a worst profit over the entire uncertainty set, and its model’s size is considerably smaller and thus exhibit superior performance.     

A simplex based algorithm to solve separated continuous linear programs

We consider the separated continuous linear programming problem with linear data. We characterize the form of its optimal solution, and present an algorithm which solves it in a finite number of steps, using an analog of the simplex method, in the space of bounded measurable functions. Research supported in part by US-Israel BSF grant 9400196, by German-Israel GIF grant I-564-246/06/97 and by Israel Science Foundation Grants 249/02 and 454/05.     

Adjustable Robust Optimization Models for a Nonlinear Two-Period System

We study two-period nonlinear optimization problems whose parameters are uncertain. We assume that uncertain parameters are revealed in stages and model them using the adjustable robust optimization approach. For problems with polytopic uncertainty, we show that quasiconvexity of the optimal value function of certain subproblems is sufficient for the reducibility of the resulting robust optimization problem to a single-level deterministic problem. We relate this sufficient condition to the cone-quasiconvexity of the feasible set mapping for adjustable variables and present several examples and applications satisfying these conditions. This work was partially supported by the National Science Foundation, Grants CCR-9875559 and DMS-0139911, and by Grant-in-Aid for Scientific Research from the Ministry of Education, Sports, Science and Culture of Japan, Grant 16710110.     

需求不确定下应急医疗服务站鲁棒配置模型与算法

大型突发事件发生后需要快速启动应急救灾网络,合理配置应急医疗服务站。本文考虑各应急医疗服务站选址节点需求的不确定性,引入三个不确定水平参数,构建四类不确定需求集合(box, ellipsoid, polyhedron和interval-polyhedron)对应的应急医疗服务站鲁棒配置模型,运用分支-切割算法求解,最后,进行需求扰动比例的灵敏度分析。算例结果表明,四类不确定需求集下的鲁棒配置模型中,ellipsoid不确定需求集合配置模型开放设施较少,总成本最小,鲁棒性较好。决策者还可以根据风险偏好选择不确定水平和需求扰动比例的组合,以使得总成本最小。     

Portfolio selection under distributional uncertainty: A relative robust CVaR approach

Robust optimization, one of the most popular topics in the field of optimization and control since the late 1990s, deals with an optimization problem involving uncertain parameters. In this paper, we consider the relative robust conditional value-at-risk portfolio selection problem where the underlying probability distribution of portfolio return is only known to belong to a certain set. Our approach not only takes into account the worst-case scenarios of the uncertain distribution, but also pays attention to the best possible decision with respect to each realization of the distribution. We also illustrate how to construct a robust portfolio with multiple experts (priors) by solving a sequence of linear programs or a second-order cone program.     

Quadratic programming with one negative eigenvalue is NP-hard

We show that the problem of minimizing a concave quadratic function with one concave direction is NP-hard. This result can be interpreted as an attempt to understand exactly what makes nonconvex quadratic programming problems hard. Sahni in 1974 [8] showed that quadratic programming with a negative definite quadratic term (n negative eigenvalues) is NP-hard, whereas Kozlov, Tarasov and Haijan [2] showed in 1979 that the ellipsoid algorithm solves the convex quadratic problem (no negative eigenvalues) in polynomial time. This report shows that even one negative eigenvalue makes the problem NP-hard.This author's work supported by the Applied Mathematical Sciences Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013. A000 and in part by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS 8920550.     

The Essential Spectrum of Schrödinger, Jacobi, and CMV Operators

We provide a very general result which identifies the essential spectrum of broad classes of operators as exactly equal to the closure of the union of the spectra of suitable limits at infinity. Included is a new result on the essential spectra when potentials are asymptotic to isospectral tori. We also recover within a unified framework the HVZ Theorem and Krein's results on orthogonal polynomials with finite essential spectra. Supported in part by The Israel Science Foundation (grant No. 188/02). Supported in part by NSF grant DMS-01 40592. Research supported in part by grant No. 2002068 from the United States-Israel Binational Science Foundation (BSF), Jerusalem, Israel.     

Robust network design in telecommunications under polytope demand uncertainty

We consider a model for robust network design in telecommunications, in which we minimize the cost of the maximum mismatch between supply and demand. In the present study, the demand is uncertain and takes its values in a polytope defined by constraints. This problem is hardly tractable, so we limit ourselves to computing lower bounds (by a column-generation mechanism) and upper bounds (using an algorithm due to Falk and Soland for maximizing a separable convex function over a polytope). The experimental gap obtained turns out to be large, and this seems to be mainly due to poor upper bounds. Two possible solutions are suggested for further research aimed at improving them: dc optimization (to minimize the difference of two convex functions) and AARC modeling (affinely adjustable robust counterpart).     

CD(4) has bounded width

We prove that the constraint languages invariant under a short sequence of Jónsson terms (containing at most three non-trivial ternary terms) are tractable by showing that they have bounded width. This improves a previous result by Kiss and Valeriote and presents some evidence that the Larose–Zádori conjecture holds in the congruence-distributive case. The first author was supported by EPSRC grant EP/C54384X/1. The second author was supported by the MEC under grant TIN 2006-15387-C03-03, the EU PASCAL Network of Excellence IST-2002-506778, and the MODNET Marie Curie Research Training Network MRTN-CT-2004-512234. The third author was supported by grant no. 144011G of the Ministry of Science and Environment of Serbia. The fourth author was partially supported by the Hungarian National Foundation for Scientific Research (OTKA), grant nos. T 48809 and K 60148.     

Robust optimization and portfolio selection: The cost of robustness

Robust optimization is a tractable alternative to stochastic programming particularly suited for problems in which parameter values are unknown, variable and their distributions are uncertain. We evaluate the cost of robustness for the robust counterpart to the maximum return portfolio optimization problem. The uncertainty of asset returns is modelled by polyhedral uncertainty sets as opposed to the earlier proposed ellipsoidal sets. We derive the robust model from a min-regret perspective and examine the properties of robust models with respect to portfolio composition. We investigate the effect of different definitions of the bounds on the uncertainty sets and show that robust models yield well diversified portfolios, in terms of the number of assets and asset weights.     

The principal pivoting method revisited

The principal pivoting method (PPM) for the linear complementarity problem (LCP) is shown to be applicable to the class of LCPs involving the newly identified class of sufficient matrices.Research partially supported by the National Science Foundation grant DMS-8800589, U.S. Department of Energy grant DE-FG03-87ER25028 and Office of Naval Research grant N00014-89-J-1659.Dedicated to George B. Dantzig on the occasion of his 75th birthday.     

Min-Max Regret Robust Optimization Approach on Interval Data Uncertainty

This paper presents a three-stage optimization algorithm for solving two-stage deviation robust decision making problems under uncertainty. The structure of the first-stage problem is a mixed integer linear program and the structure of the second-stage problem is a linear program. Each uncertain model parameter can independently take its value from a real compact interval with unknown probability distribution. The algorithm coordinates three mathematical programming formulations to iteratively solve the overall problem. This paper provides the application of the algorithm on the robust facility location problem and a counterexample illustrating the insufficiency of the solution obtained by considering only a finite number of scenarios generated by the endpoints of all intervals. This work was supported by the National Science Foundation through Grant DMI-0200162.     

一类分布鲁棒线性决策随机优化研究

随机优化广泛应用于经济、管理、工程和国防等领域,分布鲁棒优化作为解决分布信息模糊下的随机优化问题近年来成为学术界的研究热点.本文基于φ-散度不确定集和线性决策方式研究一类分布鲁棒随机优化的建模与计算,构建了易于计算实现的分布鲁棒随机优化的上界和下界问题.数值算例验证了模型分析的有效性.     

A note on issues of over-conservatism in robust optimization with cost uncertainty

We identify and discuss issues of hidden over-conservatism in robust linear optimization, when the uncertainty set is polyhedral with a budget of uncertainty constraint. The decision-maker selects the budget of uncertainty to reflect his degree of risk aversion, i.e. the maximum number of uncertain parameters that can take their worst-case value. In the first setting, the cost coefficients of the linear programming problem are uncertain, as is the case in portfolio management with random stock returns. We provide an example where, for moderate values of the budget, the optimal solution becomes independent of the nominal values of the parameters, i.e. is completely disconnected from its nominal counterpart, and discuss why this happens. The second setting focusses on linear optimization with uncertain upper bounds on the decision variables, which has applications in revenue management with uncertain demand and can be rewritten as a piecewise linear problem with cost uncertainty. We show in an example that it is possible to have more demand parameters equal their worst-case value than what is allowed by the budget of uncertainty, although the robust formulation is correct. We explain this apparent paradox.     

Sample-path optimization of convex stochastic performance functions

In this paper we propose a method for optimizing convex performance functions in stochastic systems. These functions can include expected performance in static systems and steady-state performance in discrete-event dynamic systems; they may be nonsmooth. The method is closely related to retrospective simulation optimization; it appears to overcome some limitations of stochastic approximation, which is often applied to such problems. We explain the method and give computational results for two classes of problems: tandem production lines with up to 50 machines, and stochastic PERT (Program Evaluation and Review Technique) problems with up to 70 nodes and 110 arcs. Sponsored by the National Science Foundation under grant number CCR-9109345, by the Air Force Systems Command, USAF, under grant numbers F49620-93-1-0068 and F49620-95-1-0222, by the U.S. Army Research Office under grant number DAAL03-92-G-0408, and by the U.S. Army Space and Strategic Defense Command under contract number DASG60-91-C-0144. The U.S. Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. Sponsored by a Wisconsin/Hilldale Research Award, by the U.S. Army Space and Strategic Defense Command under contract number DASG60-91-C-0144, and the Air Force Systems Command, USAF, under grant number F49620-93-1-0068. Sponsored by the National Science Foundation under grant number DDM-9201813.