Parallel Algorithms

String-Averaging Methods for Best Approximation to Common Fixed Point Sets of Operators: The Finite and Infinite Cases

  • Yair Censor
  • Ariel Nisenbaum
    • Categories Convex Optimization, Nonlinear Optimization, Parallel Algorithms

    Abstract String-averaging is an algorithmic structure used when handling a family of operators in situations where the algorithm at hand requires to employ the operators in a specific order. Sequential orderings are well-known and a simultaneous order means that all operators are used simultaneously (in parallel). String-averaging allows to use strings of indices, constructed by … 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 Novel Cooperative Multi-search Benders Decomposition for Solving the Hydrothermal Unit-Commitment Problem

  • Felipe Beltrán
  • Bruno Colonetti
  • Erlon Finardi
  • Paulo Larroyd
    • Categories Applications - Science and Engineering, Parallel Algorithms, Scheduling

    Renewable energy and modernization of power operation demand Independent System Operators (ISOs) to solve ever more complex and larger programming problems to securely and economically schedule power resources. A key step in the scheduling process is the unit commitment (UC). In a hydro-dominated system, this process also involves managing reservoirs and is called hydrothermal UC … Read more

    A Distributed and Secure Algorithm for Computing Dominant SVD Based on Projection Splitting

  • Xin Liu
  • Lei Wang
  • Yin Zhang
    • Categories Constrained Nonlinear Optimization, Parallel Algorithms Tags , , ,

    In this paper, we propose and study a distributed and secure algorithm for computing dominant (or truncated) singular value decompositions (SVD) of large and distributed data matrices. We consider the scenario where each node privately holds a subset of columns and only exchanges “safe” information with other nodes in a collaborative effort to calculate a … Read more

    Limited-memory Common-directions Method for Large-scale Optimization: Convergence, Parallelization, and Distributed Optimization

  • Ching-pei Lee
  • Po-Wei Wang
  • Chih-Jen Lin
    • Categories Parallel Algorithms, Unconstrained Optimization Tags , , ,

    In this paper, we present a limited-memory common-directions method for smooth optimization that interpolates between first- and second- order methods. At each iteration, a subspace of a limited dimension size is constructed using first-order information from previous iterations, and an ef- ficient Newton method is deployed to find an approximate minimizer within this subspace. With … Read more

    A Two-level ADMM Algorithm for AC OPF with Convergence Guarantees

  • Xu Andy Sun
  • Kaizhao Sun
    • Categories Constrained Nonlinear Optimization, Network Optimization, Parallel Algorithms Tags , , ,

    This paper proposes a two-level distributed algorithmic framework for solving the AC optimal power flow (OPF) problem with convergence guarantees. The presence of highly nonconvex constraints in OPF poses significant challenges to distributed algorithms based on the alternating direction method of multipliers (ADMM). In particular, convergence is not provably guaranteed for nonconvex network optimization problems … Read more

    Manifold Identification for Ultimately Communication-Efficient Distributed Optimization

  • Wei-Lin Chiang
  • Yu-Sheng Li
  • Ching-pei Lee
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Parallel Algorithms Tags , , ,

    This work proposes a progressive manifold identification approach for distributed optimization with sound theoretical justifications to greatly reduce both the rounds of communication and the bytes communicated per round for partly-smooth regularized problems such as the $\ell_1$- and group-LASSO-regularized ones. Our two-stage method first uses an inexact proximal quasi-Newton method to iteratively identify a sequence … Read more

    Solving Previously Unsolved MIP Instances with ParaSCIP on Supercomputers by using up to 80,000 Cores

  • Tobias Achterberg
  • Timo Berthold
  • Stefan Heinz
  • Thorsten Koch
  • Yuji Shinano
  • Michael Winkler
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms, Problem Solving Environments Tags , , , , , ,

    Mixed-integer programming (MIP) problem is arguably among the hardest classes of optimization problems. This paper describes how we solved 21 previously unsolved MIP instances from the MIPLIB benchmark sets. To achieve these results we used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP computation: up to 80,000 cores in … Read more

    Linearization and Parallelization Schemes for Convex Mixed-Integer Nonlinear Optimization

  • Meenarli Sharma
  • Prashant Palkar
  • Ashutosh Mahajan
    • Categories (Mixed) Integer Nonlinear Programming, Parallel Algorithms Tags , , , ,

    We develop and test linearization and parallelization schemes for convex mixed-integer nonlinear programming. Several linearization approaches are proposed for LP/NLP based branch-and-bound. Some of these approaches strengthen the linear approximation to nonlinear constraints at the root node and some at the other branch-and-bound nodes. Two of the techniques are specifically applicable to commonly found univariate … 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