Parallel Algorithms

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

    A Distributed Quasi-Newton Algorithm for Primal and Dual Regularized Empirical Risk Minimization

  • Stephen Wright
  • Cong Han Lim
  • Ching-pei Lee
    • Categories Nonsmooth Optimization, Parallel Algorithms Tags , , , , , , ,

    We propose a communication- and computation-efficient distributed optimization algorithm using second-order information for solving empirical risk minimization (ERM) problems with a nonsmooth regularization term. Our algorithm is applicable to both the primal and the dual ERM problem. Current second-order and quasi-Newton methods for this problem either do not work well in the distributed setting or … Read more

    A robust method based on LOVO functions for solving least squares problems

  • E. V. Castelani
  • R. Lopes
  • W. V. I. Shirabayashi
  • Francisco N. C. Sobral
    • Categories Nonlinear Systems and Least-Squares, Nonsmooth Optimization, Parallel Algorithms Tags , , ,

    The robust adjustment of nonlinear models to data is considered in this paper. When data comes from real experiments, it is possible that measurement errors cause the appearance of discrepant values, which should be ignored when adjusting models to them. This work presents a Lower Order-value Optimization (LOVO) version of the Levenberg-Marquardt algorithm, which is … Read more