Vehicle routing with stochastic demands and restricted failures

This paper considers a class of stochastic vehicle routing problems (SVRPs) with random demands, in which the number of potential failures per route is restricted either by the data or the problem constraints. These are realistic cases as it makes little sense to plan vehicle routes that systematically fail a large number of times. First, a chance constrained version of the problem is considered which can be solved to optimality by algorithms similar to those developed for the deterministic vehicle routing problem (VRP). Three classes of SVRP with recourse are then analyzed. In all cases, route failures can only occur at one of the lastk customers of the planned route. Since in general, SVRPs are considerably more intractable than the deterministic VRPs, it is interesting to note that these realistic stochastic problems can be solved as a sequence of deterministic traveling salesman problems (TSPs). In particular, whenk=1 the SVRP with recourse reduces to a single TSP.     

Stochastic second-order cone programming: Applications models

Second-order cone programs are a class of convex optimization problems. We refer to them as deterministic second-order cone programs (DSCOPs) since data defining them are deterministic. In DSOCPs we minimize a linear objective function over the intersection of an affine set and a product of second-order (Lorentz) cones. Stochastic programs have been studied since 1950s as a tool for handling uncertainty in data defining classes of optimization problems such as linear and quadratic programs. Stochastic second-order cone programs (SSOCPs) with recourse is a class of optimization problems that defined to handle uncertainty in data defining DSOCPs. In this paper we describe four application models leading to SSOCPs.     

Two-stage stochastic problems with correlated normal variables: computational experiences

Two-stage models are frequently used when making decisions under the influence of randomness. The case of normally distributed right hand side vector – with independent or correlated components – is treated here. The expected recourse function is computed by an enhanced Monte Carlo integration technique. Successive regression approximation technique is used for computing the optimal solution of the problem. Computational issues of the algorithm are discussed, improvements are proposed and numerical results are presented for random right hand side and a random matrix in the second stage problems.     

A global optimization algorithm for generalized semi-infinite,continuous minimax with coupled constraints and bi-level problems

We propose an algorithm for the global optimization of three problem classes: generalized semi-infinite, continuous coupled minimax and bi-level problems. We make no convexity assumptions. For each problem class, we construct an oracle that decides whether a given objective value is achievable or not. If a given value is achievable, the oracle returns a point with a value better than or equal to the target. A binary search is then performed until the global optimum is obtained with the desired accuracy. This is achieved by solving a series of appropriate finite minimax and min-max-min problems to global optimality. We use Laplace’s smoothing technique and a simulated annealing approach for the solution of these problems. We present computational examples for all three problem classes.     

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.     

Simulation of typical Cox–Voronoi cells with a special regard to implementation tests

We consider stationary Poisson line processes in the Euclidean plane and analyze properties of Voronoi tessellations induced by Poisson point processes on these lines. In particular, we describe and test an algorithm for the simulation of typical cells of this class of Cox–Voronoi tessellations. Using random testing, we validate our algorithm by comparing theoretical values of functionals of the zero cell to simulated values obtained by our algorithm. Finally, we analyze geometric properties of the typical Cox–Voronoi cell and compare them to properties of the typical cell of other well-known classes of tessellations, especially Poisson–Voronoi tessellations. Our results can be applied to stochastic–geometric modelling of networks in telecommunication and life sciences, for example. The lines can then represent roads in urban road systems, blood arteries or filament structures in biological tissues or cells, while the points can be locations of telecommunication equipment or vesicles, respectively.     

An adaptive least-squares collocation radial basis function method for the HJB equation

We present a novel numerical method for the Hamilton–Jacobi–Bellman equation governing a class of optimal feedback control problems. The spatial discretization is based on a least-squares collocation Radial Basis Function method and the time discretization is the backward Euler finite difference. A stability analysis is performed for the discretization method. An adaptive algorithm is proposed so that at each time step, the approximate solution can be constructed recursively and optimally. Numerical results are presented to demonstrate the efficiency and accuracy of the method.     

Computational aspects of minimizing conditional value-at-risk

We consider optimization problems for minimizing conditional value-at-risk (CVaR) from a computational point of view, with an emphasis on financial applications. As a general solution approach, we suggest to reformulate these CVaR optimization problems as two-stage recourse problems of stochastic programming. Specializing the L-shaped method leads to a new algorithm for minimizing conditional value-at-risk. We implemented the algorithm as the solver CVaRMin. For illustrating the performance of this algorithm, we present some comparative computational results with two kinds of test problems. Firstly, we consider portfolio optimization problems with 5 random variables. Such problems involving conditional value at risk play an important role in financial risk management. Therefore, besides testing the performance of the proposed algorithm, we also present computational results of interest in finance. Secondly, with the explicit aim of testing algorithm performance, we also present comparative computational results with randomly generated test problems involving 50 random variables. In all our tests, the experimental solver, based on the new approach, outperformed by at least one order of magnitude all general-purpose solvers, with an accuracy of solution being in the same range as that with the LP solvers. János Mayer: Financial support by the national center of competence in research "Financial Valuation and Risk Management" is gratefully acknowledged. The national centers in research are managed by the Swiss National Science Foundation on behalf of the federal authorities.     

