Bounds on stochastic convex allocation problems

We consider a stochastic convex program arising in a certain resource allocation problem. The uncertainty is in the demand for a resource which is to be allocated among several competing activities under convex inventory holding and shortage costs. The problem is cast as a two–period stochastic convex program and we derive tight upper and lower bounds to the problem using marginal distributions of the demands, which may be stochastically dependent. It turns out that these bounds are tighter than the usual bounds in the literature which are based on limited moment information of the underlying random variables. Numerical examples illustrate the bounds.     

A gaussian upper bound for gaussian multi-stage stochastic linear programs

This paper deals with two-stage and multi-stage stochastic programs in which the right-hand sides of the constraints are Gaussian random variables. Such problems are of interest since the use of Gaussian estimators of random variables is widespread. We introduce algorithms to find upper bounds on the optimal value of two-stage and multi-stage stochastic (minimization) programs with Gaussian right-hand sides. The upper bounds are obtained by solving deterministic mathematical programming problems with dimensions that do not depend on the sample space size. The algorithm for the two-stage problem involves the solution of a deterministic linear program and a simple semidefinite program. The algorithm for the multi-stage problem invovles the solution of a quadratically constrained convex programming problem.     

Robust solution of monotone stochastic linear complementarity problems

We consider the stochastic linear complementarity problem (SLCP) involving a random matrix whose expectation matrix is positive semi-definite. We show that the expected residual minimization (ERM) formulation of this problem has a nonempty and bounded solution set if the expected value (EV) formulation, which reduces to the LCP with the positive semi-definite expectation matrix, has a nonempty and bounded solution set. We give a new error bound for the monotone LCP and use it to show that solutions of the ERM formulation are robust in the sense that they may have a minimum sensitivity with respect to random parameter variations in SLCP. Numerical examples including a stochastic traffic equilibrium problem are given to illustrate the characteristics of the solutions.     

Natural gas cash-out problem: Bilevel stochastic optimization approach

A stochastic formulation of the natural gas cash-out problem is given in a form of a bilevel multi-stage stochastic programming model with recourse. After reducing the original formulation to a bilevel linear problem, a stochastic scenario tree is defined by its node events, and time series forecasting is used to produce stochastic values for data of natural gas price and demand. Numerical experiments were run to compare the stochastic solution with the perfect information solution and the expected value solutions.     

Relaxations and approximations of chance constraints under finite distributions

Optimization problems with constraints involving stochastic parameters that are required to be satisfied with a prespecified probability threshold arise in numerous applications. Such chance constrained optimization problems involve the dual challenges of stochasticity and nonconvexity. In the setting of a finite distribution of the stochastic parameters, an optimization problem with linear chance constraints can be formulated as a mixed integer linear program (MILP). The natural MILP formulation has a weak relaxation bound and is quite difficult to solve. In this paper, we review some recent results on improving the relaxation bounds and constructing approximate solutions for MILP formulations of chance constraints. We also discuss a recently introduced bicriteria approximation algorithm for covering type chance constrained problems. This algorithm uses a relaxation to construct a solution whose (constraint violation) risk level may be larger than the pre-specified threshold, but is within a constant factor of it, and whose objective value is also within a constant factor of the true optimal value. Finally, we present some new results that improve on the bicriteria approximation factors in the finite scenario setting and shed light on the effect of strong relaxations on the approximation ratios.     

Valid inequalities and restrictions for stochastic programming problems with first order stochastic dominance constraints

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. This research was supported by the NSF awards DMS-0603728 and DMI-0354678.     

随机P矩阵和随机P0矩阵线性互补问题

定义了随机P矩阵和随机P0矩阵,给出了矩阵为随机P矩阵或随机P0矩阵的充要条件.研究了随机线性互补问题(SLCP)的矩阵为随机P矩阵时,期望残差方法(ERM)解集的有界性.得到了期望矩阵为P矩阵时,(ERM)解集非空有界.并且研究离散情形(ERM)与期望值方法(EV)解的关系,给出了(ERM)解唯一的条件.     

Mixed-integer linear optimization for optimal lift-gas allocation with well-separator routing

