Dynamic Capacity Acquisition and Assignment under Uncertainty

Given a set of m resources and n tasks, the dynamic capacity acquisition and assignment problem seeks a minimum cost schedule of capacity acquisitions for the resources and the assignment of resources to tasks, over a given planning horizon of T periods. This problem arises, for example, in the integrated planning of locations and capacities of distribution centers (DCs), and the assignment of customers to the DCs, in supply chain applications. We consider the dynamic capacity acquisition and assignment problem in an environment where the assignment costs and the processing requirements for the tasks are uncertain. Using a scenario based approach, we develop a stochastic integer programming model for this problem. The highly non-convex nature of this model prevents the application of standard stochastic programming decomposition algorithms. We use a recently developed decomposition based branch-and-bound strategy for the problem. Encouraging preliminary computational results are provided.     

Multistage stochastic demand-side management for price-making major consumers of electricity in a co-optimized energy and reserve market

In this paper, we take an optimization-driven heuristic approach, motivated by dynamic programming, to solve a class of non-convex multistage stochastic optimization problems. We apply this to the problem of optimizing the timing of energy consumption for a large manufacturer who is a price-making major consumer of electricity. We introduce a mixed-integer program that co-optimizes consumption bids and interruptible load reserve offers, for such a major consumer over a finite time horizon. By utilizing Lagrangian methods, we decompose our model through approximately pricing the constraints that link the stages together. We construct look-up tables in the form of consumption-utility curves, and use these to determine optimal consumption levels. We also present heuristics, in order to tackle the non-convexities within our model, and improve the accuracy of our policies. In the second part of the paper, we present stochastic solution methods for our model in which, we reduce the size of the scenario tree by utilizing a tailor-made scenario clustering method. Furthermore, we report on a case study that implements our models for a major consumer in the (full) New Zealand Electricity Market and present numerical results.     

Stochastic set packing problem

In this paper a stochastic version of the set packing problem (SPP), is studied via scenario analysis. We consider a one-stage recourse approach to deal with the uncertainty in the coefficients. It consists of maximizing in the stochastic SPP a composite function of the expected value minus the weighted risk of obtaining a scenario whose objective function value is worse than a given threshold. The splitting variable representation is decomposed by dualizing the nonanticipativity constraints that link the deterministic SPP with a 0-1 knapsack problem for each scenario under consideration. As a result a (structured) larger pure 0-1 model is created. We present several procedures for obtaining good feasible solutions, as well as a preprocessing approach for fixing variables. The Lagrange multipliers updating is performed by using the Volume Algorithm. Computational experience is reported for a broad variety of instances, which shows that the new approach usually outperforms a state-of-the-art optimization engine, producing a comparable optimality gap with smaller (several orders of magnitude) computing time.     

Strategic foreign reserves risk management: Analytical framework

We present an analytical framework for active foreign exchange reserves management that integrates risk-return objectives with macroeconomic, macro-prudential and sovereign debt management concerns. Our framework allows for very general objective functions, does not restrict the class of eligible stochastic processes or limit the investment universe, and can incorporate many types of macroeconomic concerns. It incorporates several kinds of risk constraints in order to obtain benchmarks satisfying possible central bank requirements of safety, liquidity, returns, and stability. Feedback between outcomes and decisions is easy using tools that reshape distributions and functions of the outcomes. And the model can be run on a PC-based platform. We apply the framework to several common reserves management problems focusing especially on the formulation of model equations, generation of trees and estimation of density functions of outcomes. We compare our approach to those used by many central banks and discuss advantages to our approach.     

Scenario generation and stochastic programming models for asset liability management

In this paper, we develop and test scenario generation methods for asset liability management models. We propose a multi-stage stochastic programming model for a Dutch pension fund. Both randomly sampled event trees and event trees fitting the mean and the covariance of the return distribution are used for generating the coefficients of the stochastic program. In order to investigate the performance of the model and the scenario generation procedures we conduct rolling horizon simulations. The average cost and the risk of the stochastic programming policy are compared to the results of a simple fixed mix model. We compare the average switching behavior of the optimal investment policies. Our results show that the performance of the multi-stage stochastic program could be improved drastically by choosing an appropriate scenario generation method.     