Recourse-based stochastic nonlinear programming: properties and Benders-SQP algorithms

In this paper, we study recourse-based stochastic nonlinear programs and make two sets of contributions. The first set assumes general probability spaces and provides a deeper understanding of feasibility and recourse in stochastic nonlinear programs. A sufficient condition, for equality between the sets of feasible first-stage decisions arising from two different interpretations of almost sure feasibility, is provided. This condition is an extension to nonlinear settings of the “W-condition,” first suggested by Walkup and Wets (SIAM J. Appl. Math. 15:1299–1314, 1967). Notions of complete and relatively-complete recourse for nonlinear stochastic programs are defined and simple sufficient conditions for these to hold are given. Implications of these results on the L-shaped method are discussed. Our second set of contributions lies in the construction of a scalable, superlinearly convergent method for solving this class of problems, under the setting of a finite sample-space. We present a novel hybrid algorithm that combines sequential quadratic programming (SQP) and Benders decomposition. In this framework, the resulting quadratic programming approximations while arbitrarily large, are observed to be two-period stochastic quadratic programs (QPs) and are solved through two variants of Benders decomposition. The first is based on an inexact-cut L-shaped method for stochastic quadratic programming while the second is a quadratic extension to a trust-region method suggested by Linderoth and Wright (Comput. Optim. Appl. 24:207–250, 2003). Obtaining Lagrange multiplier estimates in this framework poses a unique challenge and are shown to be cheaply obtainable through the solution of a single low-dimensional QP. Globalization of the method is achieved through a parallelizable linesearch procedure. Finally, the efficiency and scalability of the algorithm are demonstrated on a set of stochastic nonlinear programming test problems.     

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

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.     

Application of Deterministic Low-Discrepancy Sequences in Global Optimization

It has been recognized through theory and practice that uniformly distributed deterministic sequences provide more accurate results than purely random sequences. A quasi Monte Carlo (QMC) variant of a multi level single linkage (MLSL) algorithm for global optimization is compared with an original stochastic MLSL algorithm for a number of test problems of various complexities. An emphasis is made on high dimensional problems. Two different low-discrepancy sequences (LDS) are used and their efficiency is analysed. It is shown that application of LDS can significantly increase the efficiency of MLSL. The dependence of the sample size required for locating global minima on the number of variables is examined. It is found that higher confidence in the obtained solution and possibly a reduction in the computational time can be achieved by the increase of the total sample size N. N should also be increased as the dimensionality of problems grows. For high dimensional problems clustering methods become inefficient. For such problems a multistart method can be more computationally expedient.     

A fuzzy goal programming and meta heuristic algorithms for solving integrated production: distribution planning problem

Integrated production–distribution planning is one of the most important issues in supply chain management (SCM). We consider a supply chain (SC) network to consist of a manufacturer, with multiple plants, products, distribution centers (DCs), retailers and customers. A multi-objective linear programming problem for integrating production–distribution, which considers various simultaneously conflicting objectives, is developed. The decision maker’s imprecise aspiration levels of goals are incorporated into the model using a fuzzy goal programming approach. Due to complexity of the considered problem we propose three meta-heuristics to tackle the problem. A simple genetic algorithm and a particle swarm optimization (PSO) algorithm with a new fitness function, and an improved hybrid genetic algorithm are developed. In order to show the efficiency of the proposed methods, two classes of problems are considered and their instances are solved using all methods. The obtained results show that the improved hybrid genetic algorithm gives us the best solutions in a reasonable computational time.     

A generalization of the Shapley–Ichiishi result

The Shapley–Ichiishi result states that a game is convex if and only if the convex hull of marginal vectors equals the core. In this paper, we generalize this result by distinguishing equivalence classes of balanced games that share the same core structure. We then associate a system of linear inequalities with each equivalence class, and we show that the system defines the class. Application of this general theorem to the class of convex games yields an alternative proof of the Shapley–Ichiishi result. Other applications range from computation of stable sets in non-cooperative game theory to determination of classes of TU games on which the core correspondence is additive (even linear). For the case of convex games we prove that the theorem provides the minimal defining system of linear inequalities. An example shows that this is not necessarily true for other equivalence classes of balanced games.     

Two-stage non-cooperative games with risk-averse players

