Title: The Multisalesman
Abstract: This paper is a discussion of the commonly encountered problem of finding an optimal route using multiple vehicles through a system of customers. The primary focus is on the task of efficiently clustering customers for a fleet of trucks. Two algorithms are discussed in depth, and results corresponding to implemented functions will be analyzed.
Both algorithms cluster the customers into truck loads that have capacity limits. The two techniques are very different but both elegantly cluster the points to be advantageous in different applications. The first method, called the cluster method, groups points based on a nearest neighbor process. The second method, the sweep, groups points based on radially sweeping the Cartesian plane.
The paper has been written for any person with minimal math experience to get a grasp of the concepts of each method, but is detailed enough to hold the interest of those with a strong math background. A basic knowledge of a Cartesian coordinate system is required as well as knowledge about calculating Euclidian distances. Basic matrix and vector operation "know how" is not a must, but will be very helpful in understanding the two methods discussed. Those with strong math background should read the improvements section throughly and ponder implementing these improvements. The Matlab functions for each method have been included in the appendices for this purpose.
Title: Bike Trail Distance / Calorie Algorithm
Abstract: This project uses a slightly modified depth first search algorithm to find bike trails of specific lengths from a local state park mountain biking trail. The user inputs the desired distance to ride, or calories to burn, along with the difficulty range of the trails, and the algorithm calculates all of the paths that meet, or are less than, the given criteria. The program then prints out these paths in order of difficulty then length. The data used for the mountain biking trail is taken from Saint Edward State in Western Washington, although any other map could be used instead. The program consists of two parts. The first part is an executable that must be run to get the user's input and that prints the paths to the screen. The second part is a bitmap that is used to view the layout of the trail, and shows the waypoints of the paths printed out from the executable.
Title: Modeling the UW Modem Pool
Abstract: Students at the University of Washington who wish to connect to the Internet through the University's free service would like to be able to connect at any time with little of no hassle. This means getting connected without receiving a busy signal. In this paper we provide a simple Markov chain as well as more complicated Monte Carlo simulations to model the University of Washington's modem pool. We found that a modest increase to 1200 modems would support most student's needs. This leaves a daily average of 68.14 people who receive a busy signal, a 49% improvement over the arrangement of 1176 modems now available.
Title: Platinum Deposition
Abstract: When Platinum atoms in a free-floating environment interact with a silicon plate, they occasionally hit and stick to the plate. Once stuck to the plate, they will usually move around on the plate until connecting with other atoms and staying stationary. Our model simulates this interaction by Monte Carlo processes at various temperatures and examines the final patterns found on the plate. We are trying to determine the optimal temperature so that a smooth, regular, hexagonal pattern develops in a reasonable time.
Title: Considering StatPR
Abstract: We explored statistical character recognition for our discrete math modeling project. In statistical character recognition, a feature vector is used to classify characters. A feature vector represents in numerical form the important characteristics of an input. From the feature vector, classification is done. A longer feature vector, containing more information, allows better recognition but makes computing slower at the same time. We wrote a program to recognize 10 Japanese handwritten characters. Then we tested the program to see how good the recognition is. A vector of length sixty-four was found to yield a 97\% recognition rate. The samples were handwritten characters obtained from several different people. The program uses basic statistical analysis to find the mean and standard deviation of each character's vectors.
Title: Network Traffic
Abstract: Doctors and nurses at the University of Washington Medical Center use ultrasound images to diagnose and care for patients. The images are transferred from the ultrasound machines to viewing stations via the data network. The devices transferring these images must compete for bandwidth with other network applications such as email, web browsing, and access to remote systems. Excessive utilization of the network has made the transfer of images unreliable. We have created a model of network traffic based on observations of utilization and error rates during image transfers. By simulating network traffic at varying rates of utilization, a range of acceptable levels of utilization can be determined.
Title: Course Scheduling Model for ACMS Program, Discrete
Mathematics and Algorithms Path
Abstract: A major challenge to professors and school administrators is to design a schedule that can meet the needs of the various departments along with accomodating the different needs of a diverse student body. Our paper investigates the Discrete Mathematics and Algorithms pathway within the Applied and Computational Mathematical sciences (ACMS) department at the University of Washington.
Our focus is to offer a time schdule of classes for each quarter that meets student demand, minimizes unwanted time conflicts between related classes, and takes into account sequences of courses, which must be taken in different quarters. Since this problem involves many constraints, we use linear programming to find the optimal solution in building a course schedule.
Title: Airplane Modeling Project
Abstract: The owners of WestCoast Airlines want to determine a suitable flight schedule that uses as few planes as possible. They want to minimize the cost of their operation so a schedule that uses the least number of planes is optimal. We attempted two different scenarios. First we started our modeling problem with five cities. We used an integer-programming problem to come up with decision variables and constraints. Next, we decided to decrease the number of cities to three for a more manageable problem. We used integer programming for this one also and used a branch and bound algorithm to solve it.
Title: Flow and Reliability Maximization in Arbitrary Connected
Networks
Abstract: The paper models an arbitrarily connected, directed computer network using graph theoretical techniques in software, where the user is allowed to specify the number of nodes, the probability of any two nodes being connected, the "source" node, and certain application-specific characteristics of the graph (edge weight scaling factors, for instance) before the graph is generated. Using several well-known algorithms, the software allows the user to view graph characteristics and tells the user how to add edges to optimize a particular feature of the graph (e.g. reliability, end-to-end capacity, etc). For this project we modeled arbitrary 10-node graphs (although the software is extensible to any number of nodes), showing where edges should be added to maximize flow and reliability. The software implements Prim's minimal spanning tree algorithm, Dijkstra's single-source shortest path procedure, and the Ford-Fulkerson (Edmonds-Karp variant) method for finding the maximal flow through a network. This models, for instance, a small business with ten terminals or computers joined together in a network. The owner wants network statistics, and information on how the computers could be set up to maximize reliability or dataflow. The computers do not need to be in any special arrangement so it does not matter which are connected. The maximum flow out of each computer per hour is 30000 packets. We generate random 10-node networks and show the results of our model upon them.
Title: A Simulation of Wave-Regenerated Balsam Fir Forests
Abstract: Wave-regeneration represents a rare form of disturbance that occurs mostly in subalpine fir forests. Within these forests, tree deaths are spatially organized into long lines, or waves, that slowly move through the forest over time. Wind appears to be the predominant organizer of the waves. Despite extensive research, the causes of these waves are still not known for certain.
Using the available knowledge, we have developed a simulation model of wave-regenerated balsam fir forests that takes into account many of the suspected causes of wave formation. Our model is based on a grid that represents the forest and a set of equations used to describe tree growth.
We have compared the results of our model to the available data for wave forests. The model produces wave patterns that closely match those found in the real forests, and produces reasonably good results for tree growth. However, there are still several discrepancies between the simulation results and the available data.
Title: Smart Automobiles: Finding the Optimal Route on a City Map
Abstract: Travelling by car requires finding a path from the starting point to a destination. "Intelligent" cars could contain a system which renders information about the shortest or fastest paths from one point to another in a city. We chose to model a city in two ways. First we model the city as a maze in which we find the shortest path from one point to another using depth-first and breath-first algorithms. Next we model the city as a graph and we determine the shortest route given weighted edges between nodes, which are subject to change according to current traffic conditions. We then determine how large the car's model of the city can be in order to make a path decision in a reasonable amount of time.
Title: Back Solving Blackjack
Abstract: Casino gambling is the icon of Las Vegas and Atlantic City. The lure of a 'quick' profit is enough motivation for millions of Americans to visit a casino. What can a gambler do to at least level the playing field and possibly leave with more money than they started with? Of all the casino games, only blackjack eluded mathematical analysis until the advent of cheap, fast computing. Modern computing, although allowing stochastic modeling, still does not enable the enumeration of all hands in blackjack. The purpose of our project was to develop a simplified version of blackjack in which enumeration of all hands is possible, and compare the results to a Monte Carlo simulation of this revised game. A Monte Carlo simulation of the full blackjack game was then run to create an optimal playing strategy. Statistical analysis of the results for both of the simulations was done, in addition to an examination of the expected returns for every card combination, given our optimal strategy.
Title: Least-Cost Daily Diet for a Student
Abstract: As students on a tight budget, we would like to determine the minimum amount of money we need to spend on daily food, while meeting certain nutritional requirements for our health. From the nutrition table we obtained from McDonald's, we see that we have certain constraints on calories, protein, fat, sodium, vitamin A, vitamin C, vitamin B1, vitamin B2, niacin, calcium and iron. In our paper, we present the problem as a linear program to minimize cost, eating only at McDonald's, and we solve the linear program with the aid of the software package LINDO. After we obtain the optimal solution, we change different parameters, such as the prices of different foods or the nutritional requirements, to see how our model reacts to the changes.
Title: A Study of Baseball Game Probabilities
Abstract: We study the effectiveness of a probability formula that calculates the probability of one baseball team defeating another. This formula is based solely upon a single characteristic: the average number of points a baseball team tends to score each game. To do this, a variety of Monte-Carlo simulations were used in which probabilities were given, statistics were generated, new probabilities were calculated, and the results analyzed. It was found that this approach is effective to some extent, and it is possible to look only at the average number of points a team tends to score each game in order to determine the probability of one baseball team defeating another.
Title: Menu Optimization for a Backpacking Trip
Abstract: Being backpackers, we have decided to take on the task of planning out menu items for a backpacking trip. We have selected the foods that we would like to enjoy on this trip. Since we are avid backpackers, we make these trips quite often. Also being obsessive mathematicians, we would like to come up with a menu that optimizes such factors as weight and cost, subject to a given set of constraints, such as nutritional requirements, variety, weight, and cost. After finding a way to quantify these factors, the problem fits very nicely into a linear programming model. Using LINDO, we started with a very small set of constraints and gradually entered new constraints into the model, and observed how the solution evolved as a result of the additions to the model.
Title: A Mathematical Modeling Approach to Simulating and
Optimizing the Execution Time of Computing Jobs Distributed Across a
Computer Network
Abstract: Distributed software design is a difficult problem which is aided by design analysis and optimization tools. This paper introduces the problem of distributed software design, describes an abstract model for representing a distributed software system, and analyzes the complexity of the model. Building upon the model, this paper explores techniques for simulating and optimizing distributed software design. Both branch-and-bound and simulated-annealing are investigated as optimization techniques for distributing computing jobs across a computer network. An implementation in Java and its results are discussed.
Title: Time Schedule
Abstract: In our project we consider the situation of a person entering college. There are two cases we will be considering: the case where the student is undecided about what major to pursue, and the other being the case in which the student is fairly sure what the person wants to major in. With this in mind we also pose another restriction, the student must complete their major within 16 quarters. These quarters are based on the University of Washington's quarter system with summer quarter taken as part of the 16. So with this in mind, we know that some classes are not offered during the summer. We will be applying two methodologies: Bound and Branch method and solving graphically. We illustrate the Branch and Bound method by directly applying it toward our simplified version of a college. Then we apply it to the University of Washington. Since we impose a time constraint on the student we will be looking at what major can be completed within the time frame given. In the event that the student isn't able to get into the major of choice, a backup major in then pursued.
Title: Optimizing Investment Return through Asset Class Selection,
Risk Evaluation, and Management Style
Abstract: One important factor inmaking investment decisions is allocation among asset classes. The amounts an investor chooses to invest in each class will impact the expected return and risk of the portfolio as a whole. To predict how a protfolio will grow over time, broad-market class index returns will be used in a Monte Carlo simulation to predict various profolios' growth for different time horizons. Using MATLAB, simulations were run for both actively and passively managed portfolios. It is shown that a shorter time horizon necessitates a more conservative portfolio. It is also shown that, to mitigate risk, passively managed portfolios require a more conservative portfolio composition than actively managed portfolios.