On the convex hull of the simple integer recourse objective function

We consider the objective function of a simple integer recourse problem with fixed technology matrix.Using properties of the expected value function, we prove a relation between the convex hull of this function and the expected value function of a continuous simple recourse program.We present an algorithm to compute the convex hull of the expected value function in case of discrete right-hand side random variables. Allowing for restrictions on the first stage decision variables, this result is then extended to the convex hull of the objective function.Supported by the National Operations Research Network in the Netherlands (LNMB).     

Convergent Bounds for Stochastic Programs with Expected Value Constraints

This article describes a bounding approximation scheme for convex multistage stochastic programs (MSP) that constrain the conditional expectation of some decision-dependent random variables. Expected value constraints of this type are useful for modelling a decision maker’s risk preferences, but they may also arise as artifacts of stage-aggregation. We develop two finite-dimensional approximate problems that provide bounds on the (infinite-dimensional) original problem, and we show that the gap between the bounds can be made smaller than any prescribed tolerance. Moreover, the solutions of the approximate MSPs give rise to a feasible policy for the original MSP, and this policy’s optimality gap is shown to be smaller than the difference of the bounds. The considered problem class comprises models with integrated chance constraints and conditional value-at-risk constraints. No relatively complete recourse is assumed.     

A tighter variant of Jensen’s lower bound for stochastic programs and separable approximations to recourse functions

In this paper, we propose a new method to compute lower bounds on the optimal objective value of a stochastic program and show how this method can be used to construct separable approximations to the recourse functions. We show that our method yields tighter lower bounds than Jensen’s lower bound and it requires a reasonable amount of computational effort even for large problems. The fundamental idea behind our method is to relax certain constraints by associating dual multipliers with them. This yields a smaller stochastic program that is easier to solve. We particularly focus on the special case where we relax all but one of the constraints. In this case, the recourse functions of the smaller stochastic program are one dimensional functions. We use these one dimensional recourse functions to construct separable approximations to the original recourse functions. Computational experiments indicate that our lower bounds can significantly improve Jensen’s lower bound and our recourse function approximations can provide good solutions.     

The value of the stochastic solution in stochastic linear programs with fixed recourse

Stochastic linear programs have been rarely used in practical situations largely because of their complexity. In evaluating these problems without finding the exact solution, a common method has been to find bounds on the expected value of perfect information. In this paper, we consider a different method. We present bounds on the value of the stochastic solution, that is, the potential benefit from solving the stochastic program over solving a deterministic program in which expected values have replaced random parameters. These bounds are calculated by solving smaller programs related to the stochastic recourse problem.This paper is an extension of part of the author's dissertation in the Department of Operations Research, Stanford University, Stanford, California. The research was supported at Stanford by the Department of Energy under Contract DE-AC03-76SF00326, PA#DE-AT03-76ER72018, Office of Naval Research under Contract N00014-75-C-0267 and the National Science Foundation under Grants MCS76-81259, MCS-7926009 and ECS-8012974 (formerly ENG77-06761).     

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.     

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.     

Monotonic bounds in multistage mixed-integer stochastic programming

Multistage stochastic programs bring computational complexity which may increase exponentially with the size of the scenario tree in real case problems. For this reason approximation techniques which replace the problem by a simpler one and provide lower and upper bounds to the optimal value are very useful. In this paper we provide monotonic lower and upper bounds for the optimal objective value of a multistage stochastic program. These results also apply to stochastic multistage mixed integer linear programs. Chains of inequalities among the new quantities are provided in relation to the optimal objective value, the wait-and-see solution and the expected result of using the expected value solution. The computational complexity of the proposed lower and upper bounds is discussed and an algorithmic procedure to use them is provided. Numerical results on a real case transportation problem are presented.     

Convex relaxations of chance constrained optimization problems

In this paper we develop convex relaxations of chance constrained optimization problems in order to obtain lower bounds on the optimal value. Unlike existing statistical lower bounding techniques, our approach is designed to provide deterministic lower bounds. We show that a version of the proposed scheme leads to a tractable convex relaxation when the chance constraint function is affine with respect to the underlying random vector and the random vector has independent components. We also propose an iterative improvement scheme for refining the bounds.     

Stochastic programming with simple integer recourse