The lift-gas allocation problem with well-separator routing constraints is a mixed-integer nonlinear program of considerable complexity. To this end, a mixed-integer linear formulation (compact) is obtained by piecewise-linearizing the nonlinear curves, using binary variables to express the linearization and routing decisions. A new formulation (integrated) combining the decisions on linearization and routing is developed by using a single binary variable. The structures of both formulations are explored to generate lifted cover cuts. Numerical tests show that the solution of the integrated formulation using cutting-plane generation is faster in spite of having more variables than the compact formulation.     

The capacitated multiple allocation hub location problem: Formulations and algorithms

In this paper we consider and present formulations and solution approaches for the capacitated multiple allocation hub location problem. We present a new mixed integer linear programming formulation for the problem. We also construct an efficient heuristic algorithm, using shortest paths. We incorporate the upper bound obtained from this heuristic in a linear-programming-based branch-and-bound solution procedure. We present the results of extensive computational experience with both the heuristic and the exact methods.     

Numerical solution of a long-term average control problem for singular stochastic processes

This paper analyzes numerically a long-term average stochastic control problem involving a controlled diffusion on a bounded region. The solution technique takes advantage of an infinite-dimensional linear programming formulation for the problem which relates the stationary measures to the generators of the diffusion. The restriction of the diffusion to an interval is accomplished through reflection at one end point and a jump operator acting singularly in time at the other end point. Different approximations of the linear program are obtained using finite differences for the differential operators (a Markov chain approximation to the diffusion) and using a finite element method to approximate the stationary density. The numerical results are compared with each other and with dynamic programming. This research has been supported in part by the U.S. National Security Agency under Grant Agreement Number H98230-05-1-0062. The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation herein.     

Multi-resource allocation in stochastic project scheduling

We propose a resource allocation model for project scheduling. Our model accommodates multiple resources and decision-dependent activity durations inspired by microeconomic theory. First, we elaborate a deterministic problem formulation. In a second stage, we enhance this model to account for uncertain problem parameters. Assuming that the first and second moments of these parameters are known, the stochastic model minimises an approximation of the value-at-risk of the project makespan. As a salient feature, our approach employs a scenario-free formulation which is based on normal approximations of the activity path durations. We extend our model to situations in which the moments of the random parameters are ambiguous and describe an iterative solution procedure. Extensive numerical results are provided.     

Planning logistics operations in the oil industry

In this paper we apply stochastic programming modelling and solution techniques to planning problems for a consortium of oil companies. A multiperiod supply, transformation and distribution scheduling problem—the Depot and Refinery Optimization Problem (DROP)—is formulated for strategic or tactical level planning of the consortium's activities. This deterministic model is used as a basis for implementing a stochastic programming formulation with uncertainty in the product demands and spot supply costs (DROPS), whose solution process utilizes the deterministic equivalent linear programming problem. We employ our STOCHGEN general purpose stochastic problem generator to ‘recreate’ the decision (scenario) tree for the unfolding future as this deterministic equivalent. To project random demands for oil products at different spatial locations into the future and to generate random fluctuations in their future prices/costs a stochastic input data simulator is developed and calibrated to historical industry data. The models are written in the modelling language XPRESS-MP and solved by the XPRESS suite of linear programming solvers. From the viewpoint of implementation of large-scale stochastic programming models this study involves decisions in both space and time and careful revision of the original deterministic formulation. The first part of the paper treats the specification, generation and solution of the deterministic DROP model. The stochastic version of the model (DROPS) and its implementation are studied in detail in the second part and a number of related research questions and implications discussed.     

Robust energy planning in buildings with energy and comfort costs

Energy management in buildings is addressed in this paper. The energetic impact of buildings in the current energetic context is first depicted. Then the studied optimization problem is defined as the optimal management of production and consumption activities in houses. A scheduling problem is identified to adjust the energy consumption to both the energy cost and the inhabitant’s comfort. The available flexibilities of the services provided by domestic appliances are used to compute optimal energy plans. These flexibilities are associated to time windows or heating storage abilities. A constraints formulation of the energy allocation problem is given. A derived mixed linear program is used to solve this problem. The energy consumption in houses is very dependent to uncertain data such as weather forecasts and inhabitants’ activities. Parametric uncertainties are introduced in the home energy management problem in order to provide robust energy allocation. Robust linear programming is implemented. Event related uncertainties are also addressed through stochastic programming in order to take into account the inhabitant’s activities. A scenario based approach is implemented to face this robust optimization problem.     

