Re-solving stochastic programming models for airline revenue management

We study some mathematical programming formulations for the origin-destination model in airline revenue management. In particular, we focus on the traditional probabilistic model proposed in the literature. The approach we study consists of solving a sequence of two-stage stochastic programs with simple recourse, which can be viewed as an approximation to a multi-stage stochastic programming formulation to the seat allocation problem. Our theoretical results show that the proposed approximation is robust, in the sense that solving more successive two-stage programs can never worsen the expected revenue obtained with the corresponding allocation policy. Although intuitive, such a property is known not to hold for the traditional deterministic linear programming model found in the literature. We also show that this property does not hold for some bid-price policies. In addition, we propose a heuristic method to choose the re-solving points, rather than re-solving at equally-spaced times as customary. Numerical results are presented to illustrate the effectiveness of the proposed approach.     

Learning failure-free PRISM programs

PRISM is a probabilistic logic programming formalism which allows defining a probability distribution over possible worlds. This paper investigates learning a class of generative PRISM programs known as failure-free. The aim is to learn recursive PRISM programs which can be used to model stochastic processes. These programs generalise dynamic Bayesian networks by defining a halting distribution over the generative process. Dynamic Bayesian networks model infinite stochastic processes. Sampling from infinite process can only be done by specifying the length of sequences that the process generates. In this case, only observations of a fixed length of sequences can be obtained. On the other hand, the recursive PRISM programs considered in this paper are self-terminating upon some halting conditions. Thus, they generate observations of different lengths of sequences. The direction taken by this paper is to combine ideas from inductive logic programming and learning Bayesian networks to learn PRISM programs. It builds upon the inductive logic programming approach of learning from entailment.     

Probabilistic programming models for traffic incident management operations planning

This paper proposes mathematical programming models with probabilistic constraints in order to address incident response and resource allocation problems for the planning of traffic incident management operations. For the incident response planning, we use the concept of quality of service during a potential incident to give the decision-maker the flexibility to determine the optimal policy in response to various possible situations. An integer programming model with probabilistic constraints is also proposed to address the incident response problem with stochastic resource requirements at the sites of incidents. For the resource allocation planning, we introduce a mathematical model to determine the number of service vehicles allocated to each depot to meet the resource requirements of the incidents by taking into account the stochastic nature of the resource requirement and incident occurrence probabilities. A detailed case study for the incident resource allocation problem is included to demonstrate the use of proposed model in a real-world context. The paper concludes with a summary of results and recommendations for future research.     

Reflections on a New Approach to Gittins Indexation

Traditional approaches to stochastic resource allocation problems (including the classical multi-armed bandit problems) have usually made use of dynamic programming (DP) methodology, perhaps buttressed by further ad hoc arguments. While such approaches seem ‘natural’ they have usually proved technically very difficult. Bertsimas and Niño-Mora have recently given a radically new account of many important results in this area which relate to Gittins indices. The key to their approach is in the characterisation of the region of achievable performance. The optimisation problems of interest are then solved as linear programs over this region. Here we exploit elements within the Bertsimas and Niño-Mora framework (in particular, its capacity to give formulae for the total return of a given policy in closed form) to obtain (i) a simple dynamic programming proof of the optimality of Gittins index policies and (ii) a range of index-based suboptimality bounds for general policies for a variety of stochastic models for resource allocation.     

Stochastic ultimate load analysis:models and solution methods 1

The stochastic ultimate load analysis model used in the safety analysis of engineering structures can be treated as a special case of chance-constrained problems (CCP) which minimize a stochastic cost function subject to some probabilistic constraints. Some special cases (such as a deterministic cost function with probabilistic constraints or deterministic constraints with a random cost function) for ultimate load analysis have airady been investigated by various researchers. In this paper, a generai probabilistic approach to stochastic ultimate load analysis is given. In doing so, some approximation techniques are needed due to the fact that the problems at hand are too complicated to evaluate precisely. We propose two extensions of the SQP method in which the variables appear in the algorithms inexactly. These algorithms are shown to be globally convergent for all models and locally superlinearly convergent for some special cases     

