MATH 464 – Spring 2024 Project
The final project is intended to be a culminating work, not only for this course, but for your path through undergraduate mathematics. While not necessarily so extensive and involved as, for example, a senior project, it will contain elements which measure your effectiveness to communicate and practice mathematics. The setting is optimization. The final product is a written report.
The description given here is the default, of which you should fee free to use without penalty. However, some students prefer a project which is more closely tailored to their particular interests and current areas of study. Thus, deviations from this description, or completely different types of projects are encouraged. If you choose to take a different path, you must provide me with a short project description and obtain my approval in a timely manner.
Project Goals
As MATH 464 is a Capstone course in Mathematics, the final project is a tool for measuring success in the program. Some relevant quotations from WSU’s Integrative Capstone website are useful to keep in mind:
Students conceptualize, plan, and execute a substantive, culminating project (presentation, paper, creative product, poster, team-based project).
Students recognize and use key concepts, methods, vocabulary and techniques of chosen academic field to solve disciplinary problems.
Students apply concepts and methods from multiple disciplines to examine cross- disciplinary issues of concern.
The UCORE committee suggests that CAPS courses and assignments intention- ally offer students: Authentic, contextualized experiences or complex scenarios; Independence and agency, with feedback along the way; Opportunities to inte- grate and extend prior learning, and to use critical inquiry.
The goals expressed above are best learned dynamically. Comfort levels with mathematical writing, modeling, coding and problem solving will vary among students. You should feel free to discuss your progress and difficulties with me at any time, and I will do my best to provide timely and significant feedback. While this project is to be your own work, it is also a learning experience.
Project Details
You are to act as a consultant to a company or institution which has approached you with an optimization problem. Your task is to review the given problem and supplied data, provide an appropriate mathematical model, solve the particular problem using appropriate software, and compose a final report encapsulating your work. During this process, it may be necessary or beneficial to meet with a company representative (the course instructor) in order to clarify information or obtain additional data. You may choose to complete any one of the following projects.
1. Assessing Business Efficiencies using Data-Envelopment Analysis.
2. Multi-period Team Assignment Planning.
3. Predicting Drug Lifetimes in the Bloodstream.
4. Optimal Placement of Emergency Supply Access Points.
5. Robust Shortest Time Delivery Routes.
Project descriptions are provided at the end of this document.
Report Content
The project is complete through the submission of a final report (see next section for submis- sion details). The format and content is of your own design within the guidelines provided here.
(a) The report is to be an extended memorandum in response to the question which was posed to you, acting as a consultant/employee.
(b) Write for a mixed audience of readers. Your report should have relevant content for executives, mathematicians, operational planners, etc.
(c) Address and satisfy the project goals. This requirement should be realized implicitly, without listing goals and responding to them.
(d) Use appropriate language and correct (English) grammar.
(e) Use accurate mathematical language, both in words and symbols.
(f) Define quantities and justify methods. Do not assume that the reader is familiar with the optimization and modeling methods you choose to use.
(g) Include an Executive Summary, a self-contained section provided for anyone who needs to quickly understand the main points and results. Make it easy to find.
(h) “How many pages should I write?” is the wrong question to ask. A well-written report can be long or short. Use the number of pages you need in order to write a good report which completes the task. Find a balance between explaining too little and being too “wordy.”
Report Submission
Your final report is the final exam for the course. As such, it is due at the (ending) time of the scheduled final exam for the course: Monday, April 29, 2024, 6:30PM (local Pullman time). Late projects will not be accepted. It is strongly recommended that you complete your project early and give yourself ample time for submission. “Last minute” technical difficulties or illness are not acceptable reasons for late work. Plan ahead, work ahead, do not risk taking a zero score.
The report submission is to be through the Final Project link in the course Canvas page. The submission should be a single PDF document, not a collection of parts. If you are submitting supplementary materials (e.g. code, data, appendices), then these should either be naturally incorporated into your report or the reader should be provided with an access link to a separate website repository. In any case, the submitted report should be self- contained, not requiring that the reader access additional materials in order to understand the work.
Assessing Business Efficiencies
AugustMoon is a rental car business in the Pacific-Northwest region of the United States. Eleven sites are staffed at which cars are available for rental and return. AugustMoon would like to understand if a re-allocation of resources (personnel, cars, advertising, etc.) among sites would improve the overall business efficiency. In particular, the company would like to know which sites are most efficient. For each site, the available monthly-average data are provided in the following table.
AugustMoon’s CEO would like to see the following analysis.
(a) Provide baseline efficiencies using Data Envelopment Analysis. (An example of this type of linear programming problem was discussed in class and in the supplemental reading material.)
(b) Consider and test several business modifications for improving efficiency.
Multi-period Team Assignment Planning
EndGameSolutions is planning to complete five key projects in the next nine weeks. They need to assign personnel to the projects from the available staff in a way that maximizes productivity. The timelines and team size for each project are given in this table:
Each of the 50 available staff members has been recently rated and given scores, ranging from 0 to 100, for productivity, creativity and teamwork. EndGameSolutions is providing an Excel file with all scores. A sample is shown in this table:
EndGameSolutions would like to assign its 50 available staff to the projects subject to the following conditions.
(a) Maximize total productivity: the total productivity of all assigned staff to all projects. (b) The average productivity score of staff assigned to each project should be at least 70. (c) The average creativity score of staff assigned to each project should be at least 50.
(d) The average teamwork score of staff assigned to each project should be at least 50.
(e) A given staff member can be assigned to more than one project as long as the projects do not overlap in time. (No one can work more than one project at a time.)
(f) At least one senior staff member must be assigned to each project, and no senior staff member can be assigned to more than one project.
(g) Not all staff need to be assigned to a project.
(h) At least 34 staff should be assigned to at least one project. (The remaining 16 or fewer will participate in other company work.)
Solve EndGameSolutions assignment problem. Report the solution and any other informa- tion that may be useful to management, based on interpretation of your results.
Predicting Drug Lifetimes in the Bloodstream
SlipStream Drug Testing Company is considering streamlining its procedure for determining the long-term bloodstream concentration of a time-release test drug taken orally. The current procedure is to sample the bloodstream concentration at regular intervals to estimate the maximum concentration along with the time, and the times at which the concentration is at one-half and one-quarter of the maximum concentration. This procedure is invasive and requires the subject to be present at a testing facility for potentially long periods of time. SlipStream would like to understand if the long-term concentration versus time curve can be accurately estimated from early-time measurements only.
Suppose we have m time-concentration data points for one individual in one
test. The standard model is to assume
ρ(t) = atbe−t/c ,
where tis the time since the drug was taken, ρ(t) is the concentration of the drug as measured at time t, and a,b,care model parameters to be determined. If we can find a set of parameters that provide a best fit to the given data, then the model can be used to predict concentrations at any time t > 0. In particular, the company is interested in time t1 at which maximum concentration occurs, time t2 as which the concentration has reduced to one-half of the maximal value, and time t3 at which the concentration has reduced to one-fourth of the maximal value.
The data-fitting problem can be approached using linear programming if we first trans- form the model into logarithmic form.
In this form, the model is linear in the modified parameters lna, b, and − c/1. Now, we can use the data-fitting approach used in the course (recall the atmospheric CO2 concentration example). SlipStream is providing an excel file containing data for 24 individuals
that underwent standard testing. An example data set is plotted in Figure 1. SlipStream would like to have answers to the following questions.
1. Does the standard model provide a good representation of the data? 2. Can early-time data alone provide similarly good model parameters?
3. What is a good early-time cutoff for which we can still obtain accurate values for t1 , t2 and t3 ?
4. Based on your analysis, what changes can you suggest in our procedure or model that can benefit the company?
Figure 1: An example data set of bloodstream concentration of a test drug over time.
Optimal Placement of Emergency Supply Access Points
CrowdMark City is planning construction of a warehouse and distribution facility which will provide relief supplies to local residents during an emergency situation. The facility should be placed in a location that results in the smallest total distance which people must travel to reach the facility. Because the city is laid out on a grid of streets, a person at location (x,y) traveling to facility location (u,v) must travel a distance |x−u|+|y−v| . The city population is divided into m neighborhoods with population pk and neighborhood location (xk ,yk ), for k = 1, 2,...,m. The locations are specified as integer values (city block locations). The new facility can be placed anywhere on the integer grid, except at a location that contains a neighborhood. The initial tasks are as follows.
1. Formulate a linear optimization problem (in a general form) that CrowdMark can use
to solve the facility placement problem for any neighborhood data set.
2. Solve the CrowdMark problem for the given data set.
The city planners are also interested in the possibility of using two facilities, instead of just one, to cover the needs of the same population distribution. As the cost of this plan will naturally be greater, their primary interest is in determining the overall travel time difference between the former scenario and this new scenario.
1. Formulate a linear optimization problem (in a general form) that CrowdMark can use to solve the two-facility placement problem for any neighborhood data set.
2. Solve the two-facility CrowdMark problem for the given data set. Apply any constraints you feel are necessary and reasonable, but unstated here.
3. Consider the results of the two problems and make some recommendations.
4. Suggest a method for generalizing the problem for d > 2 facilities. (You do not need to carry out this procedure/analysis.)
CrowdMark City is providing a data file of neighborhood locations and populations. A graphical representation of the data is shown in Figure 2.
Figure 2: Neighborhood population (in hundreds) with locations in CrowdMark City.
Robust Shortest Time Delivery Paths
The Assurance Delivery company is a startup company specializing in package delivery within the western areas of the United States. They advertise guaranteed delivery within a specified time. Their quoted times are not always shorter than other delivery companies, but delivery comes with a money-back guarantee if, for any reason, the delivery is not met on time. The company necessarily has a vested interest in finding delivery routes that are not only efficient (short) but robust (not likely to incur delays). In order to set their rates, the company is seeking a method for finding an optimal route between two given locations.
The problem of finding a shortest path between two locations can be easily solved as an integer program, provided that the number of possible routes is not too large. Also, the problem of finding the route least likely to incur a delay is similarly solved. Assurance Delivery would like to solve the problem of a compromise route that helps then maintain competitiveness without significant reduction in promised delivery time.
As a small example, consider the problem of sending a package from city A to city G along some route in the network shown below. Graph nodes indicate cities and graph edges indicate possible sub-routes between cities. Travel times are indicated in blue and the probabilities of having a serious delay are shown in red.
It is easy to verify that the shortest path is A → D → G of length 8.4, but the subpath D → G has high probability of delay. Perhaps it might be better to use a longer path with a better chance of being on time.
You are given the following tasks.
1. Use the provided network data to solve the shortest path problem for user-supplied starting and ending locations. Ignore any possible delays.
2. Use the provided network data to solve the minimum delay likelihood problem for user-supplied starting and ending locations. Ignore travel times.
3. Combine the two previous solution methods where the objective is to minimize the weighted sum of travel time and delay likelihood. The relative weight should be an adjustable parameter. Determine a reasonable relative weighting based on experiments you perform.
4. Solve the combined problem using your weight selection with starting city A and ending locations at every other city. Report your findings and make recommendations to the company.
The data set is provided as two files distance. csv and delay. csv which are comma- delimited 15 × 15 arrays. The entry in the ith row and jth column of the respective arrays gives the distance (or delay probability) between city i and city j. If an array has entry zero, this indicates that the cities are not connected by a path. For example, the sample graph above is described by the following arrays:
The networks we will consider are symmetric – distances and delays do not depend on the direction of travel.