On the formulation of stochastic linear programs using algebraic modelling languages

This paper considers extensions to algebraic modelling languages to support formulation, instantiation and solver integration for stochastic linear programs (SLPs). We present a taxonomy of SLP problem types and analyze formulation requirements including distribution handling by class of problem. We demonstrate suggested formulations for most problem classes, show solver input in the S-MPS standard, and propose consistency checks for constraints involving stochastic data items. Some unresolved difficulties are identified.     

Solution approaches for the multiobjective stochastic programming

We survey in this paper various solution approaches for multiobjective stochastic problems where random variables can be in both objectives and constraints parameters. Once a problem requires a stochastic formulation, a first step consists in transforming the problem into its deterministic formulation. We propose to classify and evaluate such transformations with regards to the many proposed concepts of efficiency. The paper addresses also some applications of the multiobjective stochastic programming models.     

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.     

Using matrix approximation for high-dimensional discrete optimization problems: Server consolidation based on cyclic time-series data

We consider the assignment of enterprise applications in virtual machines to physical servers, also known as server consolidation problem. Data center operators try to minimize the number of servers, but at the same time provide sufficient computing resources at each point in time. While historical workload data would allow for accurate workload forecasting and optimal allocation of enterprise applications to servers, the volume of data and the large number of resulting capacity constraints in a mathematical problem formulation renders this task impossible for any but small instances. We use singular value decomposition (SVD) to extract significant features from a large constraint matrix and provide a new geometric interpretation of these features, which allows for allocating large sets of applications efficiently to physical servers with this new formulation. While SVD is typically applied for purposes such as time series decomposition, noise filtering, or clustering, in this paper features are used to transform the original allocation problem into a low-dimensional integer program with only the extracted features in a much smaller constraint matrix. We evaluate the approach using workload data from a large data center and show that it leads to high solution quality, but at the same time allows for solving considerably larger problem instances than what would be possible without data reduction and model transform. The overall approach could also be applied to similar packing problems in service operations management.     

A constraint generation scheme to probabilistic linear problems with an application to power system expansion planning

In this paper, we first describe a constraint generation scheme for probabilistic mixed integer programming problems. Next, we present a decomposition approach to the peak capacity expansion planning of interconnected hydrothermal generating systems, with bounds on the transmission capacity between the regions. The objective is to minimize investments in generating units and interconnection links, subject to constraints on supply reliability. The problem is formulated as a stochastic integer program. The constraint generation scheme, which is similar to Benders decomposition, is applied in the solution of the peak capacity expansion problem. The master problem in this decomposition scheme is an integer program, solved by implicit enumeration. The operating subproblem corresponds to a stochastic network flow problem, and is solved by a maximum flow algorithm and Monte Carlo simulation. The approach is illustrated through a case study involving the expansion of the system of the Brazilian Southeastern region.     

Capacity allocation problem with random demands for the rail container carrier

In this paper, we consider the formulation and heuristic algorithm for the capacity allocation problem with random demands in the rail container transportation. The problem is formulated as the stochastic integer programming model taking into account matches in supply and demand of rail container transportation. A heuristic algorithm for the stochastic integer programming model is proposed. The solution to the model is found by maximizing the expected total profit over the possible control decisions under the uncertainty of demands. Finally, we give numerical experiments to demonstrate the efficiency of the heuristic algorithm.     

Improving constants of strong convexity in linear stochastic programming

We derive formulas for constants of strong convexity (CSCs) of expectation functions encountered in two-stage stochastic programs with linear recourse. One of them yields a CSC as the optimal value of a certain quadratically constrained quadratic program, another one in terms of the thickness of the feasibility polytope of the dual problem associated to the recourse problem. CSCs appear in Hoelder-type estimates relating the distance of optimal solution sets of stochastic programs to a suitable distance of underlying probability distributions.