Problem 1: Shortest Path Assignment (20 points).

Part A (5 points). Given node-link adjacency matrix E from below answer the following:

State the number of nodes: ___

State the number of links: ___

AND draw the network

πΈ =

[

β1 β1 0 0 0 0 0 0 0 0

1 0 0 β1 0 0 0 0 0 0

0 1 1 0 β1 β1 0 0 0 0

0 0 0 0 0 0 β1 1 1 0

0 0 0 0 0 1 1 β1 0 0

0 0 0 0 0 0 0 0 0 1

0 0 β1 1 1 0 0 0 β1 β1]

Part B (5 points). Assuming centroid A is connected via a connector to node 1, centroid B to

node 2, Centroid C from node 5, and Centroid D from node 6 (in other words A and B are

origins, C and D are destination) state the set of all acyclic paths in the network for each

origin-destination node pair.

Part C (10 points). Given the link cost vector π = [4,5,2,5,2,1,3,2,2,2] (links and nodes in

the same order as stated with matrix E in Part A) and assuming all centroid connectors have

a cost of 0, use Dijkstraβs algorithm to solve the SP problem for this network. Show all

iterations.

Give the origin-destination minimum travel cost matrix:

C D

A ____ ____

B ____ ____

1. State the shortest path from A to C:

2. State the shortest path from B to C:

3. In what order did the nodes have their labels set (when solving Dijkstraβs) from origin A?

Problem 2: Algorithm Design (12 pts)

Let πΊ = (π, π΄) be a directed graph with travel time π(π,π) for every link (π,π) β π΄. Consider

the following algorithm:

Initialization:

Let πΏ = [πππ] be a matrix where πππ = π(π,π) if (π,π) β π΄ and πππ = β otherwise.

Let π = [πππ]be a matrix where πππ = 0 if πππ = β and πππ = π otherwise.

Algorithm

Input: πΊ, πΏ, π

1 for π = 1. . |π|

2 for π = 1. . |π|, π β π

3 if πππ + πππ < 0

4 return βthere is a negative cycleβ

5 if πππ β β then

6 for π = 1. . |π|, π β π

7 π = πππ

8 if π + πππ < πππ

9 πππ β π + πππ

10 πππ β πππ

11 end if

12 end for

13 end if

14 end for

15 end for

Output: πΏ, π

Questions:

1-What does the algorithm do?

2-In the end, what does πππ represent?

3- In the end, what does πππ represent?

Problem 3: Convexity (16 points).

Definitions:

π΄ ππ’πππ‘πππ π βΆ πΏ β βπ

ππ ππππ£ππ₯ ππ, πππ ππ£πππ¦ π₯1, π₯2 β πΏ πππ ππ£πππ¦ π β [0,1]:

π((1 β π)π₯1 + ππ₯2) β€ (1 β π)π(π₯1

) + ππ(π₯2

)

π΄ ππ’πππ‘πππ π βΆ πΏ β βπ

ππ π π‘ππππ‘ππ¦ ππππ£ππ₯ ππ, πππ ππ£πππ¦ π₯1 β π₯2 β πΏ πππ

ππ£πππ¦ π β (0,1):

π((1 β π)π₯1 + ππ₯2) < (1 β π)π(π₯1

) + ππ(π₯2

)

Part A (8 points).

Using the definition of function convexity above, determine if the functions below are convex

or not on the domain specified.

1. π1

(π₯) =

π₯

3+2

π₯

2+1

for π₯ β β

2. π2

(π₯) = 3π₯

2 β |π₯ β 8| for π₯ β [1,5]

Part B (8 points).

Using the definition of strict function convexity above, determine if the functions below are

strictly convex or not on the domain specified.

3. π3

(π₯) = 11 + (π₯ β 3) + 3π₯

2

for π₯ β β

4. π4

(π₯) = max{π₯

3

, 0} for π₯ β β

HINT: Proof by contradiction can be used if the functions are not convex or strictly convex.

Problem 4: Optimality Conditions (16 points).

Part A (6 points).

Write the set of optimality conditions and state the optimal solution for the following

mathematical program:

πππππππ§π π(π₯1, π₯2

) = 3π₯1

2 β 5π₯1+π₯2

2 β 8π₯2

s.t. π₯1, π₯2 β₯ 0

Part B (10 points).

Re-write the set of optimality conditions if the following constraint is added to the above

problem: π₯1 + π₯2 = 2. Does the optimal solution change? And if so, what is the new solution?

πππππππ§π π(π₯1, π₯2

) = 3π₯1

2 β 5π₯1+π₯2

2 β 8π₯2

s.t. π₯1 + π₯2 = 2

π₯1, π₯2 β₯ 0

Problem 5: One Dimensional Optimization (16 pts)

Find the minimum of f(x) = 2x

2

-10x +7 over the interval [0,5] to determine the optimal value

of x. Stop when the final interval is within 5% of the initial interval (do no extra work). Solve

using both Golden Section and Bisection. Compare the number of iterations required for

each. Which required more iterations and why? Show all work.

Problem 6: Traffic Assignment basics and User Equilibrium (20 pts)

Consider the network below with the following link travel time functions (π₯π is the flow on

link π and π‘π

(π₯π

) is the travel time of link π):

π‘1

(π₯1

) = 4π₯1 + 5

π‘2

(π₯2

) = π₯2 + 10

π‘3

(π₯3

) = π₯3 + 10

π‘4

(π₯4

) = 4π₯4 + 5

π‘5

(π₯5

) = 2π₯5

π‘6

(π₯6

) = π₯6 + 10

π‘7

(π₯7

) = π₯7 + 10

There are two origin-destination pairs (1,5) and (2,6) with demands (π is the origin node, π is

the destination node and πππ is the travel demand from π to π ):

π15 = 30

π26 = 60

Clearly write out the full system of equations required to algebraically solve for UE, and

determine the user equilibrium traffic flow on each link of the network.