Thesis Abstracts in Operations Research


Parallel Heuristic Solvability of the Quadratic Assignment and Related  Problems
by Jai Chakrapani,      Advisor: Jadranka Skorin-Kapov (Management)
December, 1993

The heuristic solvability of the quadratic assignment and related problems is
addressed. An instance of a quadratic assignment problem (QAP) of size n is
specified by two n x n matrices D and F and is denoted by QAP(D, F).
   First, the QAP is introduced along with tabu search, the heuristic studied
predominantly in this dissertation. An introduction to the connection machine
CM-2 is also presented. CM-2 is the parallel environment in which the  parallel
tabu search algorithms are implemented. An adaptation of the  Boltzmann machine,
a connectionist model, is developed to solve the QAP. This  serves as a testbed
to compare the performance of simulated annealing and  tabu search. This also
provides a motivation for a massively parallel tabu  search heuristic Par_tabu
which is implemented on the CM-2. The heuristic  uses several advanced features
of tabu search and matches or improves the  results obtained from other
comparative studies in fewer number of  iterations. Par_tabu is then adapted to
solve the TSP, which can be  considered as a special case of the QAP. An
efficient and highly scalable  implementation of the 2-opt move on the CM-2
forms the basis of the tabu  search heuristic for TSP.
   Next, a parallel tabu search based heuristic is developed and implemented
(on the CM-2) for the problem of mapping tasks to processors in a massively
parallel system to minimize communication time. This problem is also  formulated
as a quadratic assignment problem (QAP), and problems of size up  to 64,000 are
solved. The algorithm compares favorably with other heuristics  for the same
problem.
    Finally, a new constructive approach to obtaining lower bounds for a
special class of QAPs is developed. Two matrices Fopt and Fres are  constructed
such that F D Fopt + Fres, and the optimal solution to QAP(D,  Fopt) is known.
Any existing lower bound can then be applied to QAP(D, Fres),  which in sum with
the optimal value for QAP(D, Fopt) provides a valid lower  bound to QAP(D, F).
Thus, this method could serve as a reduction process to  possibly improve the
results from a variety of bounding techniques.


Optimal Policies in Manufacturing and Queuing Systems
by Charu Srivastava Sinha,       Advisor: Matthew Sobel (Management)
     December, 1993

This dissertation studies the optimization of stochastic models of multistage
manufacturing processes and of urban emergency services. For each model, an
optimal operating policy is obtained which is notable both in its ease of
computation as well as implementation. The model of multistage manufacturing
processes has an end item demand which is stochastic. The costs of
work-in-process inventories are linear and costs of finished goods inventories
are convex. The decision problem involves determining the work-order-release
policy at each manufacturing stage for various cost minimization criteria.
Dynamic programming is used to pose the problem. However, an optimal policy is
obtained by exploiting the structure of the cost functions involved, rather
than using the techniques of dynamic programming as done hitherto. Moreover the
optimal policy obtained has a simple characterization which leads to an easy
computational procedure, greatly simplifying the computational procedures in
the literature that began with Clark and Scarf.
  The model of emergency services is a multi-server queuing system with
heterogeneous exponential servers and several classes of Poisson arrivals. The
decision problem is to assign arriving customers to idle servers. A full-
service policy assigns each arriving customer to the fastest idle server; this
policy is easy to implement. Sufficient conditions are obtained for the
full-service policy to optimize various cost criteria.


Combinatorial Algorithms for Computational Biology
by Gopal Sundaram,      Advisor: Steven Skiena (Computer Science)       
 May, 1994

The DNA sequence of a living organism is a string of millions of characters
over the alphabet {A, C, G, T}. DNA sequencing, i.e., determining the DNA
sequence is a fundamental effort underlying almost every problem being in
Molecular Biology. Biologists determine short sequences of hundreds of
characters from different parts of the original DNA sequence and put them
together using computer algorithms. There are numerous algorithmic and
computational issues involved in this process.
  In this dissertation, we address some of the algorithmic and computational
