Search

We introduce a new class of distributionally robust optimization problems under decision-dependent ambiguity sets. In particular, as our ambiguity sets, we consider balls centered on a decision-dependent probability distribution. The balls are based on a class of earth mover's distances that includes both the total variation distance and the Wasserstein metrics. We discuss the main computational challenges in solving the problems of interest and provide an overview of various settings leading to tractable formulations. Some of the arising side results, such as the mathematical programming expressions for robustified risk measures in a discrete space, are also of independent interest. Finally, we rely on state-of-the-art modeling techniques from machine scheduling and humanitarian logistics to arrive at potentially practical applications, and present a numerical study for a novel risk-averse scheduling problem with controllable processing times. Summary of Contribution: In this study, we introduce a new class of optimization problems that simultaneously address distributional and decision-dependent uncertainty. We present a unified modeling framework along with a discussion on possible ways to specify the key model components, and discuss the main computational challenges in solving the complex problems of interest. Special care has been devoted to identifying the settings and problem classes where these challenges can be mitigated. In particular, we provide model reformulation results, including mathematical programming expressions for robustified risk measures, and describe how these results can be utilized to obtain tractable formulations for specific applied problems from the fields of humanitarian logistics and machine scheduling. Toward demonstrating the value of the modeling approach and investigating the performance of the proposed mixed-integer linear programming formulations, we conduct a computational study on a novel risk-averse machine scheduling problem with controllable processing times. We derive insights regarding the decision-making impact of our modeling approach and key parameter choices., Office of Naval Research

We focus on the resource provisioning problem of a cloud consumer from an Infrastructure-as-a-Service type of cloud. The cloud provider offers two deployment options, which can be mixed and matched as appropriate. Cloud instances may be reserved for a fixed time period in advance at a smaller usage cost per hour but require a full commitment and payment for the entire contract duration. In contrast, on-demand instances reflect a pay-as-you-go policy at a premium. The trade-off between these two options is rooted in the inherent uncertainty in demand and price and makes it attractive to complement a base reserved capacity with on-demand capacity to hedge against the spikes in demand. This paper provides several novel multi-stage stochastic programming formulations to enable a cloud consumer to handle the cloud resource provisioning problem at a tactical level. We first formulate the cloud resource provisioning problem as a risk-neutral multi-stage stochastic program, which serves as the base model for further modeling variants. In our second set of models, we also incorporate a certain concept of system reliability. In particular, chance constraints integrated into the base formulation require a minimum service level met from reserved capacity, provide more visibility into the future available capacity, and smooth out expensive on-demand usage by hedging against possible demand fluctuations. An extensive computational study demonstrates the value of the proposed models by discussing computational performance, gleaning practical managerial insights from the analysis of the solutions of the proposed models, and quantifying the value of the stochastic solutions.

We introduce a new class of two-stage stochastic uncapacitated facility location problems under system nervousness considerations. The location and allocation decisions are made under uncertainty, while the allocation decisions may be altered in response to the realizations of the uncertain parameters. A practical concern is that the uncertainty-adaptive second-stage allocation decisions might substantially deviate from the corresponding pre-determined first-stage allocation decisions, resulting in a high level of nervousness in the system. To this end, we develop two-stage stochastic programming models with restricted recourse that hedge against undesirable values of a dispersion measure quantifying such deviations. In particular, we control the robustness between the corresponding first-stage and scenario-dependent recourse decisions by enforcing an upper bound on the Conditional Value-at-Risk (CVaR) measure of the random CVaR-norm associated with the scenario-dependent deviations of the recourse decisions. We devise exact Benders-type decomposition algorithms to solve the problems of interest. To enhance the computational performance, we also develop efficient combinatorial algorithms to construct optimal solutions of the Benders cut generation subproblems, as an alternative to using an off-the-shelf solver. The results of our computational study demonstrate the value of the proposed modeling approaches and the effectiveness of our solution methods.