An Asset Liability Management Model for Casualty Insurers: Complexity Reduction vs. Parameterized Decision Rules

In this paper we study possibilities for complexity reductions in large scale stochastic programming problems with specific reference to the asset liability management (ALM) problem for casualty insurers. We describe a dynamic, stochastic portfolio selection model, within which the casualty insurer maximizes a concave objective function, indicating that the company perceives itself as risk averse. In this context we examine the sensitivity of the solution to the quality and accuracy with which economic uncertainties are represented in the model. We demonstrate a solution method that combines two solution approaches: A truly stochastic, dynamic solution method that requires scenario aggregation, and a solution method based on ex ante decision rules, that allow for a greater number of scenarios. This dynamic/fix mix decision policy, which facilitates a huge number of outcomes, is then compared to a fully dynamic decision policy, requiring fewer outcomes. We present results from solving the model. Basically we find that the insurance company is likely to prefer accurate representation of uncertainties. In order to accomplish this, it will accept to calculate its current portfolio using parameterized decision rules.     

Constraint-based analysis of concurrent probabilistic hybrid systems: An application to networked automation systems

In previous publications, the authors have introduced the notion of stochastic satisfiability modulo theories (SSMT) and the corresponding SiSAT solving algorithm, which provide a symbolic method for the reachability analysis of probabilistic hybrid systems. SSMT extends satisfiability modulo theories (SMT) with randomized (or stochastic), existential, and universal quantification, as known from stochastic propositional satisfiability. In this paper, we extend the SSMT-based procedures to the symbolic analysis of concurrent probabilistic hybrid systems. After formally introducing the computational model, we provide a mechanized translation scheme to encode probabilistic bounded reachability problems of concurrent probabilistic hybrid automata as linearly sized SSMT formulae, which in turn can be solved by the SiSAT tool. We furthermore propose an algorithmic enhancement which tailors SiSAT to probabilistic bounded reachability problems by caching and reusing solutions obtained on bounded reachability problems of smaller depth. An essential part of this article is devoted to a case study from the networked automation systems domain. We explain in detail the formal model in terms of concurrent probabilistic automata, its encoding into the SiSAT modeling language, and finally the automated quantitative analysis.     

Resource capacity allocation to stochastic dynamic competitors: knapsack problem for perishable items and index-knapsack heuristic

In this paper we propose an approach for solving problems of optimal resource capacity allocation to a collection of stochastic dynamic competitors. In particular, we introduce the knapsack problem for perishable items, which concerns the optimal dynamic allocation of a limited knapsack to a collection of perishable or non-perishable items. We formulate the problem in the framework of Markov decision processes, we relax and decompose it, and we design a novel index-knapsack heuristic which generalizes the index rule and it is optimal in some specific instances. Such a heuristic bridges the gap between static/deterministic optimization and dynamic/stochastic optimization by stressing the connection between the classic knapsack problem and dynamic resource allocation. The performance of the proposed heuristic is evaluated in a systematic computational study, showing an exceptional near-optimality and a significant superiority over the index rule and over the benchmark earlier-deadline-first policy. Finally we extend our results to several related revenue management problems.     

Structural properties of the optimal resource allocation policy for single-queue systems

This paper studies structural properties of the optimal resource allocation policy for single-queue systems. Jobs arrive at a service facility and are sent one by one to a pool of computing resources for parallel processing. The facility poses a constraint on the maximum expected sojourn time of a job. A central decision maker allocates the servers dynamically to the facility. We consider two models: a limited resource allocation model, where the allocation of resources can only be changed at the start of a new service, and a fully flexible allocation model, where the allocation of resources can also change during a service period. In these two models, the objective is to minimize the average utilization costs whilst satisfying the time constraint. To this end, we cast these optimization problems as Markov decision problems and derive structural properties of the relative value function. We show via dynamic programming that (1) the optimal allocation policy has a work-conservation property, and (2) the optimal number of servers follows a step function with as extreme policy the bang-bang control policy. Moreover, (3) we provide conditions under which the bang-bang control policy takes place. These properties give a full characterization of the optimal policy, which are illustrated by numerical experiments.     