issues involved in Computational Biology problems. In particular, we give new
algorithms for three different problems, viz., Restriction Site Mapping,
Reconstructing DNA strings from Sequencing By Hybridization(SBH) data, and
Subgraph detection algorithms. When a DNA molecule is exposed to a restriction
enzyme, the enzyme cleaves the molecule wherever a particular pattern occurs,
which are called restriction sites. By a partial digest experiment, we can
obtain the set of inter-site distances, which usually contain a certain
relative error. From the inter-site distances, we want to determine a
consistent set of positions for the sites. We propose new, practical algorithms
which resolves the noisy experimental data, including the possibility of
missing fragments. We analyze the performance of these algorithms under a
reasonable probability distribution, establishing a relative error limit of r D
Q(1/n2) beyond which our technique becomes infeasible. Through simulations, we
establish that our technique is robust enough to reconstruct data with relative
errors of up to 7.0% in the measured fragment lengths for typical problems,
which appears sufficient for certain biological applications.
 Sequencing By Hybridization is a new approach to DNA sequencing in which we
sequence the DNA by asking all substring queries of length m, using a
sequencing chip C(m). We develop a theory of interactive sequencing by
hybridization, based on reconstructing strings from substrings. We provide
tight bounds on the complexity of reconstructing unknown strings from substring
queries. Specifically, we show that Q(na) substring queries are necessary and
sufficient, where a is the alphabet size. We also demonstrate that subsequence
queries are more efficient by showing O(n lg a) queries are necessary and
sufficient. When the unknown DNA string is one of a small set of possibilities,
we give algorithms to build decision trees which are within a constant factor
of an optimal decision tree(it is NP-hard to find an optimal decision tree),
with the constant depending upon a. We also give algorithms to verify existing
DNA sequences using the classical sequencing chip C(m). We also consider the
problem of building efficient sequencing chips and the associated reconstruction
algorithms.
  Finally, we consider the problem of Subgraph Isomorphism which has
applications in Fragment Assembly and other DNA sequencing algorithms. Although
the general problem of subgraph isomorphism is NP-complete, polynomial-time
algorithms exist for recognizing any fixed subgraph. However, certain subgraphs
appear easier to recognize than others. In this paper, we present general
algorithms for fixed-subgraph isomorphism which improve or unify previous
results. In particular, we present an O(nfm) algorithm for recognizing a fixed
subgraph H with flower number f within a graph G with n vertices and m edges.
Special cases of this algorithm match the best algorithms known for recognizing
small paths, cycles, and cliques. Further, we improve previous results for
recognizing C~ and small even cycles C2k, k > 3.



Optimization of Stochastic Models for Planning Reservoir Releases
by Susan Lynn Monroe,   Advisor: Matthew Sobel (Management)      August, 1994

This dissertation analyzes a discrete-time model of a reservoir system whose
discharges generate hydroelectric power to satisfy a single known demand. The
characteristics of a planning model include a monthly or seasonal time step and
a planning horizon of at least one year. Because of the large time step the
uncertainty of the inflows in each period cannot be ignored. Stochastic
optimization methods are used in this dissertation to handle the uncertainty of
the inflow. The problem is to decide how much water should be released in each
time period in order to maximize the expected benefits over the entire planning
horizon. Planning models are used by utilities to project monthly, seasonal,
and yearly earnings. This information is then used in relicensing of
powerhouses, setting price structures, and planning alternative energy sources.
  Chapter 2 considers the most fundamental of all reservoir systems; a single
reservoir serving a single hydroelectric plant. For this problem an optimal
policy can be stated explicitly. Chapter 3 investigates a system with any
number of reservoirs in a parallel network configuration. A network has a
parallel configuration if the release from any reservoir in the system does not
flow into any other reservoir in the system. For this model an optimal policy
is stated, and an upper bound on the value function is given that is calculated
by solving an appropriate single reservoir problem. In addition a heuristic is
presented that greatly reduces the amount of work needed to solve these large
problems. Chapter 4 presents extensions of the model that include seasonal
demands, seasonal inflows and autocorrelated inflows.


