Convex approximations for a class of mixed-integer recourse models

We consider mixed-integer recourse (MIR) models with a single recourse constraint. We relate the second-stage value function of such problems to the expected simple integer recourse (SIR) shortage function. This allows to construct convex approximations for MIR problems by the same approach used for SIR models.     

Higher-order total variation bounds for expectations of periodic functions and simple integer recourse approximations

We derive bounds on the expectation of a class of periodic functions using the total variations of higher-order derivatives of the underlying probability density function. These bounds are a strict improvement over those of Romeijnders et al. (Math Program 157:3–46, 2016b), and we use them to derive error bounds for convex approximations of simple integer recourse models. In fact, we obtain a hierarchy of error bounds that become tighter if the total variations of additional higher-order derivatives are taken into account. Moreover, each error bound decreases if these total variations become smaller. The improved bounds may be used to derive tighter error bounds for convex approximations of more general recourse models involving integer decision variables.     

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).     

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).     

Designing a majorization scheme for the recourse function in two-stage stochastic linear programming

We discuss issues pertaining to the domination from above of the second-stage recourse function of a stochastic linear program and we present a scheme to majorize this function using a simpler sublinear function. This majorization is constructed using special geometrical attributes of the recourse function. The result is a proper, simplicial function with a simple characterization which is well-suited for calculations of its expectation as required in the computation of stochastic programs. Experiments indicate that the majorizing function is well-behaved and stable.     

Newton-type methods for stochastic programming

Stochastic programming is concerned with practical procedures for decision making under uncertainty, by modelling uncertainties and risks associated with decision in a form suitable for optimization. The field is developing rapidly with contributions from many disciplines such as operations research, probability and statistics, and economics. A stochastic linear program with recourse can equivalently be formulated as a convex programming problem. The problem is often large-scale as the objective function involves an expectation, either over a discrete set of scenarios or as a multi-dimensional integral. Moreover, the objective function is possibly nondifferentiable. This paper provides a brief overview of recent developments on smooth approximation techniques and Newton-type methods for solving two-stage stochastic linear programs with recourse, and parallel implementation of these methods. A simple numerical example is used to signal the potential of smoothing approaches.     

Postoptimality for mean-risk stochastic mixed-integer programs and its application

The mean-risk stochastic mixed-integer programs can better model complex decision problems under uncertainty than usual stochastic (integer) programming models. In order to derive theoretical results in a numerically tractable way, the contamination technique is adopted in this paper for the postoptimality analysis of the mean-risk models with respect to changes in the scenario set, here the risk is measured by the lower partial moment. We first study the continuity of the objective function and the differentiability, with respect to the parameter contained in the contaminated distribution, of the optimal value function of the mean-risk model when the recourse cost vector, the technology matrix and the right-hand side vector in the second stage problem are all random. The postoptimality conclusions of the model are then established. The obtained results are applied to two-stage stochastic mixed-integer programs with risk objectives where the objective function is nonlinear with respect to the probability distribution. The current postoptimality results for stochastic programs are improved.     

On multiple simple recourse models

We consider multiple simple recourse (MSR) models, both continuous and integer versions, which generalize the corresponding simple recourse (SR) models by allowing for a refined penalty cost structure for individual shortages and surpluses. It will be shown that (convex approximations of) such MSR models can be represented as explicitly specified continuous SR models, and thus can be solved efficiently by existing algorithms. This research has been made possible by a fellowship of the Royal Netherlands Academy of Arts and Sciences.     

Convex approximations for complete integer recourse models

We consider convex approximations of the expected value function of a two-stage integer recourse problem. The convex approximations are obtained by perturbing the distribution of the random right-hand side vector. It is shown that the approximation is optimal for the class of problems with totally unimodular recourse matrices. For problems not in this class, the result is a convex lower bound that is strictly better than the one obtained from the LP relaxation.This research has been made possible by a fellowship of the Royal Netherlands Academy of Arts and Sciences.Key words.integer recourse – convex approximationMathematics Subject Classification (1991):90C15, 90C11     