It is of crucial importance to develop risk-averse models for multicriteria decision making under uncertainty. A major stream of the related literature studies optimization problems that feature multivariate stochastic benchmarking constraints. These problems typically involve a univariate stochastic preference relation, often based on stochastic dominance or a coherent risk measure such as conditional value-at-risk, which is then extended to allow the comparison of random vectors by the use of a family of scalarization functions: All scalarized versions of the vector of the uncertain outcomes of a decision are required to be preferable to the corresponding scalarizations of the benchmark outcomes. While this line of research has been dedicated almost entirely to linear scalarizations, the corresponding deterministic literature uses a wide variety of scalarization functions that, among other advantages, offer a high degree of modeling flexibility. In this paper we aim to incorporate these scalarizations into a stochastic context by introducing the general class of min-biaffine functions. We study optimization problems in finite probability spaces with multivariate stochastic benchmarking constraints based on min-biaffine scalarizations. We develop duality results, optimality conditions, and a cut generation method to solve these problems. We also introduce a new characterization of the risk envelope of a coherent risk measure in terms of its Kusuoka representation as a tool toward proving the finite convergence of our solution method. The main computational challenge lies in solving cut generation subproblems; we develop several mixed-integer programming formulations by exploiting the min-affine structure and leveraging recent advances for solving similar problems with linear scalarizations. We conduct a computational study on a well-known homeland security budget allocation problem to examine the impact of the proposed scalarizations on optimal solutions, and illustrate the computational performance of our solution methods. The online appendix is available at https://doi.org/10.1287/opre.2017.1671 .

The ability to compare random outcomes based on the decision makers' risk preferences is crucial to modeling decision-making problems under uncertainty. In this tutorial, the primary focus is on the stochastic preference relations based on the widely applied risk measure, conditional value-at-risk (CVaR), and the second-order stochastic dominance (SSD). We present single- and two-stage stochastic optimization problems that feature such risk-averse preference relations. We discuss the main computational challenges in solving the problems of interest, and for finite probability spaces, we describe alternative mathematical programming formulations and effective solution methods. Our focus is on delayed cut generation solution algorithms, which rely on a Benders-type scenario decomposition approach in the case of a two-stage problem. In addition, we review the recent developments in risk-averse stochastic programming, with a particular focus on multicriteria optimization problems that feature multivariate stochastic benchmarking constraints based on CVaR and SSD.

Recent technological advancements provide a level of mobility never seen before to modern societies. Sustaining today's economy and societies depend on maintaining this mobility. However, this mobility also causes undesirable effects, especially in high urban population areas. Even though, higher priority is given to public transport in metropolitan areas, road network is still an important part of everyday commute and should be planned and managed with great care. In this study, we propose an optimisation methodology that would help the traffic authorities to better predict the results of strategic management decisions in a realistic traffic model. We formulate a bi-level multi-objective traffic optimisation model with a sustainability perspective. The upper level of the proposed model considers the traffic authority's management strategies while the lower level considers the traffic users' decisions. The lower level is modelled using the Stochastic User Equilibrium since it allows more realistic results than the deterministic one. A case study is provided to illustrate the proposed model. The proposed methodology provides an avenue for understanding the trade-offs among conflicting objectives and for designing an environmentally and socially sustainable transportation system. More importantly, it builds the foundation for an intelligent traffic management decision support system. (C) 2018 Elsevier Ltd. All rights reserved.

We consider a stochastic pre-disaster relief network design problem, which mainly determines the capacities and locations of the response facilities and their inventory levels of the relief supplies in the presence of uncertainty in post-disaster demands and transportation network conditions. In contrast to the traditional humanitarian logistics literature, we develop a chance-constrained two-stage mean-risk stochastic programming model. This risk-averse model features a mean-risk objective, where the conditional value at-risk (CVaR) is specified as the risk measure, and enforces a joint probabilistic constraint on the feasibility of the second-stage problem concerned with distributing the relief supplies to the affected areas in case of a disaster. To solve this computationally challenging stochastic optimization model, we employ an exact Benders decomposition-based branch and-cut algorithm. We develop three variants of the proposed algorithm by using alternative representations of CVaR We illustrate the application of our model and solution methods on a case study concerning the threat of hurricanes in the Southeastern part of the United States. An extensive computational study provides practical insights about the proposed modeling approach and demonstrates the computational effectiveness of the solution framework. (C) 2017 Elsevier Ltd. All rights reserved.

