Invited Session Mon.2.MA 376

Monday, 13:15 - 14:45 h, Room: MA 376

Cluster 22: Stochastic optimization [...]

Stochastic mixed-integer programming


Chair: Maarten H. van der Vlerk



Monday, 13:15 - 13:40 h, Room: MA 376, Talk 1

Lanah Evers
The orienteering problem under uncertainty: Robust optimization and stochastic programming compared

Coauthors: Ana Barros, Kristiaan Glorie, Herman Monsuur, Suzanne van der Ster


The Orienteering Problem (OP) is a generalization of the well-known traveling salesman problem and has many interesting applications in logistics, tourism and defense. To reflect real-life situations, we focus on an uncertain variant of the OP. Two main approaches that deal with optimization under uncertainty are stochastic programming and robust optimization. We will explore the potentialities and bottlenecks of these two approaches applied to the uncertain OP. We will compare the known robust approach for the uncertain OP (the robust orienteering problem) to the new stochastic programming counterpart (the two-stage orienteering problem). The application of both approaches will be explored in terms of their suitability in practice.



Monday, 13:45 - 14:10 h, Room: MA 376, Talk 2

Ward Romeijnders
On the performance of a class of convex approximations for integer recourse models

Coauthors: Willem K. Klein Haneveld, Maarten H. van der Vlerk


We consider the performance of the convex approximations introduced by Van der Vlerk (2004) for the class of integer recourse problems with totally unimodular (TU) recourse matrices. We show that the main theorem in Van der Vlerk (2004) needs stronger assumptions. As a result, a performance guarantee for the convex approximations is lacking in general. In order to obtain such a performance guarantee, we first analyze the approximations for simple integer recourse models. Using a new approach we improve the existing error bound for these models by a factor 2. We use insights from this analysis to obtain an error bound for complete integer recourse problems with TU recourse matrices. This error bound ensures that the performance of the approximations is good as long as the dispersion of the random variables in the model is large enough.



Monday, 14:15 - 14:40 h, Room: MA 376, Talk 3

Simge Kucukyavuz
Decomposition algorithms with Gomory cuts for two-stage stochastic integer programs

Coauthors: Dinakar Gade, Suvrajeet Sen


We consider a class of two-stage stochastic integer programs (SIP) with binary variables in the first stage and general integer variables in the second stage. We develop decomposition algorithms akin to the L-shaped or Benders' decomposition scheme by utilizing Gomory cuts method to obtain iteratively tighter approximations of the second stage integer programs. We show that the proposed methodology is flexible in that it allows several modes of implementation, all of of which lead to finitely convergent algorithms. This development allows both disjunctive as well as Gomory cuts to be included within finitely convergent decomposition algorithms for SIP. Such disparate collections of cuts have proved to be indispensable for the success of branch-and-cut algorithms in deterministic IP, and we are hopeful that the introduction of Gomory cuts within a decomposition algorithm will be just as valuable for SIP. We will illustrate the use of these cuts both within a pure cutting plane, as well as a branch-and-cut based decomposition algorithm.


  payday advance . Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.