Problem-based optimal scenario generation and reduction in stochastic programming

Scenarios are indispensable ingredients for the numerical solution of stochastic programs. Earlier approaches to optimal scenario generation and reduction are based on stability arguments involving distances of probability measures. In this paper we review those ideas and suggest to make use of stability estimates based only on problem specific data. For linear two-stage stochastic programs we show that the problem-based approach to optimal scenario generation can be reformulated as best approximation problem for the expected recourse function which in turn can be rewritten as a generalized semi-infinite program. We show that the latter is convex if either right-hand sides or costs are random and can be transformed into a semi-infinite program in a number of cases. We also consider problem-based optimal scenario reduction for two-stage models and optimal scenario generation for chance constrained programs. Finally, we discuss problem-based scenario generation for the classical newsvendor problem.

     

A visual interactive approach for scenario-based stochastic multi-objective problems and an application

In many practical applications of stochastic programming, discretization of continuous random variables in the form of a scenario tree is required. In this paper, we deal with the randomness in scenario generation and present a visual interactive method for scenario-based stochastic multi-objective problems. The method relies on multi-variate statistical analysis of solutions obtained from a multi-objective stochastic problem to construct joint confidence regions for the objective function values. The decision maker (DM) explores desirable parts of the efficient frontier using a visual representation that depicts the trajectories of the objective function values within confidence bands. In this way, we communicate the effects of randomness inherent in the problem to the DM to help her understand the trade-offs and the levels of risk associated with each objective.     

A scenario decomposition approach for stochastic production planning in sawmills

This study considers a real world stochastic multi-period, multi-product production planning problem. Motivated by the challenges encountered in sawmill production planning, the proposed model takes into account two important aspects: (i) randomness in yield and in demand; and (ii) set-up constraints. Rather than considering a single source of randomness, or ignoring set-up constraints as is typically the case in the literature, we retain all these characteristics while addressing real life-size instances of the problem. Uncertainties are modelled by a scenario tree in a multi-stage environment. In the case study, the resulting large-scale multi-stage stochastic mixed-integer model cannot be solved by using the mixed-integer solver of a commercial optimization package, such as CPLEX. Moreover, as the production planning model under discussion is a mixed-integer programming model lacking any special structure, the development of decomposition and cutting plane algorithms to obtain good solutions in a reasonable time-frame is not straightforward. We develop a scenario decomposition approach based on the progressive hedging algorithm, which iteratively solves the scenarios separately. CPLEX is then used for solving the sub-problems generated for each scenario. The proposed approach attempts to gradually steer the solutions of the sub-problems towards an implementable solution by adding some penalty terms in the objective function used when solving each scenario. Computational experiments for a real-world large-scale sawmill production planning model show the effectiveness of the proposed solution approach in finding good approximate solutions.     

A mixed R&D projects and securities portfolio selection model

The business environment is full of uncertainty. Allocating the wealth among various asset classes may lower the risk of overall portfolio and increase the potential for more benefit over the long term. In this paper, we propose a mixed single-stage R&D projects and multi-stage securities portfolio selection model. Specifically, we present a bi-objective mixed-integer stochastic programming model. Moreover, we use semi-absolute deviation risk functions to measure the risk of mixed asset portfolio. Based on the idea of moments approximation method via linear programming, we propose a scenario generation approach for the mixed single-stage R&D projects and multi-stage securities portfolio selection problem. The bi-objective mixed-integer stochastic programming problem can be solved by transforming it into a single objective mixed-integer stochastic programming problem. A numerical example is given to illustrate the behavior of the proposed mixed single stage R&D projects and multi-stage securities portfolio selection model.     

Airline network revenue management by multistage stochastic programming

A multistage stochastic programming approach to airline network revenue management is presented. The objective is to determine seat protection levels for all itineraries, fare classes, points of sale of the airline network and all dcps of the booking horizon such that the expected revenue is maximized. While the passenger demand and cancelation rate processes are the stochastic inputs of the model, the stochastic protection level process represents its output and allows to control the booking process. The stochastic passenger demand and cancelation rate processes are approximated by a finite number of tree structured scenarios. The scenario tree is generated from historical data using a stability-based recursive scenario reduction scheme. Numerical results for a small hub-and-spoke network are reported. This research is supported by the DFG Research Center Matheon “Mathematics for key technologies” in Berlin.     