We study a last mile distribution network design problem for situations where there exist local distribution centers (LDCs) with pre-positioned supplies. Given the information on the existing pre-disaster relief network, the problem determines the locations and capacities of LDCs and points of distribution in the relief network, while capturing the uncertain aspects of the post-disaster environment. We introduce a new accessibility metric and develop a two-stage stochastic programming model that would allow more accessible and equitable distribution of relief supplies. Since solving the proposed stochastic optimization model is computationally challenging, we employ a scenario decomposition-based branch-and-cut algorithm. We perform a computational study -- based on the real-world data from the 2011 Van earthquake in Turkey -- to provide insights about the model and demonstrate the effectiveness of the solution method.

We focus on optimization models involving individual chance constraints, in which only the right-hand side vector is random with a finite distribution. A recently introduced class of such models treats the reliability levels / risk tolerances associated with the chance constraints as decision variables and trades off the actual cost / return against the cost of the selected reliability levels in the objective function. Leveraging recent methodological advances for modeling and solving chance-constrained linear programs with fixed reliability levels, we develop strong mixed-integer programming formulations for this new variant with variable reliability levels. In addition, we introduce an alternate cost function type associated with the risk tolerances which requires capturing the value-at-risk (VaR) associated with a variable reliability level. We accomplish this task via a new integer linear programming representation of VaR. Our computational study illustrates the effectiveness of our mathematical programming formulations. We also apply the proposed modeling approach to a new stochastic last mile relief network design problem and provide numerical results for a case study based on the real-world data from the 2011 Van earthquake in Turkey. (C) 2018 Elsevier Ltd. All rights reserved.

In this paper, we study risk-averse models for multicriteria optimization problems under uncertainty. We use a weighted sum-based scalarization and take a robust approach by considering a set of scalarization vectors to address the ambiguity and inconsistency in the relative weights of each criterion. We model the risk aversion of the decision makers via the concept of multivariate conditional value-at-risk (CVaR). First, we introduce a model that optimizes the worst-case multivariate CVaR and show that its optimal solution lies on a particular type of stochastic efficient frontier. To solve this model, we develop a finitely convergent delayed cut generation algorithm for finite probability spaces. We also show that the proposed model can be reformulated as a compact linear program under certain assumptions. In addition, for the cut generation problem, which is in general a mixed-integer program, we give a stronger formulation than the existing ones for the equiprobable case. Next, we observe that similar polyhedral enhancements are also useful for a related class of multivariate CVaR-constrained optimization problems that has attracted attention recently. In our computational study, we use a budget allocation application to benchmark our proposed maximin type risk-averse model against its risk-neutral counterpart and a related multivariate CVaR-constrained model. Finally, we illustrate the effectiveness of the proposed solution methods for both classes of models.

Toll pricing strategies have received significant attention from transportation planners and researchers, and they have been widely applied in practice. In this study, we consider the toll pricing problem under uncertain network conditions resulting in stochastic travel times. Using the conditional value-at-risk (CVaR) as a risk measure on the alternate functions of the random travel times we introduce several travel time reliability-related network performance measures. Basically, CVaR is used to control the possible large realizations of random outcomes based on travel times, and consequently, improve the reliability of the transportation system. We characterize the random network parameters, which are in general highly correlated, by a finite set of scenarios and propose alternate risk-averse toll pricing models that incorporate the travel time reliability-related performance criteria. These optimization models involve decisions of transportation managers that aim to improve the system-wide network reliability and decisions of network users that are assumed to choose their routes to minimize their expected total travel costs. We describe a solution method integrating mathematical programming approaches with a genetic algorithm. We also conduct a computational study to illustrate the effectiveness of the proposed modeling approaches.

In this study, we consider two classes of multicriteria two-stage stochastic programs in finite probability spaces with multivariate risk constraints. The first-stage problem features multivariate stochastic benchmarking constraints based on a vector-valued random variable representing multiple and possibly conflicting stochastic performance measures associated with the second-stage decisions. In particular, the aim is to ensure that the decision-based random outcome vector of interest is preferable to a specified benchmark with respect to the multivariate polyhedral conditional value-at-risk or a multivariate stochastic order relation. In this case, the classical decomposition methods cannot be used directly due to the complicating multivariate stochastic benchmarking constraints. We propose an exact unified decomposition framework for solving these two classes of optimization problems and show its finite convergence. We apply the proposed approach to a stochastic network design problem in the context of pre-disaster humanitarian logistics and conduct a computational study concerning the threat of hurricanes in the Southeastern part of the United States. The numerical results provide practical insights about our modeling approach and show that the proposed algorithm is computationally scalable.

