Linear programming Solution

$35.00

Description

TAs in charge

All four TAs will be working on this assignment. You can contact anyone of them if you have questions.

Overview

For this project, you will model the following problems as linear programs and solve them using a language and linear programming solver of your choice. For a (non-comprehensive) list of freely available LP solvers, see this wikipedia page: http://en.wikipedia.org/wiki/Linear_programming. These problems have previously been tested using Matlab and Matlab’s linear programming solver, linprog (which you have access to through the College of Engineering) as well as GLPK via the Python PuLP package (see https: //projects.coin-or.org/PuLP).

Warm-up question: Least squares isn’t good enough for me

You are given a set of points (x1; y1); (x2; y2); : : : ; (xn; yn) in the plane. You want to nd a line y = ax + b that comes close to each point. You probably have learnt the method of least squares to nd a line of best t in your past, but we want to nd the line of best t that minimizes the maximum absolute deviation. That is, you want to nd the values of a and b that minimizes:

max jaxi + b yij

1 i n

Model this general problem as a linear program. Use the linear program to nd the line of minimum-maximum-absolute-deviation for the instance:

(1; 3); (2; 5); (3; 7); (5; 11); (7; 14); (8; 15); (10; 19)

Your report must include:

the linear program for the general problem written as an objective and set of constraints the best solution for the speci c problem above

the output of the LP solver that you used (showing that an optimal solution was found) a plot of the points and your solution for the instance

Warming-up question: Local temperature change

The daily average temperature at a given location can be modeled by a linear function plus two sinusoidal functions; the rst sinusoidal function has a period of one year (modeling the rise and fall of the temperature

with the seasons) and the second sinusoidal function has a period of 10.7 years (modeling the solar cycle).

That is, a decent model of average temperature T on day d is given by:

T (d) = x0 + x1 d + x2

cos

365:25

+ x3 sin

365:25

+ x4

cos

365:25

10:7

+ x5

sin

365:25 10:7

2 d

2 d

2 d

2 d

|

{z

}

}

|

{z

}

linear

trend

seasonal

{z

pattern

solar

cycle

|

The values of x0; x1; : : : ; x5 depend on the location. For example, the amplitude of the seasonal change (x2 and x3) would be much greater in Chicago, IL than in San Diego, CA. Given daily temperature recordings (pairs (di; Ti): the average temperature Ti on day di), we can nd values for x0; x1; : : : ; x5 that result in an equation T (d) that best ts the data. You will use what you learned in the warm-up question to nd the curve T (d) of best t that minimizes the maximum absolute deviation for a given set of daily average temperatures.

Data from Corvallis is provided on canvas. The rst four columns are the raw data downloaded from NOAA. Raw minimum and maximum temperature recordings are given in tenths of degrees Celcius. Average daily temperature (column average) is in degrees Celcius and is simply the average of the maximum and minimum temperatures on a given day. The number of days since May 1, 1952 is given in the last column (day). Note that you need to take the day number into account because several days (and a few entire months) were missing from the data set. These last two columns give you the (di; Ti) data pairs.

Your best t curve (de ned by the linear program you use to nd the values of x0; x1; : : : ; x5 that minimize the maximum absolute deviation of T (d) from your data points), gives you a value x1 that describes the linear drift of the temperature as degrees per day.

Your report must include:

A description for a linear program for nding the best t curve for temperature data.

The values of all of the variables to your linear program in the optimal solution that your linear program solver nds for the Corvallis data. Solving this LP may take a while depending on your computer. Be patient. Include the output of the LP solver that you use (showing that an optimal solution was found).

A single plot that contains:

{ the raw data plotted as points in 2-d (with d as the x-axis and T as the y-axis),

{ your best t curve, and

{ the linear part of the curve x0 + x1 d.

Based on the value x1 how many degrees Celcius per century is Corvallis changing and is it a warming or cooling trend?

[BONUS] Repeat this whole process for a location of your choice. You can download this from NOAA (http://www.ncdc.noaa.gov/cdo-web/search) for many locations. Be sure that your data covers at least 50 years to get a good t. You will need to plan ahead as NOAA can take several hours to return the data to you given a request. Also note that the data is not necessarily clean: it may miss some measurements or include nonsense measurements (like -9999) that should be removed. The number of elapsed days should be carefully calculated from the date stamp.

2