Retrospective optimization of mixed-integer stochastic systems using dynamic simplex linear interpolation

We propose a family of retrospective optimization (RO) algorithms for optimizing stochastic systems with both integer and continuous decision variables. The algorithms are continuous search procedures embedded in a RO framework using dynamic simplex interpolation (RODSI). By decreasing dimensions (corresponding to the continuous variables) of simplex, the retrospective solutions become closer to an optimizer of the objective function. We present convergence results of RODSI algorithms for stochastic “convex” systems. Numerical results show that a simple implementation of RODSI algorithms significantly outperforms some random search algorithms such as Genetic Algorithm (GA) and Particle Swarm Optimization (PSO).     

An algorithm for the construction of convex hulls in simple integer recourse programming

We consider the objective function of a simple integer recourse problem with fixed technology matrix and discretely distributed right-hand sides. Exploiting the special structure of this problem, we devise an algorithm that determines the convex hull of this function efficiently. The results are improvements over those in a previous paper. In the first place, the convex hull of many objective functions in the class is covered, instead of only one-dimensional versions. In the second place, the algorithm is faster than the one in the previous paper. Moreover, some new results on the structure of the objective function are presented.     

Solving stochastic programs with integer recourse by enumeration: A framework using Gröbner basis

In this paper we present a framework for solving stochastic programs with complete integer recourse and discretely distributed right-hand side vector, using Gröbner basis methods from computational algebra to solve the numerous second-stage integer programs. Using structural properties of the expected integer recourse function, we prove that under mild conditions an optimal solution is contained in a finite set. Furthermore, we present a basic scheme to enumerate this set and suggest improvements to reduce the number of function evaluations needed.     

On solving integral equations using Markov chain Monte Carlo methods

In this paper, we propose an original approach to the solution of Fredholm equations of the second kind. We interpret the standard Von Neumann expansion of the solution as an expectation with respect to a probability distribution defined on a union of subspaces of variable dimension. Based on this representation, it is possible to use trans-dimensional Markov chain Monte Carlo (MCMC) methods such as Reversible Jump MCMC to approximate the solution numerically. This can be an attractive alternative to standard Sequential Importance Sampling (SIS) methods routinely used in this context. To motivate our approach, we sketch an application to value function estimation for a Markov decision process. Two computational examples are also provided.     

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.     

PROBABILISTIC OSTROWSKI TYPE INEQUALITIES

New very general univariate and multivariate probabilistic Ostrowski type inequalities are established, involving ‖·‖_∞ and ‖·‖ _p , p≥1 norms of probability density functions. Some of these inequalities provide pointwise estimates to the error of probability distribution function from the expectation of some simple function of the engaged random variable. Other inequalities give upper bounds for the expectation and variance of a random variable. All are done over finite domains. At the end are given applications, especially for the Beta random variable.     

A two-stage model for a day-ahead paratransit planning problem

We consider a dynamic planning problem for paratransit transportation. The focus is on a decision to take one day ahead: which requests to serve with own vehicles, and which requests to subcontract to taxis? We call this problem the day-ahead paratransit planning problem. The developed model is a non-standard two-stage integer recourse model. Both stages consist of two consecutive optimization problems: the clustering of requests into routes, and the assignment of these routes to vehicles. To solve this model, a genetic algorithm approach is used. Computational results are presented for randomly generated data sets.     

A new variable reduction technique for convex integer quadratic programs

Convex integer quadratic programming involves minimization of a convex quadratic objective function with affine constraints and is a well-known NP-hard problem with a wide range of applications. We proposed a new variable reduction technique for convex integer quadratic programs (IQP). Based on the optimal values to the continuous relaxation of IQP and a feasible solution to IQP, the proposed technique can be applied to fix some decision variables of an IQP simultaneously at zero without sacrificing optimality. Using this technique, computational effort needed to solve IQP can be greatly reduced. Since a general convex bounded IQP (BIQP) can be transformed to a convex IQP, the proposed technique is also applicable for the convex BIQP. We report a computational study to demonstrate the efficacy of the proposed technique in solving quadratic knapsack problems.