Bounds for Probabilistic Programming with Application to a Blend Planning Problem

In this paper, we derive deterministic inner approximations for single and joint probabilistic constraints based on classical inequalities from probability theory such as the one-sided Chebyshev inequality, Bernstein inequality, Chernoff inequality and Hoeffding inequality (see Pinter 1989). New assumptions under which the bounds based approximations are convex allowing to solve the problem efficiently are derived. … Read more

Direct search based on probabilistic feasible descent for bound and linearly constrained problems

Direct search is a methodology for derivative-free optimization whose iterations are characterized by evaluating the objective function using a set of polling directions. In deterministic direct search applied to smooth objectives, these directions must somehow conform to the geometry of the feasible region and typically consist of positive generators of approximate tangent cones (which then … Read more

Guaranteed Bounds for General Non-discrete Multistage Risk-Averse Stochastic Optimization Programs

In general, multistage stochastic optimization problems are formulated on the basis of continuous distributions describing the uncertainty. Such ”infinite” problems are practically impossible to solve as they are formulated and finite tree approximations of the underlying stochastic processes are used as proxies. In this paper, we demonstrate how one can find guaranteed bounds, i.e. finite … Read more

On the Number of Stages in Multistage Stochastic Programs

Multistage stochastic programs are a viable modeling tool for sequential decisions conditional on information revealed at different points in time (stages). However, as the number of stages increases their applicability is soon halted by the curse of dimensionality. A typical, sometimes forced, alternative is to approximate stages by their expected values thus considering fewer stages … Read more

BOUNDS AND APPROXIMATIONS FOR MULTISTAGE STOCHASTIC PROGRAMS

Consider (typically large) multistage stochastic programs, which are defined on scenario trees as the basic data structure. It is well known that the computational complexity of the solution depends on the size of the tree, which itself increases typically exponentially fast with its height, i.e. the number of decision stages. For this reason approximations which … Read more

Scenario-Tree Decomposition: Bounds for Multistage Stochastic Mixed-Integer Programs

Multistage stochastic mixed-integer programming is a powerful modeling paradigm appropriate for many problems involving a sequence of discrete decisions under uncertainty; however, they are difficult to solve without exploiting special structures. We present scenario-tree decomposition to establish bounds for unstructured multistage stochastic mixed-integer programs. Our method decomposes the scenario tree into a number of smaller … Read more

Combining QCR and CHR for Convex Quadratic MINLP Problems with Linear Constraints

The convex hull relaxation (CHR) method (Albornoz 1998, Ahlatçıoğlu 2007, Ahlatçıoğlu and Guignard 2010) provides lower bounds and feasible solutions (thus upper bounds) on convex 0-1 nonlinear programming problems with linear constraints. In the quadratic case, these bounds may often be improved by a preprocessing step that adds to the quadratic objective function terms which … Read more

An information-based approximation scheme for stochastic optimization problems in continuous time

Dynamic stochastic optimization problems with a large (possibly infinite) number of decision stages and high-dimensional state vector are inherently difficult to solve. In fact, scenario tree based algorithms are unsuitable for problems with many stages, while dynamic programming type techniques are unsuitable for problems with many state variables. This article proposes a stage aggregation scheme … Read more