This paper formally introduces and studies a non-cooperative multi-agent game under uncertainty. The well-known Nash equilibrium is employed as the solution concept of the game. While there are several formulations of a stochastic Nash equilibrium problem, we focus mainly on a two-stage setting of the game wherein each agent is risk-averse and solves a rival-parameterized stochastic program with quadratic recourse. In such a game, each agent takes deterministic actions in the first stage and recourse decisions in the second stage after the uncertainty is realized. Each agent’s overall objective consists of a deterministic first-stage component plus a second-stage mean-risk component defined by a coherent risk measure describing the agent’s risk aversion. We direct our analysis towards a broad class of quantile-based risk measures and linear-quadratic recourse functions. For this class of non-cooperative games under uncertainty, the agents’ objective functions can be shown to be convex in their own decision variables, provided that the deterministic component of these functions have the same convexity property. Nevertheless, due to the non-differentiability of the recourse functions, the agents’ objective functions are at best directionally differentiable. Such non-differentiability creates multiple challenges for the analysis and solution of the game, two principal ones being: (1) a stochastic multi-valued variational inequality is needed to characterize a Nash equilibrium, provided that the players’ optimization problems are convex; (2) one needs to be careful in the design of algorithms that require differentiability of the objectives. Moreover, the resulting (multi-valued) variational formulation cannot be expected to be of the monotone type in general. The main contributions of this paper are as follows: (a) Prior to addressing the main problem of the paper, we summarize several approaches that have existed in the literature to deal with uncertainty in a non-cooperative game. (b) We introduce a unified formulation of the two-stage SNEP with risk-averse players and convex quadratic recourse functions and highlight the technical challenges in dealing with this game. (c) To handle the lack of smoothness, we propose smoothing schemes and regularization that lead to differentiable approximations. (d) To deal with non-monotonicity, we impose a generalized diagonal dominance condition on the players’ smoothed objective functions that facilitates the application and ensures the convergence of an iterative best-response scheme. (e) To handle the expectation operator, we rely on known methods in stochastic programming that include sampling and approximation. (f) We provide convergence results for various versions of the best-response scheme, particularly for the case of private recourse functions. Overall, this paper lays the foundation for future research into the class of SNEPs that provides a constructive paradigm for modeling and solving competitive decision making problems with risk-averse players facing uncertainty; this paradigm is very much at an infancy stage of research and requires extensive treatment in order to meet its broad applications in many engineering and economics domains.     

A comparison of two methods for solving 0–1 integer programs using a general purpose simulated annealing algorithm

0–1 problems are often difficult to solve. Although special purpose algorithms (exact as well as heuristic) exist for solving particular problem classes or problem instances, there are few general purpose algorithms for solving practical-sized instances of 0–1 problems. This paper deals with a general purpose heuristic algorithm for 0–1 problems. In this paper, we compare two methods based on simulated annealing for solving general 0–1 integer programming problems. The two methods differe in the scheme used for neighbourhood transitions in the simulated annealing framework. We compare the performance of the two methods on the set partitioning problem.     

A regularity theory for variational integrals with L\ln L-Growth

In the present paper we study regularity for local minimizers of the convex variational integral defined on certain classes of vector–valued functions . The underlying energy spaces are natural from the point of view of existence theory. We then show that local minimizers are of class apart from a closed singular set with vanishing Lebesgue measure, provided . For twodimensional problems we obtain smoothness in the interior of . Received June 21, 1996 / In revised form December 2, 1996 / Accepted December 17, 1996     

An inexact Newton method for nonconvex equality constrained optimization

We present a matrix-free line search algorithm for large-scale equality constrained optimization that allows for inexact step computations. For strictly convex problems, the method reduces to the inexact sequential quadratic programming approach proposed by Byrd et al. [SIAM J. Optim. 19(1) 351–369, 2008]. For nonconvex problems, the methodology developed in this paper allows for the presence of negative curvature without requiring information about the inertia of the primal–dual iteration matrix. Negative curvature may arise from second-order information of the problem functions, but in fact exact second derivatives are not required in the approach. The complete algorithm is characterized by its emphasis on sufficient reductions in a model of an exact penalty function. We analyze the global behavior of the algorithm and present numerical results on a collection of test problems.     

A structured pattern matrix algorithm for multichain Markov decision processes

In this paper, we are concerned with a new algorithm for multichain finite state Markov decision processes which finds an average optimal policy through the decomposition of the state space into some communicating classes and a transient class. For each communicating class, a relatively optimal policy is found, which is used to find an optimal policy by applying the value iteration algorithm. Using a pattern matrix determining the behaviour pattern of the decision process, the decomposition of the state space is effectively done, so that the proposed algorithm simplifies the structured one given by the excellent Leizarowitz’s paper (Math Oper Res 28:553–586, 2003). Also, a numerical example is given to comprehend the algorithm.