A linear programming approach for linear programs with probabilistic constraints

We study a class of mixed-integer programs for solving linear programs with joint probabilistic constraints from random right-hand side vectors with finite distributions. We present greedy and dual heuristic algorithms that construct and solve a sequence of linear programs. We provide optimality gaps for our heuristic solutions via the linear programming relaxation of the extended mixed-integer formulation of Luedtke et al. (2010) [13] as well as via lower bounds produced by their cutting plane method. While we demonstrate through an extensive computational study the effectiveness and scalability of our heuristics, we also prove that the theoretical worst-case solution quality for these algorithms is arbitrarily far from optimal. Our computational study compares our heuristics against both the extended mixed-integer programming formulation and the cutting plane method of Luedtke et al. (2010) [13]. Our heuristics efficiently and consistently produce solutions with small optimality gaps, while for larger instances the extended formulation becomes intractable and the optimality gaps from the cutting plane method increase to over 5%.     

A simulation-based approach to two-stage stochastic programming with recourse

In this paper we consider stochastic programming problems where the objective function is given as an expected value function. We discuss Monte Carlo simulation based approaches to a numerical solution of such problems. In particular, we discuss in detail and present numerical results for two-stage stochastic programming with recourse where the random data have a continuous (multivariate normal) distribution. We think that the novelty of the numerical approach developed in this paper is twofold. First, various variance reduction techniques are applied in order to enhance the rate of convergence. Successful application of those techniques is what makes the whole approach numerically feasible. Second, a statistical inference is developed and applied to estimation of the error, validation of optimality of a calculated solution and statistically based stopping criteria for an iterative alogrithm. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Supported by CNPq (Conselho Nacional de Desenvolvimento Científico e Tecnológico), Brasília, Brazil, through a Doctoral Fellowship under grant 200595/93-8.     

An integer programming approach for linear programs with probabilistic constraints

Linear programs with joint probabilistic constraints (PCLP) are difficult to solve because the feasible region is not convex. We consider a special case of PCLP in which only the right-hand side is random and this random vector has a finite distribution. We give a mixed-integer programming formulation for this special case and study the relaxation corresponding to a single row of the probabilistic constraint. We obtain two strengthened formulations. As a byproduct of this analysis, we obtain new results for the previously studied mixing set, subject to an additional knapsack inequality. We present computational results which indicate that by using our strengthened formulations, instances that are considerably larger than have been considered before can be solved to optimality.     

A multicut algorithm for two-stage stochastic linear programs

Outer linearization methods, such as Van Slyke and West's L-shaped method for stochastic linear programs, generally apply a single cut on the nonlinear objective at each major iteration. The structure of stochastic programs allows for several cuts to be placed at once. This paper describes a multicut algorithm to carry out this procedure. It presents experimental and theoretical justification for reductions in major iterations.     

A regularized stochastic decomposition algorithm for two-stage stochastic linear programs

In this paper a regularized stochastic decomposition algorithm with master programs of finite size is described for solving two-stage stochastic linear programming problems with recourse. In a deterministic setting cut dropping schemes in decomposition based algorithms have been used routinely. However, when only estimates of the objective function are available such schemes can only be properly justified if convergence results are not sacrificed. It is shown that almost surely every accumulation point in an identified subsequence of iterates produced by the algorithm, which includes a cut dropping scheme, is an optimal solution. The results are obtained by including a quadratic proximal term in the master program. In addition to the cut dropping scheme, other enhancements to the existing methodology are described. These include (i) a new updating rule for the retained cuts and (ii) an adaptive rule to determine when additional reestimation of the cut associated with the current solution is needed. The algorithm is tested on problems from the literature assuming both descrete and continuous random variables.A majority of this work is part of the author's Ph.D. dissertation prepared at the University of Arizona in 1990.     

An inexact approach to solving linear semi-infinite programming problems

In this paper, we propose an “inexact solution” approach to deal with linear semi-infinite programming problems with finitely many variables and infinitely many constraints over a compact metric space. A general convergence proof with some numerical examples are given and the advantages of using this approach are discussed     

A two-stage approach for bi-objective integer linear programming

We present a new exact approach for solving bi-objective integer linear programs. The new approach employs two of the existing exact algorithms in the literature, including the balanced box and the $?$-constraint methods, in two stages. A computationally study shows that the new approach has three desirable characteristics. (1) It solves less single-objective integer linear programs. (2) Its solution time is significantly smaller. (3) It is competitive with the two-stage algorithm proposed by Leitner et al. (2016).     

A stochastic linear programming approach to hierarchical production planning

This paper examines production planning decisions. The process is formulated as a hierarchical production planning (HPP) model under uncertain demand. A review of HPP articles indicates that while current models do consider uncertainty as a part of their solution methods, a deficiency persists since these models fail to incorporate the uncertain demand explicitly in the formulation of the problem. A stochastic linear programming model (SLP) is proposed to better reflect reality and to provide a superior solution. The model remains computationally tractable despite the precise incorporation of uncertainty and the imposition of penalties when constraints are violated. A problem is introduced which illustrates the superiority of the proposed model over those currently being applied.     

A model of distributionally robust two-stage stochastic convex programming with linear recourse

We consider distributionally robust two-stage stochastic convex programming problems, in which the recourse problem is linear. Other than analyzing these new models case by case for different ambiguity sets, we adopt a unified form of ambiguity sets proposed by Wiesemann, Kuhn and Sim, and extend their analysis from a single stochastic constraint to the two-stage stochastic programming setting. It is shown that under a standard set of regularity conditions, this class of problems can be converted to a conic optimization problem. Numerical results are presented to show the efficiency of the distributionally robust approach.     

