Future Directions of Parallel Processing
Steven J. Wallach (Hewlett-Packard, Convex Technology Center)
Modularity, expandability, etc., have been the watchwords of
Computer Architecture, hardware and software, since the dawn
of the computer age. Perhaps, much like every new generation
of cars, attributes will have higher reliability, more
flexibility, and be more cost effective. Today we even buy the
vast majority of computers at a retail establishment.
Finally this may, in fact, be true with the new generation of
multiprocessor ready microprocessors, standardized I/O busses.
This presentation explores, through the use of the term
"bricks", how teraflop class systems will be constructed. The
various alternative system architectures, the market
requirements, and cost structures will be examined in more
detail.
In particular, we will discuss massively parallel various ways
teraflop class sytems can be built. Different approaches to
cache coherency, latency issues on the interconnects, and
various programming paradigms. As part of this analysis, a
Kalmen Filter will be used to predict future technology. Also
some of the characteristics of the HP PA-8000 will be
described that assist in constructing teraflop class systems.
Return to Program Overview
Chair: Richard D. McBride (University of Southern California)
1. Solving A Stochastic Network Capacity Expansion Problem
David Morton (The University of Texas at Austin) and Kevin Wood
(Naval Postgraduate School)
We describe a method for solving a capacity expansion problem
in a stochastic multicommodity network from the
telecommunications industry (Sen et al. 1993). This system
has uncertain point-to- point demand pairs that are modeled as
discrete random variables; link capacities may be expanded,
subject to limited resources. The object is to minimize the
expected value of unmet demand. The solution methodology
adaptively derives a sequence of approximation models that use
Jensen's inequality to compute both upper and lower bounds on
the optimal objective of the original formulation.
2. Solving Integer Multicommodity Network Flow Problems
Pamela H. Vance (Auburn University) and Cynthia Barnhart
(Massachusetts Institute of Technology)
We present an algorithm for solving multicommodity network
flow problems where each commodity must flow on a single path.
The approach uses column generation to solve the LP relaxation
of a path-based formulation of the problem. A customized
branch-and-bound scheme is used to obtain provably optimal
integer solutions. Computational results are discussed.
3. Solving Multicommodity Flow Problems
Richard D. McBride (University of Southern California) and John
Mamer (University of California, Los Angeles)
This paper presents an over view of some advances made to
EMNET. The modifications have enhanced the size of the
problems that can be effectively solved; multicommodity flow
problems with numbers of constraints ranging from 85,000 to
565,000 are being solved routinely using EMNET by major food
companies. Computational experience will be given where
PDS10, PDS20, ..., PDS80 are solved to optimality.
Return to Program Overview
Chair: Evangelos Triantaphyllou (Louisiana State University)
1. Houria II: Solver For Hierarchical System: Planning of
Lexicographic Weight Sum Better Graph For Functional Constraints
Mouhssine Bouzoubaa, Bertrand Neveu (SECOIA, INRIA-CERMICS), and
Geir Hasle (SINTEF Informatics)
Constraints allow programmers and users to state declaratively
a relation that should be maintained, rather than requiring
them to write procedures to maintain the relation themselves.
They are thus useful in many applications such as user
interface and simulation packages. In many situations, it is
desirable to be able to state both hard and soft constraints.
The hard constraints must hold, and the soft constraints are
satisfied as much as possible, depending on the criterion
uses. A constraint hierarchy consists of a set of constraints,
each labeled as either hard or soft at some strength, and each
soft constraint is weighted by a real weight. The existing
solvers for satisfying constraint hierarchy imposes is that
every class of soft constraints labeled by a strength contains
constraints with the same weight. This paper surmounts this
restriction by presenting an incremental solver that proposes
a new implementation of constraints hierarchy. This solver
handles different class of soft constraints labeled with a
strengths where each class may contain weighted constraints.
The criterion of comparison used in this solver is global. It
allows the comparison of some valuations, which are not
comparable by local criteria used in some existing solvers.
This criterion is the generalization of the global criterion
used in other solvers.
2. Case-Based Retrieval and Indexing Using A Bayesian Network Model
LiWu Chang and Patrick Harrison (Naval Research Laboratory)
Bayesian case-based reasoning has at its core a Bayesian
network model for memory retrieval, indexing and organization.
In retrieval, a query network is constructed with the query as
the root and features as the leaf nodes. We select the case
that maximizes posterior probability of the query. In the
presence of non-informative features, dependent features or
noisy cases, we use adaptive methods such as feature
selection, feature dependency analysis and representative
cases selection to refine the Bayesian network model. Both
feature selection and feature dependency analysis use a
cross-validation scheme for evaluating different feature
combinations and the back and forth hill-climbing search
strategy. As a result, predictive accuracy of retrieval can be
greatly improved via adaptation. As for indexing, conceptual
clustering methods can be used to generate new indices for new
and stored cases. We propose an iterative refinement
clustering procedure. This procedure helps to avoid stopping
at local minimal of performance functions too early. After
labels of some new instances are assigned, clustering
iteratively adjusts contents of clusters by recalculating
class probability for instances of some clusters. As a result,
misplaced instances are minimized. The number of desired
indices is the maximum of probabilities of a number given all
stored instances. Since the condition of the clusters is not
known, it is viewed as a hidden variable. Thus, the final case
organization is represented by a Bayesian network with hidden
variables. Our implemented system has been used as a testbed
for studying CBR functions.
3. Some Recent Developments in Logical Analysis
Evangelos Triantaphyllou, Boris Kovalerchuk, and Aniruddha
Deshpande (Louisiana State University)
One of the main areas of great potential in the interface of
operations research and computer science is in inductive
inference. Inductive inference refers to the extraction of a
pattern from observations which belong to different classes.
This is the essence of building many intelligent systems with
learning capabilities. In this paper we discuss a logical
analysis approach to this problem. Given are sets of binary
vectors. The main problem is how to extract a Boolean function
in CNF or DNF form with as few clauses (conjunctions or
disjunctions) as possible. Therefore, this is an optimization
problem. We present a number of theoretical results and also
some possible extensions.
Return to Program Overview
Chair: Hossam Zaki (Sabre Decision Technologies)
1. Scheduling Partitionable Massively Parallel Mesh Connected
Computer Systems
Udatta S. Palekar, Yi Zhang, and Mary Johnson (University of
Illinois at Urbana-Champaign)
We address the problem of makespan minimization while
scheduling jobs on a mesh-connected parallel computers. We
assume that the speed-up function is super-linear and concave
in the number of processors assigned to a job. The problem is
shown to be NP-hard. Lower and upper bounds are established
for the makespan based on a continuous approximation of the
mesh. A rounding heuristic is developed and is shown to have a
worst-case performance ratio of 2. Variants of the heuristic
have been developed and computational experience with these
heuristics will be presented.
2. Multi-Mode Fleet Planning For Air-Cargo Distribution
Ram Pandit (Consolidated Freightways, Inc.)
This paper describes an optimization based approach taken for
a long , range planning study for a major air-cargo
transportation company operating in North America. The study
addresses two strategic problems: the service network design
and the selection of service modes - planes and/or trucks. We
present a mixed integer optimization model that enables the
fleet planner to conduct what-if analyses for the daily
operations of the company and to determine the most
cost-effective selection of routes and service modes.
3. Solving Large-Scale Crew Scheduling Problems
Hai D. Chu (Sabre Decision Technologies), Eric Gelman (Pyramid
Technologies), Ellis Johnson (Georgia Institute of Technology)
The crew pairing problem is posed as a set partitioning
zero-one integer program. Variables are generated as legal
pairings meeting all work rules. Dual values obtained from
solving successive large linear program relaxations are used
to prune the search tree.
In this paper we present a graph based branching
heuristic applied to a restricted set partitioning problem
representing a collection of "best" pairings. The algorithm
exploits the natural integer properties of the crew pairing
problem. Computational results are presented to show realized
crew cost savings.
4. Hybrid Methods for the Assignment Problem,
Hossam Zaki (Sabre Decision Technologies) and David Kempka (Delta
Airlines)
In this paper we develop a hybrid method for the linear
assignment problem, present its theoretical justification, and
demonstrate its computational characteristics.
Return to Program Overview
Chair: William R. Stewart, Jr. (College of William and Mary)
1. Artificial Reef Development Model Phase 1: The Geographic
Information System
Edward K. Baker and Maria L. Villanueva (University of Miami)
Dade county has been increasingly recognized as one of the
artificial reef leaders ion the nation. In the past twenty years
the Dade County Artificial Reef Program has deployed 99 reef
components on 21 sites, both offshore and inshore, with an
expenditure of $2 to $2.5 million. A Florida Sea Grant household
survey of registered boat owners estimates 13.5% of resident
divers surveyed use artificial reefs sites in Dade County.
A 1990 survey of boat use patterns in Dade County estimated that
nine percent of recreational boat ramp users listed diving in
reefs as their primary boating related activity during the summer
season.
Artificial reef programs have traditionally been conceived as a
tool for fishery management. However, recreational diving on
artificial reefs has emerged as a primary by-product of the
programs over the past decade. There has been a substantial
increase in the number of dive shops and especially dive charter
boats since 1980.
This first phase of the artificial reef evaluation model utilizes
a computer-based geographic information system. Within this
system, each of the existing artificial reefs in the country is
located, identified, and described with an attribute table.
Additionally, the marinas, boat ramps, and recreational charter
piers in the country are identified and described as a source of
boater activity. Using boat trip survey data and demand models
of participation, each of the reef locations is evaluated in
terms of cost per participation. The geographic information
system is then used to identify favorable zones of deployment.
2. Coupling a Greedy Route Construction Heuristic with a Genetic
Algorithm for the Vehicle Routing Problem with Time Windows
Jean-Yves Potvin and Franc~ois Guertin (Universite' de Montreal)
Vehicle routing algorithms can be divided into three broad
classes: route construction heuristics that "build" routes
through the insertion of new customers, route improvement
heuristics that modify the location of customers within the
existing routes through exchange procedures, and composite
heuristics that intermix route construction and route
improvement procedures. In this paper, a greedy route
construction heuristic for the vehicle routing problem with
time windows is described. This heurist
ic inserts customers one by one into the routes using a fixed
a priori ordering of the customers. Then, a genetic algorithm
is proposed to identify the ordering that produces the best
routes.
3. Voronoi Diagrams and Euclidean Traveling Salesman Problems
William R. Stewart, Jr. (College of William and Mary)
This presentation encompasses three aspects of ongoing
research into the relationship between Voronoi diagrams,
Delaunay triangulations, and Euclidean traveling salesman
problems (ETSP's). The initial part of the presentation
reports on empirical tests to assess the quality of the edges
in the Delaunay triangulation as candidate edges for solving
ETSP's. In particular, 99% of the edges in the optimal
solution to an ETSP are usually found in the set of edges that
define the Delaunay triangulation, and the optimal tour on the
Delaunay triangulation is typically within .2% of the length
of the optimal tour on the complete graph.
The second part of the presentation applies the insights
gained in the empirical phase to design a heuristic approach
for solving ETSP's based on the edges in the Delaunay
triangulation and a directed assignment problem. The
heuristic recursively shrinks large instances of the ETSP into
smaller problems until the directed assignment solution
contains no subtours. The resulting tour on the reduced
problem is then recursively exploded until a feasible tour of
he original problem is obtained. This approach produces good
solutions to problems with over 10,000 vertices in practicable
amounts of computer time.
Finally the another heuristic is presented that exploits the
underlying data structure in the Delaunay triangulation and
produces feasible solutions very quickly. The construction
and local search heuristics based on the edges in the
Delaunay triangulation both run in time O(nlogn). Due to the
speed of the local search heuristic this approach lends itself
to metaheuristic techniques like tabu search or simulated
annealing.
Return to Program Overview