import%20marimo%0A%0A__generated_with%20%3D%20%220.23.16%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Congestion%20Pricing%20on%20a%20Braess%20Network%0A%0A%20%20%20%20A%20road%20authority%20chooses%20a%20toll%20before%20travelers%20select%20their%20routes%0A%20%20%20%20through%20a%20network.%20Travelers%20minimize%20their%20own%20generalized%20travel%20cost%2C%0A%20%20%20%20while%20the%20authority%20anticipates%20this%20equilibrium%20and%20minimizes%20total%20time%0A%20%20%20%20spent%20in%20the%20network.%0A%0A%20%20%20%20The%20example%20uses%20a%20four-node%20Braess%20network.%20Without%20a%20toll%2C%20the%20apparently%0A%20%20%20%20attractive%20central%20link%20draws%20too%20much%20traffic%20and%20increases%20congestion.%0A%20%20%20%20Pricing%20that%20link%20can%20coordinate%20individual%20route%20choices%20and%20recover%20a%0A%20%20%20%20nearly%20system-optimal%20allocation.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20from%20pathlib%20import%20Path%0A%0A%20%20%20%20import%20cvxpy%20as%20cp%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20import%20numpy%20as%20np%0A%0A%20%20%20%20from%20blvpy%20import%20BilevelProblem%2C%20LowerProblem%0A%0A%20%20%20%20plt.style.use(Path(__file__).resolve().parents%5B1%5D%20%2F%20%22_shared%22%20%2F%20%22zhlatex.mplstyle%22)%0A%20%20%20%20return%20BilevelProblem%2C%20LowerProblem%2C%20Path%2C%20cp%2C%20mo%2C%20np%2C%20plt%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Bilevel%20formulation%0A%0A%20%20%20%20Let%20the%20directed%20edge%20set%20be%20ordered%20as%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20E%3D(OA%2COB%2CAD%2CBD%2CAB)%2C%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20and%20let%20the%20three%20paths%20be%20%24OAD%24%2C%20%24OBD%24%2C%20and%20%24OABD%24.%20The%20path%20flow%0A%20%20%20%20%24x%5Cin%5Cmathbf%7BR%7D%5E3%24%20induces%20the%20edge%20flow%20%24f%5Cin%5Cmathbf%7BR%7D%5E5%24%20through%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20f%3DHx%2C%5Cqquad%0A%20%20%20%20H%3D%5Cbegin%7Bbmatrix%7D%0A%20%20%20%201%260%261%5C%5C%0A%20%20%20%200%261%260%5C%5C%0A%20%20%20%201%260%260%5C%5C%0A%20%20%20%200%261%261%5C%5C%0A%20%20%20%200%260%261%0A%20%20%20%20%5Cend%7Bbmatrix%7D.%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20Thus%2C%20each%20column%20of%20%24H%24%20records%20the%20edges%20used%20by%20one%20path.%20In%20particular%2C%0A%20%20%20%20only%20the%20third%20path%20uses%20the%20central%20edge%20%24AB%24.%20The%20fixed%20demand%20is%20%24q%24%2C%20so%0A%20%20%20%20feasible%20path%20flows%20satisfy%20%24x%5Csucceq0%24%20and%20%24%5Cmathbf%7B1%7D%5ETx%3Dq%24.%0A%0A%20%20%20%20Edge%20%24e%24%20has%20affine%20travel%20time%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20T_e(f_e)%3Db_e%2Ba_ef_e.%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20For%20a%20toll%20%24%5Ctau%24%20on%20%24AB%24%2C%20travelers%20reach%20the%20Wardrop%20equilibrium%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20%20%20%20%20%5Cbegin%7Barray%7D%7Brl%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20S(%5Ctau)%20%3D%20%5Cmathop%7B%5Crm%20argmin%7D_x%20%26%20%5Csum_%7Be%20%5Cin%20E%7D%20(b_e%20f_e%20%2B%20(1%2F2)%20a_e%20f_e%5E2)%20%2B%20%5Ctau%20f_%7BAB%7D%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%5Cmbox%7Bsubject%20to%7D%20%26%20x%20%5Csucceq%200%2C%5Cquad%20%5Cmathbf%7B1%7D%5ET%20x%20%3D%20q%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%26%20f%20%3D%20Hx%2C%0A%20%20%20%20%20%20%20%20%5Cend%7Barray%7D%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20which%20is%20called%20the%20Beckmann%20formulation.%0A%20%20%20%20Noticing%20that%20differentiating%20its%20edge%20term%20with%0A%20%20%20%20respect%20to%20%24f_e%24%20gives%20%24T_e(f_e)%24%2C%20so%20its%20optimality%20conditions%20reproduce%0A%20%20%20%20travelers'%20route-choice%20conditions.%20The%20authority%20solves%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20%5Cbegin%7Barray%7D%7Bll%7D%0A%20%20%20%20%5Cmathop%7B%5Cmathrm%7Bminimize%7D%7D_%7B%5Ctau%2Cx%7D%0A%20%20%20%20%20%20%20%20%26%20%5Cdisplaystyle%5Csum_%7Be%5Cin%20E%7Df_eT_e(f_e)%2B%5Crho%5Ctau%5E2%5C%5C%0A%20%20%20%20%5Cmathop%7B%5Cmathrm%7Bsubject%5C%20to%7D%7D%0A%20%20%20%20%20%20%20%20%26%200%5Cleq%5Ctau%5Cleq5%2C%5C%5C%0A%20%20%20%20%20%20%20%20%26%20x%5Cin%20S(%5Ctau).%0A%20%20%20%20%5Cend%7Barray%7D%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20Toll%20payments%20are%20transfers%20rather%20than%20travel%20time%20and%20therefore%20do%20not%0A%20%20%20%20enter%20the%20first%20term.%20The%20small%20quadratic%20penalty%20selects%20the%20least%20costly%0A%20%20%20%20toll%20among%20policies%20with%20similar%20network%20performance.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20q%20%3D%206.0%0A%20%20%20%20b%20%3D%20np.array(%5B0.0%2C%205.0%2C%205.0%2C%200.0%2C%200.0%5D)%0A%20%20%20%20a%20%3D%20np.array(%5B1.0%2C%200.01%2C%200.01%2C%201.0%2C%200.01%5D)%0A%20%20%20%20H%20%3D%20np.array(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B1.0%2C%200.0%2C%201.0%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B0.0%2C%201.0%2C%200.0%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B1.0%2C%200.0%2C%200.0%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B0.0%2C%201.0%2C%201.0%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B0.0%2C%200.0%2C%201.0%5D%2C%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20)%0A%20%20%20%20rho%20%3D%200.1%0A%20%20%20%20return%20H%2C%20a%2C%20b%2C%20q%2C%20rho%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Synthetic%20network%0A%0A%20%20%20%20We%20set%20%24q%3D6%24%20and%20use%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20b%3D(0%2C5%2C5%2C0%2C0)%2C%5Cqquad%0A%20%20%20%20a%3D(1%2C0.01%2C0.01%2C1%2C0.01)%2C%5Cqquad%20%5Crho%3D0.1.%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20The%20outer%20links%20%24OA%24%20and%20%24BD%24%20become%20congested%20quickly.%20The%20remaining%0A%20%20%20%20links%20approximate%20the%20constant-time%20links%20of%20the%20classical%20Braess%20network.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(BilevelProblem%2C%20H%2C%20LowerProblem%2C%20a%2C%20b%2C%20cp%2C%20q%2C%20rho)%3A%0A%20%20%20%20tau%20%3D%20cp.Variable(1%2C%20bounds%3D%5B0.0%2C%205.0%5D%2C%20name%3D%22tau%22)%0A%20%20%20%20x%20%3D%20cp.Variable(3%2C%20nonneg%3DTrue%2C%20name%3D%22path_flow%22)%0A%20%20%20%20f%20%3D%20H%20%40%20x%0A%0A%20%20%20%20equilibrium%20%3D%20LowerProblem(%0A%20%20%20%20%20%20%20%20cp.Minimize(0.5%20*%20a%20%40%20cp.square(f)%20%2B%20b%20%40%20f%20%2B%20tau%5B0%5D%20*%20x%5B2%5D)%2C%0A%20%20%20%20%20%20%20%20%5Bcp.sum(x)%20%3D%3D%20q%5D%2C%0A%20%20%20%20%20%20%20%20parameters%3D%5Btau%5D%2C%0A%20%20%20%20)%0A%20%20%20%20network_travel_time%20%3D%20b%20%40%20f%20%2B%20a%20%40%20cp.square(f)%0A%20%20%20%20problem%20%3D%20BilevelProblem(%0A%20%20%20%20%20%20%20%20cp.Minimize(network_travel_time%20%2B%20rho%20*%20cp.sum_squares(tau))%2C%0A%20%20%20%20%20%20%20%20equilibrium%2C%0A%20%20%20%20)%0A%0A%20%20%20%20assert%20problem.is_dblp()%0A%20%20%20%20return%20problem%2C%20tau%2C%20x%0A%0A%0A%40app.cell%0Adef%20_(problem)%3A%0A%20%20%20%20epsilon_target%20%3D%201e-5%0A%20%20%20%20result%20%3D%20problem.solve(%0A%20%20%20%20%20%20%20%20epsilon_initial%3D1e-2%2C%0A%20%20%20%20%20%20%20%20epsilon_target%3Depsilon_target%2C%0A%20%20%20%20%20%20%20%20verbose%3DFalse%2C%0A%20%20%20%20)%0A%20%20%20%20diagnostics%20%3D%20problem.gap_diagnostics(result)%0A%20%20%20%20return%20diagnostics%2C%20epsilon_target%2C%20result%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Independent%20reference%20problems%0A%0A%20%20%20%20Three%20ordinary%20convex%20programs%20provide%20checks%20on%20the%20bilevel%20result.%20The%0A%20%20%20%20untolled%20reference%20fixes%20%24%5Ctau%3D0%24%20in%20the%20traveler%20problem.%20The%20fixed-toll%0A%20%20%20%20reference%20resolves%20that%20problem%20at%20the%20toll%20selected%20by%20BLVPY.%20Finally%2C%20the%0A%20%20%20%20system%20optimum%20minimizes%20%24%5Csum_e%20f_eT_e(f_e)%24%20directly%2C%20as%20if%20a%20central%0A%20%20%20%20controller%20could%20assign%20routes.%0A%0A%20%20%20%20The%20untolled%20equilibrium%20is%20not%20system%20optimal%3A%20individual%20travelers%20see%0A%20%20%20%20their%20own%20travel%20time%20but%20not%20the%20congestion%20delay%20they%20impose%20on%20others.%0A%20%20%20%20The%20central%20link%20magnifies%20this%20difference%20(i.e.%2C%20the%20Braess%20effect).%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(H%2C%20a%2C%20b%2C%20cp%2C%20np%2C%20q%2C%20tau)%3A%0A%20%20%20%20def%20_solve_equilibrium(_tau)%3A%0A%20%20%20%20%20%20%20%20_path_flow%20%3D%20cp.Variable(3%2C%20nonneg%3DTrue)%0A%20%20%20%20%20%20%20%20_link_flow%20%3D%20H%20%40%20_path_flow%0A%20%20%20%20%20%20%20%20_problem%20%3D%20cp.Problem(%0A%20%20%20%20%20%20%20%20%20%20%20%20cp.Minimize(0.5%20*%20a%20%40%20cp.square(_link_flow)%20%2B%20b%20%40%20_link_flow%20%2B%20_tau%20*%20_path_flow%5B2%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%5Bcp.sum(_path_flow)%20%3D%3D%20q%5D%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20_problem.solve(%0A%20%20%20%20%20%20%20%20%20%20%20%20solver%3Dcp.CLARABEL%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20tol_gap_abs%3D1e-11%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20tol_gap_rel%3D1e-11%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20tol_feas%3D1e-11%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20assert%20_problem.status%20%3D%3D%20cp.OPTIMAL%0A%20%20%20%20%20%20%20%20return%20np.array(_path_flow.value%2C%20copy%3DTrue)%0A%0A%20%20%20%20untolled_path_flow%20%3D%20_solve_equilibrium(0.0)%0A%20%20%20%20fixed_toll_path_flow%20%3D%20_solve_equilibrium(float(tau.value%5B0%5D))%0A%0A%20%20%20%20system_path_variable%20%3D%20cp.Variable(3%2C%20nonneg%3DTrue)%0A%20%20%20%20system_link_expression%20%3D%20H%20%40%20system_path_variable%0A%20%20%20%20system_problem%20%3D%20cp.Problem(%0A%20%20%20%20%20%20%20%20cp.Minimize(b%20%40%20system_link_expression%20%2B%20a%20%40%20cp.square(system_link_expression))%2C%0A%20%20%20%20%20%20%20%20%5Bcp.sum(system_path_variable)%20%3D%3D%20q%5D%2C%0A%20%20%20%20)%0A%20%20%20%20system_problem.solve(%0A%20%20%20%20%20%20%20%20solver%3Dcp.CLARABEL%2C%0A%20%20%20%20%20%20%20%20tol_gap_abs%3D1e-11%2C%0A%20%20%20%20%20%20%20%20tol_gap_rel%3D1e-11%2C%0A%20%20%20%20%20%20%20%20tol_feas%3D1e-11%2C%0A%20%20%20%20)%0A%20%20%20%20assert%20system_problem.status%20%3D%3D%20cp.OPTIMAL%0A%20%20%20%20system_path_flow%20%3D%20np.array(system_path_variable.value%2C%20copy%3DTrue)%0A%0A%20%20%20%20untolled_link_flow%20%3D%20H%20%40%20untolled_path_flow%0A%20%20%20%20fixed_toll_link_flow%20%3D%20H%20%40%20fixed_toll_path_flow%0A%20%20%20%20system_link_flow%20%3D%20H%20%40%20system_path_flow%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20fixed_toll_link_flow%2C%0A%20%20%20%20%20%20%20%20fixed_toll_path_flow%2C%0A%20%20%20%20%20%20%20%20system_link_flow%2C%0A%20%20%20%20%20%20%20%20system_path_flow%2C%0A%20%20%20%20%20%20%20%20untolled_link_flow%2C%0A%20%20%20%20%20%20%20%20untolled_path_flow%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20H%2C%0A%20%20%20%20a%2C%0A%20%20%20%20b%2C%0A%20%20%20%20diagnostics%2C%0A%20%20%20%20epsilon_target%2C%0A%20%20%20%20fixed_toll_link_flow%2C%0A%20%20%20%20fixed_toll_path_flow%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20np%2C%0A%20%20%20%20q%2C%0A%20%20%20%20result%2C%0A%20%20%20%20system_link_flow%2C%0A%20%20%20%20system_path_flow%2C%0A%20%20%20%20tau%2C%0A%20%20%20%20untolled_link_flow%2C%0A%20%20%20%20untolled_path_flow%2C%0A%20%20%20%20x%2C%0A)%3A%0A%20%20%20%20def%20_network_time(_link_flow)%3A%0A%20%20%20%20%20%20%20%20return%20float(b%20%40%20_link_flow%20%2B%20a%20%40%20np.square(_link_flow))%0A%0A%20%20%20%20selected_tau%20%3D%20float(tau.value%5B0%5D)%0A%20%20%20%20optimized_path_flow%20%3D%20np.array(x.value%2C%20copy%3DTrue)%0A%20%20%20%20optimized_link_flow%20%3D%20H%20%40%20optimized_path_flow%0A%20%20%20%20untolled_time%20%3D%20_network_time(untolled_link_flow)%0A%20%20%20%20optimized_time%20%3D%20_network_time(optimized_link_flow)%0A%20%20%20%20fixed_toll_time%20%3D%20_network_time(fixed_toll_link_flow)%0A%20%20%20%20system_time%20%3D%20_network_time(system_link_flow)%0A%20%20%20%20improvement_percent%20%3D%20100.0%20*%20(untolled_time%20-%20optimized_time)%20%2F%20untolled_time%0A%0A%20%20%20%20assert%20result.succeeded%2C%20result.message%0A%20%20%20%20assert%20np.isfinite(result.objective)%0A%20%20%20%20assert%20result.final_epsilon%20%3C%3D%20epsilon_target%0A%20%20%20%20assert%20result.residuals.max_violation%20%3C%3D%201e-6%0A%20%20%20%20assert%20abs(diagnostics.source_gap)%20%3C%3D%20epsilon_target%0A%20%20%20%20assert%20-1e-8%20%3C%3D%20selected_tau%20%3C%3D%205.0%20%2B%201e-8%0A%20%20%20%20assert%20np.min(optimized_path_flow)%20%3E%3D%20-1e-8%0A%20%20%20%20assert%20abs(np.sum(optimized_path_flow)%20-%20q)%20%3C%3D%201e-7%0A%20%20%20%20assert%20np.allclose(optimized_link_flow%2C%20H%20%40%20optimized_path_flow%2C%20atol%3D1e-8)%0A%20%20%20%20assert%20np.allclose(%0A%20%20%20%20%20%20%20%20fixed_toll_path_flow%2C%0A%20%20%20%20%20%20%20%20optimized_path_flow%2C%0A%20%20%20%20%20%20%20%20atol%3D1e-2%2C%0A%20%20%20%20)%0A%20%20%20%20assert%20np.allclose(%0A%20%20%20%20%20%20%20%20fixed_toll_link_flow%2C%0A%20%20%20%20%20%20%20%20optimized_link_flow%2C%0A%20%20%20%20%20%20%20%20atol%3D1e-2%2C%0A%20%20%20%20)%0A%20%20%20%20assert%20abs(fixed_toll_time%20-%20optimized_time)%20%3C%3D%201e-2%0A%20%20%20%20assert%20optimized_time%20%3C%20untolled_time%20-%201.0%0A%20%20%20%20assert%20optimized_time%20%3E%3D%20system_time%20-%201e-5%0A%0A%20%20%20%20mo.md(rf%22%22%22%0A%20%20%20%20%23%23%20Result%0A%0A%20%20%20%20%7C%20quantity%20%7C%20value%20%7C%0A%20%20%20%20%7C%20---%20%7C%20---%3A%20%7C%0A%20%20%20%20%7C%20status%20%7C%20%60%7Bresult.status%7D%60%20%7C%0A%20%20%20%20%7C%20selected%20toll%20%24%5Ctau%5E%5Cstar%24%20%7C%20%7Bselected_tau%3A.6f%7D%20%7C%0A%20%20%20%20%7C%20untolled%20path%20flow%20%24x%24%20%7C%20%7Bnp.array2string(untolled_path_flow%2C%20precision%3D3)%7D%20%7C%0A%20%20%20%20%7C%20optimized%20path%20flow%20%24x%5E%5Cstar%24%20%7C%20%7Bnp.array2string(optimized_path_flow%2C%20precision%3D3)%7D%20%7C%0A%20%20%20%20%7C%20system-optimal%20path%20flow%20%7C%20%7Bnp.array2string(system_path_flow%2C%20precision%3D3)%7D%20%7C%0A%20%20%20%20%7C%20untolled%20network%20travel%20time%20%7C%20%7Buntolled_time%3A.6f%7D%20%7C%0A%20%20%20%20%7C%20optimized%20network%20travel%20time%20%7C%20%7Boptimized_time%3A.6f%7D%20%7C%0A%20%20%20%20%7C%20system-optimal%20network%20travel%20time%20%7C%20%7Bsystem_time%3A.6f%7D%20%7C%0A%20%20%20%20%7C%20travel-time%20improvement%20%7C%20%7Bimprovement_percent%3A.2f%7D%25%20%7C%0A%20%20%20%20%7C%20upper%20objective%20%7C%20%7Bfloat(result.objective)%3A.6f%7D%20%7C%0A%20%20%20%20%7C%20final%20epsilon%20%7C%20%7Bresult.final_epsilon%3A.3e%7D%20%7C%0A%20%20%20%20%7C%20maximum%20lifted%20residual%20%7C%20%7Bresult.residuals.max_violation%3A.3e%7D%20%7C%0A%20%20%20%20%7C%20complementarity%20%7C%20%7Bresult.complementarity%3A.3e%7D%20%7C%0A%20%20%20%20%7C%20signed%20source%20gap%20%7C%20%7Bdiagnostics.source_gap%3A.3e%7D%20%7C%0A%0A%20%20%20%20With%20no%20toll%2C%20approximately%20%243.94%24%20flow%20units%20use%20the%20central%20path%20%24OABD%24%2C%0A%20%20%20%20raising%20network%20travel%20time%20to%20%7Buntolled_time%3A.2f%7D.%20The%20selected%20toll%0A%20%20%20%20%24%5Ctau%5E%5Cstar%3D%7Bselected_tau%3A.2f%7D%24%20removes%20almost%20all%20flow%20from%20%24AB%24%20and%20divides%0A%20%20%20%20demand%20between%20%24OAD%24%20and%20%24OBD%24.%20Network%20travel%20time%20falls%20by%0A%20%20%20%20%7Bimprovement_percent%3A.1f%7D%25%20to%20%7Boptimized_time%3A.2f%7D%2C%20essentially%20matching%0A%20%20%20%20the%20direct%20system%20optimum.%20The%20fixed-toll%20reference%20independently%0A%20%20%20%20reproduces%20this%20response.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%20optimized_link_flow%2C%20optimized_path_flow%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Policy%20and%20outcome%20comparison%0A%0A%20%20%20%20The%20left%20panels%20compare%20the%20untolled%20and%20optimized%20networks.%20Arrow%20width%0A%20%20%20%20represents%20edge%20flow%2C%20and%20each%20edge%20is%20labeled%20with%20its%20numerical%20flow.%0A%20%20%20%20The%20central%20edge%20%24AB%24%20is%20highlighted%20because%20it%20is%20the%20tolled%20link.%0A%0A%20%20%20%20The%20right%20panel%20shows%20every%20feasible%20path-flow%20allocation%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20x_1%2Bx_2%2Bx_3%3Dq%2C%5Cqquad%20x%5Csucceq0%2C%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20and%20contours%20report%20its%20total%20network%20travel%20time.%20The%20vertices%20assign%20all%0A%20%20%20%20demand%20to%20one%20path.%20The%20markers%20locate%20the%20untolled%20equilibrium%2C%20optimized%0A%20%20%20%20equilibrium%2C%20and%20system%20optimum%20in%20the%20complete%20feasible%20set.%20The%20latter%0A%20%20%20%20two%20lie%20together%20at%20the%20minimum%2C%20whereas%20the%20untolled%20equilibrium%20uses%20the%0A%20%20%20%20central%20path%20heavily%20and%20has%20greater%20total%20travel%20time.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(np%2C%20optimized_link_flow%2C%20plt%2C%20untolled_link_flow)%3A%0A%20%20%20%20node_positions%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%22O%22%3A%20np.array(%5B0.0%2C%200.0%5D)%2C%0A%20%20%20%20%20%20%20%20%22A%22%3A%20np.array(%5B0.5%2C%200.42%5D)%2C%0A%20%20%20%20%20%20%20%20%22B%22%3A%20np.array(%5B0.5%2C%20-0.42%5D)%2C%0A%20%20%20%20%20%20%20%20%22D%22%3A%20np.array(%5B1.0%2C%200.0%5D)%2C%0A%20%20%20%20%7D%0A%20%20%20%20edge_nodes%20%3D%20((%22O%22%2C%20%22A%22)%2C%20(%22O%22%2C%20%22B%22)%2C%20(%22A%22%2C%20%22D%22)%2C%20(%22B%22%2C%20%22D%22)%2C%20(%22A%22%2C%20%22B%22))%0A%20%20%20%20label_offsets%20%3D%20(%0A%20%20%20%20%20%20%20%20np.array(%5B-0.03%2C%200.08%5D)%2C%0A%20%20%20%20%20%20%20%20np.array(%5B-0.03%2C%20-0.08%5D)%2C%0A%20%20%20%20%20%20%20%20np.array(%5B0.03%2C%200.08%5D)%2C%0A%20%20%20%20%20%20%20%20np.array(%5B0.03%2C%20-0.08%5D)%2C%0A%20%20%20%20%20%20%20%20np.array(%5B0.08%2C%200.0%5D)%2C%0A%20%20%20%20)%0A%0A%20%20%20%20def%20_draw_network(_axis%2C%20_flows%2C%20_title)%3A%0A%20%20%20%20%20%20%20%20for%20_index%2C%20((_tail%2C%20_head)%2C%20_label_offset)%20in%20enumerate(zip(edge_nodes%2C%20label_offsets))%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_start%20%3D%20node_positions%5B_tail%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20_end%20%3D%20node_positions%5B_head%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20_is_central%20%3D%20_index%20%3D%3D%204%0A%20%20%20%20%20%20%20%20%20%20%20%20_axis.annotate(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xy%3D_end%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xytext%3D_start%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arrowprops%3D%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22arrowstyle%22%3A%20%22-%7C%3E%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22color%22%3A%20%22C3%22%20if%20_is_central%20else%20%220.35%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22linewidth%22%3A%200.9%20%2B%200.55%20*%20_flows%5B_index%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22mutation_scale%22%3A%2010%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22shrinkA%22%3A%209%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22shrinkB%22%3A%209%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20zorder%3D2%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20_midpoint%20%3D%200.5%20*%20(_start%20%2B%20_end)%20%2B%20_label_offset%0A%20%20%20%20%20%20%20%20%20%20%20%20_axis.text(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20*_midpoint%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20rf%22%24%7B_flows%5B_index%5D%3A.2f%7D%24%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20va%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D10%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20for%20_node%2C%20_position%20in%20node_positions.items()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_axis.scatter(*_position%2C%20s%3D55%2C%20color%3D%22black%22%2C%20zorder%3D4)%0A%20%20%20%20%20%20%20%20%20%20%20%20_axis.text(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_position%5B0%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_position%5B1%5D%20%2B%20(0.09%20if%20_node%20in%20%7B%22A%22%2C%20%22D%22%7D%20else%20-0.09)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20rf%22%24%7B_node%7D%24%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20va%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D10%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20_axis.set(%0A%20%20%20%20%20%20%20%20%20%20%20%20xlim%3D(-0.08%2C%201.08)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20ylim%3D(-0.62%2C%200.62)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20aspect%3D%22equal%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20_axis.set_title(_title%2C%20fontsize%3D15%2C%20pad%3D0)%0A%20%20%20%20%20%20%20%20_axis.axis(%22off%22)%0A%0A%20%20%20%20def%20make_network_figure()%3A%0A%20%20%20%20%20%20%20%20_figure%20%3D%20plt.figure(figsize%3D(7.5%2C%205)%2C%20layout%3D%22constrained%22)%0A%20%20%20%20%20%20%20%20_grid%20%3D%20_figure.add_gridspec(2%2C%202%2C%20width_ratios%3D%5B1%2C%201.5%5D)%0A%20%20%20%20%20%20%20%20_untolled_axis%20%3D%20_figure.add_subplot(_grid%5B0%2C%200%5D)%0A%20%20%20%20%20%20%20%20_optimized_axis%20%3D%20_figure.add_subplot(_grid%5B1%2C%200%5D)%0A%20%20%20%20%20%20%20%20_outcome_axis%20%3D%20_figure.add_subplot(_grid%5B%3A%2C%201%5D)%0A%0A%20%20%20%20%20%20%20%20_draw_network(_untolled_axis%2C%20untolled_link_flow%2C%20r%22%24%5Ctau%3D0%24%22)%0A%20%20%20%20%20%20%20%20_draw_network(%0A%20%20%20%20%20%20%20%20%20%20%20%20_optimized_axis%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20optimized_link_flow%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20r%22%24%5Ctau%3D%5Ctau%5E%5Cstar%24%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20return%20_figure%2C%20_outcome_axis%0A%0A%20%20%20%20return%20(make_network_figure%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20H%2C%0A%20%20%20%20Path%2C%0A%20%20%20%20a%2C%0A%20%20%20%20b%2C%0A%20%20%20%20make_network_figure%2C%0A%20%20%20%20np%2C%0A%20%20%20%20optimized_path_flow%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20q%2C%0A%20%20%20%20system_path_flow%2C%0A%20%20%20%20untolled_path_flow%2C%0A)%3A%0A%20%20%20%20simplex_figure%2C%20simplex_axis%20%3D%20make_network_figure()%0A%0A%20%20%20%20simplex_resolution%20%3D%2040%0A%20%20%20%20simplex_path_flow%20%3D%20%5B%5D%0A%20%20%20%20for%20_index_1%20in%20range(simplex_resolution%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20for%20_index_2%20in%20range(simplex_resolution%20%2B%201%20-%20_index_1)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_x_1%20%3D%20q%20*%20_index_1%20%2F%20simplex_resolution%0A%20%20%20%20%20%20%20%20%20%20%20%20_x_2%20%3D%20q%20*%20_index_2%20%2F%20simplex_resolution%0A%20%20%20%20%20%20%20%20%20%20%20%20_x_3%20%3D%20q%20-%20_x_1%20-%20_x_2%0A%20%20%20%20%20%20%20%20%20%20%20%20simplex_path_flow.append((_x_1%2C%20_x_2%2C%20_x_3))%0A%20%20%20%20simplex_path_flow%20%3D%20np.asarray(simplex_path_flow)%0A%0A%20%20%20%20simplex_vertices%20%3D%20np.array(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B0.0%2C%200.0%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B1.0%2C%200.0%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B0.5%2C%20np.sqrt(3.0)%20%2F%202.0%5D%2C%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20)%0A%20%20%20%20simplex_coordinates%20%3D%20(simplex_path_flow%20%2F%20q)%20%40%20simplex_vertices%0A%20%20%20%20simplex_link_flow%20%3D%20simplex_path_flow%20%40%20H.T%0A%20%20%20%20simplex_network_time%20%3D%20simplex_link_flow%20%40%20b%20%2B%20np.sum(%0A%20%20%20%20%20%20%20%20a%20*%20np.square(simplex_link_flow)%2C%0A%20%20%20%20%20%20%20%20axis%3D1%2C%0A%20%20%20%20)%0A%0A%20%20%20%20filled_contours%20%3D%20simplex_axis.tricontourf(%0A%20%20%20%20%20%20%20%20simplex_coordinates%5B%3A%2C%200%5D%2C%0A%20%20%20%20%20%20%20%20simplex_coordinates%5B%3A%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20simplex_network_time%2C%0A%20%20%20%20%20%20%20%20levels%3D10%2C%0A%20%20%20%20%20%20%20%20cmap%3D%22Greys%22%2C%0A%20%20%20%20%20%20%20%20alpha%3D0.75%2C%0A%20%20%20%20)%0A%20%20%20%20contour_lines%20%3D%20simplex_axis.tricontour(%0A%20%20%20%20%20%20%20%20simplex_coordinates%5B%3A%2C%200%5D%2C%0A%20%20%20%20%20%20%20%20simplex_coordinates%5B%3A%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20simplex_network_time%2C%0A%20%20%20%20%20%20%20%20levels%3Dfilled_contours.levels%2C%0A%20%20%20%20%20%20%20%20colors%3D%22black%22%2C%0A%20%20%20%20%20%20%20%20linewidths%3D0.45%2C%0A%20%20%20%20%20%20%20%20alpha%3D0.55%2C%0A%20%20%20%20)%0A%20%20%20%20simplex_axis.clabel(contour_lines%2C%20inline%3DTrue%2C%20fontsize%3D7%2C%20fmt%3D%22%25.0f%22)%0A%0A%20%20%20%20closed_vertices%20%3D%20np.vstack(%5Bsimplex_vertices%2C%20simplex_vertices%5B0%5D%5D)%0A%20%20%20%20simplex_axis.plot(%0A%20%20%20%20%20%20%20%20closed_vertices%5B%3A%2C%200%5D%2C%0A%20%20%20%20%20%20%20%20closed_vertices%5B%3A%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20color%3D%22black%22%2C%0A%20%20%20%20%20%20%20%20linewidth%3D1.0%2C%0A%20%20%20%20)%0A%0A%20%20%20%20def%20_simplex_position(_path_flow)%3A%0A%20%20%20%20%20%20%20%20return%20(_path_flow%20%2F%20q)%20%40%20simplex_vertices%0A%0A%20%20%20%20untolled_position%20%3D%20_simplex_position(untolled_path_flow)%0A%20%20%20%20optimized_position%20%3D%20_simplex_position(optimized_path_flow)%0A%20%20%20%20system_position%20%3D%20_simplex_position(system_path_flow)%0A%0A%20%20%20%20simplex_axis.scatter(%0A%20%20%20%20%20%20%20%20*untolled_position%2C%0A%20%20%20%20%20%20%20%20color%3D%22C0%22%2C%0A%20%20%20%20%20%20%20%20edgecolor%3D%22white%22%2C%0A%20%20%20%20%20%20%20%20linewidth%3D0.6%2C%0A%20%20%20%20%20%20%20%20marker%3D%22o%22%2C%0A%20%20%20%20%20%20%20%20s%3D55%2C%0A%20%20%20%20%20%20%20%20zorder%3D5%2C%0A%20%20%20%20%20%20%20%20label%3Dr%22%24x%5E%7B%5Ctau%3D0%7D%24%22%2C%0A%20%20%20%20)%0A%20%20%20%20simplex_axis.scatter(%0A%20%20%20%20%20%20%20%20*system_position%2C%0A%20%20%20%20%20%20%20%20facecolors%3D%22none%22%2C%0A%20%20%20%20%20%20%20%20edgecolors%3D%22C2%22%2C%0A%20%20%20%20%20%20%20%20marker%3D%22*%22%2C%0A%20%20%20%20%20%20%20%20linewidths%3D1.8%2C%0A%20%20%20%20%20%20%20%20s%3D210%2C%0A%20%20%20%20%20%20%20%20zorder%3D6%2C%0A%20%20%20%20%20%20%20%20label%3Dr%22%24x%5E%7B%5Crm%20sys%7D%24%22%2C%0A%20%20%20%20)%0A%20%20%20%20simplex_axis.scatter(%0A%20%20%20%20%20%20%20%20*optimized_position%2C%0A%20%20%20%20%20%20%20%20color%3D%22C3%22%2C%0A%20%20%20%20%20%20%20%20marker%3D%22X%22%2C%0A%20%20%20%20%20%20%20%20s%3D70%2C%0A%20%20%20%20%20%20%20%20zorder%3D7%2C%0A%20%20%20%20%20%20%20%20label%3Dr%22%24x%5E%7B%5Ctau%3D%5Ctau%5E%5Cstar%7D%24%22%2C%0A%20%20%20%20)%0A%0A%20%20%20%20simplex_axis.text(%0A%20%20%20%20%20%20%20%200%2C%0A%20%20%20%20%20%20%20%20-0.045%2C%0A%20%20%20%20%20%20%20%20r%22%24x_1%3Dq%24%22%2C%0A%20%20%20%20%20%20%20%20ha%3D%22right%22%2C%0A%20%20%20%20%20%20%20%20va%3D%22top%22%2C%0A%20%20%20%20%20%20%20%20fontsize%3D12%2C%0A%20%20%20%20)%0A%20%20%20%20simplex_axis.text(%0A%20%20%20%20%20%20%20%200%2C%0A%20%20%20%20%20%20%20%20-0.115%2C%0A%20%20%20%20%20%20%20%20r%22%24OAD%24%22%2C%0A%20%20%20%20%20%20%20%20ha%3D%22right%22%2C%0A%20%20%20%20%20%20%20%20va%3D%22top%22%2C%0A%20%20%20%20%20%20%20%20fontsize%3D12%2C%0A%20%20%20%20)%0A%20%20%20%20simplex_axis.text(%0A%20%20%20%20%20%20%20%201%2C%0A%20%20%20%20%20%20%20%20-0.045%2C%0A%20%20%20%20%20%20%20%20r%22%24x_2%3Dq%24%22%2C%0A%20%20%20%20%20%20%20%20ha%3D%22left%22%2C%0A%20%20%20%20%20%20%20%20va%3D%22top%22%2C%0A%20%20%20%20%20%20%20%20fontsize%3D12%2C%0A%20%20%20%20)%0A%20%20%20%20simplex_axis.text(%0A%20%20%20%20%20%20%20%201%2C%0A%20%20%20%20%20%20%20%20-0.115%2C%0A%20%20%20%20%20%20%20%20r%22%24OBD%24%22%2C%0A%20%20%20%20%20%20%20%20ha%3D%22left%22%2C%0A%20%20%20%20%20%20%20%20va%3D%22top%22%2C%0A%20%20%20%20%20%20%20%20fontsize%3D12%2C%0A%20%20%20%20)%0A%20%20%20%20simplex_axis.text(%0A%20%20%20%20%20%20%20%200.5%2C%0A%20%20%20%20%20%20%20%20simplex_vertices%5B2%2C%201%5D%20%2B%200.13%2C%0A%20%20%20%20%20%20%20%20r%22%24x_3%3Dq%24%22%2C%0A%20%20%20%20%20%20%20%20ha%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20va%3D%22bottom%22%2C%0A%20%20%20%20%20%20%20%20fontsize%3D12%2C%0A%20%20%20%20)%0A%20%20%20%20simplex_axis.text(%0A%20%20%20%20%20%20%20%200.5%2C%0A%20%20%20%20%20%20%20%20simplex_vertices%5B2%2C%201%5D%20%2B%200.055%2C%0A%20%20%20%20%20%20%20%20r%22%24OABD%24%22%2C%0A%20%20%20%20%20%20%20%20ha%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20va%3D%22bottom%22%2C%0A%20%20%20%20%20%20%20%20fontsize%3D12%2C%0A%20%20%20%20)%0A%20%20%20%20simplex_axis.set(%0A%20%20%20%20%20%20%20%20xlim%3D(-0.15%2C%201.15)%2C%0A%20%20%20%20%20%20%20%20ylim%3D(-0.18%2C%201.05)%2C%0A%20%20%20%20%20%20%20%20aspect%3D%22equal%22%2C%0A%20%20%20%20)%0A%20%20%20%20simplex_axis.axis(%22off%22)%0A%20%20%20%20simplex_axis.legend(%0A%20%20%20%20%20%20%20%20loc%3D%22upper%20right%22%2C%0A%20%20%20%20%20%20%20%20frameon%3DFalse%2C%0A%20%20%20%20%20%20%20%20fontsize%3D15%2C%0A%20%20%20%20)%0A%20%20%20%20simplex_colorbar%20%3D%20simplex_figure.colorbar(%0A%20%20%20%20%20%20%20%20filled_contours%2C%0A%20%20%20%20%20%20%20%20ax%3Dsimplex_axis%2C%0A%20%20%20%20%20%20%20%20fraction%3D0.04%2C%0A%20%20%20%20%20%20%20%20pad%3D0.03%2C%0A%20%20%20%20)%0A%20%20%20%20simplex_colorbar.set_label(r%22%24%5Csum_%7Be%5Cin%20E%7D%20f_eT_e(f_e)%24%22%2C%20fontsize%3D12)%0A%20%20%20%20simplex_colorbar.ax.tick_params(labelsize%3D12)%0A%0A%20%20%20%20figure_dir%20%3D%20Path(__file__).resolve().parent%20%2F%20%22figures%22%0A%20%20%20%20figure_dir.mkdir(parents%3DTrue%2C%20exist_ok%3DTrue)%0A%20%20%20%20figure_path%20%3D%20figure_dir%20%2F%20%22traffic_tolling.pdf%22%0A%20%20%20%20simplex_figure.savefig(figure_path%2C%20bbox_inches%3D%22tight%22)%0A%20%20%20%20plt.show()%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A
8b3c27b9a0ee594523e005bbe5a0a46e