Oleg A. Prokopyev

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

  • Oleg A. Prokopyev
  • Andrew J. Schaefer
  • Gabriel L. Zenarosa
    • Categories Integer Programming, Parallel Algorithms, Stochastic Programming Tags , ,

    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

    Two-Stage Quadratic Integer Programs with Stochastic Right-Hand Sides

  • Osman Y. Ozaltin
  • Oleg A. Prokopyev
  • Andrew J. Schaefer
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming, Stochastic Programming Tags , , ,

    We consider two-stage quadratic integer programs with stochastic right-hand sides, and present an equivalent reformulation using value functions. We fi rst derive some basic properties of value functions of quadratic integer programs. We then propose a two-phase solution approach. The first phase constructs the value functions of quadratic integer programs in both stages. The second phase … Read more

    Streaming Cache Placement Problems: Complexity and Algorithms

  • Carlos A. S. Oliveira
  • Panos M. Pardalos
  • Oleg A. Prokopyev
  • Mauricio G.C. Resende
    • Categories Approximation Algorithms, Network Optimization, Telecommunications Tags , , ,

    Virtual private networks (VPN) are often used to distribute live content, such as video or audio streams, from a single source to a large number of destinations. Streaming caches or splitters are deployed in these multicast networks to allow content distribution without overloading the network. In this paper, we consider two combinatorial optimization problems that … Read more