External Contacts.
- Meteo France are interested in new (parallel) optimization
algorithms for problems that arise in weather forecasting. JorgeN's
student Richard Waltz is currently involved; Steve may also be
involved; the contact is Jean-Noel Thepaut. Currently, new
optimization methods for their variational data assimilation models
are being tested. A long-term goal is to develop reverse communication
and distributed computing environments to accelerate the optimization
calculation.
- Electricite' de France (Jean-Pierre Goux's current employers) are
interested in a metacomputing environment for transmission network
planning. Jean-Pierre Goux and Jorge Nocedal are studying the
feasibility of this project. Their formulation uses Benders
Decomposition and requires the solution of a series of master MIPs, of
increasing size. Marcel Good may work on this as part of his MS
thesis. This project has possible overlap with the work of Golbon and
Linderoth.
- David Abramson and the NIMROD team at Monash University in
Melbourne are interested in using NIMROD in various optimization
contexts. They are affiliated with the Globus project and after a
number of mutual visits their ties to metaneos are getting
stronger. NIMROD has an advantage of ease-of-use that will fit it well
for certain optimization algorithms.
Projects and Goals
NEOS Server
Jorge More' and Mike Mesnier continue to develop the Server
infrastructure. Server usage picked up sharply from February onwards,
mostly because of its widespread use in class assignments.
Many new solvers have been added. There is a large collection of
solvers with AMPL front-ends, described in a recent note by Jorge
More' in "Optima." The XPRESS-MP package was recently brought up on
TESTNEOS and will be transferred to the main Server after some
testing. This is the first integer programming solver to be made
available on NEOS and it may present the Server with significant
resource challenges, because of the possibility of many large jobs.
Development of NEOS-in-a-Box, the package that allows installation of
NEOS-like Servers at other sites, in continuing. NEOS-in-a-Box
installations have been done in Taiwan and at Columbia. ANU in
Canberra is keen to use Server technology to facilitate remote access
to the numerical tools they have been developing for their Fujitsu
supercomputer.
Jorge Nocedal, Leo Lopes and Marcelo Marazzi will introduce new
features into the NITRO (nonlinear programming interior-point) solver
that attempt to bridge the gap between working with NEOS, and the
standard environment in which all programs reside in the user's
machine. The goal is to facilitate the search for bugs in the
information submitted to NEOS, and to enable a variety of program
options. The user will be able to download a number of "drivers" that
can be used as templates in the NEOS submissions.
Mike Mesnier's departure leaves a large gap in the Server project that
will be hard to fill, given the current general shortage of
computer-savvy people. However the centrality of the NEOS Server makes
it important that we address this need. The Server should be a focal
point for the metaneos project. Software developed under the aegis of
metaneos should be made available through the Server in
single-processor or modestly parallel form.
Jorge More' is canvassing Server users to ask what new features are in
demand.
Recent/Ongoing Developments:
-
NEOS-in-a-Box Portable Server implementation; new Servers installed
in Taiwan and at Columbia
-
Server described in papers and documentation
-
Enhanced NEOS Communications package and Server architecture
-
CORBA and C library interfaces
-
Implementation of access restrictions to prevent overuse by any one
individual or site of the Server - particularly of proprietary solvers
such as XPRESS-MP.
-
NEOS/NEXUS (with Todd Munson; see below)
- Many new solvers added to the Server, including AMPL/* and
XPRESS-MP.
Future Directions:
- More solvers can be added. Areas of emphasis should include
integer programming (XPRESS, MIQP)
global optimization solvers of different flavors
application-specific solvers in key areas
- More AMPL front-ends to current solver collection, and add GAMS
front-end versions as well
- A Java-based Interface to supplement or replace the current Tcl/Tk
"submit" tool.
- Establishment of NEOS-like servers at other sites, in other
numerical computing disciplines, via NEOS-in-a-Box.
Reverse-Communication and Remote-Invocation Modes
Jean-Pierre Goux, Mike Mesnier, and Todd Munson have all worked on
client-server models in which remotely executing optimization codes
are called from user native (C or FORTRAN) codes. In Mike's
CORBA-based facility, the client machine uses the NEOS Server to
obtain the address of the CORBA name server, which in turn yields the
address of the optimization code. The client and optimization code
then interact directly; the function/derivative information can be
evaluated on the client and the search direction decisions made by the
optimization server. In Jean-Pierre's Nexus-based facility, the remote
server process provides a port number to which the client attaches
directly. Interaction between client and server now takes place in the
usual way. NEOS/NEXUS (Todd and Jorge More') is another client/server
model that allows blocking and non-blocking calls to be made to remote
optimization processes; PATH, DGSOL, and PCx were used in the demo
version. For further info see
http://www-neos.mcs.anl.gov/neos/neos_nexus/neos_nexus.html
What is the current status of NEOS/NEXUS?
Jorge Nocedal and Leo Lopes are currently collaborating with Kyle
Anderson from NASA-Langley on a reverse communication environment for
shape optimization. This work builds on the Nexus-based code developed
by Jean-Pierre Goux. The goal is to perform the fluid flow simulation
on an SGI at NASA and the optimization at NU. When this project is
complete, Todd Plantenga will use the software to perform reverse
communication computations for molecular conformation problems at
Sandia Lab.
Reverse communication modes are of (long-term) interest in the Meteo
France collaboration; see personnel section above.
Future Directions:
- Development of NEOS/NEXUS
- Application of reverse-communication optimization technology to
meteorology / data assimilation, shape optimization,
- Identifying other applications that require this technology,
e.g. applications for which the data or model is sensitive, or where
the model evaluation must run on dedicated client hardware (for
reasons of security or non-portability of the simulation code)
AMPL/NEOS Server
Bob Fourer (Northwestern) and Jean-Pierre Goux have collaborated on a
system that allows users to invoke optimization codes remotely from an
AMPL session running on their own workstation. They are keen to
continue development of this system and extend it to PC-based
operating systems.
Parallel Integer Programming
At Columbia (Sebastian and Dan) the focus is on the MIPO (mixed
integer optimizer) linear programming solver, which uses
branch-and-cut techniques involving lift-and-project cuts and
disjunctive cuts. The approach is to develop a parallel code for
shared-memory architechures, and then transition it to a metacomputing
platform. Testing on the shared-memory version of MIPO is giving
excellent results. This has been a summer project of Philipp Gross
(Sys Admin in IEOR at Columbia). Transitioning to a cluster of
workstations should not be too difficult.
Michael Ferris and student Qun Chen are developing a fault tolerant
mixed integer programming code written in PVM that runs over Condor.
A version is already working and I have had some success solving the
VOD (video-on-demand) problems using this code. Miron and Bin Song
were instrumental in helping to get the Condor PVM environment
running. The code uses GAMS for input of the problems, making it easy
to generate large numbers of problems and also to interact directly
with the named applications. Michael's intention was to develop a
further collaboration with Ceria at Columbia to try to port his codes
into this environment, but he has not followed this through as yet.
Future Directions:
- Further code and environment development of the branch-and-bound /
Condor code at Wisconsin.
- Applications of this code to very large, multiple-MIP problems
arising from video-on-demand.
- Further development and testing of Columbia shared-memory code
- Transition of the Columbia MIPO code to metacomputing
environment. Michael is keen to collaborate on a Condor-based
implementation. Implementation on Globus platforms (e.g. GUSTO) and
use in solving very large problems would be a coup!
Approximate Solvers for Large LPs
Dan Bienstock has been implementing a general-purpose approximate LP
solver built on the ideas of Gregoriadis and Khachiyan, and Plotkin,
Shmoys and Tardos on exponential penalty functions. The code has been
tested on two classes of problems: large scale relaxations of network
design problems (the original motivating application) and large-scale
set covering problems. On both classes of problems the approach seems
to work quite well, obtaining solutions with 2.5 digits of accuracy
much faster than possible with simplex or barrier methods (i.e. much
faster than those methods can obtain a solution with comparable
accuracy). Much work remains to be done. The current code does not
work well with set-partitioning problems, for example. In general, the
main thrust of the work is to make the code perform well with
large-scale block-diagonal problems (with linking constraints). In
this context, parallel and distributed implementations may be
possible. The effectiveness of the parallel version remains to be
determined, but the very large scale of these problems makes them a
candidate for solution on a powerful metacomputing system.
Stochastic Programming
Golbon and Steve are interested in this topic. Like integer
programming, it is an area that stands to benefit a great deal from
the explosion in computational capacity. In particular, it could
benefit a great deal from metacomputing technology. Problems tend to
be very large; most applications are in economic planning and finance,
where intranet/networked-workstation platforms are widespread;
parallel algorithms based on decompositions/dissections are generally
intermediate in complexity between global optimization algorithms and
parallel integer programming algorithms. There are many flavors of
stochastic programming paradigms and algorithms; Steve is still
learning about them. One caveat: The business of modeling/formulation
of stochastic programs does not yet appear to be well advanced; good
techniques for modeling under uncertainty have apparently not broken
through to a wide user community.
Possible target algorithms include those that attempt to solve exactly
multistage stochastic programs with recourse. Parallel dissection
algorithms map the computational tree - which is known a priori,
unlike in integer programming - to the available
resources. Information must be passed back from later stages to
earlier ones (in the form of feasibility and optimality cuts), from
earlier stages to later ones (in the form of candidate
solutions). Communication/synchronization requirements are not too
stringent. Parallel implementations exist, even on workstation
arrays. Metacomputing implementation would allow solution of much
larger problems.
Algorithms involving sampling of the uncertainty parameter space
parallelize in a fairly obvious way, though it is still a challenge to
retain some of the computational efficiences that are available on a
uniprocessor. Proximal-point approaches such as progressive hedging
also parallelize well, but these approaches appear to be slow.
John Birge has agreed to let us experiment with metacomputing
implementation of his group's state-of-the-art nested decomposition
code, which has been implemented already on a small cluster of
workstations. The heuristics in this code (particularly those
involving sampling) may need to be modified for a metacomputing
platform.
Another class of problems involving optimization of expected-value
functions has received some recent attention in the literature
(e.g. recent paper by Steve Robinson). The approach is to sample the
function and its gradient for many values of the random variable, and
then apply a subgradient algorithm. The function may be expected
time-to-completion of an assembly line process, for instance, with
stochastic delays and breakdowns at different points in the line. For
many applications, the sampling is trivially parallelizable. If there
is a "quorum" of interesting problems in this area, we will
investigate a metacomputing implementation. The demands on the
metacomputing platform should be no more complex than for DGSOL, so
APIs based on Condor or Nimrod may be appropriate.
Current Status: Still investigating.
Global Optimization
The More'-Wu global optimization code DGSOL is a natural candidate for
metacomputing implementation. Motivating applications have come mainly
from molecular conformation problems, in which the "native" state is
assumed to be the global minimizer of a certain potential function
that has many local minima.
Current and ongoing work involves Jorge More' and Golbon. They are
looking at making the following connections:
DGSOL/Condor/PVM - Golbon
DGSOL/Globus - Golbon
DGSOL/Nimrod - Golbon (currently lower priority)
DGSOL/Nexus - Todd Munson (ongoing work, started in summer 1997)
Optimization Modeling Language Interfaces to Metacomputing Environments
Michael Ferris and Todd Munson at Wisconsin are investigating the
interface between the better-known optimization modeling languages and
Condor, and are collecting applications that demonstrate the utility
of such an interface. A draft paper is obtainable from Michael. It
proposes a "spawn/retrieve" mechanism, implementable in GAMS and AMPL
by which large task pools of optimization jobs can be solved in a
Condor pool.
The applications are extremely interesting: radiotherapy and
video-on-demand (VOD). A report on the former is available on
Michael's web site; a report on the latter is forthcoming. In both
applications, it is proposed to use a GAMS model is used to generate
large numbers of computationally intensive optimization programs that
will test out our interface. Work on realization of these proposals is
ongoing, in collaboration with the Condor group. An immediate need is
to have Condor allow the inclusion of certain named files in a
checkpoint.
The AMPL/NEOS work (Goux and Fourer) combines in an obvious way with
this - it adds the dimension of remote execution. A modeling process
executing on a workstation could solve a very demanding optimizaiton
problem by spawning a large number of tasks on a remote Condor pool.
Relevant External Work
It will benefit us to know about what other groups are up to in the
area of scientific computing (optimization in particular) on
distributed platforms. People in these groups are potential
collaborators and could be invited to our project meetings, for
instance.
- NIMROD is a project of a group in Melbourne headed by David
Abramson. They are currently affiliated with Globus, but not
metaneos. Nimrod is a system for running a batch of similar tasks on
each node of a heterogeneous network, where the tasks differ in the
values of a few input parameters. It is useful for searching the whole
parameter space. A current activity is to implement unconstrained
optimization algorithms such as steepest descent and BFGS on a
platform that combines elements of Globus and Nimrod. Their
applications are large-scale environmental remediation problems. For
details see
http://www.dgs.monash.edu.au/~davida/optdss.html
- NETSOLVE is the Dongarra project based at Oak Ridge and Tennessee
whose aim is to make existing numerical libraries invokable over the
Internet, via calls from native code and MATLAB. Their emphasis
differs from the that of NEOS Server in a number of respects, and the
system (still evolving) is sophisticated and deserves
attention. Unfortunately, they view themselves as rivals of ours and
the possibilities of cooperation seem limited. See
http://www.cs.utk.edu/netsolve/
[metaneos home page]