Project Goals

The goals of MetaNEOS are to
  • design metacomputing environments suitable for solving large optimization problems,
  • identify optimization problems that fit these environments, and develop algorithms to solve them, and
  • use the resulting tools to solve problems of unprecedented size and complexity.

What's a Metacomputer?

A metacomputing platform is made up of a collection of computers (and possibly other resources such as visualization and storage devices) that are geographically distributed, but networked in various ways.

The metacomputing platforms that we use in metaNEOS have the overriding advantage that they are inexpensive. We focus in particular on platforms that utilize idle time on collections of workstations, which is essentially free. The Condor system delivers an environment of this type.

Despite their low cost, the platforms we use are potentially very powerful. However, they have features that make them much more difficult to program than traditional parallel computers. These include:
  • Dynamic availability. The number of processors available to us may vary over time, as may the throughput we receive from an individual processor.
  • Unreliability. Processors that we are using for our computations may disappear without notice.
  • Poor communications properties. Communication latency between any given pair of processors may be high, variable, and unpredictable. Connectivity (as measured, for example, by bisection bandwidth) may be particularly low.
  • Heterogeneity. The processors in our metacomputer may differ in their CPU speed or amount of memory, for instance.
  • Scale. The number of resources available to us may be much larger than in a conventional parallel computer.
Our Approach

The metaNEOS project integrates fundamental algorithmic research in optimization with research and infrastructure tool development in distributed systems management. Algorithms that can exploit the powerful but heterogeneous, high-latency and possibly failure-prone virtual hardware platform typical of metacomputing platforms have been developed in such areas as
  • global optimization,
  • integer linear optimization,
  • integer nonlinear optimization,
  • combinatorial optimization, and
  • stochastic optimization.
News!

We have developed a new API called MW that enables straightforward implementation of a wide variety of algorithms and applications on the Condor high-throughput computing environment.

Check out iMW, our web-based problem-solving environment for metacomputing applications.

We're now solving benchmark problems in stochastic programming and the quadratic assignment problem of record-breaking size on the Condor pools at the University of Wisconsin.

Seymour mixed integer programming instance solved! (07/2000)

metaneos@mcs.anl.gov
Last modified: February 28, 2002.