Session 5: Exercises

Exercise 1:

Recall the Price of Anarchy function from Exercise 2.3. Use the Maximize function to find the worst case demand rate r≥0 with highest price of anarchy for the cost functions

c1[x_]:=x+1;
c2[x_]:=2x

and the cost functions with parameter

c1[x_]:=a1*x;
c2[x_]:=1;

(Use the poa function generated by Exercise 2.3)

Solution

(* The price of anarchy function generated by Ex. 2.3 for the functions without *)
poa=Piecewise[{{1, r <= 1/4}, {(24*r^2)/(-1 + 8*r + 8*r^2), 
    Inequality[1/4, Less, r, LessEqual, 1/2]}}, (8*r*(1 + r))/(-1 + 8*r + 8*r^2)];
(* Compute the maximal PoA *)
Maximize[{poa,r≥0},r]

(* The price of anarchy function generated by Ex. 2.3 for the functions with parameter *)
poa=Piecewise[{{4/(-1+4*a1*r),a1*r==1},{4*a1^2*r^2,2*a1*r==1},{1,2*a1*r≤1},{(4*a1^2*r^2)/(-1+4*a1*r),1/2≤a1*r≤1},{(2*a1^2*r^2)/(-1+2*a1*r+2*a1^2*r^2),a1*r≤1},{(4*a1*r)/(-1+4*a1*r),a1*r≥1},{(4*(-1+a1*r+a1^2*r^2))/(-1+4*a1*r),2*a1*r≥1}},(2*(-1+a1*r+a1^2*r^2))/(-1+2*a1*r+2*a1^2*r^2)];
(* Compute maximal PoA depending on a1 *)
Simplify[Maximize[{poa,r≥0,a1≥0}, r]]

Exercise 2:

a)

Use the code from Exercise 4.2c) to setup and print the convex program to compute a Wardrop equilibrium. Use the Minimize[ ] function to solve the convex program (in dependence of r).
Recall, that Minimize expects a list containing {objective, constraint1, constraint2, ...} as first argument. To concatenate lists, use the function Join[ list1, list2 ] or the short form list1~Join~list2.
Use the existing list flowvars as second argument for Minimize.

Solution

Execute all solution of Exercise 4.2. first.

solution=Simplify[Minimize[{objective}~Join~flowconditions~Join~nonnegconditions,flowvars],Assumptions->r≥0]

b)

Create a Manipulate[ ] environment, that lets you set a demand rate “rate” and solves the convec program from a) with the given rate.
You might need to use a replacement rule to create flow-conditions that actually contain the manipulated demand rate rather than r, write for example:

fc=flowconditions/.r->rate;

and use the fc in the Minimize function instead.

Create a graph with edge weights that contain the flow values computed by the convex program as EdgeWeight to visualize the solution.

Solution

See the notebook wardropConvexProgram.nb for a complete solution.

(* Compute and print the solution *)
Print["Solution:"];
Manipulate[
(* Create new flowconditions vector that depends on the "rate" variable of the Manipulate function *)
fc=flowconditions/.r->rate;
(* Execute the actual convex optimization *)
solution=Minimize[{objective}~Join~fc~Join~nonnegconditions,flowvars];
(* Extract optimal value and the optimal solution from the solution variable *)
optvalue=solution[[1]];
optflow=solution[[2]];
(* Create Arrays that describe the labels and the style of the edges *)
edgeweights=(Table[ edges[[e]]->f[e],{e,1,m}])/.optflow;
edgestyle=(Table[ edges[[e]]-> Directive[Thickness[(1/2+f[e])/50],If[f[e]==0,Gray,Blue]], {e,1,m} ])/.optflow;
(* Create the actual graph, by copying the input graph and equipping it with EdgeWeights and Labels *)
Graph[graph,EdgeWeight->edgeweights,EdgeLabels->"EdgeWeight", VertexLabels->Automatic, EdgeStyle->edgestyle]
,{rate,0,4,1/1000}]