# Presentation: 431497

## AcroA Common Repository for Optimizers

- William E Hart
- Discrete Algorithms and Math Dept
- Sandia National Laboratories
- _[wehart@sandia.gov](mailto:wehart@sandia.gov)_
- www.cs.sandia.gov/~wehart

## Acro

**Acro**

*acro* - From Greek akros, at the point, end, or top.
*acro* - A generic term for warblers of the genus Acrocephalus, usually referring to the sedge and/or reed warblers. It spends summers in the UK and winters in Africa, south of the Sahara Desert.
*acro* - A Common Repository for Optimizers

## Outline

- Overview of Acro
- Acro projects
- Acro management
- Ongoing/Future activities

## The Acro Software Repository

- Goal:
- Integrate the management of SNL optimization libraries
- Software Management:
- Consolidation of configuration management
- Easier build management (avoid multiple library checkouts)
- Consolidated testing management
- Management of third-party solvers
- Software Design:
- Finer-grain library development
- E.g. simplifies Coliny interaction with other optimizers
- Facilitate the development of hybrid optimization methods

## Acro Organization

- Packages – distinct software libraries
- SNL optimization libraries whose development is managed by the Acro CVS repository
- Snapshots of third-party libraries that integrated into the Acro CVS repository
- Projects – ensembles of packages
- Acro manages package integration
- Projects can be checked out separately from the CVS repository

## Acro Packages

## Overview of Acro Projects

- APPSPACK
- Parallel pattern search
- Tammy Kolda
- Coliny
- Global optimization heuristics, derivative-free local search
- Bill Hart
- EXACT
- Framework for software testing and experimental analysis
- Jonathan Berry
- GNLP
- PEBBL-based rigorous global nonlinear optimization (continuous)
- Bill Hart

## Overview of Acro Projects		       (cont’d)

- OPT++
- Nonlinear programming methods
- Patty Hough
- ParPCx
- Parallel linear programming solver
- Erik Boman
- PEBBL
- Parallel branch and bound library (scalable to 10,000s processors)
- Jonathan Eckstein
- PICO
- PEBBL-based MILP solver
- Cindy Phillips

## Overview of Acro Projects		       (cont’d)

- UTILIB
- C++ utility library
- Bill Hart
- Note: there are *many* other contributors to these libraries...

## Acro Software Management

- Configuration management
- This is a key element of software quality
- Supports builds of software on diverse platforms
- Enables automatic builds for testing
- Acro Impact
- Historically, Acro packages were separate libraries built independently
- Acro integrated the configuration system for all packages
- Saving Bill H. from maintaining multiple config scripts...
- Software integrated avoids multiple library checkouts
- Consolidated software has facilitated testing management
- Management of third-party solvers can be done in an integrated fashion

## Managing Third Party Libraries

- Goal: integrate third party software into a common software repository
- Motivation: need to integrate a diverse range of solvers for sophisticated optimization solvers
- Example: PICO MILP solver
- UTILIB
- PEBBL
- MILP
- COIN-OR (CLP, OSI, COIN)
- GLPK
- SOPLEX

**Sandia Software**

**Third Party Software**

## Managing Third Party Libraries	       (cont’d)

- Acro Impact
- Management of build process
- Each TPL has its own build process
- Acro integration enables seamless builds
- TPL version control
- Acro TPL integration enables consistent dependency on TPLs for Acro developers
- Developers can try out new TPL releases without sacrificing stable builds
- TPL AcroVersioning of TPLs enables more facile integration
- TPL integration has promoted more direct comparisons of different sub-solvers (e.g. linear-programming solvers)

## Acro Software Quality Management

- Support for SQA activities is critical to successful software development
- Software stability is necessary for application impact
- Acro solvers are integrated into frameworks like DAKOTA
- PICO solver application is being deployed to the EPA
- FAST/EXACT
- Integration of distributed testing results
- Configuration and build statistics
- General-purpose computer experiments
- Computational experimental design
- Validation, benchmarking, performance comparisons, etc...

## Acro SQA

- Nightly testing
- Application interface tests
- DAKOTA, AutoDock, PDock
- Per-project build tests
- Different configuration setups (e.g. with/without MPI)
- Solver validation tests
- Portability tests – builds on 10+ different systems
- Target platforms
- Linux, Solaris, Darwin, *IRIX*, *OSF*, *AIX*, Cygwin, RedStorm, Windows
- Nightly email summaries w/ links to detailed web page summary
- Nightly summary of code stats: commits, documentation info, copyright blurbs, etc...

