parallel computing

Nested Benders Decomposition for Large-Scale Multi-Follower Bilevel Optimization

  • Dominic C. Flocco
  • Philine Schiewe
  • Steven A. Gabriel
    • Categories Bilevel Optimization, Parallel Algorithms, Transportation Tags , , , ,

    We propose a scalable nested Benders decomposition (BD) framework for single-leader, multi-follower bilevel optimization problems. The proposed framework is applicable to bilevel optimization problems in which each follower solves a linear program and is particularly well suited for instances involving a large number of followers. By identifying the upper-level decisions as complicating variables, the method … Read more

    Stochastic convergence of parallel asynchronous adaptive first-order methods

  • Serge Gratton
  • Philippe L. Toint
    • Categories Data Science Algorithms, Stochastic Programming, Unconstrained Optimization Tags , , , , ,

    A new class of asynchronous adaptive first-order optimization methods is introduced, comprising asynchronous variants of several popular algorithms. Versions of these methods using momentum and/or inexact normalization are also considered. The convergence of methods in the class on non-convex functions is analyzed in a fully stochastic setting, and is shown to be (up to logarithmic … Read more

    PaPILO: A Parallel Presolving Library for Integer and Linear Optimization with Multiprecision Support

  • Alexander Hoen
  • Ambros Gleixner
  • Leona Gottwald
    • Categories (Mixed) Integer Linear Programming, Integer Programming, Linear Programming Tags , , , ,

    Presolving has become an essential component of modern MIP solvers both in terms of computational performance and numerical robustness. In this paper we present PaPILO (https://github.com/scipopt/papilo), a new C++ header-only library that provides a large set of presolving routines for MIP and LP problems from the literature. The creation of \papilo was motivated by the … Read more

    Batch Learning in Stochastic Dual Dynamic Programming

  • Daniel Ávila
  • Nils Löhndorf
  • Anthony Papavasiliou
    • Categories Dynamic Programming, Stochastic Programming Tags , , , ,

    We consider the stochastic dual dynamic programming (SDDP) algorithm, which is a widely employed algorithm applied to multistage stochastic programming, and propose a variant using batch learning, a technique used with success in the reinforcement learning framework. We cast SDDP as a type of Q-learning algorithm and describe its application in both risk neutral and … Read more

    Improving Column-Generation for Vehicle Routing Problems via Random Coloring and Parallelization

  • Viswanath Nagarajan
  • Siqian Shen
  • Miao Yu
    • Categories Network Optimization, Parallel Algorithms, Transportation Tags , , , ,

    We consider a variant of the Vehicle Routing Problem (VRP) where each customer has a unit demand and the goal is to minimize the total cost of routing a fleet of capacitated vehicles from one or multiple depots to visit all customers. We propose two parallel algorithms to efficiently solve the column-generation based linear-programming relaxation … Read more

    A Parallel Hub-and-Spoke System for Large-Scale Scenario-Based Optimization Under Uncertainty

  • Bernard Knueven
  • Christopher Muir
  • Jean-Paul Watson
  • David T. Mildebrath
  • John D. Siirola
  • David L. Woodruff
    • Categories Stochastic Programming Tags , , ,

    Efficient solution of stochastic programming problems generally requires the use of parallel computing resources. Here, we describe the open source package mpi-sppy, in which efficient and scalable parallelization is a central feature. We describe the overall architecture and provide computational examples and results showing scalability to the largest instances that we know of for the … Read more

    A parallel splitting ALM-based algorithm for separable convex programming

  • Bingsheng He
  • Shengjie Xu
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Parallel Algorithms Tags , , , ,

    The augmented Lagrangian method (ALM) provides a benchmark for tackling the canonical convex minimization problem with linear constraints. We consider a special case where the objective function is the sum of $m$ individual subfunctions without coupled variables. The recent study reveals that the direct extension of ALM for separable convex programming problems is not necessarily … Read more

    On Electricity Market Equilibria with Storage: Modeling, Uniqueness, and a Distributed ADMM

  • Julia Grübel
  • Thomas Kleinert
  • Vanessa Krebs
  • Lars Schewe
  • Martin Schmidt
  • Johannes Thürauf
  • Galina Orlinskaya
    • Categories Convex Optimization, Parallel Algorithms, Quadratic Programming Tags , , , , , ,

    We consider spot-market trading of electricity including storage operators as additional agents besides producers and consumers. Storages allow for shifting produced electricity from one time period to a later one. Due to this, multiple market equilibria may occur even if classical uniqueness assumptions for the case without storages are satisfied. For models containing storage operators, … Read more

    Decomposition Methods for Solving Two-Stage Distributionally Robust Optimization Problems

  • Hailin Sun
  • Huifu Xu
  • Chen Yannan
    • Categories Robust Optimization, Stochastic Programming Tags , , , , ,

    Decomposition methods have been well studied for solving two-stage and multi-stage stochastic programming problems, see [29, 32, 33]. In this paper, we propose an algorithmic framework based on the fundamental ideas of the methods for solving two-stage minimax distributionally robust optimization (DRO) problems where the underlying random variables take a finite number of distinct values. … Read more

    Parallel and Distributed Successive Convex Approximation Methods for Big-Data Optimization

  • Gesualdo Scutari
  • Ying Sun
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    Recent years have witnessed a surge of interest in parallel and distributed optimization methods for large-scale systems. In particular, nonconvex large-scale optimization problems have found a wide range of applications in several engineering fields. The design and the analysis of such complex, large-scale, systems pose several challenges and call for the development of new optimization … Read more