Some Topics on the Design and Cost Allocation in Telecommunications Networks
by Hector Fernando Beltran,      Advisor: Darko Skorin (Management)   May,
1995

This dissertation addresses two different aspects of the development of
telecommunications networks. Specifically we study the design of low-cost
networks immune to isolated failures and the cost allocation problems
associated with some classes of capacitated network design problems.
 In the first part, the design problem of an isolated failure immune (IFI)
network is considered. A telecommunications network is isolated failure immune
if and only if communication between operative sites can be completed as long
as network failures are isolated. It is known that the class of minimal IFI
networks is equivalent to the class of spanning 2-trees. The objective is to
construct a minimum cost IFI network. The problem is known to be NP-complete.
We develop a tabu search based heuristic for solving the minimum cost spanning
2-tree (MCS2T) problem. We develop four heuristic algorithms to obtain
diversified 'good' starting solutions. They are: completion of a 2-tree from a
spanning tree, two greedy approaches, and a method based on the recursive
definition of a 2-tree. We also formulate an integer programming problem (IP)
whose objective function value is a lower bound to the MCS2T problem. We solve
the IP by developing a constraint generation scheme. The algorithms were tested
on complete random graphs with euclidean distances and on two real data sets
(Civil Aeronautics Board).
  In the second part, we analyze some game theoretic solution concepts
associated with a cost allocation problem arising from the Capacitated Network
Design (CND) problem. The CND problem generalizes several problems that often
appear in the design of telecommunication networks. Among them are: the
Capacitated Minimum Spanning Tree problem, the Capacitated Concentrator
Location Pro
blem, and the Capacitated Steiner Tree Problem. The associated cost
allocation problem is formulated as a cost cooperative game in characteristic
function form to be referred to as the CND game. We provide a unifying
efficient representation of several game theoretic solutions concepts
associated with the CND game. In particular we efficiently characterize the
core, and in some cases the nucleolus, the least weighted e- core and a certain
'central' point in the least weighted ~-core. Our model properly generalizes
several previously studied cooperative games. We also employ our unifying model
to analyze the cost allocation problems associated with several classes of
network design problems which were not previously studied in the literature.
Specifically, we efficiently characterize the above cost allocation solutions
for cost allocation problems associated with the Capacitated Concentrator
Location problem, the Capacitated Minimum
Spanning Tree Problem and the Capacitated Steiner Tree problem.


Bicriterion Optimization of Produce-to-Order Manufacturing Systems: A Queuing
Approach
by Dong-Jin Kim,       Advisor: Eugene Feinberg (Management)           August,
1995

A single facility production system with stochastic demand and general
processing, start-up. and shut-down times is analyzed. The facility may be
switched on and off. After the production facility has been shut-down. it may
stay idle or may be switched to a secondary mode of operation and carry out
some other works for a random length of time. During this period, the facility
does not produce items. The demand is generated by a Poisson or a compound
Poisson process. There is no inventory and the arriving orders are backordered
until they are completed. The cost structure is production costs. Production
costs consist of system running costs and set-up and shut-down costs.
  We consider a bicriterion problem when one criterion is the average time to
complete an order and another criterion is the average production cost per unit
time. The main objective is to find a control policy which balances the
trade-offs between these two criteria. The structure of Pareto optimal policies
is described. This structure is exploited to find the optimal policy for a
constrained problem to optimize one of the criteria under the constraint for
the other. We model the above production system as a proper queuing system and
use queuing theory to analyze it.


The Fleet Coordination Problem
by Herbert Francis Lewis,         Advisor: Thomas Sexton Management)
August, 1996