## Impacts on Acro Software Development

- Acro integration has encouraged fine-grain software decomposition
- Example: PICO -> PEBBL + PICO
- PEBBL branch and bound library was always generic, but couldn’t easily be used in other applications
- New applications: Lipshitzian global optimizer, quadratic semi-assignment solver, GNLP solver
- Acro integration has enabled hybridization of Acro solvers
- Example: GNLP solver integrates PEBBL, COIN (w/PICO LP management), and Coliny
- Example: Coliny includes COLIN solver wrappers for PEBBL Lipshitzian solver and APPSPACK solver

## Acro Release History

- Beta release: March 3, 2006
- Autoconf’d version of Acro
- Nightly testing of all Acro components
- Portability tests for key platforms (needed by DAKOTA)
- First official release: July 3, 2006
- (More) Uniform documentation within Acro software
- Documentation of Acro projects
- Resolution of outstanding Bugzilla issues
- GNU L-GPL licensing of all Acro projects
- Web interface to testing database
- Several subsequent incremental releases for specific projects: Coliny, PICO

## Ongoing/Future Work

- Conversion to SVN
- Acro release 1.1
- General PICO release
- FAST/EXACT release
- Upcoming Acro packages
- TMF: templatized meta-heuristics framework
- TraceCache: caching mechanism for optimization
- GNLP general release
- DDACE, DAKOTA, JEGA integration
- Other third-party libraries
- IPOPT integration, multi-objective EAs

## Thanks!

