Parallel Algorithms

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

    Assessing the Effectiveness of (Parallel) Branch-and-bound Algorithms

  • Stephen J. Maher
  • Ted K. Ralphs
  • Yuji Shinano
    • Categories (Mixed) Integer Linear Programming, Integer Programming, Parallel Algorithms Tags , , , , , ,

    Empirical studies are fundamental in assessing the effectiveness of implementations of branch-and-bound algorithms. The complexity of such implementations makes empirical study difficult for a wide variety of reasons. Various attempts have been made to develop and codify a set of standard techniques for the assessment of optimization algorithms and their software implementations; however, most previous … Read more

    Decentralized Online Integer Programming Problems with a Coupling Cardinality Constraint

  • Shabbir Ahmed
  • George L. Nemhauser
  • Ezgi Karabulut
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms Tags , ,

    We consider a problem involving a set of agents who need to coordinate their actions to optimize the sum of their objectives while satisfying a common resource constraint. The objective functions of the agents are unknown to them a priori and are revealed in an online manner. The resulting problem is an online optimization problem … Read more

    Scalable Preconditioning of Block-Structured Linear Algebra Systems using ADMM

  • Carl D. Laird
  • Victor M. Zavala
  • Jose Rodriguez
    • Categories Parallel Algorithms, Quadratic Programming, Stochastic Programming

    We study the solution of block-structured linear algebra systems arising in optimization by using iterative solution techniques. These systems are the core computational bottleneck of many problems of interest such as parameter estimation, optimal control, network optimization, and stochastic programming. Our approach uses a Krylov solver (GMRES) that is preconditioned with an alternating method of … Read more

    On Electricity Market Equilibria with Storage: Modeling, Uniqueness, and a Distributed ADMM

  • Julia Grübel
  • Thomas Kleinert
  • Vanessa Krebs
  • Lars Schewe
  • Martin Schmidt
  • Johannes Thürauf
  • Galina Orlinskaya
    • Categories Convex Optimization, Parallel Algorithms, Quadratic Programming Tags , , , , , ,

    We consider spot-market trading of electricity including storage operators as additional agents besides producers and consumers. Storages allow for shifting produced electricity from one time period to a later one. Due to this, multiple market equilibria may occur even if classical uniqueness assumptions for the case without storages are satisfied. For models containing storage operators, … Read more

    A two-level distributed algorithm for nonconvex constrained optimization

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

    This paper aims to develop distributed algorithms for nonconvex optimization problems with complicated constraints associated with a network. The network can be a physical one, such as an electric power network, where the constraints are nonlinear power flow equations, or an abstract one that represents constraint couplings between decision variables of different agents. Despite the … Read more

    Pattern-based models and a cooperative parallel metaheuristic for high school timetabling problems

  • Alysson Machado Costa
  • Lana M. R. Santos
  • Maristela O. Santos
  • Landir Saviniec
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms, Scheduling Tags , , ,

    High school timetabling problems consist in building periodic timetables for class-teacher meetings considering compulsory and non-compulsory requisites. This family of problems has been widely studied since the 1950s, mostly via mixed-integer programming and metaheuristic techniques. However, the efficient obtention of optimal or near-optimal solutions is still a challenge for many problems of practical size. In … Read more

    Scalable Branching on Dual Decomposition of Stochastic Mixed-Integer Programming Problems

  • Brian Dandurand
  • Kibaek Kim
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms, Stochastic Programming

    We present a scalable branching method for the dual decomposition of stochastic mixed-integer programming. Our new branching method is based on the branching method proposed by Caro e and Schultz that creates branching disjunctions on first-stage variables only. We propose improvements to the process for creating branching disjunctions, including 1) branching on the optimal solutions … Read more

    POLO: a POLicy-based Optimization library

  • Arda Aytekin
  • Martin Biel
  • Mikael Johansson
    • Categories Convex and Nonsmooth Optimization, Optimization Software Design Principles, Parallel Algorithms Tags , , , ,

    We present POLO — a C++ library for large-scale parallel optimization research that emphasizes ease-of-use, flexibility and efficiency in algorithm design. It uses multiple inheritance and template programming to decompose algorithms into essential policies and facilitate code reuse. With its clear separation between algorithm and execution policies, it provides researchers with a simple and powerful … Read more