This dissertation considers the fleet coordination problem (FCP). We assume a
set of n demand sites along with a specified depot. For each demand site we are
given the number of dump trucks required to service it as well as its location.
The location of the depot is assumed known. A positive integer c, indicating
the number of cranes available, is also given. For the bulk of the dissertation
it is assumed that n is a multiple of c. We seek to find a set of p packages,
where p D n/c, each containing c demand sites. We then seek to find a set of c
tours. The generation of each tour starts at the depot and continues by
sequencing the packages and assigning each demand site within a package to a
different tour. Each package represents the demand sites serviced
simultaneously, one by each crane. Our objective can be expressed in two parts.
The first part is to minimize the maximum package demand, which is defined to
be the sum of the dump truck requirements at the demand sites within a package.
Given the solution to the first part, we minimize the total travel distance of
the cranes, which is defined as the sum of the lengths of the crane tours.
  This dissertation begins with a discussion of the various settings in which
the fleet coordination problem arises. We survey routing problems in chapter 2.
In chapter 3 we formally define the FCP and give a mathematical programming
formulation. Methods for packaging the demand sites is the topic of chapter 4.
In chapter 5 we deal with crane routing when the optimal packaging is unique.
In chapter 6 we handle crane routing when all feasible sets of packages are
optimal. Crane routing in general is discussed in chapter 7. In chapter 8 we
consider two special cases of the FCP in which the number of cranes is 2 and
the number of packages is 2, respectively. Computational results of the various
approximation algorithms and heuristics developed throughout this dissertation
are presented in chapter 9. In chapter 10 we consider various extensions to the
FCP as well as topics for future research.



Estimation of the Volatility of Stocks Using the High, Low and Closing  Prices.
by Josselyne Kone,       Advisor: Michael Taksar        Decmeber, 1996

In the Black-Scholes theory of option pricing, it is necessary to estimate the
volatility of the underlying stock. We derive a method of estimation of the
volatility which is based on the functionals of the range of a Brownian motion
which models the stock price fluctuation. We also investigate two versions of
this method. The first deals with at the expectation of the difference between
the running maximum and the current value of a Brownian motion or the
expectation of the difference between the current value and the running minimum
of a Brownian motion. The second analyses the expectation of the range of the
Brownian motion.


Capital Accumulation with Population Dynamics
by Joan Marie Harnett,  Advisor: Matthew Sobel (Management)      August, 1997

Many collections of assets are managed on behalf of specific population groups.
This study concerns the tradeoff between re-investment and spending when the
composition of the population is taken into account. The specific motivation is
management of the assets of congregations of religious women in the United
States. Rates of return on investments and the numbers of members are random
variables. This dissertation explores a variety of models which are analyzed as
dynamic programs and evaluates the appropriateness of each. A bicriterion
stopping problem is the model in which the effects of the generally decreasing
size of the congregation on the level of re-investment is analyzed most
closely.


Stable Cost Allocations on Minimum Spanning Tree Networks
by Kathryn Joy Kent      Advisor:  Esther Arkin         August, 1997

In areas which employ networks, such as telecommunications, cable television
and computers, it is often necessary to allocate the cost of the network to
users. It is normally economical to encourage as many participants as possible
to join a network, and this work addresses numerous concepts that encourage
participation by the maximum number of users.
  This work considers allocation of the cost of the solution to the Minimum
Cost Spanning Tree (MST) problem. The cost allocation issue is defined as a
cooperative game called the MST game. Given an MST game, an algorithm is
developed that allocates the cost of the MST and produces core allocations;
i.e. no coalition pays more than they would if they worked on their own.
  Further refinements are made to the algorithm so that the allocations can be
shown to be stable in a number of ways. They are proven to be both Population
Monotonic and Distance Monotonic. A Population Monotonic allocation scheme is
such that when a new user is added to the network, and the cost of the new MST
is allocated, the cost to none of the old users increases. Distance
Monotonicity is defined such that if the cost of some edge connecting nodes in
the network goes down, and the new allocation is determined, none of the
players has an increase in their cost. It is then shown that the solution set of
this algorithm is equivalent to the game's Irreducible Core. The Irreducible
Core, introduced by Bird (1976), is shown to be an important object of study
because the above mentioned stability properties do not hold for core
allocation schemes outside of the Irreducible Core. Lack of these stability
provides a disincentive for players to join the network. An example is given to
show that the core of a general MST game is not
necessarily large, though some subcases are shown to have large cores. Finally,
some extensions of the original MST problem are described, including multiple
hub networks and networks in which pre-existing, possibly non- optimal, edges
are included, and it is proposed that some of their cost be paid for by new
users.