- See _[http://software.sandia.gov/Acro](http://software.sandia.gov/Acro)_ for more details...

## A More Detailed Discussion of Acro Projects...

## The APPSPACK Project

*A library for asynchronous parallel pattern search*
- Overview:
- Pattern search methods that can asynchronously manage function evaluations
- Integrates mechanisms for linear and nonlinear constraint management
- History:
- Earlier versions used PVM with a very decentralized parallelization (for robustness)
- Current version supports MPI and assumes more robust inter-processor communication

## APPSPACK Impact

- Application interfaces:
- Stand-alone executable (using file I/O for evaluations)
- AMPL interface (through Coliny)
- DAKOTA interface (through Coliny)
- Applications:
- Parameter estimation
- Protein structure prediction
- Engineering design
- Groundwater flow
- Microfluidics

## The Coliny Project

*A collection of COLIN optimizers*
- Overview:
- Mostly includes derivative-free and global search methods
- Also includes COLIN interfaces to non-Coliny solvers
- APPSPACK, Cobyla2, PLGO
- History:
- Coliny is the next generation of the SGOPT library
- SGOPT was decomposed into two pieces
- COLIN – a Common Optimization Library Interface
- Coliny – a collection of COLIN optimizers

## COLIN

- Idea: provide a common interface for optimization libraries
- Easily extensible C++ components to wrap third-party solvers
- Facilitates plug-and-play of optimizers for hybrid methods
- Can specify real parameters for generic search domains
- Dynamic mapping between problem domains
- Note: our goal is *not* to create the *best* OO optimization class heirarchy ... whatever that means

## Coliny Impact

**Coliny Impact**

- Application interfaces:
- AMPL interface
- DAKOTA interface
- Applications:
- Flexible Docking within AutoDock and PDock
- Engineering design
- Designing stable levitron devices
- Production planning for Pantex

## The EXACT and FAST Projects

*Tools for doing experimental testing*
- Overview:
- EXACT supports generic experimental design and analysis
- FAST supports a generic mechanism for nightly testing and data gathering
- History:
- Earlier versions were tightly integrated into Acro’s testing mechanism
- Recent generalization of EXACT into a separate python module (based on J. Berry’s earlier work)
- Recent generalization of FAST from Acro, supporting general-purpose clients and servers for nightly testing and code evaluations.

## EXACT/FAST Impact

- EXACT
- General toolkit has been used to manage computational experiments with several code projects: DAKOTA, Acro, SPOT
- Supports interactive experimentation – being used to for computational experiments in ongoig research
- Diagnostic tools like valgrind can be easily employed for testing
- Statistical analysis tools (from R) are being integrated
- FAST
- General framework for coordinating nightly builds – used in Acro, SPOT, Zoltan
- Supports “code checks” – analyses that assist in SW management
- Bugzilla summaries, commit activity, copyright documentation, analysis of subversion externals

## The GNLP Project

*A rigorous global optimizer for nonlinear problems*
- Overview:
- Leverages an explicit, algebraic problem representation
- Use branch-and-bound to solve to a specified tolerance
- Example: unique signal identification
- Goal: bound maximal probability of a malfunction in an electronics package
- Rigorous global optimization is needed to certify that the level of risk is acceptable.

## Summary of GNLP Activities

- CSRF Project:
- Extensions of PICO for nonlinear branch-and-bound
- Leveraging components of the COCONUT library
- Interfaces:
- AMPL interface
- COCONUT ‘dag’ representation
- Exploring funding possibilities w/in DOE Office of Science
- Applications (in progress):
- Fitting molecular mechanics force fields (M. Martin)
- Constraint satisfaction in system dynamics models (V. Tidwell)
- Parameter estimation (e.g. for surrogate-based optimization)
- Detangling in meshing (P. Knupp)

## The OPT++ Project

*An Object-Oriented Library for Nonlinear Optimizers*
- Overview:
- Algorithmic development of parallel derivative-free and gradient-based optimization methods to solve simulation-based optimization problems
- Includes unconstrained and constrained optimization methods
- Object structure distinguishes between nonlinear problem and optimization algorithm
- History:
- Earlier versions limited to solving unconstrained optimization problems
- Originally developed as serial package for prototyping and comparing algorithms
- Now incorporates coarse-grain parallelism using MPI and has been applied to a range of applications

## OPT++ Impact

- Application interfaces:
- Stand-alone executable (using file I/O for evaluations)
- Direct library interface
- DAKOTA interface
- Applications:
- Reliability-based design optimization
- Parameter identification
- Optimal design and control
- Computational fluid dynamics design optimization
- Molecular conformation
- Supernova search
- External radiotherapy treatment planning
- Fixed income analytics

## PEBBL

*A library for massively parallel branch-and-bound*
- Overview:
- Provides a generic, application-independent mechanism for parallel branch-and-bound
- Specifically tailored for massively parallel super computers
- History:
- Most of PEBBL’s development has been driven by the development of PICO, a parallel mixed-integer linear programming (MILP) solver
- Recently it has been more widely used for other applications

## The PEBBL Project

- Capabilities:
- Application framework can integrate PEBBL’s parallelization with multiple inheritance
- PEBBL manages a heterogeneous set of parallel “threads”
- Heuristics and bounding calculations
- Flexible hub/worker interaction
- Distributed management of subproblems
- Dynamic load balancing
- Asynchronous termination
- Applications:
- Lipshitzian global optimizer, PLGO, in Coliny
- Combinatorial peptide docking
- Rigorous nonlinear global optimizers (in GNLP)

## The PICO Project

- Goal: scalable parallel MILP solver
- Supports ramp-up parallelization phase
- Enables enumeration of near-optimal solutions
- Application Interfaces:
- AMPL interface
- PICO code generation using symbolic information from AMPL
- Applications:
- Combinatorial peptide docking
- Sensor placement for water security
- PICO solver delivered to the EPA
- Scheduling of supernovae observations
- Inventory logistics

## The ParPCx Project

*A Library for Parallel Linear Programming*
- Overview:
- ParPCx can solve linear programs in parallel using moderate number of processors.
- Uses interior-point method, suitable for large problems.
- History:
- Based upon PCx, a LP solver from Argonne.
- ParPCx uses Trilinos to solve linear systems in parallel.
- Intended both as a stand-alone LP solver and as a parallel solver to be used within PICO for MIP.
- Currently not actively developed.

## The UTILIB Project

*A C++ utility library*
- Overview:
- This is a library of commonly used C++ utilities within Acro
- UTILIB is similar in spirit to BOOST and STL
- Notes:
- There is a lot of overlap with BOOST and STL
- UTILIB supports mechanisms for error checking and debugging (e.g. trapping exceptions)
- Virtually all Acro projects depend on UTILIB
- UTILIB has been used outside of Acro a few times...

## UTILIB Capabilities

- Abstract data types
- hash tables, splay trees, heaps, arrays, extended reals, etc.
- Random number generators
- RNG’s, objects for generating various distributions
- Mathematical utilities
- Shuffling arrays, summary statistics, sorting wrappers, etc.
- I/O management
- Management of Common I/O operations (streaming to file, etc)
- Packing/Unpacking buffers for MPI
- Processing of command-line parameters