Parallel Algorithms

Parallel Interior Point Solver for Structured Quadratic Programs: Application to Financial Planning Problems

  • Jacek Gondzio
  • Andreas Grothey
    • Categories Finance and Economics, Parallel Algorithms, Quadratic Programming

    Issues of implementation of a library for parallel interior-point methods for quadratic programming are addressed. The solver can easily exploit any special structure of the underlying optimization problem. In particular, it allows a nested embedding of structures and by this means very complicated real-life optimization problems can be modeled. The efficiency of the solver is … Read more

    A methodology for the analysis of parallel GRASP strategies

  • Renata M. Aiex
  • Mauricio G.C. Resende
    • Categories Meta Heuristics, Parallel Algorithms Tags , ,

    In this paper, we describe a methodology for the analysis of greedy randomized adaptive search procedures (GRASP). GRASP is a metaheuristic for combinatorial optimization. It usually consists of a construction procedure based on a greedy randomized algorithm and a local search. Hybrid approaches of GRASP with path-relinking developed for the 3-index assignment problem (AP3) and … Read more

    Parallel Interval Continuous Global Optimization Algorithms

  • Abdeljalil Benyoub
    • Categories Branch and Cut Algorithms, Global Optimization, Parallel Algorithms Tags , , , , ,

    We theorically study, on a distributed memory architecture, the parallelization of Hansen’s algorithm for the continuous global optimization with inequality constraints, using interval arithmetic. We propose a parallel algorithm based on a dynamic redistribution of the working list among the processors. On the other hand, we exploit the reduction technique, developped by Hansen, for computing … Read more

    Parallel Computing on Semidefinite Programs

  • Steven Benson
    • Categories Parallel Algorithms, Semi-definite Programming Tags , , ,

    This paper demonstrates how interior-point methods can use multiple processors efficiently to solve large semidefinite programs that arise in VLSI design, control theory, and graph coloring. Previous implementations of these methods have been restricted to a single processor. By computing and solving the Schur complement matrix in parallel, multiple processors enable the faster solution of … Read more

    Large-Scale Linear Programming Techniques for the Design of Protein Folding Potentials

  • Ron Elber
  • Jaroslaw Meller
  • Michael Wagner
    • Categories Basic Sciences Applications, Linear Programming, Parallel Algorithms Tags , , ,

    We present large-scale optimization techniques to model the energy function that underlies the folding process of proteins. Linear Programming is used to identify parameters in the energy function model, the objective being that the model predict the structure of known proteins correctly. Such trained functions can then be used either for {\em ab-initio} prediction or … Read more

    NLPQLP: A New Fortran Implementation of a Sequential Quadratic Programming Algorithm

  • Klaus Schittkowski
    • Categories Constrained Nonlinear Optimization, Optimization Software Benchmark, Parallel Algorithms Tags , , , , , ,

    The Fortran subroutine NLPQLP solves smooth nonlinear programming problems and is an extension of the code NLPQL. The new version is specifically tuned to run under distributed systems. A new input parameter l is introduced for the number of parallel machines, that is the number of function calls to be executed simultaneously. In case of … Read more

    Pivot, Cut, and Dive: A Heuristic for 0-1 Mixed Integer Programming

  • Jonathan Eckstein
  • Mikhail S. Nediak
    • Categories (Mixed) Integer Linear Programming, Meta Heuristics, Parallel Algorithms Tags , ,

    We present a heuristic method for general 0-1 mixed integer programming, intended for eventual incorporation into parallel branch-and-bound methods for solving such problems exactly. The core of the heuristic is a rounding method based on simplex pivots, employing only gradient information, for a strictly concave, differentiable merit function measuring integer feasibility. When local minima of … Read more

    Solving large MINLPs on computational grids

  • Jean-Pierre Goux
  • Sven Leyffer
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Parallel Algorithms Tags , , ,

    We consider the solution of Mixed Integer Nonlinear Programming (MINLP) problems by a parallel implementation of nonlinear branch-and-bound on a computational grid or meta-computer. Computational experience on a set of large MINLPs is reported which indicates that this approach is efficient for the solution of large MINLPs. Citation Numerical Analysis Report NA/200, Department of Mathematics, … Read more

    Decomposition Algorithms for Stochastic Programming on a Computational Grid

  • Jeff Linderoth
  • Stephen Wright
    • Categories Parallel Algorithms, Stochastic Programming Tags ,

    We describe algorithms for two-stage stochastic linear programming with recourse and their implementation on a grid computing platform. In particular, we examine serial and asynchronous versions of the L-shaped method and a trust-region method. The parallel platform of choice is the dynamic, heterogeneous, opportunistic platform provided by the Condor system. The algorithms are of master-worker … Read more

    Optimization on Computational Grids

  • Stephen Wright
    • Categories Branch and Cut Algorithms, Parallel Algorithms, Stochastic Programming Tags , , , ,

    We define the concept of a computational grid, and describe recent work in solving large and complex optimization problems on this type of platform; in particular, integer programming, the quadratic assignment problem, and stochastic programming problems. This article focuses on work conducted in the metaneos project. Citation Preprint, Mathematics and Computer Science Division, Argonne National … Read more