# bertsekas.mod # This problem is based on a traffic assigment problem, found in: # D.P. Bertsekas and E.M. Gafni, "Projection Methods for Variational # Inequalities with Application to the Traffic Assignment Problem", # Mathematical Programming Study 17(1982), 139-159. # Just so you know, x(i) is the flow (from node(i) to node(i+3)) on the # (longer) outside loop, z(i) the flow on the inside loop, and y the # dual variables. # The source problem here is a VI, where the constraints consist of # non-negative bounds and x(I) + z(I) = demand(I). Without much # fiddling, we can write the problem as a MCP. # We can write the problem in (at least) 2 different ways. In the # first, y is free, and the demand constraints are satisfied exactly. # In the second, we change the demand constraint to an inequality, where # extra flow is allowed. This doesn't occur in solutions, and we can # write the problem as an NCP. set Nodes circular; # nodes in the network set Types; # types of arcs param demand {Nodes}; # flow demand, i -> i+3 param c {Nodes,Types}; # delay coefficients for links in the network param gamma; # gamma is a coupling coefficient. The delay on some of # the links is increased gamma * delay on merging links. var x {Nodes}; # outside flow var z {Nodes}; # inside flow var y {Nodes}; # dual vars var fx {i in Nodes} = 1 + x[i] + x[i]^2; var fz {i in Nodes} = 1 + z[i] + z[i]^2; s.t. delay_o {i in Nodes}: 0 <= x[i] complements c[i,"oon"]*fx[i] + gamma * (1 + x[next(i,Nodes,3)] + x[next(i,Nodes,4)] + (x[next(i,Nodes,3)]+x[next(i,Nodes,4)])^2) + 10 * c[i,"ohy"]*(1 + x[i] + x[next(i,Nodes,3)] + x[next(i,Nodes,4)] + (x[i] + x[next(i,Nodes,3)] + x[next(i,Nodes,4)])^2) + 2 * gamma * fx[next(i,Nodes,3)] + c[next(i),"oby"] * (1 + x[i] + x[next(i,Nodes,4)] + (x[i] + x[next(i,Nodes,4)])^2) + 10 * c[next(i),"ohy"] * (1 + x[i] + x[next(i)] + x[next(i,Nodes,4)] + (x[i] + x[next(i)] + x[next(i,Nodes,4)])^2) + 2 * gamma * fx[next(i,Nodes,4)] + c[next(i,Nodes,2),"oby"] * (1 + x[i] + x[next(i)] + (x[i]+x[next(i)])^2) + 10 * c[next(i,Nodes,2),"ohy"] * (1 + x[i] + x[next(i)] + x[next(i,Nodes,2)] + (x[i] + x[next(i)] + x[next(i,Nodes,2)])^2) + 2 * gamma * fx[i] + c[next(i,Nodes,3),"ooff"] * fx[i] >= y[i]; s.t. delay_i {i in Nodes}: 0 <= z[i] complements c[i,"ion"]*fz[i] + gamma * fz[next(i)] + 10 * c[i,"ihy"]*(1 + z[i] + z[next(i)] + (z[i] + z[next(i)])^2) + 2 * gamma * fz[next(i)] + c[prev(i),"iby"]*fz[i] + 10 * c[prev(i),"ihy"] * (1 + z[i] + z[next(i,Nodes,4)] + (z[i]+z[next(i,Nodes,4)])^2) + 2 * gamma * fz[i] + c[prev(i,Nodes,2),"ioff"] * fz[i] >= y[i]; s.t. dem_cons {i in Nodes}: x[i] + z[i] == demand[i];