network

import%20marimo%0A%0A__generated_with%20%3D%20%220.25.2%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20import%20statistics%0A%20%20%20%20import%20sys%0A%20%20%20%20import%20time%0A%20%20%20%20from%20pathlib%20import%20Path%0A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20from%20scipy.optimize%20import%20linprog%0A%0A%20%20%20%20start%20%3D%20Path(__file__).resolve().parent%20if%20%22__file__%22%20in%20globals()%20else%20Path.cwd().resolve()%0A%20%20%20%20for%20candidate%20in%20(start%2C%20*start.parents)%3A%0A%20%20%20%20%20%20%20%20if%20(candidate%20%2F%20%22fomtools%22).is_dir()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20repo_root%20%3D%20candidate%0A%20%20%20%20%20%20%20%20%20%20%20%20break%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20repo_root%20%3D%20start%0A%0A%20%20%20%20if%20str(repo_root)%20not%20in%20sys.path%3A%0A%20%20%20%20%20%20%20%20sys.path.insert(0%2C%20str(repo_root))%0A%0A%20%20%20%20examples_dir%20%3D%20repo_root%20%2F%20%22examples%22%0A%0A%20%20%20%20from%20docs.tutorials.helper_functions.network%20import%20(%0A%20%20%20%20%20%20%20%20make_network_data%2C%0A%20%20%20%20%20%20%20%20pdhg_step%2C%0A%20%20%20%20%20%20%20%20solve_pdhg_numpy%2C%0A%20%20%20%20)%0A%20%20%20%20from%20docs.tutorials.helper_functions.codegen_benchmarks%20import%20run_codegen_benchmark%0A%20%20%20%20from%20fomtools.codegen%20import%20CodegenConfig%2C%20TerminationSpec%0A%20%20%20%20import%20fomtools%20as%20ft%0A%0A%20%20%20%20timing_file%20%3D%20start%20%2F%20%22_recorded_timings.json%22%0A%0A%20%20%20%20np.set_printoptions(precision%3D5)%0A%20%20%20%20np.set_printoptions(suppress%3DTrue)%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20CodegenConfig%2C%0A%20%20%20%20%20%20%20%20TerminationSpec%2C%0A%20%20%20%20%20%20%20%20examples_dir%2C%0A%20%20%20%20%20%20%20%20ft%2C%0A%20%20%20%20%20%20%20%20linprog%2C%0A%20%20%20%20%20%20%20%20make_network_data%2C%0A%20%20%20%20%20%20%20%20mo%2C%0A%20%20%20%20%20%20%20%20np%2C%0A%20%20%20%20%20%20%20%20pdhg_step%2C%0A%20%20%20%20%20%20%20%20run_codegen_benchmark%2C%0A%20%20%20%20%20%20%20%20solve_pdhg_numpy%2C%0A%20%20%20%20%20%20%20%20statistics%2C%0A%20%20%20%20%20%20%20%20time%2C%0A%20%20%20%20%20%20%20%20timing_file%2C%0A%20%20%20%20)%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%20Network%20Flow%3A%20Python%20vs%20Codegen%0A%0A%20%20%20%20%5BBack%20to%20the%20code%20generation%20tutorials%5D(.%2F)%0A%0A%20%20%20%20In%20this%20tutorial%20we%20benchmark%20a%20small%20capacitated%20network-flow%20problem.%0A%20%20%20%20There%20are%20supply%20nodes%2C%20demand%20nodes%2C%20edge%20capacities%2C%20and%20linear%20edge%20costs.%0A%0A%20%20%20%20The%20solver%20uses%20a%20primal-dual%20projected%20update%3A%20each%20iteration%20clips%20the%20flow%20to%20the%20capacity%20box%2C%20projects%20one%20dual%20variable%20to%20be%20nonnegative%2C%20and%20updates%20the%20demand-side%20dual%20variable.%0A%20%20%20%20We%20compare%20a%20direct%20NumPy%20implementation%20with%20the%20verified%20generated%20C%20solver.%0A%20%20%20%20The%20problem%20construction%2C%20PDHG%20step%2C%20and%20NumPy%20reference%20solver%20are%20shared%20with%20the%20%5Bnetwork%20verification%20tutorial%5D(..%2Fverification%2Fnetwork.html).%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%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%20We%20generate%20a%20complete%20bipartite%20graph%20from%20supply%20nodes%20to%20demand%20nodes.%0A%20%20%20%20The%20starting%20flow%20is%20computed%20once%20by%20solving%20the%20linear%20program%20at%20the%20lower-demand%20endpoint.%0A%20%20%20%20Both%20implementations%20then%20run%20the%20same%20fixed%20iteration%20map.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(examples_dir%2C%20linprog%2C%20make_network_data%2C%20np)%3A%0A%20%20%20%20n_supply%2C%20n_demand%20%3D%203%2C%202%0A%20%20%20%20A_supply%2C%20A_demand%2C%20supply_capacity%2C%20edge_capacity%2C%20edge_cost%20%3D%20make_network_data(%0A%20%20%20%20%20%20%20%20n_supply%3Dn_supply%2C%20n_demand%3Dn_demand%2C%20data_seed%3D2%2C%20complete%3DTrue%0A%20%20%20%20)%0A%20%20%20%20n_edges%20%3D%20A_supply.shape%5B1%5D%0A%20%20%20%20x_lb%20%3D%20-7.0%20*%20np.ones(n_demand)%0A%20%20%20%20x_ub%20%3D%20-6.0%20*%20np.ones(n_demand)%0A%20%20%20%20x_mid%20%3D%200.5%20*%20(x_lb%20%2B%20x_ub)%0A%0A%20%20%20%20initial_flow%20%3D%20linprog(%0A%20%20%20%20%20%20%20%20c%3Dedge_cost%2C%0A%20%20%20%20%20%20%20%20A_ub%3DA_supply%2C%0A%20%20%20%20%20%20%20%20b_ub%3Dsupply_capacity%2C%0A%20%20%20%20%20%20%20%20A_eq%3DA_demand%2C%0A%20%20%20%20%20%20%20%20b_eq%3Dx_lb%2C%0A%20%20%20%20%20%20%20%20bounds%3D%5B(0.0%2C%20float(capacity))%20for%20capacity%20in%20edge_capacity%5D%2C%0A%20%20%20%20%20%20%20%20method%3D%22highs%22%2C%0A%20%20%20%20)%0A%20%20%20%20if%20not%20initial_flow.success%3A%0A%20%20%20%20%20%20%20%20raise%20RuntimeError(initial_flow.message)%0A%0A%20%20%20%20z0%20%3D%20initial_flow.x%0A%20%20%20%20v0%20%3D%20np.zeros(n_supply)%0A%20%20%20%20w0%20%3D%20np.zeros(n_demand)%0A%20%20%20%20L%20%3D%20float(np.linalg.norm(np.hstack(%5BA_supply.T%2C%20A_demand.T%5D)%2C%202))%0A%20%20%20%20eta%20%3D%200.5%20%2F%20L%0A%20%20%20%20K%20%3D%20200%0A%20%20%20%20out_dir%20%3D%20examples_dir%20%2F%20%22_codegen_speedups%22%20%2F%20%22network_codegen_speedup%22%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20A_demand%2C%0A%20%20%20%20%20%20%20%20A_supply%2C%0A%20%20%20%20%20%20%20%20K%2C%0A%20%20%20%20%20%20%20%20edge_capacity%2C%0A%20%20%20%20%20%20%20%20edge_cost%2C%0A%20%20%20%20%20%20%20%20eta%2C%0A%20%20%20%20%20%20%20%20n_demand%2C%0A%20%20%20%20%20%20%20%20n_edges%2C%0A%20%20%20%20%20%20%20%20n_supply%2C%0A%20%20%20%20%20%20%20%20out_dir%2C%0A%20%20%20%20%20%20%20%20supply_capacity%2C%0A%20%20%20%20%20%20%20%20v0%2C%0A%20%20%20%20%20%20%20%20w0%2C%0A%20%20%20%20%20%20%20%20x_lb%2C%0A%20%20%20%20%20%20%20%20x_mid%2C%0A%20%20%20%20%20%20%20%20x_ub%2C%0A%20%20%20%20%20%20%20%20z0%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20A_demand%2C%0A%20%20%20%20A_supply%2C%0A%20%20%20%20CodegenConfig%2C%0A%20%20%20%20K%2C%0A%20%20%20%20TerminationSpec%2C%0A%20%20%20%20edge_capacity%2C%0A%20%20%20%20edge_cost%2C%0A%20%20%20%20eta%2C%0A%20%20%20%20ft%2C%0A%20%20%20%20n_demand%2C%0A%20%20%20%20n_edges%2C%0A%20%20%20%20n_supply%2C%0A%20%20%20%20pdhg_step%2C%0A%20%20%20%20supply_capacity%2C%0A%20%20%20%20v0%2C%0A%20%20%20%20w0%2C%0A%20%20%20%20x_lb%2C%0A%20%20%20%20x_ub%2C%0A%20%20%20%20z0%2C%0A)%3A%0A%20%20%20%20verifier%20%3D%20ft.Verifier(%0A%20%20%20%20%20%20%20%20method%3D%22mip%22%2C%0A%20%20%20%20%20%20%20%20solver%3D%22highs%22%2C%0A%20%20%20%20%20%20%20%20obbt_solver%3DNone%2C%0A%20%20%20%20)%0A%0A%20%20%20%20x_param%20%3D%20verifier.parameter(n_demand%2C%20lb%3Dx_lb%2C%20ub%3Dx_ub)%0A%20%20%20%20z%20%3D%20verifier.iterate(n_edges%2C%20lb%3Dz0%2C%20ub%3Dz0)%0A%20%20%20%20v%20%3D%20verifier.iterate(n_supply%2C%20lb%3Dv0%2C%20ub%3Dv0)%0A%20%20%20%20w%20%3D%20verifier.iterate(n_demand%2C%20lb%3Dw0%2C%20ub%3Dw0)%0A%20%20%20%20z_next%2C%20v_next%2C%20w_next%2C%20_%20%3D%20pdhg_step(%0A%20%20%20%20%20%20%20%20verifier%2C%0A%20%20%20%20%20%20%20%20A_supply%2C%0A%20%20%20%20%20%20%20%20A_demand%2C%0A%20%20%20%20%20%20%20%20eta%2C%0A%20%20%20%20%20%20%20%20z%2C%0A%20%20%20%20%20%20%20%20v%2C%0A%20%20%20%20%20%20%20%20w%2C%0A%20%20%20%20%20%20%20%20x_param%2C%0A%20%20%20%20%20%20%20%20edge_capacity%2C%0A%20%20%20%20%20%20%20%20edge_cost%2C%0A%20%20%20%20%20%20%20%20supply_capacity%2C%0A%20%20%20%20%20%20%20%20k%3D1%2C%0A%20%20%20%20%20%20%20%20momentum%3DFalse%2C%0A%20%20%20%20)%0A%0A%20%20%20%20config%20%3D%20CodegenConfig(%0A%20%20%20%20%20%20%20%20termination%3DTerminationSpec(max_iters%3DK)%2C%0A%20%20%20%20%20%20%20%20num_verify_samples%3D4%2C%0A%20%20%20%20)%0A%20%20%20%20next_state%20%3D%20%5Bz_next%2C%20v_next%2C%20w_next%5D%0A%20%20%20%20s_state%20%3D%20%5Bz%2C%20v%2C%20w%5D%0A%20%20%20%20params%20%3D%20%5Bx_param%5D%0A%20%20%20%20return%20config%2C%20next_state%2C%20params%2C%20s_state%2C%20verifier%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20A_demand%2C%0A%20%20%20%20A_supply%2C%0A%20%20%20%20K%2C%0A%20%20%20%20edge_capacity%2C%0A%20%20%20%20edge_cost%2C%0A%20%20%20%20eta%2C%0A%20%20%20%20solve_pdhg_numpy%2C%0A%20%20%20%20statistics%2C%0A%20%20%20%20supply_capacity%2C%0A%20%20%20%20time%2C%0A%20%20%20%20v0%2C%0A%20%20%20%20w0%2C%0A%20%20%20%20x_mid%2C%0A%20%20%20%20z0%2C%0A)%3A%0A%20%20%20%20def%20network_solve()%3A%0A%20%20%20%20%20%20%20%20return%20solve_pdhg_numpy(%0A%20%20%20%20%20%20%20%20%20%20%20%20A_supply%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20A_demand%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20eta%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20edge_capacity%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20edge_cost%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20supply_capacity%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20z0%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20v0%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20w0%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20x_mid%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20max_iters%3DK%2C%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20for%20_%20in%20range(3)%3A%0A%20%20%20%20%20%20%20%20network_solve()%0A%0A%20%20%20%20python_times%20%3D%20%5B%5D%0A%20%20%20%20for%20_%20in%20range(40)%3A%0A%20%20%20%20%20%20%20%20t0%20%3D%20time.perf_counter()%0A%20%20%20%20%20%20%20%20network_solve()%0A%20%20%20%20%20%20%20%20python_times.append((time.perf_counter()%20-%20t0)%20*%201.0e6)%0A%0A%20%20%20%20python_us%20%3D%20statistics.median(python_times)%0A%20%20%20%20return%20(python_us%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20config%2C%0A%20%20%20%20next_state%2C%0A%20%20%20%20out_dir%2C%0A%20%20%20%20params%2C%0A%20%20%20%20python_us%2C%0A%20%20%20%20run_codegen_benchmark%2C%0A%20%20%20%20s_state%2C%0A%20%20%20%20timing_file%2C%0A%20%20%20%20verifier%2C%0A)%3A%0A%20%20%20%20timings%20%3D%20run_codegen_benchmark(%0A%20%20%20%20%20%20%20%20config%3Dconfig%2C%0A%20%20%20%20%20%20%20%20example%3D%22network%22%2C%0A%20%20%20%20%20%20%20%20name%3D%22network_codegen_speedup%22%2C%0A%20%20%20%20%20%20%20%20next_state%3Dnext_state%2C%0A%20%20%20%20%20%20%20%20out_dir%3Dout_dir%2C%0A%20%20%20%20%20%20%20%20params%3Dparams%2C%0A%20%20%20%20%20%20%20%20python_us%3Dpython_us%2C%0A%20%20%20%20%20%20%20%20state%3Ds_state%2C%0A%20%20%20%20%20%20%20%20timing_file%3Dtiming_file%2C%0A%20%20%20%20%20%20%20%20verifier%3Dverifier%2C%0A%20%20%20%20)%0A%20%20%20%20return%20(timings%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(K%2C%20mo%2C%20out_dir%2C%20timings)%3A%0A%20%20%20%20if%20timings%5B%22live%22%5D%3A%0A%20%20%20%20%20%20%20%20_footer%20%3D%20f%22%22%22%0A%20%20%20%20Generated%20solver%20directory%3A%20%60%7Bout_dir%7D%60%0A%0A%20%20%20%20Generated%20solver%20source%3A%20%60%7Btimings%5B%22solver_path%22%5D%7D%60%0A%20%20%20%20%22%22%22%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_footer%20%3D%20%22%22%0A%20%20%20%20summary%20%3D%20mo.md(f%22%22%22%0A%20%20%20%20%23%23%20Timing%20summary%0A%0A%20%20%20%20One%20complete%20solve%20runs%20%60%7BK%7D%60%20iterations.%0A%0A%20%20%20%20%7C%20implementation%20%7C%20median%20%2F%20mean%20per%20solve%20%7C%0A%20%20%20%20%7C---%7C---%3A%7C%0A%20%20%20%20%7C%20direct%20NumPy%20Python%20%7C%20%60%7Btimings%5B%22python_us%22%5D%3A.3f%7D%20%C2%B5s%60%20%7C%0A%20%20%20%20%7C%20generated%20C%20after%20code%20generation%20%7C%20%60%7Btimings%5B%22codegen_us%22%5D%3A.3f%7D%20%C2%B5s%60%20%7C%0A%20%20%20%20%7C%20generated%20C%20after%20optimization%20iteration%20%7C%20%60%7Btimings%5B%22iteration_us%22%5D%3A.3f%7D%20%C2%B5s%60%20%7C%0A%0A%20%20%20%20The%20speedup%20from%20code%20generation%20is%20%60%7Btimings%5B%22codegen_speedup%22%5D%3A.1f%7Dx%60%2C%20while%20the%20speedup%20from%20the%20optimization%20iteration%20is%20%60%7Btimings%5B%22iteration_speedup%22%5D%3A.2f%7Dx%60%2C%20totaling%20a%20speedup%20of%20%60%7Btimings%5B%22total_speedup%22%5D%3A.1f%7Dx%60.%0A%20%20%20%20%7B_footer%7D%22%22%22%0A%20%20%20%20)%0A%20%20%20%20summary%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