An integrated producer–buyer supply chain with delivery cost under stochastic transportation time

An integrated producer–buyer supply chain is used to simultaneously determine the optimum levels of the safety stock, delivery quantity, and number of shipments in this paper. The scenario is created by scheduling a single-setup at the producer with multiple deliveries to the buyer, and all shipments to the buyer are equal-sized batches. This study attempts to study the effects of delivery cost and transportation time, assumes that there is a stochastic transportation time between both producer and buyer, and that shortages are allowed. The transportation time is assumed to be Weibull distributed. The objective functions of the integrated model include the setup cost, inventory carrying cost, and delivery cost. We analyze the scenario where the delivery cost is explicitly considered in the model rather than considered as part of the fixed ordering cost or insignificant. A numerical example is also presented to demonstrate the proposed model using actual shipping rate data. In particular, the results show that when the producer's and buyer's carrying costs are low, and/or the mean time of transportation and delivery costs are high, then this can benefit both parties with regard to sharing total profit.     

选址-库存-路径问题模型及其集成优化算法

设施选址、库存控制和车辆路径安排是物流系统优化中的三个关键问题,三者之间存在相互依赖的关系,应该根据这种关系来相应地进行综合优化与管理物流活动。以典型的单一生产基地、单一产品、采用不断审查的(Q, r)库存策略的供应链二级分销网络为研究对象,建立了一个随机型选址-库存-路径问题优化模型;在将非线性混合整数规划转化为线性整数集合覆盖模型的基础上,采用列生成算法来获得一个近似最优解,再用分支定价法对初始解进行改进,以实现对整个问题“完全集成”的优化。最后,用随机生成的方式,产生了10至160个客户的计算实例,分析了运输费用和库存费用对总成本的影响,算法运算时间表明本文给出的算法能较快地求解这一复杂问题。     

A scenario generation-based lower bounding approach for stochastic scheduling problems

In this paper, we investigate scenario generation methods to establish lower bounds on the optimal objective value for stochastic scheduling problems that contain random parameters with continuous distributions. In contrast to the Sample Average Approximation (SAA) approach, which yields probabilistic bound values, we use an alternative bounding method that relies on the ideas of discrete bounding and recursive stratified sampling. Theoretical support is provided for deriving exact lower bounds for both expectation and conditional value-at-risk objectives. We illustrate the use of our method on the single machine total weighted tardiness problem. The results of our numerical investigation demonstrate good properties of our bounding method, compared with the SAA method and an earlier discrete bounding method.     

Two-Stage Nested Partitions Method for Stochastic Optimization

We address the problem of optimizing over a large but finite set when the objective function does not have an analytical expression and is evaluated using noisy estimation. Building on the recently proposed nested partitions method for stochastic optimization, we develop a new approach that combines this random search method and statistical selection for guiding the search. We prove asymptotic convergence and analyze the finite time behavior of the new approach. We also report extensive numerical results to illustrate the benefits of the new approach.     

Multi-stage portfolio selection problem with dynamic stochastic dominance constraints

We study the multi-stage portfolio selection problem where the utility function of an investor is ambiguous. The ambiguity is characterized by dynamic stochastic dominance constraints, which are able to capture the dynamics of the random return sequence during the investment process. We propose a multi-stage dynamic stochastic dominance constrained portfolio selection model, and use a mixed normal distribution with time-varying weights and the K-means clustering technique to generate a scenario tree for the transformation of the proposed model. Based on the scenario tree representation, we derive two linear programming approximation problems, using the sampling approach or the duality theory, which provide an upper bound approximation and a lower bound approximation for the original nonconvex problem. The upper bound is asymptotically tight with infinitely many samples. Numerical results illustrate the practicality and efficiency of the proposed new model and solution techniques.

     

Stochastic non-convex envelopment of data: Applying isotonic regression to frontier estimation