A Markov decision process model for equitable distribution of supplies under uncertainty

Many individuals suffering from food insecurity obtain assistance from governmental programs and nonprofit agencies such as food banks. Much of the food distributed by food banks come from donations which are received from various sources in uncertain quantities at random points in time. This paper presents a model that can assist food banks in distributing these uncertain supplies equitably and measure the performance of their distribution efforts. We formulate this decision problem as a discrete-time, discrete state Markov decision process that considers stochastic supply, deterministic demand and an equity-based objective. We investigate three different allocation rules and describe the optimal policy as a function of available inventory. We also provide county level estimates of unmet need and determine the probability distribution associated with the number of underserved counties. A numerical study is performed to show how the allocation policy and unmet need are impacted by uncertain supply and deterministic, time-varying demand. We also compare different allocation rules in terms of equity and effectiveness.     

On stages and consistency checks in stochastic programming

This paper gives a rigorous definition of a stage, usable for dynamic stochastic programs with both recourse and probabilistic constraints. Algebraic modelling languages can make use of this definition for automatic consistency checks.     

The value of rolling-horizon policies for risk-averse hydro-thermal planning

We consider the optimal management of a hydro-thermal power system in the mid and long terms. From the optimization point of view, this amounts to a large-scale multistage stochastic linear program, often solved by combining sampling with decomposition algorithms, like stochastic dual dynamic programming. Such methodologies, however, may entail prohibitive computational time, especially when applied to a risk-averse formulation of the problem. We propose instead a risk-averse rolling-horizon policy that is nonanticipative, feasible, and time consistent. The policy is obtained by solving a sequence of risk-averse problems with deterministic constraints for the current time step and future chance and CVaR constraints.The considered hydro-thermal model takes into account losses resulting from run-of-river plants efficiencies as well as uncertain demand and streamflows. Constraints aim at satisfying demand while keeping reservoir levels above minzones almost surely. We show that if the problem uncertainty is represented by a periodic autoregressive stochastic process with lag one, then the probabilistic constraints can be computed explicitly. As a result, each one of the aforementioned risk-averse problems is a medium-size linear program, easy to solve.For a real-life power system we compare our approach with three alternative policies. Namely, a robust nonrolling-horizon policy and two risk-neutral policies obtained by stochastic dual dynamic programming, implemented in nonrolling- and rolling-horizon modes, respectively. Our numerical assessment confirms the superiority of the risk-averse rolling-horizon policy that yields comparable average indicators, but with reduced volatility and with substantially less computational effort.     

Book review of advances in gabor analysis,applied and numerical harmonic analysis,Hans G. Feichtinger and Thomas Strohmer (Eds.), Birkhäuser,Boston-Basel-Berlin, 2002, 356 pages. ISBN 0-8176-4239-0

In some recent publications it was shown that certain stationary stochastic dynamic programming problems with general state and action spaces can be solved by generalized linear programming. It Is the main aim of the present paper to demonstrate that a similar linear programming approach is feasible even in the non-stationary case. For this end, we formulate a programming problem (D^?) and show that (D^?) is equivalent to the problem of finding a p=optimal policy for the stochastic dynamic program, whereas a modification of (D^?) turns out to be the dual program of a pair of general linear programs.     

Beam search heuristic to solve stochastic integer problems under probabilistic constraints

This paper proposes a Beam Search heuristic strategy to solve stochastic integer programming problems under probabilistic constraints. Beam Search is an adaptation of the classical Branch and Bound method in which at any level of the search tree only the most promising nodes are kept for further exploration, whereas the remaining are pruned out permanently. The proposed algorithm has been compared with the Branch and Bound method. The numerical results collected on the probabilistic set covering problem show that the Beam Search technique is very efficient and appears to be a promising tool to solve difficult stochastic integer problems under probabilistic constraints.     

Managing capacity flexibility in make-to-order production environments

