Search

Kusuoka representations provide an important and useful characterization of law invariant coherent risk measures in atomless probability spaces. However, the applicability of these results is limited by the fact that such representations do not always exist in probability spaces with atoms, such as finite probability spaces. We introduce the class of functionally coherent risk measures, which allow us to use Kusuoka representations in any probability space. We show that this class contains every law invariant risk measure that can be coherently extended to a family containing all finite discrete distributions. Thus, it is possible to preserve the desirable properties of law invariant coherent risk measures on atomless spaces without sacrificing generality. We also specialize our results to risk measures on finite probability spaces, and prove a denseness result about the family of risk measures with finite Kusuoka representations.

In this paper we examine the various effects that workstations and repair loops with identical parallel processors and stochastic processing times have on the performance of a mixed-model assembly line. Of particular interest are issues related to sequence scrambling. In many production systems (especially those operating on just-in-time or in-line vehicle sequencing principles), the sequence of orders is selected carefully to optimize line efficiency while taking into account various line balancing and product spacing constraints. However, this sequence is often altered due to stochastic factors during production. This leads to significant economic consequences, due to either the degraded performance of the assembly line, or the added cost of restoring the sequence (via the use of systems such as mix banks or automated storage and retrieval systems). We develop analytical formulas to quantify both the extent of sequence scrambling caused by a station of the assembly line, and the effects of this scrambling on downstream performance. We also develop a detailed Markov chain model to analyze related issues regarding line stoppages and throughput. We demonstrate the usefulness of our methods on a range of illustrative numerical examples, and discuss the implications from a managerial point of view.

In this paper, we consider the joint overbooking and capacity control problem over a single flight leg with multiple fare classes. The objective is to maximize the expected profit, which is given by the difference between the expected revenue from the accepted requests and the expected penalty cost from the denied reservations. We study a class of open loop policies that accept the requests for each fare class with a fixed acceptance probability. In this case, the challenge becomes that of finding a set of acceptance probabilities that maximize the expected profit. We derive a simple expression that can be used to compute the optimal acceptance probabilities, despite the fact that the problem of finding the optimal acceptance probabilities is a high dimensional optimization problem. We show that the optimal acceptance probabilities randomize the acceptance decisions for at most one fare class, indicating that the randomized nature of our open loop policies is not a huge practical concern. We bound the performance loss of our open loop policies when compared with the optimal policy. Computational experiments demonstrate that open loop policies perform remarkably well, providing expected pro¯ts within two percent of the optimal expected profits on average.

The vast majority of the machine scheduling literature focuses on deterministic problems, in which all data is known with certainty a priori. This may be a reasonable assumption when the variability in the problem parameters is low. However, as variability in the parameters increases incorporating this uncertainty explicitly into a scheduling model is essential to mitigate the resulting adverse effects. In this paper, we consider the celebrated single-machine total weighted tardiness (TWT) problem in the presence of uncertain problem parameters. We impose a probabilistic constraint on the random TWT and introduce a risk-averse stochastic programming model. In particular, the objective of the proposed model is to find a non-preemptive static job processing sequence that minimizes the value-at-risk (VaR) measure on the random TWT at a specified confidence level. Furthermore, we develop a lower bound on the optimal VaR that may also benefit alternate solution approaches in the future. In this study, we implement a tabu-search heuristic to obtain reasonably good feasible solutions and present results to demonstrate the effect of the risk parameter and the value of the proposed model with respect to a corresponding risk-neutral approach.

Traditional two-stage stochastic programming is risk-neutral; that is, it considers the expectation as the preference criterion while comparing the random variables (e.g., total cost) to identify the best decisions. However, in the presence of variability risk measures should be incorporated into decision making problems in order to model its effects. In this study, we consider a risk-averse two-stage stochastic programming model, where we specify the conditional-value-at-risk (CVaR) as the risk measure. We construct two decomposition algorithms based on the generic Benders-decomposition approach to solve such problems. Both single-cut and multicut versions of the proposed decomposition algorithms are presented. We apply the proposed framework to disaster management, which is one of the research fields that can significantly benefit from risk-averse two-stage stochastic programming models. In particular, we consider the problem of determining the response facility locations and the inventory levels of the relief supplies at each facility in the presence of uncertainty in demand and the damage level of the disaster network. We present numerical results to discuss how incorporating a risk measure affects the optimal solutions and to demonstrate the computational efficiency of the proposed methods.

