Applying the minimax criterion in stochastic recourse programs

We consider an optimization problem in which some uncertain parameters are replaced by random variables. The minimax approach to stochastic programming concerns the problem of minimizing the worst expected value of the objective function with respect to the set of probability measures that are consistent with the available information on the random data. Only very few practicable solution procedures have been proposed for this problem and the existing ones rely on simplifying assumptions. In this paper, we establish a number of stability results for the minimax stochastic program, justifying in particular the approach of restricting attention to probability measures with support in some known finite set. Following this approach, we elaborate solution procedures for the minimax problem in the setting of two-stage stochastic recourse models, considering the linear recourse case as well as the integer recourse case. Since the solution procedures are modifications of well-known algorithms, their efficacy is immediate from the computational testing of these procedures and we do not report results of any computational experiments.     

A simple recourse model for power dispatch under uncertain demand

Optimal power dispatch under uncertainty of power demand is tackled via a stochastic programming model with simple recourse. The decision variables correspond to generation policies of a system comprising thermal units, pumped storage plants and energy contracts. The paper is a case study to test the kernel estimation method in the context of stochastic programming. Kernel estimates are used to approximate the unknown probability distribution of power demand. General stability results from stochastic programming yield the asymptotic stability of optimal solutions. Kernel estimates lead to favourable numerical properties of the recourse model (no numerical integration, the optimization problem is smooth convex and of moderate dimension). Test runs based on real-life data are reported. We compute the value of the stochastic solution for different problem instances and compare the stochastic programming solution with deterministic solutions involving adjusted demand portions.This research is supported by the Schwerpunktprogramm Anwendungsbezogene Optimierung und Steuerung of the Deutsche Forschungsgemeinschaft.     

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.

     

Plastic Structural Analysis Under Stochastic Uncertainty

Problems from limit load or shakedown analysis are based on the convex, linear or linearized yield/strength condition and the linear equilibrium equation for the generic stress vector. Having to take into account, in practice, stochastic variations of the model parameters (e.g., yield stresses, plastic capacities) and external loadings, the basic stochastic plastic analysis problem must be replaced by an appropriate deterministic substitute problem. Instead of calculating approximatively the probability of failure based on a certain choice of failure modes, here, a direct approach is presented based on the costs for missing carrying capacity and the failure costs (e.g., costs for damage, repair, compensation for weakness within the structure, etc.). Based on the basic mechanical survival conditions, the failure costs may be represented by the minimum value of a convex and often linear program. Several mathematical properties of this program are shown. Minimizing then the total expected costs subject to the remaining (simple) deterministic constraints, a stochastic optimization problem is obtained which may be represented by a “Stochastic Convex Program (SCP) with recourse”. Working with linearized yield/strength conditions, a “Stochastic Linear Program (SLP) with complete fixed recourse” is obtained. In case of a discretely distributed probability distribution or after the discretization of a more general probability distribution of the random structural parameters and loadings as well as certain random cost factors one has a linear program (LP) with a so-called “dual decomposition data” structure. For stochastic programs of this type many theoretical results and efficient numerical solution procedures (LP-solver) are available. The mathematical properties of theses substitute problems are considered. Furthermore approximate analytical formulas for the limit load factor are given.     

Restricted recourse strategies for bounding the expected network recourse function

This paper presents bounds for the expected recourse function for stochastic programs with network recourse. Cyclic recourse, a concept introduced by Wallace [18], allows the approximation of the recourse problem by restricting the optimal flows on a set of cycles and by augmenting the original network to induce separability. We introduce a new procedure that uses again a set of cycles but does not approximate the problem; instead it solves it heuristically without altering the original network or requiring separability. The method produces tighter bounds and is computationally feasible for large networks. Numerical experiments with selected networks illustrate the effectiveness of the approach.     

A compromise solution for the multiobjective stochastic linear programming under partial uncertainty

This paper solves the multiobjective stochastic linear program with partially known probability. We address the case where the probability distribution is defined by crisp inequalities. We propose a chance constrained approach and a compromise programming approach to transform the multiobjective stochastic linear program with linear partial information on probability distribution into its equivalent uniobjective problem. The resulting program is then solved using the modified L-shaped method. We illustrate our results by an example.     

Convergent Cutting-Plane and Partial-Sampling Algorithm for Multistage Stochastic Linear Programs with Recourse

We propose an algorithm for multistage stochastic linear programs with recourse where random quantities in different stages are independent. The algorithm approximates successively expected recourse functions by building up valid cutting planes to support these functions from below. In each iteration, for the expected recourse function in each stage, one cutting plane is generated using the dual extreme points of the next-stage problem that have been found so far. We prove that the algorithm is convergent with probability one.     

Aspiration level approach in stochastic MCDM problems