Efficient Collision Detection for Interactive 3D Graphics and Virtual
Enviornments

by Jim Klosowski,        Advisor: Joseph Mitchell       May, 1998

Collision detection is of paramount importance for many applications in
computer graphics and visualization. Typically, the input to a collision
detection algorithm is a large number of geometric objects comprising an
environment, together with a set of objects moving within the environment.  In
addition to determining accurately the contacts that occur between pairs of
objects, one needs also to do so at real-time rates. Applications such as
haptic force-feedback can require over collision queries per second.
  We initially analyze several methods of performing collision detection which
utilize standard box-based data structures. These methods are compared against
a more sophisticated technique, based upon recent computational geometry
results on ray shooting using meshes of low stabbing number.
  Building upon these results, we develop and analyze a method, based on
bounding-volume hierarchies, for efficient collision detection for objects
moving within highly complex environments. our choice of bounding volume (BV)
is to use a "discrete orientation polytope" ("k-dop"), a convex polytope whose
facets are determined by halfspaces whose outward normals come from a small
fixed set of k orientations. We compare a variety of methods for constructing
hierarchies ("BV-trees") of bounding k-dops, including a novel technique in
which the BV-tree "oscillates" as it is contracted. Further, we propose
algorithms for maintaining an effective BV-tree of k-dops for moving objects as
they rotate, and for performing fast collision detection using BV- trees of the
moving objects and of the environment. By maintaining a "front" as the objects
move within the environment, we are able to exploit temporal coherence during
the collision detection checks and accelerate the tree traversal algorithm
considerably.
  Our algorithms have been implemented, tested, and are being publicly
released within our QuickCD library of collision detection routines. We
provide experimental evidence showing that our approach yields substantially
faster collision detection than previous methods.
  To further test the practicality and effectiveness of our method, we also
demonstrate its efficiency in performing NC verification, i.e., in testing tool
paths for gouging in 3-axis machining.




Succinct Strip Encoding of Triangle Meshes

by Xinyu Xiang		Adviser: Joseph Mitchell	Aug. 2001


A fundamental algorithmic problem in computer graphics is that of computing
a succinct encoding of a triangulation of a polygonal surface model in order
to be able to transmit and render it efficiently. The goal is to take a
given polygonal surface model, whose facets are given by (possibly
multiply-connected) polygons, triangulate its facets, and then decompose the
triangulation into a small number of "tristrips," each of which has its
connectivity stored implicitly in the ordering of the data points. We
develop methods that are effective in solving the stripification problem,
both in theory (provably good encodings) and in practice. Our methods are
based on carefully constructed search trees in the dual graph, followed by
algorithms to decompose dual trees into tristrips. One decomposition
algorithm is provably optimal (based on dynamic programming), allowing us a
sound basis of comparison among our other (heuristic) algorithms. We
demonstrate the speed and effectiveness of our algorithms through a battery
of experiments. In comparison with the recently released STRIPE system for
stripification, we find that our stripifier, FTSG, produces comparable or
better quality encodings, while requiring significantly less computing time
on a large variety of datasets. Further, FTSG is carefully engineered and
implemented to be robust, even in the face of highly degenerate and
corrupted real-world data. In addition to fast and effective practical
algorithms, we also develop optimization algorithms to extract a minimum
number of tristrips from a given mesh, using both integer programming and
branch-and-bound methods. We are able to find optimal solutions for models
containing several tens of triangles in a few minutes. We also incorporate
our optimization algorithms into FTSG to provide the user the option of
spending more CPU time to obtain fewer tristrips. Furthermore, we study the
effect of allowing a small on-board vertex cache on computing a succinct
encoding of a triangulation. Methods of maximizing cache utility are
developed in an attempt to minimize the encoding cost.