Airline revenue management is concerned with identifying the maximum revenue seat allocation policies. Because a major loss in revenue results from cancellations and no-shows, overbooking has received significant attention in the literature over the years. In this study, we propose new static and dynamic single-leg overbooking models. In the static case we introduce two models: the first one aims to determine the overbooking limit and the second one is about finding the overbooking limit and the booking limits to allocate the virtual capacity among multiple fare classes. Because the second static model is hard to solve, we also introduce computationally tractable models that give upper and lower bounds on its optimal expected net revenue. In the dynamic case, we propose a dynamic programming model, which is based on two streams of events. The first stream corresponds to the arrival of booking requests and the second one corresponds to the cancellations. We conduct simulation experiments to illustrate the effectiveness of the proposed models.

For many decision-making problems under uncertainty, it is crucial to develop risk-averse models and specify the decision makers' risk preferences based on multiple stochastic performance measures (or criteria). Incorporating such multivariate preference rules into optimization models is a fairly recent research area. Existing studies focus on extending univariate stochastic dominance rules to the multivariate case. However, enforcing multivariate stochastic dominance constraints can often be overly conservative in practice. As an alternative, we focus on the widely applied risk measure conditional value-at-risk (CVaR), introduce a multivariate CVaR relation, and develop a novel optimization model with multivariate CVaR constraints based on polyhedral scalarization. To solve such problems for finite probability spaces, we develop a cut generation algorithm, where each cut is obtained by solving a mixed-integer problem. We show that a multivariate CVaR constraint reduces to finitely many univariate CVaR constraints, which proves the finite convergence of our algorithm. We also show that our results can be naturally extended to a wider class of coherent risk measures. The proposed approach provides a flexible and computationally tractable way of modeling preferences in stochastic multicriteria decision making. We conduct a computational study for a budget allocation problem to illustrate the effect of enforcing multivariate CVaR constraints and demonstrate the computational performance of the proposed solution methods.

In this study, we introduce a distribution network design problem that determines the locations and capacities of the relief distribution points in the last mile network, while considering demand- and network-related uncertainties in the post-disaster environment. The problem addresses the critical concerns of relief organizations in designing last mile networks, which are providing accessible and equitable service to beneficiaries. We focus on two types of supply allocation policies and propose a hybrid version considering their different implications on equity and accessibility. Then, we develop a two-stage stochastic programming model that incorporates the hybrid allocation policy and achieves high levels of accessibility and equity simultaneously. We devise a branch-and-cut algorithm based on Benders decomposition to solve large problem instances in reasonable times and conduct a numerical study to demonstrate the computational effectiveness of the solution method. We also illustrate the application of our model on a case study developed based on the real-world data from the 2011 Van earthquake in Turkey. TÜBİTAK, TÜBA

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 adapt the concepts of the value of perfect information (VPI) and the value of the stochastic solution (VSS) for the proposed risk-averse two-stage stochastic programming framework and define two stochastic measures on the VPI and VSS. We apply the proposed model 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 demonstrate the computational effectiveness of the proposed methods.