The paper considers a discrete stochastic multiple criteria decision making problem. This problem is defined by a finite set of actions A, a set of attributes X and a set of evaluations of actions with respect to attributes E. In stochastic case the evaluation of each action with respect to each attribute takes form of a probability distribution. Thus, the comparison of two actions leads to the comparison of two vectors of probability distributions. In the paper a new procedure for solving this problem is proposed. It is based on three concepts: stochastic dominance, interactive approach, and preference threshold. The idea of the procedure comes from the interactive multiple objective goal programming approach. The set of actions is progressively reduced as the decision maker specifies additional requirements. At the beginning the decision maker is asked to define preference threshold for each attribute. Next, at each iteration the decision maker is confronted with the set of considered actions. If the decision maker is able to make a final choice then the procedure ends, otherwise he/she is asked to specify aspiration level. A didactical example is presented to illustrate the proposed technique.     

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.     

Stochastic linear programs with restricted recourse

Stochastic programs with recourse provide an effective modeling paradigm for sequential decision problems with uncertain or noisy data, when uncertainty can be modeled by a discrete set of scenarios. In two-stage problems the decision variables are partitioned into two groups: a set of structural, first-stage decisions, and a set of second-stage, recourse decisions. The structural decisions are scenario-invariant, but the recourse decisions are scenario-dependent and can vary substantially across scenarios. In several applications it is important to restrict the variability of recourse decisions across scenarios, or to investigate the tradeoffs between the stability of recourse decisions and expected cost of a solution.We present formulations of stochastic programs with restricted recourse that trade off recourse stability with expected cost. The models generate a sequence of solutions to which recourse robustness is progressively enforced via parameterized, satisficing constraints. We investigate the behavior of the models on several test cases, and examine the performance of solution procedures based on the primal-dual interior point method.     

A Polynomial-Time Solution Scheme for Quadratic Stochastic Programs

We consider quadratic stochastic programs with random recourse—a class of problems which is perceived to be computationally demanding. Instead of using mainstream scenario tree-based techniques, we reduce computational complexity by restricting the space of recourse decisions to those linear and quadratic in the observations, thereby obtaining an upper bound on the original problem. To estimate the loss of accuracy of this approach, we further derive a lower bound by dualizing the original problem and solving it in linear and quadratic recourse decisions. By employing robust optimization techniques, we show that both bounding problems may be approximated by tractable conic programs.     

Measures as Lagrange multipliers in multistage stochastic programming

A duality theory is developed for multistage convex stochastic programming problems whose decision (or recourse) functions can be approximated by continuous functions satisfying the same constraints. Necessary and sufficient conditions for optimality are obtained in terms of the existence of multipliers in the class of regular Borel measures on the underlying probability space, these being decomposable, of course, into absolutely continuous and singular components with respect to the given probability measure. This provides an alternative to the approach where the multipliers are elements of the dual of $\text{L}$^∞ with an analogous decomposition. However, besides the existence of strictly feasible solutions, special regularity conditions are required, such as the “laminarity” of the probability measure, a property introduced in an earlier paper. These are crucial in ensuring that the minimum in the optimization problem can indeed be approached by continuous functions.     

An algorithm for approximating piecewise linear concave functions from sample gradients

An effective algorithm for solving stochastic resource allocation problems is to build piecewise linear, concave approximations of the recourse function based on sample gradient information. Algorithms based on this approach are proving useful in application areas such as the newsvendor problem, physical distribution and fleet management. These algorithms require the adaptive estimation of the approximations of the recourse function that maintain concavity at every iteration. In this paper, we prove convergence for a particular version of an algorithm that produces approximations from stochastic gradient information while maintaining concavity.     

Prepositioning can improve the performance of a dynamic stochastic on-demand public bus system

This paper presents the first application of prepositioning in the context of the dynamic stochastic on-demand bus routing problem (DODBRP). The DODBRP is a large-scale dial-a-ride problem that involves bus station assignment and aims to minimize the total user ride time (URT) by simultaneously assigning passengers to alternative stations and determining optimal bus routes.In the DODBRP, transportation requests are introduced dynamically, and buses are dispatched to stations with known requests. This paper investigates the concept of prepositioning, which involves sending buses not only to currently known requests but also to requests that are likely to appear in the future, based on a given probability.To solve this dynamic and stochastic ODBRP, the paper proposes a heuristic algorithm based on variable neighborhood search (VNS). The algorithm considers multiple scenarios to represent different realizations of the stochastic requests.Experimental results demonstrate the superiority of the prepositioning approach over the DODBRP across various levels of forecast accuracy, lengths of time bucket, and probabilities of realization. Furthermore, the paper shows that removing empty stations as a recourse action can further enhance solution quality. Additionally, in situations with low prediction accuracy, increasing the number of scenarios can lead to improved solutions. Finally, a combination of prepositioning, empty station removal, and the insertion of dynamic requests proves to be effective.Overall, the findings of this paper provide valuable insights into the application of prepositioning in the dynamic stochastic on-demand bus routing problem, highlighting its potential for addressing real-world transportation challenges.     

