Parallel Algorithms

Implementing Algorithms for Signal and Image Reconstruction on Graphical Processing Units

  • Sangkyun Lee
  • Stephen Wright
    • Categories Nonsmooth Optimization, Parallel Algorithms Tags , , ,

    Several highly effective algorithms that have been proposed recently for compressed sensing and image processing applications can be implemented efficiently on commodity graphical processing units (GPUs). The properties of algorithms and application that make for efficient GPU implementation are discussed, and computational results for several algorithms are presented that show large speedups over CPU implementations. … Read more

    Parallel Space Decomposition of the Mesh Adaptive Direct Search algorithm

  • Charles Audet
  • John E. Dennis, Jr.
  • Sébastien Le Digabel
    • Categories Applications - OR and Management Sciences, Nonsmooth Optimization, Parallel Algorithms Tags , , , ,

    This paper describes a parallel space decomposition PSD technique for the mesh adaptive direct search MADS algorithm. MADS extends a generalized pattern search for constrained nonsmooth optimization problems. The objective of the present work is to obtain good solutions to larger problems than the ones typically solved by MADS. The new method PSD-MADS is an … Read more

    Computational Experience with a Software Framework for Parallel Integer Programming

  • Lazslo Ladanyi
  • Ted K. Ralphs
  • Matthew Saltzman
  • Yan Xu
    • Categories (Mixed) Integer Linear Programming, Optimization Software Design Principles, Parallel Algorithms

    In this paper, we discuss the challenges that arise in parallelizing algorithms for solving mixed integer linear programs and introduce a software framework that aims to address these challenges. The framework was designed specifically with support for implementation of relaxation-based branch-and-bound algorithms in mind. Achieving efficiency for such algorithms is particularly challenging and involves a … Read more

    Asynchronous parallel generating set search for linearly-constrained optimization

  • Joshua D. Griffin
  • Robert Michael Lewis
  • Tamara Kolda
    • Categories Constrained Nonlinear Optimization, Parallel Algorithms, Robust Optimization Tags , , , , , , , ,

    Generating set search (GSS) is a family of direct search methods that encompasses generalized pattern search and related methods. We describe an algorithm for asynchronous linearly-constrained GSS, which has some complexities that make it different from both the asynchronous bound-constrained case as well as the synchronous linearly-constrained case. The algorithm has been implemented in the … Read more

    MW: A Software Framework for Combinatorial Optimization on Computational Grids

  • Wasu Glankwamdee
  • Jeff Linderoth
    • Categories Combinatorial Optimization, Parallel Algorithms Tags , , ,

    Our goal in this paper is to demonstrate that branch-and-bound algorithms for combinatorial optimization can be effectively implemented on a relatively new type of multiprocessor platform known as a computational grid. We will argue that to easily and effectively harness the power of computational grids for branch-and-bound algorithms, the master-worker paradigm should be used to … Read more

    A DISTRIBUTED, SCALEABLE SIMPLEX METHOD

  • Richard Van Slyke
  • Gavriel Yarmish
    • Categories Linear Programming, Parallel Algorithms

    We present a simple, scaleable, distributed simplex implementation for large linear programs. It is designed for coarse grained computation, particularly, readily available networks of workstations. Scalability is achieved by using the standard form of the simplex rather than the revised method. Virtually all serious implementations are based on the revised method because it is much … Read more

    Social Cognitive Maps, Swarm Collective Perception and Distributed Search on Dynamic Landscapes

  • Carlos Fernandes
  • Vitorino Ramos
  • Agostinho C. Rosa
    • Categories Nonlinear Systems and Least-Squares, Parallel Algorithms, Stochastic Approaches Tags , , , ,

    Swarm Intelligence (SI) is the property of a system whereby the collective behaviors of (unsophisticated) entities interacting locally with their environment cause coherent functional global patterns to emerge. SI provides a basis with wich it is possible to explore collective (or distributed) problem solving without centralized control or the provision of a global model. To … Read more

    Varying the Population Size of Artificial Foraging Swarms on Time Varying Landscapes

  • Carlos Fernandes
  • Vitorino Ramos
  • Agostinho C. Rosa
    • Categories Nonlinear Systems and Least-Squares, Parallel Algorithms, Stochastic Approaches Tags , , , , , ,

    Swarm Intelligence (SI) is the property of a system whereby the collective behaviors of (unsophisticated) entities interacting locally with their environment cause coherent functional global patterns to emerge. SI provides a basis with wich it is possible to explore collective (or distributed) problem solving without centralized control or the provision of a global model. In … Read more

    Exploiting Structure in Parallel Implementation of Interior Point Methods for Optimization

  • Jacek Gondzio
  • Andreas Grothey
    • Categories Optimization Software Design Principles, Parallel Algorithms Tags , ,

    OOPS is an object oriented parallel solver using the primal dual interior point methods. Its main component is an object-oriented linear algebra library designed to exploit nested block structure that is often present is truly large-scale optimization problems. This is achieved by treating the building blocks of the structured matrices as objects, that can use … Read more

    Algorithm xxx: APPSPACK 4.0: Asynchronous Parallel Pattern Search for Derivative-Free Optimization

  • Genetha Gray
  • Tamara Kolda
    • Categories Bound-constrained Optimization, Optimization Software and Modeling Systems, Parallel Algorithms Tags , , ,

    APPSPACK is software for solving unconstrained and bound constrained optimization problems. It implements an asynchronous parallel pattern search method that has been specifically designed for problems characterized by expensive function evaluations. Using APPSPACK to solve optimization problems has several advantages: No derivative information is needed; the procedure for evaluating the objective function can be executed … Read more