Other Reference Material

A summary of techniques introduced to date

---

Homework Assignments and Solutions

Homework should be submitted via Canvas.

Duality and Linear Programming

Assignment 1

Due Sept. 5th

• Solutions. 

Integer Programming; Optimization as Matching Observations - Estimation and Diagnostic Problems;

Assignment 2

1. Problems 11.2, 11.3, 11.5, 11.9 and 11.10 (see pdf file of Chapter 11  problems).
2. Implement a Matlab routine to solve a MIP using branch and bound. Use the lp or linprog functions for solving the linear programming problems at each branch. Your solution should show the resulting search tree. Try to make your routine general. Apply your solution to 11.2 and 11.10.
3. Solve the example state estimation problem in class using Weighted Least Absolute Value (WLAV) assuming equal weighting as done in class with z=[0.60.05 0.40] ^T ( z ₁ = -5x ₁;  z ₂ = - 2.5x ₂; z ₃ = 4x ₁ - 4x ₂ ). Compare the solution to the Weighted Least Squares (WLS) method with equal weighting as done in class (i.e., linear regression). Now add an additional measurement of the injected flow at bus 2 ( z ₄ = 9x ₁ - 4x ₂ ) with a value of 0.25 and repeat the analysis. Comment on the solution.
4. This problem refers to the alarm processing problem that was discussed in class. You are to formulate and solve an LP for this problem by finding the minimal set of events to explain the alarms received. There are 11 possible alarms and 10 possible events, below are listed 10 event-alarm relationships. For this problem, you receive the following alarms:{a2,a6,a8,a9,a11}.  Also, you should state whether the solution is unique and if not, how you ensure a unique solution.  For background on this approach see Dijk.
   

e1-> {a1 a4 a6 a7}
e2-> {a1 a4 a6 a8}
e3-> {a1 a4 a5 a9 a10}
e4-> {a1 a4 a9 a10}
e5-> {a1 a3 a4 a9 a10}
e6-> {a1 a3 a9}
e7-> {a9}
e8-> {a11}
e9-> {a1 a2}
e10-> {a1}

• Solutions (zip file which includes some Matlab routines).
• Some slides on alarm processing.

Graph Searches

Assignment 3

This file contains a list of cities in Washington state with latitude and longitudinal information and driving distances between the cities. Perform the following to find a path between Tacoma and Pullman:

1. Use depth-first search to find a path showing how the search proceeds. State clearly your depth-first rule.
2. Solve for the shortest path using Dijkstra's shortest path algorithm.
3. Formulate the search as an LP problem and solve using Matlab.
4. Define an evaluation function based on the latitudinal and longitudinal values given. Then: (a) show for evaluation function that it satisfies the A* heuristic requirement, i.e., is conservative, (b) show whether this evaluation function is consistent , and (c) solve using A* search showing clearly how the search proceeds.
5. Compare the search efficiencies in terms of the nodes visited for parts(1), (2) and (4). Note: It would be nice to compare these to the efficiency for LP in (3) as well. Essentially, each basic solution would be a candidate path and then you could count how many steps (pivots) till you found the optimal solution. In the older versions of Matlab, you could see the m-file and step your way through it. Unfortunately, I haven't found an easy way to do this in the newer versions of Matlab so it is tough to make a comparison. But if you can find an old version of the Matlab code (or perhaps some other open source Simplex algorithm where you can count pivots), I would be interested in your results. 

General Duality and Lagrangian Relaxation

Assignment 4

1. Solve the following optimization problem using general duality (form the dual and find the maximum of the dual).

min f(x)=x²₁+3x²₂
such that
3x₁+2x₂<-4

2. Consider the following optimization problem:
                   min f(x)=10-3x₁-2x₂-x₃
                   such that
                        2x₁+3x₂+4x₃<4
                        0<x_i<1
       (a) Solve using the general duality principle.
       (b) Now assume that x _i is binary and solve both the primal and dual. Find the duality gap.
3. Modify the search problem from Assignment 3 so that is has a maximum allowable transit time (i.e., so it now becomes a constrained shortest path). Assume there are freeways for the paths listed below where one can travel at 75 MPH and smaller roads for all the remaining paths where one can travel at 40 MPH. Given a maximum allowable time of 8 hours. Use Lagrangian Relaxation to find a solution.
• Tacoma-Olympia
• Tacoma-Seattle
• Seattle-Renton
• Seattle-Everett
• Everett-Bellingham
• Renton-Yakima
• Yakima-Moses Lake
• Moses Lake - Spokane
4. Use Matlab to implement a Lagrangian relaxation approach to solving the scheduling problem below. (For those in power systems, this is a unit commitment problem modified from Wood and Wollenberg.)
       Costs if unit scheduled (no cost otherwise): 
                   f₁ (x)=500+10P₁ +0.002P ² ₁
                    f₂(x)=300+8P ₂ +0.004P ²₂
                   f₃(x)=100+6P₃ +0.006P ²₃
        Unit limits:
                        100 < P₁ < 400
                         50 < P₂ < 500
                       100 < P₃ < 300
        Loads at (i.e., quantity needed at each hour, P₁(t)+P₂(t)+P₃(t)=Load(t) ):

                       Hour 1    250
                       Hour 2  1050
                       Hour 3    350
                       Hour 4    150