Isotonic nonparametric least squares (INLS) is a regression method for estimating a monotonic function by fitting a step function to data. In the literature of frontier estimation, the free disposal hull (FDH) method is similarly based on the minimal assumption of monotonicity. In this paper, we link these two separately developed nonparametric methods by showing that FDH is a sign-constrained variant of INLS. We also discuss the connections to related methods such as data envelopment analysis (DEA) and convex nonparametric least squares (CNLS). Further, we examine alternative ways of applying isotonic regression to frontier estimation, analogous to corrected and modified ordinary least squares (COLS/MOLS) methods known in the parametric stream of frontier literature. We find that INLS is a useful extension to the toolbox of frontier estimation both in the deterministic and stochastic settings. In the absence of noise, the corrected INLS (CINLS) has a higher discriminating power than FDH. In the case of noisy data, we propose to apply the method of non-convex stochastic envelopment of data (non-convex StoNED), which disentangles inefficiency from noise based on the skewness of the INLS residuals. The proposed methods are illustrated by means of simulated examples.     

Integrated data envelopment analysis: Global vs. local optimum

Chiou et al. (2010) (A joint measurement of efficiency and effectiveness for non-storable commodities: integrated data envelopment analysis approaches. European Journal of Operational Research 201, 477–489) propose an integrated data envelopment analysis model in measuring decision making units (DMUs) that have a two-stage internal network structure with multiple inputs, outputs, and consumptions. They claim that any optimal solutions determined by their DEA model are a global optimum, not a local optimum. We show that such a conclusion is a false statement due to their misuse of Hessian matrix in examining the concavity of the objective function, and their DEA model is actually a non-convex optimization problem. As a result, their DEA model is unusable in practice due to a lack of efficient algorithm for this particular non-convex DEA model. We further show that Chiou et al.’s (2010) model is a special case of a well-known two-stage network DEA model, and it can be transformed into a parametric linear program for which an approximate global optimal solution can be obtained by solving a sequence of linear programs in combination with a simple search algorithm.     

A Riccati-based primal interior point solver for multistage stochastic programming

We propose a new method for certain multistage stochastic programs with linear or nonlinear objective function, combining a primal interior point approach with a linear-quadratic control problem over the scenario tree. The latter problem, which is the direction finding problem for the barrier subproblem is solved through dynamic programming using Riccati equations. In this way we combine the low iteration count of interior point methods with an efficient solver for the subproblems. The computational results are promising. We have solved a financial problem with 1,000,000 scenarios, 15,777,740 variables and 16,888,850 constraints in 20 hours on a moderate computer.     

An Approach for Strategic Supply Chain Planning under Uncertainty based on Stochastic 0-1 Programming

We present a two-stage stochastic 0-1 modeling and a related algorithmic approach for Supply Chain Management under uncertainty, whose goal consists of determining the production topology, plant sizing, product selection, product allocation among plants and vendor selection for raw materials. The objective is the maximization of the expected benefit given by the product net profit over the time horizon minus the investment depreciation and operations costs. The main uncertain parameters are the product net price and demand, the raw material supply cost and the production cost. The first stage is included by the strategic decisions. The second stage is included by the tactical decisions. A tight 0-1 model for the deterministic version is presented. A splitting variable mathematical representation via scenario is presented for the stochastic version of the model. A two-stage version of a Branch and Fix Coordination (BFC) algorithmic approach is proposed for stochastic 0-1 program solving, and some computational experience is reported for cases with dozens of thousands of constraints and continuous variables and hundreds of 0-1 variables.     

Computational strategies for non-convex multistage MINLP models with decision-dependent uncertainty and gradual uncertainty resolution

In many planning problems under uncertainty the uncertainties are decision-dependent and resolve gradually depending on the decisions made. In this paper, we address a generic non-convex MINLP model for such planning problems where the uncertain parameters are assumed to follow discrete distributions and the decisions are made on a discrete time horizon. In order to account for the decision-dependent uncertainties and gradual uncertainty resolution, we propose a multistage stochastic programming model in which the non-anticipativity constraints in the model are not prespecified but change as a function of the decisions made. Furthermore, planning problems consist of several scenario subproblems where each subproblem is modeled as a nonconvex mixed-integer nonlinear program. We propose a solution strategy that combines global optimization and outer-approximation in order to optimize the planning decisions. We apply this generic problem structure and the proposed solution algorithm to several planning problems to illustrate the efficiency of the proposed method with respect to the method that uses only global optimization.