Stochastic integer programs are notoriously difficult. Very few properties are known and solution algorithms are very scarce. In this paper, we introduce the class of stochastic programs with simple integer recourse, a natural extension of the simple recourse case extensively studied in stochastic continuous programs.Analytical as well as computational properties of the expected recourse function of simple integer recourse problems are studied. This includes sharp bounds on this function and the study of the convex hull. Finally, a finite termination algorithm is obtained that solves two classes of stochastic simple integer recourse problems.Supported by the National Operations Research Network in the Netherlands (LNMB).     

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.     

Optimal production run length for deteriorating production system with a two-state continuous-time Markovian processes under allowable shortages

The paper studies optimal production run length for a deteriorating production system in which the shortages are allowed and the deterioration processes are characterized by a two-state continuous-time Markov chain. We show that there exists a unique optimal production run length to minimize the expected total relevant cost. In addition, bounds for the optimal production run length are provided to develop the solution procedure. Finally, a numerical example is given to illustrate the results and sensitivity analysis is also performed     

Decomposition strategy for the stochastic pooling problem

The stochastic pooling problem is a type of stochastic mixed-integer bilinear program arising in the integrated design and operation of various important industrial networks, such as gasoline blending, natural gas production and transportation, water treatment, etc. This paper presents a rigorous decomposition method for the stochastic pooling problem, which guarantees finding an ${\epsilon}$ -optimal solution with a finite number of iterations. By convexification of the bilinear terms, the stochastic pooling problem is relaxed into a lower bounding problem that is a potentially large-scale mixed-integer linear program (MILP). Solution of this lower bounding problem is then decomposed into a sequence of relaxed master problems, which are MILPs with much smaller sizes, and primal bounding problems, which are linear programs. The solutions of the relaxed master problems yield a sequence of nondecreasing lower bounds on the optimal objective value, and they also generate a sequence of integer realizations defining the primal problems which yield a sequence of nonincreasing upper bounds on the optimal objective value. The decomposition algorithm terminates finitely when the lower and upper bounds coincide (or are close enough), or infeasibility of the problem is indicated. Case studies involving two example problems and two industrial problems demonstrate the dramatic computational advantage of the proposed decomposition method over both a state-of-the-art branch-and-reduce global optimization method and explicit enumeration of integer realizations, particularly for large-scale problems.     

Quantitative stability of full random two-stage stochastic programs with recourse

In this paper, we consider quantitative stability analysis for two-stage stochastic linear programs when recourse costs, the technology matrix, the recourse matrix and the right-hand side vector are all random. For this purpose, we first investigate continuity properties of parametric linear programs. After deriving an explicit expression for the upper bound of its feasible solutions, we establish locally Lipschitz continuity of the feasible solution sets of parametric linear programs. These results are then applied to prove continuity of the generalized objective function derived from the full random second-stage recourse problem, from which we derive new forms of quantitative stability results of the optimal value function and the optimal solution set with respect to the Fortet–Mourier probability metric. The obtained results are finally applied to establish asymptotic behavior of an empirical approximation algorithm for full random two-stage stochastic programs.     

New upper bounds for the two-dimensional orthogonal non-guillotine cutting stock problem

The two-dimensional orthogonal non-guillotine cutting stockproblem (NGCP) appears in many industries (e.g. the wood andsteel industries) and consists of cutting a rectangular mastersurface into a number of rectangular pieces, each with a givensize and value. The pieces must be cut with their edges alwaysparallel to the edges of the master surface (orthogonal cuts).The objective is to maximize the total value of the pieces cut. New upper bounds on the optimal solution to the NGCP are described.The new bounding procedures are obtained by different relaxationsof a new mathematical formulation of the NGCP. Various proceduresfor strengthening the resulting upper bounds and reducing thesize of the original problem are discussed. The proposed newupper bounds have been experimentally evaluated on test problemsderived from the literature. Comparisons with previous boundingprocedures from the literature are given. The computationalresults indicate that these bounds are significantly betterthan the bounds proposed in the literature.     

Quantitative stability of mixed-integer two-stage quadratic stochastic programs

