Implementation assignment #3: Linear programming Solution

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 find a line y = ax + b that comes close to each point. You probably have learnt the method of least squares to find a line of best fit in your past, but we want to find the line of best fit that minimizes the maximum absolute deviation. That is, you want to find the values of a and b that minimizes:




max |axi + b − yi |

1≤i≤n




Model this general problem as a linear program. Use the linear program to find 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 specific 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 first 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:




2πd




2πd




2πd




2πd
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
|linea{r ztrend}

| seasona{lzpattern }

| solar{zcycle }
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 find values for x0 , x1 , . . . , x5 that result in an equation T (d) that best fits the data. You will use what you learned in the warm-up question to find the curve T (d) of best fit that minimizes the maximum absolute deviation for a given set of daily average temperatures.

Data from Corvallis is provided on canvas. The first 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 fit curve (defined by the linear program you use to find 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 finding the best fit curve for temperature data.




• The values of all of the variables to your linear program in the optimal solution that your linear program solver finds for the Corvallis data. Solving this LP may take a while depending on your computer. 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 fit 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?