A Log-Barrier method with Benders decomposition for solving two-stage stochastic linear programs

An algorithm incorporating the logarithmic barrier into the Benders decomposition technique is proposed for solving two-stage stochastic programs. Basic properties concerning the existence and uniqueness of the solution and the underlying path are studied. When applied to problems with a finite number of scenarios, the algorithm is shown to converge globally and to run in polynomial-time. Received: August 1998 / Accepted: August 2000?Published online April 12, 2001     

Adaptive multicut aggregation for two-stage stochastic linear programs with recourse

Outer linearization methods for two-stage stochastic linear programs with recourse, such as the L-shaped algorithm, generally apply a single optimality cut on the nonlinear objective at each major iteration, while the multicut version of the algorithm allows for several cuts to be placed at once. In general, the L-shaped algorithm tends to have more major iterations than the multicut algorithm. However, the trade-offs in terms of computational time are problem dependent. This paper investigates the computational trade-offs of adjusting the level of optimality cut aggregation from single cut to pure multicut. Specifically, an adaptive multicut algorithm that dynamically adjusts the aggregation level of the optimality cuts in the master program, is presented and tested on standard large-scale instances from the literature. Computational results reveal that a cut aggregation level that is between the single cut and the multicut can result in substantial computational savings over the single cut method.     

Solution approach to infinite linear programming problem with capacity constraints

The purpose of this article is to investigate a kind of infinite linear programming problem (ILPP) arising from infinite multiclass network equilibrium problems. In several cases, we construct special feasible solutions to the ILPP. By virtue of the nature of network, we prove that the solutions are optimal. Marcotte and Zhu (Oper Res Lett 37:211?C214, 2009) proved the existence of the valid tolls for the infinite multiclass network equilibrium problems. Based on this, we analyze the property of the tolls vector, i.e., the relationship between breakpoints and the tolls. We also consider the solutions in the network where origin-destination pairs may differ in their probability density functions.     

A warm-start approach for large-scale stochastic linear programs

We describe a way of generating a warm-start point for interior point methods in the context of stochastic programming. Our approach exploits the structural information of the stochastic problem so that it can be seen as a structure-exploiting initial point generator. We solve a small-scale version of the problem corresponding to a reduced event tree and use the solution to generate an advanced starting point for the complete problem. The way we produce a reduced tree tries to capture the important information in the scenario space while keeping the dimension of the corresponding (reduced) deterministic equivalent small. We derive conditions which should be satisfied by the reduced tree to guarantee a successful warm-start of the complete problem. The implementation within the HOPDM and OOPS interior point solvers shows remarkable advantages.     

Computational methods for solving two-stage stochastic linear programming problems

Approximating a given continuous probability distribution of the data of a linear program by a discrete one yields solution methods for the stochastic linear programming problem with complete fixed recourse. For a procedure along the lines of [8], the reduction of the computational amount of work compared to the usual revised simplex method is figured out. Furthermore, an alternative method is proposed, where by refining particular discrete distributions the optimal value is approximated.

---

Zusammenfassung Für das zweistufige Modell der stochastischen linearen Programmierung mit vollständiger Kompensation werden Verfahren untersucht, die sich aus der Annäherung einer gegebenen stetigen Wahrscheinlichkeitsverteilung der Daten durch endlich diskrete Verteilungen ergeben. Beim Vorgehen nach [8] wird die Reduktion des Rechenaufwandes im Vergleich zur üblichen revidierten Simplexmethode ermittelt. Als Alternative wird ein Verfahren vorgeschlagen, in dem durch sukzessive Verfeinerung speziell gewählter diskreter Verteilungen der Optimalwert monoton angenähert wird.

---

---

Herrn Prof. Dr. Eduard Stiefel in kollegialer Verbundenheit     

Nonsmooth semi-infinite programming problems with mixed constraints

We consider a nonsmooth semi-infinite programming problem with a feasible set defined by inequality and equality constraints and a set constraint. First, we study some alternative theorems which involve linear and sublinear functions and a convex set and we propose several generalizations of them. Then, alternative theorems are applied to obtain, under different constraint qualifications, several necessary optimality conditions in the type of Fritz-John and Karush-Kuhn-Tucker.     

A multiobjective based approach for mathematical programs with linear flexible constraints

In this paper a mathematical problem with linear flexible constraints is considered. In order to solve the problem an approach is proposed based on multiobjective linear programming. Indeed, allowing violations for the constraints, and using multiobjective linear programming to minimize these violations, a subset of solution set which has less violations, namely efficiently feasible set, is obtained. Then, the corresponding objective function is optimized over efficiently feasible set in order to obtain an optimal solution. An application of the proposed approach in pattern classification is introduced.     

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.     

A numerical method for solving stochastic programming problems with moment constraints on a distribution function

The stochastic programming problem is considered in the case of a distribution function with partially known random parameters. A minimax approach is taken, and a numerical method is proposed for problems when information on the distribution function can be expressed in the form of finitely many moment constraints. Convergence is proved and results of numerical experiments are reported.     

A sequential quadratic programming with a dual parametrization approach to nonlinear semi-infinite programming

In the sequel of the work reported in Liu et al. (1999), in which a method based on a dual parametrization is used to solve linear-quadratic semi-infinite programming (SIP) problems, a sequential quadratic programming technique is proposed to solve nonlinear SIP problems. A merit function to measure progress toward the solution and a procedure to compute the penalty parameter are also proposed.