Parallel Algorithms

Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs

  • Kibaek Kim
  • Victor M. Zavala
    • Categories Optimization Software and Modeling Systems, Parallel Algorithms, Stochastic Programming

    We develop algorithmic innovations for the dual decomposition method to address two-stage stochastic programs with mixed-integer recourse and provide a parallel software implementation that we call DSP. Our innovations include the derivation of valid inequalities that tighten Lagrangian subproblems and that allow the guaranteed recovery of feasible solutions for problems without (relative) complete recourse. We … Read more

    ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates

  • Zhimin Peng
  • Yangyang Xu
  • Ming Yan
  • Wotao Yin
    • Categories Convex Optimization, Nonsmooth Optimization, Parallel Algorithms Tags , , , , ,

    We propose ARock, an asynchronous parallel algorithmic framework for finding a fixed point to a nonexpansive operator. In the framework, a set of agents (machines, processors, or cores) update a sequence of randomly selected coordinates of the unknown variable in an asynchronous parallel fashion. As special cases of ARock, novel algorithms for linear systems, convex … Read more

    Parallelizing the dual revised simplex method

  • J. A. Julian Hall
  • Q. Huangfu
    • Categories Linear Programming, Parallel Algorithms

    This paper introduces the design and implementation of two parallel dual simplex solvers for general large scale sparse linear programming problems. One approach, called PAMI, extends a relatively unknown pivoting strategy called suboptimization and exploits parallelism across multiple iterations. The other, called SIP, exploits purely single iteration parallelism by overlapping computational components when possible. Computational … Read more

    Object-Parallel Infrastructure for Implementing First-Order Methods, with an Example Application to LASSO

  • Jonathan Eckstein
  • Gyorgy Matyasfalvi
    • Categories Bound-constrained Optimization, Parallel Algorithms, Unconstrained Optimization Tags , ,

    We describe the design of a C++ vector-manipulation substrate that allows first-order optimization algorithms to be expressed in a concise and readable manner, yet still achieve high performance in parallel computing environments. We use standard object-oriented techniques of encapsulation and operator overloading, combined with a novel “symbolic temporaries” delayed-evaluation system that greatly reduces the overhead … Read more

    Coordinate descent algorithms

  • Stephen Wright
    • Categories Convex Optimization, Parallel Algorithms Tags , ,

    Coordinate descent algorithms solve optimization problems by successively performing approximate minimization along coordinate directions or coordinate hyperplanes. They have been used in applications for many years, and their popularity continues to grow because of their usefulness in data analysis, machine learning, and other areas of current interest. This paper describes the fundamentals of the coordinate … Read more

    PSMG-A Parallel Structured Model Generator for Mathematical Programming

  • Andreas Grothey
  • Feng Qiang
    • Categories Optimization Software and Modeling Systems, Parallel Algorithms

    In this paper, we present PSMG–Parallel Structured Model Generator–an efficient parallel implementation of a model generator for the structure conveying modelling language (SML[4]). Unlike the earlier proof-of-concept implementation presented with SML, PSMG does not depend on AMPL. The main purposes of PSMG are: to provide an easy to use framework for modelling and generating large … Read more

    A Parallel Line Search Subspace Correction Method for Composite Convex Optimization

  • Qian Dong
  • Xin Liu
  • Zaiwen Wen
  • Ya-xiang Yuan
    • Categories Convex and Nonsmooth Optimization, Parallel Algorithms Tags , , , ,

    In this paper, we investigate a parallel subspace correction framework for composite convex optimization. The variables are first divided into a few blocks based on certain rules. At each iteration, the algorithms solve a suitable subproblem on each block simultaneously, construct a search direction by combining their solutions on all blocks, then identify a new … Read more

    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

    A scalable bounding method for multi-stage stochastic integer programs

  • Osman Y. Ozaltin
  • Burhaneddin Sandikçi
    • Categories Integer Programming, Parallel Algorithms, Stochastic Programming Tags , , , ,

    Many dynamic decision problems involving uncertainty can be appropriately modeled as multi-stage stochastic programs. However, most practical instances are so large and/or complex that it is impossible to solve them on a single computer, especially due to memory limitations. Extending the work of Sandikci et al. (2013) on two-stage stochastic mixed-integer-programs (SMIPs), this paper develops … Read more

    A Parallel Local Search Framework for the Fixed-Charge Multicommodity Network Flow Problem

  • Shabbir Ahmed
  • Lluís-Miquel Munguía
  • George L. Nemhauser
  • David A. Bader
  • Vikas Goel
  • Yufen Shao
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Parallel Algorithms Tags , ,

    We present a parallel local search approach for obtaining high quality solutions to the Fixed Charge Multi-commodity Network Flow problem (FCMNF). The approach proceeds by improving a given feasible solution by solving restricted instances of the problem where flows of certain commodities are fixed to those in the solution while the other commodities are locally … Read more