# Presentation: 223393

- Metacomputing + Optimization
- Plan to
- develop metacomputing-aware optimization software for specific problems and applications
- develop metacomputing infrastructure that is applicable to other areas of computational science and engineering
- leverages and builds on NEOS, Condor, Globus
- NSF funding from now til 2000; investigators from ANL, Wisconsin, Columbia, Northwestern

- metaNEOS

**http://www.mcs.anl.gov/metaneos/**

## Target Problems and Applications

***Problems must be amenable to an asynchronous, heterogeneous environment***
***Problems must be very large, or there must be a real-time imperative***

## Mixed-Integer Programming

- probably the biggest “market share” in optimization
- MIP codes traditionally built on simplex codes (use of interior-point codes is a research question)
- use branch-and-bound (traditional) along with new ideas in branch-and-cut, branch-and-price
- parallel algorithms are typically master/worker, with variants. Compact checkpointing is possible.
- efforts at Columbia, Wisconsin, Argonne (?);collaboration with Sandia.

## Discrete problems in network design/routing

- telecommunications networks: installation of capacity (design), real-time routing
- large and complex
***multicommodity flow problems*** solved by a master-worker approach, possibly with replicated masters. Workers use new techniques for approximate solution of LPs.
***set-covering problems*** also solved with master-worker approach (similar issues arise).
- effort at Columbia

## Global Optimization

- target: distance geometry from NMR data
- DGSOL code implements smoothing / continuation strategy; enhance with multistart for  additional parallel capability.
- mainly asynchronous, but tasks can be spawned dynamically (when solutions bifurcate)
- first phase: DGSOL + CONDOR
- effort at Argonne and Wisconsin

## Traffic Flow and Guidance Information

- real-time imperative; ultimate goal is control of traffic flow to minimize congestion (ambitious)
- issues of data movement/integration and heterogeneity
- two paradigms: system equilibrium  and user equilibrium. Latter is more promising, but need extensions for dynamic road conditions, stochastic effects, user non-compliance, route changing
- effort at Wisconsin: task-spawning AMPL processes, stochastic version of user equilibrium

## Metacomputing Issues

- Build on Condor and Globus features
- resource identification, management, scheduling
- communications protocols
- persistency
- checkpointing (compact for many optimization apps)
- metaNEOS applications are challenging; will influence the development of metacomputing infrastructure
- tasks spawned dynamically
- sometimes difficult to estimate resource needs a priori
- a variety of communications and synchronicity needs

## metaNEOS optimization applications

- metaNEOS resource broker

**GRM interface**

**GRM interface**

**GRM interface**

**GRM interface**

**Condor pool**

**Condor pool**

**MPP scheduler**

**LSF pool**

## Network Accessibility

- Build on NEOS tools for
- adding software components
- constructing network interface for new components
- web-accessible usage monitoring

***Solvers should be invokable over a network from ***
***legacy code, modeling  language, or GUIs ***
***running on a user’s workstation.***

## NEOS/NEXUS effort at Argonne, Wisconsin, NU
AMPL/NEOS: user runs an AMPL session locally, invokes remote solvers
NEOS solvers invoked remotely from procedural codes. allows nonblocking calls (cheap parallelism)

- AMPL/NEOS: user runs an AMPL session locally, invokes remote solvers
- NEOS solvers invoked remotely from procedural codes. allows nonblocking calls (cheap parallelism)