For our introduced mixed-integer quadratic stochastic program with fixed recourse matrices, random recourse costs, technology matrix and right-hand sides, we study quantitative stability properties of its optimal value function and optimal solution set when the underlying probability distribution is perturbed with respect to an appropriate probability metric. To this end, we first establish various Lipschitz continuity results about the value function and optimal solutions of mixed-integer parametric quadratic programs with parameters in the linear part of the objective function and in the right-hand sides of linear constraints. The obtained results extend earlier results about quantitative stability properties of stochastic integer programming and stability results for mixed-integer parametric quadratic programs.     

Bounds on the value of information in uncertain decision problems II†

In most stochastic decision problems one has the opportunity to collect information that would partially or totally eliminate the inherent uncertainty. One wishes to compare the cost and value of such information in terms of the decision maker's preferences to determine an optimal information gathering plan. The calculation of the value of information generally involves oneor more stochastic recourse problems as well as one or more expected value distribution problems. The difficulty and costs of obtaining solutions to these problems has led to a focus on the development of upper and lower bounds on the various subproblems that yield bounds on the value of information. In this paper we discuss published and new bounds for static problems with linear and concave preference functions for partial and perfect information. We also provide numerical examples utilizing simple production and investment problems that illustrate the calculations involved in the computation of the various bounds and provide a setting for a comparison of the bounds that yields some tentative guidelines for their use. The bounds compared are the Jensen's Inequality bound,the Conditional Jensen's Inequality bound and the Generalized Jensen and Edmundson-Madansky bounds.     

A level-2 reformulation–linearization technique bound for the quadratic assignment problem

This paper studies polyhedral methods for the quadratic assignment problem. Bounds on the objective value are obtained using mixed 0–1 linear representations that result from a reformulation–linearization technique (rlt). The rlt provides different “levels” of representations that give increasing strength. Prior studies have shown that even the weakest level-1 form yields very tight bounds, which in turn lead to improved solution methodologies. This paper focuses on implementing level-2. We compare level-2 with level-1 and other bounding mechanisms, in terms of both overall strength and ease of computation. In so doing, we extend earlier work on level-1 by implementing a Lagrangian relaxation that exploits block-diagonal structure present in the constraints. The bounds are embedded within an enumerative algorithm to devise an exact solution strategy. Our computer results are notable, exhibiting a dramatic reduction in nodes examined in the enumerative phase, and allowing for the exact solution of large instances.     

Second-order matrix concentration inequalities

Matrix concentration inequalities give bounds for the spectral-norm deviation of a random matrix from its expected value. These results have a weak dimensional dependence that is sometimes, but not always, necessary. This paper identifies one of the sources of the dimensional term and exploits this insight to develop sharper matrix concentration inequalities. In particular, this analysis delivers two refinements of the matrix Khintchine inequality that use information beyond the matrix variance to improve the dimensional dependence.     

Sublinear upper bounds for stochastic programs with recourse

Separable sublinear functions are used to provide upper bounds on the recourse function of a stochastic program. The resulting problem's objective involves the inf-convolution of convex functions. A dual of this problem is formulated to obtain an implementable procedure to calculate the bound. Function evaluations for the resulting convex program only require a small number of single integrations in contrast with previous upper bounds that require a number of function evaluations that grows exponentially in the number of random variables. The sublinear bound can often be used when other suggested upper bounds are intractable. Computational results indicate that the sublinear approximation provides good, efficient bounds on the stochastic program objective value.This research has been partially supported by the National Science Foundation. The first author's work was also supported in part by Office of Naval Research Grant N00014-86-K-0628 and by the National Research Council under a Research Associateship at the Naval Postgraduate School, Monterey, California.     

Branch-and-Sandwich: a deterministic global optimization algorithm for optimistic bilevel programming problems. Part I: Theoretical development

We present a global optimization algorithm, Branch-and-Sandwich, for optimistic bilevel programming problems that satisfy a regularity condition in the inner problem. The functions involved are assumed to be nonconvex and twice continuously differentiable. The proposed approach can be interpreted as the exploration of two solution spaces (corresponding to the inner and the outer problems) using a single branch-and-bound tree. A novel branching scheme is developed such that classical branch-and-bound is applied to both spaces without violating the hierarchy in the decisions and the requirement for (global) optimality in the inner problem. To achieve this, the well-known features of branch-and-bound algorithms are customized appropriately. For instance, two pairs of lower and upper bounds are computed: one for the outer optimal objective value and the other for the inner value function. The proposed bounding problems do not grow in size during the algorithm and are obtained from the corresponding problems at the parent node.