Invited Session Wed.2.MA 141

Wednesday, 13:15 - 14:45 h, Room: MA 141

Cluster 22: Stochastic optimization [...]

Scenario generation in stochastic optimization


Chair: David Papp



Wednesday, 13:15 - 13:40 h, Room: MA 141, Talk 1

David Papp
Generating moment matching scenarios using optimization techniques

Coauthor: Sanjay Mehrotra


An optimization based method is proposed to generate moment matching scenarios for stochastic programming. The main advantage of the method is its flexibility: it can generate scenarios matching any prescribed set of moments of the underlying distribution rather than matching all moments up to a certain order. The method is based on a semi-infinite linear programming formulation of the problem that is shown to be solvable with polynomial iteration complexity. A practical column generation method is also presented, in which the column generation subproblems are polynomial optimization problems. It is found that the columns in the column generation approach can be efficiently generated by random sampling. The number of scenarios generated matches a lower bound of Tchakaloff's. Empirical results show that the proposed approach outperforms Monte Carlo and quasi-Monte Carlo based approaches on the tested problems.



Wednesday, 13:45 - 14:10 h, Room: MA 141, Talk 2

Teemu Pennanen
Tractability of stochastic programs


Recently, Nemirovski et al. established the tractability of a class of convex stochastic programs in the randomized setting. This talk describes classes of convex stochastic programs that are tractable in the stronger, worst case setting.



Wednesday, 14:15 - 14:40 h, Room: MA 141, Talk 3

Jitamitra Desai
A mathematical programming framework for decision tree analysis

Coauthor: Suvrajeet Sen


One of the most important analytical tools often used by management executives is decision tree analysis. Traditionally, the solution to decision tree problems has been accomplished using backward recursion or more specifically (stochastic) dynamic programming techniques, but such methods have been shown to suffer from a number of shortcomings. In this research effort, we present a mathematical programming formulation for solving decision tree problems that not only alleviate the difficulties faced by traditional approaches but also allows for the incorporation of new classes of constraints that were hitherto unsolvable in this decision-making context. We begin by presenting a mathematical representation of decision trees as a (path-based) polynomial programming problem, which can be efficiently solved using a branch-and-bound method. Recognizing the exponential increase in problem size for large-scale instances, we extend this basic characterization to a compact path-based relaxation and exploit the special structure of this formulation to design an efficient globally optimal branch-price-and-cut algorithm.


  There are three major facts that should be watched out for in all payday loans in the United States. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.