Airline revenue management (ARM) problem focuses on ¯nding a seat allocation policy, that would result in the maximum pro¯t. Overbooking has been receiving signi¯cant attention in ARM over the years, since a major loss in revenue results from cancellations and no-shows. In this study, we propose new models for static and dynamic single-leg overbooking problems. In the static case, we introduce models that give upper and lower bounds for the optimal expected pro¯t. In the dynamic case, we propose a new dynamic programming model, which is based on two streams of arrivals, booking and cancellation. We also present numerical results to show the validity of our models.

For a proper cone K ⊂ Rn and its dual cone K the complementary slackness condition xT s = 0 defines an n-dimensional manifold C(K) in the space { (x, s) | x ∈ K, s ∈ K^* }. When K is a symmetric cone, this manifold can be described by a set of n bilinear equalities. When K is a symmetric cone, this fact translates to a set of n linearly independent bilinear identities (optimality conditions) satisfied by every (x, s) ∈ C(K). This proves to be very useful when optimizing over such cones, therefore it is natural to look for similar optimality conditions for non-symmetric cones. In this paper we define the bilinearity rank of a cone, which is the number of linearly independent bilinear identities valid for the cone, and describe a linear algebraic technique to bound this quantity. We examine several well-known cones, in particular the cone of positive polynomials P2n+1 and its dual, the closure of the moment cone M2n+1, and compute their bilinearity ranks. We show that there are exactly four linearly independent bilinear identities which hold for all (x,s) ∈ C(P2n+1), regardless of the dimension of the cones. For nonnegative polynomials over an interval or half-line there are only two linearly independent bilinear identities. These results are extended to trigonometric and exponential polynomials.

The stochastic nature of emergency service requests and the unavailability of emergency vehicles (ambulances) when requested to serve demands are critical issues in constructing valid models representing real life emergency medical service (EMS) systems. Such stochastic emergency facility location models has received significant attention in the last decades. In this paper, the EMS system design problem involves decisions on where each emergency response facility (ambulance station) should be located and how many vehicles should be assigned to each facility. Unlike the existing models in the literature, we locate the facilities and decide on their capacities in such a way as to ensure a reliable level of coverage, which is quantified using risk measures on random total unmet demand. We specify reliability levels of service for each demand site and also for the entire service area. We develop two stochastic optimization models under demand uncertainty; the first one includes integrated chance constraints (ICCs), whereas the second one incorporates ICCs and a second order dominance constraint. We propose solution methods for our stochastic optimization problems and present extensive numerical results demonstrating their computational eectiveness.

Several approaches exist to model decision making under risk, where risk can be broadly defined as the effect of variability of random outcomes. One of the main approaches in the practice of decision making under risk uses mean-risk models; one such well-known is the classical Markowitz model, where variance is used as risk measure. Along this line, we consider a portfolio selection problem, where the asset returns have an elliptical distribution. We mainly focus on portfolio optimization models constructing portfolios with minimal risk, provided that a prescribed expected return level is attained. In particular, we model the risk by using Value-at- Risk (VaR) and Conditional Value-at-Risk (CVaR). After reviewing the main properties of VaR and CVaR, we present short proofs to some of the well-known results. Finally, we describe a computationally efficient solution algorithm and present numerical results. Keywords: Elliptical distributions; mean-risk; value-at-risk; conditional value-at-risk; portfolio optimization

Protein structure prediction is one of the most important research areas in bioinformatics. CASP has been one of the world-wide experiments in this area. It assesses the quality of methods and results of international research in this area. CASP evaluation is based on comparison of each model with the corresponding native model. In this work, we aim to estimate a new function to calculate the measure of similarity between model and native protein structures. Moments of graph theoretical properties were used to find a similarity measure between two protein structures. Multiple Linear Regression was applied to these graph properties to estimate a new function.

We describe an optimization method to approximate the arrival rate of data such as e-mail messages, website visits, changes to databases, and changes to websites mirrored by other servers. We model these arrival rates as non-homogeneous Poisson process based on observed arrival data. We estimate the arrival function by cubic splines using the maximum likelihood principle. A critical feature of the model is that the splines are constrained to be everywhere nonnegative. We formulate this constraint using a characterization of nonnegative polynomials by positive semidefinite matrices. We also describe versions of our model that allow for periodic arrival rate functions and input data of limited precision. We formulate the estimation problem as a convex program related to semidefinite programming and solve it with a standard nonlinear optimization package called KNITRO. We present numerical results using both an actual record of e-mail arrivals over a period of sixty weeks, and artificially generated data sets. We also present a cross-validation procedure for determining an appropriate number of spline knots to model a set of arrival observations.