For a proper cone $${{\mathcal K}\subset\mathbb{R}^n}$$ and its dual cone $${{\mathcal K}^*}$$ the complementary slackness condition $${\langle{\rm {\bf x}},{\rm {\bf s}}\rangle=0}$$ defines an n-dimensional manifold $${C({\mathcal K})}$$ in the space $${{\mathbb R}^{2n}}$$. When $${{\mathcal K}}$$ is a symmetric cone, points in $${C({\mathcal K})}$$ must satisfy at least n linearly independent bilinear identities. This fact proves to be useful when optimizing over such cones, therefore it is natural to look for similar bilinear relations 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 points in $${C({\mathcal K})}$$. We examine several well-known cones, in particular the cone of positive polynomials $${{\mathcal P}_{2n+1}}$$ and its dual, and show that there are exactly four linearly independent bilinear identities which hold for all $${({\rm {\bf x}},{\rm {\bf s}})\in C({\mathcal P}_{2n+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. We prove similar results for Muntz polynomials.

The stochastic nature of emergency service requests and the unavailability of emergency vehicles when requested to serve demands are critical issues in constructing valid models representing real life emergency medical service (EMS) systems. We consider an EMS system design problem with stochastic demand and locate the emergency response facilities and vehicles in order to ensure target levels of coverage, which are quantified using risk measures on random unmet demand. The target service levels for each demand site and also for the entire service area are specified. In order to increase the possibility of representing a wider range of risk preferences we develop two types of stochastic optimization models involving alternate risk measures. The first type of the model includes integrated chance constraints (ICCs ), whereas the second type incorporates ICCs and a stochastic dominance constraint. We develop solution methods for the proposed single-stage stochastic optimization problems and present extensive numerical results demonstrating their computational effectiveness.

We describe an optimization method to approximate the arrival rate of data such as e-mail messages, Web site visits, changes to databases, and changes to Web sites 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

Stochastic dominance relations are well studied in statistics, decision theory and economics. Recently, there has been significant interest in introducing dominance relations into stochastic optimization problems as constraints. In the discrete case, stochastic optimization models involving second order stochastic dominance constraints can be solved by linear programming. However, problems involving first order stochastic dominance constraints are potentially hard due to the non-convexity of the associated feasible regions. In this paper we consider a mixed 0–1 linear programming formulation of a discrete first order constrained optimization model and present a relaxation based on second order constraints. We derive some valid inequalities and restrictions by employing the probabilistic structure of the problem. We also generate cuts that are valid inequalities for the disjunctive relaxations arising from the underlying combinatorial structure of the problem by applying the lift-and-project procedure. We describe three heuristic algorithms to construct feasible solutions, based on conditional second order constraints, variable fixing, and conditional value at risk. Finally, we present numerical results for several instances of a real world portfolio optimization problem.

We consider a class of stochastic optimization problems that features benchmarking preference relations among random vectors representing multiple random performance measures (criteria) of interest. Given a benchmark random performance vector, preference relations are incorporated into the model as constraints, which require the decision-based random vector to be preferred to the benchmark according to a relation based on multivariate conditional value-at-risk (CVaR) or second-order stochastic dominance (SSD). We develop alternative mixed-integer programming formulations and solution methods for cut generation problems arising in optimization under such multivariate risk constraints. The cut generation problems for CVaR- and SSD-based models involve the epigraphs of two distinct piecewise linear concave functions, which we refer to as reverse concave sets. We give the complete linear description of the linearization polytopes of these two non-convex substructures. We present computational results that show the effectiveness of our proposed models and methods.

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.

Linear stochastic programming problems with first order stochastic dominance (FSD) constraints are non-convex. For their mixed 0-1 linear programming formulation we present two convex relaxations based on second order stochastic dominance (SSD). We develop necessary and sufficient conditions for FSD, used to obtain a disjunctive programming formulation and to strengthen one of the SSD-based relaxations.

The vast majority of the machine scheduling literature focuses on deterministic problems in which all data is known with certainty a priori. In practice, this assumption implies that the random parameters in the problem are represented by their point estimates in the scheduling model. The resulting schedules may perform well if the variability in the problem parameters is low. However, as variability increases accounting for this randomness explicitly in the model becomes crucial in order to counteract the ill effects of the variability on the system performance. In this paper, we consider single-machine scheduling problems in the presence of uncertain parameters. We impose a probabilistic constraint on the random performance measure of interest, such as the total weighted completion time or the total weighted tardiness, and introduce a generic 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) of the random performance measure at a specified confidence level. We propose a Lagrangian relaxation-based scenario decomposition method to obtain lower bounds on the optimal VaR and provide a stabilized cut generation algorithm to solve the Lagrangian dual problem. Furthermore, we identify promising schedules for the original problem by a simple primal heuristic. An extensive computational study on two selected performance measures is presented to demonstrate the value of the proposed model and the effectiveness of our solution method.

In this paper we examine the various effects that workstations and rework loops with identical parallel processors and stochastic processing times have on the performance of a mixed-model production 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 production 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 production 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. (C) 2014 Elsevier B.V. All rights reserved.

Transport systems play a crucial role for sustainable development, and hence, sustainable urban transportation has recently become a major research area. Most of the existing studies propose evaluation methods that use simulation tools to assess the sustainability of different transportation policies. Although there are some recent studies, considering the sustainability dimension and the resulting policies through mathematical programming models is still an open research area. In this study, we focus on controlling the gas emissions for the environmental sustainability and propose several mathematical programming models that incorporate the measurements of gas emissions over a traffic network. We define emission functions in terms of the traffic flow so that the accumulated emission amounts can be modeled accurately, particularly in case of congestion. Using these emission functions, we introduce alternate objective functions and develop optimization models under various policies which are based on the well-known toll pricing and capacity enhancement. The proposed models both reflect the route choice decisions of the network users and the decisions of the transportation managers that aim at making the transport systems more sustainable through the policies of interest. We conduct a computational study on a well-known testing network and present numerical results to evaluate the proposed alternate models. We conclude that simultaneously applying the toll pricing and capacity enhancement policies is in general more effective in serving the travel demand and reducing the emission amounts compared to implementing these policies individually.

The uncertainties inherent in the airport flight arrival and departure traffic may lead to the unavailability of gates for accommodating the scheduled flights. Mechanical failures, severe weather conditions, heavy traffic volume at the airport are some typical causes of the uncertainties in the input data. Incorporating such random disruptions is crucial in constructing effective flight-gate assignment plans. We consider the gate assignment problem in the presence of uncertainty in arrival and departure times of the flights and represent the randomness associated with these uncertain parameters by a finite set of scenarios. Using the scenario-based approach, we develop new stochastic programming models incorporating alternate robustness measures to obtain assignments that would perform well under potential random disruptions. In particular, we focus on the number of conflicting flights, the idle and buffer times as robustness measures. Minimizing the expected variance of idle times or the expected total semi-deviation of idle times from a specified buffer time value are some examples of the objectives that we incorporate in our models to appropriately distribute the idle times among gates, and by this way, to decrease the number of potential flight conflicts. The proposed stochastic optimization models are formulated as computationally expensive large-scale mixed-integer programming problems, which are hard to solve. In order to find good feasible solutions in reasonably short CPU times, we employ tabu search algorithms. We conduct an extensive computational study to analyze the proposed alternate formulations and show the effectiveness of the proposed solution methods.

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 net expected revenue, 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 finding a set of acceptance probabilities that maximize the net expected revenue. We derive a simple expression that can be used to compute the optimal acceptance probabilities, despite the problem of finding the optimal acceptance probabilities being 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 net expected revenues within two percent of the optimal on average.

P-efficient points (pLEPs), introduced by Prekopa (1990), are utilized to solve probabilistically constrained problems which have been receiving significant attention in a wide range of application fields. Due to their non-convex feasible regions such problems are hard to solve. In a special case, the probabilistic constraint is enforced jointly on constraints involving randomness only in the right hand side and the vector of random variables has a finite distribution. For this special class of problems, the concept of the p-efficient point has been widely used to develop associated ecient solution methods. Those methods require the generation of pLEPs. We consider a finite random vector that is characterized by a set of scenarios and propose a mathematical programming based approach to generate pLEPs. Using a mixed-integer formulation, we obtain a method to generate pLEPs based on a new preprocessing technique and iterative outer approximations. Moreover, some valid inequalities are derived to strengthen the formulations of the outer approximations, which result in improved computational performance of the proposed generation method. We also develop a heuristic algorithm to generate “quasi pLEPs” efficiently. To the best of our knowledge, developing an optimizationbased approach for generating multiple pLEPs and developing a method for generating pLEPs for random variables characterized by a set of scenarios are novel. We also present some numerical results to show the computational efficiency and effectiveness of the proposed methods.

The ‘Hungarian inventory control model’ was initiated by Prekopa [1965. Reliability equation for an inventory problem and its asymptotic solutions. In: Prekopa, A. (Ed.), Application of the Mathematics to Economics. Publication House of the Hungarian Academy of Science, pp. 317–327] and Ziermann [1964. Application of Smirnov's theorems for an inventory control problem. Publications of the Mathematical Institute of the Hungarian Academy of Science Series B 8, 509–518 (in Hungarian)], where the ordered amount is delivered in an interval, rather than at a time epoch according to some stochastic process and consumption takes place in the same interval. The problem is to determine the minimum level of initial safety stock that ensures continuous consumption, without disruption, in the whole time interval with a prescribed high probability. Prekopa [2006. On the Hungarian inventory control model. European Journal of Operational Research 171, 894–914] has formulated a two-stage model with such interval type processes and probabilistic constraints. In this paper we modify the assumptions of those models and formulate simpler, numerically more tractable models. We also present numerical examples.