Final Project

Project progress report due Nov. 14^th. Final Project report due TBD. Presentations TBD.

Note last day of class is Dec. 5th so let's schedule presentations tentatively in class on Nov. 30th and Dec. 5th but we can change as needed. Also, if your project is not fully complete, then you can still present preliminaries and send in your full report later.

• Define an optimization problem of some practical use in some application domain. The problem cannot be trivial.
• For this problem, first formulate and solve using a traditional optimization method in the most straightforward or simple method possible way by making appropriate simplifications. Typically, this would be say a linear program or shortest path type of method.
  
• Now with the same problem, remove some of the simplifications too reflect some more practical objectives (for example, discrete constraints, non-linearities, multiple objectives, soft constraints, change of variables, etc.) and reformulate. Still try to solve using a traditional approach. The idea is you should use some "clever" way of implementing a constraint or objective so that it is still relatively easy to solve, for example, piece-wise linear, turning multi-objectives into constraints.
• Finally, reformulate again to reflect even more of the true problem complexity (for example, multiple objectives, very difficult constraints, non-convexity, etc.) and it should be something that requires a more creative solution, e.g., solving a series of solutions, population based method, robust methods, etc.. 
• Compare the three problem formulations in terms of ease of formulation, simplicity of implementation, computational speed, practicality (usefulness) of solution, quality of solution and any other metric you care wish to show.
  

• A detailed description of the optimization problem you are solving, including overall objectives and contraints with specifics as well as background material. 
• An outline of the methods to be employed, which also identifies the differences between the models and approaches.
• Any results you have to date (this does not need to be final and only include if meaningful).
  

Gradient Methods, Downhill Simplex and Stochastic Optimization

Assignment 5

1. Problem 7.3 (pg. 327) parts i-v in Baldick (scanned copy).
   
2. Consider the peaks function defined as: z =f(x,y)= 3*(1-x).^2.*exp(-(x.^2) - (y+1).^2) - 10*(x/5 - x.^3 -y.^5).*exp(-x.^2-y.^2) - 1/3*exp(-(x+1).^2 - y.^2) (see Matlab file below), where one wishes to find the maximum. Using a steepest ascent gradient method (the peak functions and derivatives are given in this file) with a randomly generated initial solution.

For the following three problems, you are to use the price and load data contained in this Excel file. It should be self-explanatory but the data represents MW load at fours of each day for one year (2002) and the associated prices for each of those data points.

3. Solve a linear regression model of the form Price = a₀ + a₁·Load  +a₂·Load² for each of the four hours and for two different splits of training and testing data: a) using the first 6 months for training and using the last 6 months for testing and b)  a random separation of the data into two equal sized sets. Thus, you will have 8 models. Compare the approaches using the RMSE on the test sets. 
4. Repeat above using an ANN model using this Matlab function that implements a steepest descent training for a hyperbolic tangent activation function. The syntax of for this routine is [W1, W2, RMSE] = tanmlp(trn_data, mlp_config, train_opt), where: 
   - W1 is the first layer set of weights, W2 is the second layer and RMSE is the error
   - trn_data is the training data
   - mlp_config is the number of inputs, nodes in hidden layer and outputs, e.g., mlp_config = [2 5 1];
   - trn_config is error goal, learning rate, momentum term, max training cycles, normalization (use 0), debugging flag, e.g., train_opt = [0.01 0.01 0.01 2000 0 0];
   - to get the output simply use tanh function, e.g., hidden layer X1 = tanh([test_data ones(n,1)]*W1) and then the output y = tanh([X1 ones(n,1)]*W2) .
   
5. Compare your solutions in 4 and 5.

Data Driven Problem and Simple Game Theory

Mini Assignment 6

1. Given the data below of previously classified events with three attributes thay can take on integers between [0 2], give the classification for a new point x=[1 1 2] using: (a) Decision trees to optimize entropy (each decision rule should branch on a single variable - you can decide the depth); (b) Bayesian analysis. Compare solutions.

   Sample	X1	X2	X3	Class
   1	1	2	1	1
   2	0	0	1	1
   3	2	1	2	2
   4	1	2	1	2
   5	0	1	2	1
   6	2	2	2	2
   7	1	0	1	1
   8	2	2	0	2
   9	2	1	1	2
   10	1	1	1	1

2. Consider a two player zero sum game, where each player has two options: A or B. For the payoff matrix below (payoff(x,y)) with rows showing x decision and columns showing y decision, find the Nash equilibrium (both mixed and pure strategy if they both exist) with expected payoffs for each player. 

   Decision	A	B
   A	-1, 1	10,-10
   B	5,-5	-1,1

3. Consider a two player non-zero sum game, where each player has two options: A or B. For the payoff matrix below(payoff(x,y)), find the Nash equilibrium (both mixed and pure strategy if they both exist) with expected payoffs for each player. Suggest other solutions (i.e., where collusion is allowed).

   Decision	A	B
   A	-1,3	6,4
   B	5,6	-1,1