Starting from:
$30
Assignment 3: Linear programming
CS325 Implementation assignment 3: Linear programming
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
1≤i≤n
|axi + b − yi
|
Model this general problem as a linear program. Use the linear program to find the line of minimummaximum-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
1
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
| {z }
linear trend
+ x2 · cos ?
2πd
365.25?
+ x3 · sin ?
2πd
365.25?
| {z }
seasonal pattern
+ x4 · cos ?
2πd
365.25 × 10.7
?
+ x5 · sin ?
2πd
365.25 × 10.7
?
| {z }
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 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.
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 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?
• [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 fit. 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
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
1≤i≤n
|axi + b − yi
|
Model this general problem as a linear program. Use the linear program to find the line of minimummaximum-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
1
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
| {z }
linear trend
+ x2 · cos ?
2πd
365.25?
+ x3 · sin ?
2πd
365.25?
| {z }
seasonal pattern
+ x4 · cos ?
2πd
365.25 × 10.7
?
+ x5 · sin ?
2πd
365.25 × 10.7
?
| {z }
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 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.
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 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?
• [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 fit. 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
1 file (1.1MB)