This paper addresses the problem of managing flexible production capacity in a make-to-order (MTO) manufacturing environment. We present a multi-period capacity management model where we distinguish between process flexibility (the ability to produce multiple products on multiple production lines) and operational flexibility (the ability to dynamically change capacity allocations among different product families over time). For operational flexibility, we consider two polices: a fixed allocation policy where the capacity allocations are fixed throughout the planning horizon and a dynamic allocation policy where the capacity allocations change from period to period. The former approach is modeled as a single-stage stochastic program and solved using a cutting-plane method. The latter approach is modeled as a multi-stage stochastic program and a sampling-based decomposition method is presented to identify a feasible policy and assess the quality of that policy. A computational experiment quantifies the benefits of operational flexibility and demonstrates that it is most beneficial when the demand and capacity are well-balanced and the demand variability is high. Additionally, our results reveal that myopic operating policies may lead a firm to adopt more process flexibility and form denser flexibility configuration chains. That is, process flexibility may be over-valued in the literature since it is assumed that a firm will operate optimally after the process flexibility decision. We also show that the value of process flexibility increases with the number of periods in the planning horizon if an optimal operating policy is employed. This result is reversed if a myopic allocation policy is adopted instead.     

运筹学中若干离散规划问题的相对差分搜索解法

运筹学中有很多离散规划问题。其中的线性规划通常用分枝定界法或割平面法，还有图上作业法求解。不论哪种方法工作量都不小，而且效率低；至于非线性规划大都是用动态规划法求解，也很麻烦、耗时。对于大规模问题，不论线性或非线性离散规划，现有解法都受到问题规模的限制；还有资源分配和背包问题至今没有见到解决方法。本文就是为了解决这些问题，提出了相对差分搜索算法。通过5个算例和其它文献中的一些算例计算验证了本法简单、快速、有效和精确，尤其不受问题规模的限制是其最大的优点。     

Optimal greedy policies for stochastic control models

We introduce the notion of a greedy policy for general stochastic control models. Sufficient conditions for the optimality of the greedy policy for finite and infinite horizon are given. Moreover, we derive error bounds if the greedy policy is not optimal. The main results are illustrated by Bayesian information models, discounted Bayesian search problems, stochastic scheduling problems, single-server queueing networks and deterministic dynamic programs.     

Stochastic programming approach to optimization under uncertainty

In this paper we discuss computational complexity and risk averse approaches to two and multistage stochastic programming problems. We argue that two stage (say linear) stochastic programming problems can be solved with a reasonable accuracy by Monte Carlo sampling techniques while there are indications that complexity of multistage programs grows fast with increase of the number of stages. We discuss an extension of coherent risk measures to a multistage setting and, in particular, dynamic programming equations for such problems.      

Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming

Decomposition has proved to be one of the more effective tools for the solution of large-scale problems, especially those arising in stochastic programming. A decomposition method with wide applicability is Benders' decomposition, which has been applied to both stochastic programming as well as integer programming problems. However, this method of decomposition relies on convexity of the value function of linear programming subproblems. This paper is devoted to a class of problems in which the second-stage subproblem(s) may impose integer restrictions on some variables. The value function of such integer subproblem(s) is not convex, and new approaches must be designed. In this paper, we discuss alternative decomposition methods in which the second-stage integer subproblems are solved using branch-and-cut methods. One of the main advantages of our decomposition scheme is that Stochastic Mixed-Integer Programming (SMIP) problems can be solved by dividing a large problem into smaller MIP subproblems that can be solved in parallel. This paper lays the foundation for such decomposition methods for two-stage stochastic mixed-integer programs.     

Optimal control policy for a standing order inventory system

In this paper, we consider a standing order inventory system in which an order of fixed size arrives in each period. Since demand is stochastic, such a system must allow for procurement of extra units in the case of an emergency and sell-offs of excess inventory. Assuming the average-cost criterion, Rosenshine and Obee (Operations Research 24 (1976) 1143–1155) first studied such a system and devised a 4-parameter inventory control policy that is not generally optimal. The current paper uses dynamic programming to determine the optimal control policy for a standing order system, which consists of only two operational parameters: the dispose-down-to level and order-up-to level. Either the average-cost or discounted-cost criterion can be assumed in the proposed model. Also, both the backlogged and lost-sales problems are investigated in this paper. By using a convergence theorem, we stop the dynamic programming computation and obtain the two optimal parameters.