A probability metrics approach for reducing the bias of optimality gap estimators in two-stage stochastic linear programming

Monte Carlo sampling-based estimators of optimality gaps for stochastic programs are known to be biased. When bias is a prominent factor, estimates of optimality gaps tend to be large on average even for high-quality solutions. This diminishes our ability to recognize high-quality solutions. In this paper, we present a method for reducing the bias of the optimality gap estimators for two-stage stochastic linear programs with recourse via a probability metrics approach, motivated by stability results in stochastic programming. We apply this method to the Averaged Two-Replication Procedure (A2RP) by partitioning the observations in an effort to reduce bias, which can be done in polynomial time in sample size. We call the resulting procedure the Averaged Two-Replication Procedure with Bias Reduction (A2RP-B). We provide conditions under which A2RP-B produces strongly consistent point estimators and an asymptotically valid confidence interval. We illustrate the effectiveness of our approach analytically on a newsvendor problem and test the small-sample behavior of A2RP-B on a number of two-stage stochastic linear programs from the literature. Our computational results indicate that the procedure effectively reduces bias. We also observe variance reduction in certain circumstances.     

Designing a two-echelon distribution network under demand uncertainty

This paper proposes a comprehensive methodology for the stochastic multi-period two-echelon distribution network design problem (2E-DDP) where product flows to ship-to-points are directed from an upper layer of primary warehouses to distribution platforms (DPs) before being transported to the ship-to-points. A temporal hierarchy characterizes the design level dealing with DP location and capacity decisions, as well as the operational level involving transportation decisions as origin-destination flows. These design decisions must be calibrated to minimize the expected distribution cost associated with the two-echelon transportation schema on this network under stochastic demand. We consider a multi-period planning horizon where demand varies dynamically from one planning period to the next. Thus, the design of the two-echelon distribution network under uncertain customer demand gives rise to a complex multi-stage decisional problem. Given the strategic structure of the problem, we introduce alternative modeling approaches based on two-stage stochastic programming with recourse. We solve the resulting models using a Benders decomposition approach. The size of the scenario set is tuned using the sample average approximation (SAA) approach. Then, a scenario-based evaluation procedure is introduced to post-evaluate the design solutions obtained. We conduct extensive computational experiments based on several types of instances to validate the proposed models and assess the efficiency of the solution approaches. The evaluation of the quality of the stochastic solution underlines the impact of uncertainty in the two-echelon distribution network design problem (2E-DDP).     

Conditioning of linear-quadratic two-stage stochastic optimization problems

In this paper a condition number for linear-quadratic two-stage stochastic optimization problems is introduced as the Lipschitz modulus of the multifunction assigning to a (discrete) probability distribution the solution set of the problem. Being the outer norm of the Mordukhovich coderivative of this multifunction, the condition number can be estimated from above explicitly in terms of the problem data by applying appropriate calculus rules. Here, a chain rule for the extended partial second-order subdifferential recently proved by Mordukhovich and Rockafellar plays a crucial role. The obtained results are illustrated for the example of two-stage stochastic optimization problems with simple recourse.     

The Multi-Handler Knapsack Problem under Uncertainty

The Multi-Handler Knapsack Problem under Uncertainty is a new stochastic knapsack problem where, given a set of items, characterized by volume and random profit, and a set of potential handlers, we want to find a subset of items which maximizes the expected total profit. The item profit is given by the sum of a deterministic profit plus a stochastic profit due to the random handling costs of the handlers. On the contrary of other stochastic problems in the literature, the probability distribution of the stochastic profit is unknown. By using the asymptotic theory of extreme values, a deterministic approximation for the stochastic problem is derived. The accuracy of such a deterministic approximation is tested against the two-stage with fixed recourse formulation of the problem. Very promising results are obtained on a large set of instances in negligible computing time.     

Quantitative stability of full random two-stage problems with quadratic recourse

ABSTRACT

In this paper, we discuss quantitative stability of two-stage stochastic programs with quadratic recourse where all parameters in the second-stage problem are random. By establishing the Lipschitz continuity of the feasible set mapping of the restricted Wolfe dual of the second-stage quadratic programming in terms of the Hausdorff distance, we prove the local Lipschitz continuity of the integrand of the objective function of the two-stage stochastic programming problem and then establish quantitative stability results of the optimal values and the optimal solution sets when the underlying probability distribution varies under the Fortet–Mourier metric. Finally, the obtained results are applied to study the asymptotic behaviour of the empirical approximation of the model.