09 tsp callbacks

This is a static, read-only snapshot — sliders and other controls will not respond. Back to notebook list · Run it yourself

%23%20%2F%2F%2F%20script%0A%23%20%5Btool.marimo.opengraph%5D%0A%23%20title%20%3D%20%22TSP%20with%20Callbacks%22%0A%23%20description%20%3D%20%22Solver%20Callbacks%20and%20Cut%20Generation%22%0A%23%20image%20%3D%20%22__marimo__%2Fthumbnail-tsp.svg%22%0A%23%20%2F%2F%2F%0A%0Aimport%20marimo%0A%0A__generated_with%20%3D%20%220.24.0%22%0Aapp%20%3D%20marimo.App()%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20xpress%20as%20xp%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20networkx%20as%20nx%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20import%20itertools%0A%20%20%20%20import%20time%0A%0A%20%20%20%20return%20itertools%2C%20mo%2C%20np%2C%20nx%2C%20plt%2C%20time%2C%20xp%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%20**Solving%20a%20TSP%20problem%20using%20callbacks**%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%20Solve%20an%20instance%20of%20the%20%5BTraveling%20Salesperson%20Problem%20(TSP)%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FTravelling_salesman_problem)%20with%20Xpress%20using%20callbacks%20and%20*NumPy*%20arrays.%0A%0A%20%20%20%20We%20compare%20three%20ways%20of%20eliminating%20subtours%20from%20the%20standard%20TSP%20formulation%3A%20adding%20every%20subtour%20elimination%20constraint%20upfront%2C%20the%20Miller-Tucker-Zemlin%20(MTZ)%20formulation%2C%20and%20a%20solver%20**callback**%20that%20adds%20only%20the%20subtour%20elimination%20cuts%20that%20are%20actually%20needed%20while%20the%20branch-and-bound%20runs.%0A%0A%20%20%20%20*This%20example%20requires%20a%20full%20license%20of%20the%20FICO%26reg%3B%20Xpress%20Optimizer%20to%20run%20the%20larger%20instances%20below.%20Click%20on%20%5Bthis%20link%5D(https%3A%2F%2Fwww.fico.com%2Fen%2Ffico-xpress-trial-and-licensing-options)%20for%20more%20information%20about%20trial%20and%20licensing%20options.*%0A%0A%20%20%20%20%26copy%3B%20Copyright%202025-2026%20Fair%20Isaac%20Corporation.%20The%20use%20of%20this%20example%20is%20subject%20to%20%5Blegal%20and%20license%20requirements%5D(https%3A%2F%2Fgithub.com%2Ffico-xpress%2Fpython-notebooks%23legal-and-license-requirements).%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%20%23%20Install%20the%20necessary%20packages%0A%20%20%20%20%23%20'%25pip%20install%20-q%20xpress%20networkx%20matplotlib'%20command%20supported%20automatically%20in%20marimo%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%20%23%23%20Problem%20description%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%20Binary%20variables%20%24use_%7Bij%7D%20%5Cin%20%5C%7B0%2C1%5C%7D%2C%20%5Cforall%20i%2Cj%20%5Cin%20%5Cmathcal%7BN%7D%24%20represent%20the%20decision%20of%20whether%20the%20tour%20uses%20the%20arc%20%24(i%2Cj)%24%20(i.e.%20if%20we%20go%20from%20city%20%24i%24%20to%20%24j%24)%20or%20not.%20An%20optimal%20tour%20can%20be%20found%20by%20solving%3A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cmin%20%5Csum_%7Bi%2Cj%20%5Cin%20%5Cmathcal%7BN%7D%7D%20dist_%7Bij%7D%20%5Ccdot%20use_%7Bij%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20subject%20to%3A%0A%0A%20%20%20%20*%20We%20have%20to%20enter%20and%20leave%20every%20city%2C%20and%20a%20city%20cannot%20be%20its%20own%20destination%3A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Csum_%7Bj%20%5Cin%20%5Cmathcal%7BN%7D%7D%20use_%7Bij%7D%20%3D%201%2C%20%5Cquad%20%5Cforall%20i%20%5Cin%20%5Cmathcal%7BN%7D%20%5C%5C%0A%20%20%20%20%5Csum_%7Bj%20%5Cin%20%5Cmathcal%7BN%7D%7D%20use_%7Bji%7D%20%3D%201%2C%20%5Cquad%20%5Cforall%20i%20%5Cin%20%5Cmathcal%7BN%7D%20%5C%5C%0A%20%20%20%20use_%7Bii%7D%20%3D%200%2C%20%5Cquad%20%5Cforall%20i%20%5Cin%20%5Cmathcal%7BN%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20where%20%24dist_%7Bij%7D%2C%20%5Cforall%20i%2Cj%20%5Cin%20%5Cmathcal%7BN%7D%24%20represents%20the%20distance%20(or%20cost)%20associated%20with%20traveling%20on%20an%20arc%20%24(i%2Cj)%24.%20These%20constraints%20alone%20allow%20**subtours**%3A%20several%20disjoint%20short%20cycles%20that%20together%20visit%20every%20city%2C%20instead%20of%20one%20single%20tour.%20We%20look%20at%20three%20ways%20of%20ruling%20subtours%20out%20below.%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%20%23%23%20Model%20parameters%0A%0A%20%20%20%20**You%20can%20adjust%20the%20parameters%20below%20to%20change%20the%20problem%20instance%20and%20re-solve%20each%20formulation%20automatically.**%0A%0A%20%20%20%20**Values%20of%2013%20cities%20or%20more%20require%20a%20full%20Xpress%20license%3A%20the%20naive%20(upfront%20constraints)%20formulation%20below%20already%20exceeds%20the%20Community%20license's%20combined%20rows-plus-columns%20limit%20of%205000%20at%20that%20size.%20Further%20down%2C%20we%20provide%20separate%20sliders%20for%20the%20formulations%20that%20scale%20well%20under%20a%20Community%20license.**%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20small_n_slider%20%3D%20mo.ui.slider(10%2C%2015%2C%20value%3D12%2C%20label%3D%22Number%20of%20cities%22%2C%20show_value%3DTrue)%0A%20%20%20%20seed_slider%20%3D%20mo.ui.slider(0%2C%2099%2C%20value%3D0%2C%20label%3D%22Random%20seed%20(each%20value%20gives%20a%20different%20instance)%22%2C%20show_value%3DTrue)%0A%20%20%20%20time_limit_slider%20%3D%20mo.ui.slider(5%2C%2060%2C%20value%3D20%2C%20step%3D5%2C%20label%3D%22Solver%20time%20limit%20in%20seconds%22%2C%20show_value%3DTrue)%0A%20%20%20%20mo.vstack(%5Bsmall_n_slider%2C%20seed_slider%2C%20time_limit_slider%5D)%0A%20%20%20%20return%20seed_slider%2C%20small_n_slider%2C%20time_limit_slider%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%20Data%20preparation%20and%20visualization%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%20random%20city%20coordinates%20and%20the%20resulting%20distance%20matrix%20for%20the%20naive%2FMTZ%20instance%20size%20chosen%20above%20(**Number%20of%20cities**).%20The%20callback%20demo%20further%20down%20generates%20its%20own%2C%20larger%20instance%20using%20the%20same%20seed.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo%2C%20np%2C%20seed_slider%2C%20small_n_slider)%3A%0A%20%20%20%20n_small%20%3D%20small_n_slider.value%0A%20%20%20%20CITIES_small%20%3D%20range(n_small)%0A%0A%20%20%20%20np.random.seed(seed_slider.value)%0A%20%20%20%20X_small%20%3D%20100%20*%20np.random.rand(n_small)%0A%20%20%20%20Y_small%20%3D%20100%20*%20np.random.rand(n_small)%0A%0A%20%20%20%20%23%20Compute%20distance%20matrix%0A%20%20%20%20dist_small%20%3D%20np.ceil(np.sqrt((X_small.reshape(n_small%2C%201)%20-%20X_small.reshape(1%2C%20n_small))%20**%202%20%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20(Y_small.reshape(n_small%2C%201)%20-%20Y_small.reshape(1%2C%20n_small))%20**%202))%0A%20%20%20%20mo.show_code()%0A%20%20%20%20return%20CITIES_small%2C%20X_small%2C%20Y_small%2C%20dist_small%2C%20n_small%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%20A%20small%20helper%20function%20draws%20a%20set%20of%20cities%20and%2C%20if%20given%2C%20the%20arcs%20used%20by%20a%20tour%20(highlighted%20in%20red%20if%20it%20contains%20a%20subtour%2C%20dictated%20by%20the%20%60subtour%60%20flag).%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(nx%2C%20plt)%3A%0A%20%20%20%20def%20plot_tour(X%2C%20Y%2C%20edges%2C%20title%2C%20subtour%3DFalse)%3A%0A%20%20%20%20%20%20%20%20fig%2C%20ax%20%3D%20plt.subplots(figsize%3D(8%2C%206)%2C%20dpi%3D100)%0A%0A%20%20%20%20%20%20%20%20xy%20%3D%20%7Bi%3A%20(X%5Bi%5D%2C%20Y%5Bi%5D)%20for%20i%20in%20range(len(X))%7D%0A%0A%20%20%20%20%20%20%20%20graph%20%3D%20nx.Graph()%0A%20%20%20%20%20%20%20%20graph.add_nodes_from(range(len(X)))%0A%20%20%20%20%20%20%20%20graph.add_edges_from(edges)%0A%0A%20%20%20%20%20%20%20%20edge_color%20%3D%20%22%23cc3333%22%20if%20subtour%20else%20%22%235555ff%22%0A%20%20%20%20%20%20%20%20nx.draw(graph%2C%20pos%3Dxy%2C%20node_size%3D250%2C%20with_labels%3DTrue%2C%20node_color%3D%22lightblue%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edge_color%3Dedge_color%2C%20ax%3Dax)%0A%20%20%20%20%20%20%20%20ax.set_title(title)%0A%20%20%20%20%20%20%20%20plt.tight_layout()%0A%20%20%20%20%20%20%20%20return%20fig%0A%0A%20%20%20%20return%20(plot_tour%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20time%2C%20xp)%3A%0A%20%20%20%20def%20optimize_safe(p)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Call%20p.optimize()%2C%20returning%20(error%2C%20solve_time).%20error%20is%20None%20on%20success.%0A%0A%20%20%20%20%20%20%20%20Catching%20xp.SolverError%20here%20means%20a%20Community-license%20size%20limit%20shows%20up%0A%20%20%20%20%20%20%20%20as%20a%20clear%2C%20copyable%20message%20in%20the%20cell%20output%20below%2C%20instead%20of%20marimo's%0A%20%20%20%20%20%20%20%20generic%20%22see%20console%22%20error%20popup%20-%20which%20is%20unhelpful%2C%20and%20there%20may%20be%20no%0A%20%20%20%20%20%20%20%20visible%20console%20at%20all%20when%20running%20locally%20with%20%60marimo%20run%60.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20start%20%3D%20time.time()%0A%20%20%20%20%20%20%20%20%20%20%20%20p.optimize()%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20None%2C%20time.time()%20-%20start%0A%20%20%20%20%20%20%20%20except%20xp.SolverError%20as%20e%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20e%2C%20None%0A%0A%20%20%20%20def%20license_error_callout(error%2C%20max_safe_n)%3A%0A%20%20%20%20%20%20%20%20return%20mo.callout(mo.md(f%22%22%22%0A%20%20%20%20%20%20%20%20**This%20instance%20could%20not%20be%20solved%3A**%0A%0A%20%20%20%20%20%20%20%20%60%60%60%0A%20%20%20%20%20%20%20%20%7Berror%7D%0A%20%20%20%20%20%20%20%20%60%60%60%0A%0A%20%20%20%20%20%20%20%20This%20is%20due%20to%20the%20Community%20license's%20combined%20rows-plus-columns%20limit%20of%205000%20being%20exceeded%20-%20see%20the%20license%20note%20next%20to%20the%20relevant%20slider%20above.%20Try%20a%20smaller%20**Number%20of%20cities**%20value%20(up%20to%20%7Bmax_safe_n%7D)%2C%20or%20use%20a%20full%20Xpress%20license%20to%20avoid%20this%20limit.%0A%20%20%20%20%20%20%20%20%22%22%22)%2C%20kind%3D%22danger%22)%0A%0A%20%20%20%20return%20license_error_callout%2C%20optimize_safe%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(X_small%2C%20Y_small%2C%20plot_tour)%3A%0A%20%20%20%20plot_tour(X_small%2C%20Y_small%2C%20%5B%5D%2C%20%22Cities%20(no%20tour%20yet)%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%20%23%23%20Standard%20formulation%20(subtours%20possible)%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%20first%20solve%20the%20standard%20formulation%20above%20with%20no%20subtour%20elimination%20at%20all.%20Note%20the%20use%20of%20%5Bproblem.addVariables%5D(https%3A%2F%2Fwww.fico.com%2Ffico-xpress-optimization%2Fdocs%2Flatest%2Fsolver%2Foptimizer%2Fpython%2FHTML%2Fproblem.addVariables.html)%20to%20create%20a%20square%20matrix%20of%20binary%20variables%2C%20which%20lets%20NumPy%20operations%20like%20%60.flatten()%60%20and%20slicing%20(%60use%5Bi%2C%3A%5D%60)%20work%20directly%20on%20the%20Xpress%20variables.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(CITIES_small%2C%20dist_small%2C%20mo%2C%20n_small%2C%20xp)%3A%0A%20%20%20%20%23%20Create%20problem%0A%20%20%20%20p_naive%20%3D%20xp.problem()%0A%0A%20%20%20%20%23%20Create%20variables%20as%20a%20square%20matrix%20of%20binary%20variables.%0A%20%20%20%20use_naive%20%3D%20p_naive.addVariables(n_small%2C%20n_small%2C%20vartype%3Dxp.binary%2C%20name%3D%22x%22)%0A%0A%20%20%20%20%23%20Degree%20constraints%0A%20%20%20%20p_naive.addConstraint(xp.Sum(use_naive%5Bi%2C%20%3A%5D)%20%3D%3D%201%20for%20i%20in%20CITIES_small)%0A%20%20%20%20p_naive.addConstraint(xp.Sum(use_naive%5B%3A%2C%20i%5D)%20%3D%3D%201%20for%20i%20in%20CITIES_small)%0A%0A%20%20%20%20%23%20Fix%20diagonals%20(i.e.%20city%20X%20-%3E%20city%20X)%20to%20zero%0A%20%20%20%20p_naive.addConstraint(use_naive%5Bi%2C%20i%5D%20%3D%3D%200%20for%20i%20in%20CITIES_small)%0A%0A%20%20%20%20%23%20Objective%20function%0A%20%20%20%20p_naive.setObjective(xp.Sum((dist_small%20*%20use_naive).flatten()))%0A%0A%20%20%20%20p_naive.controls.outputlog%20%3D%200%0A%20%20%20%20p_naive.optimize()%0A%0A%20%20%20%20sol_naive%20%3D%20p_naive.getSolution(use_naive)%0A%20%20%20%20edges_naive%20%3D%20%5B(i%2C%20j)%20for%20i%20in%20CITIES_small%20for%20j%20in%20CITIES_small%20if%20i%20!%3D%20j%20and%20sol_naive%5Bi%2C%20j%5D%20%3E%200.5%5D%0A%20%20%20%20mo.show_code()%0A%20%20%20%20return%20edges_naive%2C%20p_naive%2C%20use_naive%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%20The%20plot%20below%20shows%20the%20resulting%20tour.%20As%20you%20can%20see%2C%20the%20solution%20contains%20subtours%3A%20it%20is%20not%20yet%20a%20valid%20solution%20for%20the%20problem%2C%20since%20a%20valid%20tour%20must%20visit%20every%20city%20exactly%20once%20in%20a%20single%20loop.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(X_small%2C%20Y_small%2C%20edges_naive%2C%20plot_tour)%3A%0A%20%20%20%20plot_tour(X_small%2C%20Y_small%2C%20edges_naive%2C%20%22Standard%20formulation%3A%20subtours%20present%22%2C%20subtour%3DTrue)%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%20%23%23%20Adding%20subtour%20elimination%20constraints%20upfront%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%20A%20straightforward%20way%20to%20rule%20out%20subtours%20is%20to%20add%20a%20constraint%20for%20every%20possible%20subset%20%24%5Cmathcal%7BS%7D%20%5Csubsetneq%20%5Cmathcal%7BN%7D%24%20of%20size%20%24%5Cgeq%202%24%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Csum_%7Bi%2Cj%20%5Cin%20%5Cmathcal%7BS%7D%7D%20use_%7Bij%7D%20%5Cleq%20%7C%5Cmathcal%7BS%7D%7C%20-%201%20%5Cquad%20%5Cforall%20%5Cmathcal%7BS%7D%20%5Csubsetneq%20%5Cmathcal%7BN%7D%2C%5C%20%7C%5Cmathcal%7BS%7D%7C%20%5Cgeq%202%0A%20%20%20%20%24%24%0A%0A%20%20%20%20The%20number%20of%20such%20constraints%20grows%20exponentially%20with%20the%20number%20of%20cities%2C%20so%20this%20only%20scales%20to%20a%20handful%20of%20cities%20-%20which%20is%20why%20the%20**Number%20of%20cities**%20control%20above%20is%20capped%20at%2015%20for%20this%20comparison%20(see%20the%20license%20note%20next%20to%20that%20control).%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20CITIES_small%2C%0A%20%20%20%20itertools%2C%0A%20%20%20%20license_error_callout%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20optimize_safe%2C%0A%20%20%20%20p_naive%2C%0A%20%20%20%20time_limit_slider%2C%0A%20%20%20%20use_naive%2C%0A%20%20%20%20xp%2C%0A)%3A%0A%20%20%20%20%23%20Add%20every%20subtour%20elimination%20constraint%2C%20then%20re-solve.%0A%20%20%20%20p_naive.addConstraint(%0A%20%20%20%20%20%20%20%20xp.Sum(use_naive%5Bi%2C%20j%5D%20for%20i%20in%20subset%20for%20j%20in%20subset)%20%3C%3D%20len(subset)%20-%201%0A%20%20%20%20%20%20%20%20for%20L%20in%20range(2%2C%20len(CITIES_small))%0A%20%20%20%20%20%20%20%20for%20subset%20in%20itertools.combinations(CITIES_small%2C%20L)%0A%20%20%20%20)%0A%0A%20%20%20%20p_naive.controls.timelimit%20%3D%20time_limit_slider.value%0A%20%20%20%20%23%20optimize_safe()%20re-solves%20p_naive%2C%20catching%20a%20Community-license%20size%0A%20%20%20%20%23%20error%20so%20it%20renders%20as%20a%20clear%20message%20instead%20of%20crashing.%0A%20%20%20%20naive_error%2C%20naive_solve_time%20%3D%20optimize_safe(p_naive)%0A%0A%20%20%20%20if%20naive_error%20is%20None%3A%0A%20%20%20%20%20%20%20%20sol_naive_full%20%3D%20p_naive.getSolution(use_naive)%0A%20%20%20%20%20%20%20%20edges_naive_full%20%3D%20%5B(i%2C%20j)%20for%20i%20in%20CITIES_small%20for%20j%20in%20CITIES_small%20if%20i%20!%3D%20j%20and%20sol_naive_full%5Bi%2C%20j%5D%20%3E%200.5%5D%0A%20%20%20%20%20%20%20%20naive_obj%20%3D%20p_naive.attributes.objval%0A%20%20%20%20%20%20%20%20naive_callout%20%3D%20None%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20edges_naive_full%20%3D%20None%0A%20%20%20%20%20%20%20%20naive_obj%20%3D%20None%0A%20%20%20%20%20%20%20%20naive_callout%20%3D%20license_error_callout(naive_error%2C%2012)%0A%0A%20%20%20%20mo.show_code(naive_callout%2C%20position%3D%22above%22)%0A%20%20%20%20return%20edges_naive_full%2C%20naive_error%2C%20naive_obj%2C%20naive_solve_time%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20naive_error%2C%20naive_obj%2C%20naive_solve_time)%3A%0A%20%20%20%20if%20naive_error%20is%20None%3A%0A%20%20%20%20%20%20%20%20naive_result_md%20%3D%20mo.md(f%22%22%22%0A%20%20%20%20%20%20%20%20**Objective%20value%20with%20all%20subtour%20elimination%20constraints%20added%20upfront%3A**%20%7Bnaive_obj%3A.1f%7D%20%26nbsp%3B%26nbsp%3B%20**Solve%20time%3A**%20%7Bnaive_solve_time%3A.2f%7Ds%20(if%20the%20limit%20was%20hit%2C%20this%20may%20only%20be%20the%20best%20solution%20found%20so%20far%2C%20not%20a%20proven%20optimum).%0A%20%20%20%20%20%20%20%20%22%22%22)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20naive_result_md%20%3D%20None%0A%20%20%20%20naive_result_md%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(X_small%2C%20Y_small%2C%20edges_naive_full%2C%20plot_tour)%3A%0A%20%20%20%20naive_full_fig%20%3D%20plot_tour(X_small%2C%20Y_small%2C%20edges_naive_full%2C%20%22All%20subtour%20elimination%20constraints%20added%20upfront%22)%20if%20edges_naive_full%20is%20not%20None%20else%20None%0A%20%20%20%20naive_full_fig%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%20%23%23%20Miller-Tucker-Zemlin%20(MTZ)%20formulation%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%20The%20Miller%2C%20Tucker%2C%20Zemlin%20subtour%20elimination%20constraints%20instead%20introduce%20a%20new%20set%20of%20continuous%20variables%20%24step_i%24%20%3D%20the%20step%20at%20which%20node%20%24i%24%20is%20visited%2C%20%24%5Cforall%20i%20%5Cin%20%5C%7B2%2C...%2C%7C%5Cmathcal%7BN%7D%7C%5C%7D%24%2C%20and%20use%20them%20to%20forbid%20subtours%20with%20only%20%24(%7C%5Cmathcal%7BN%7D%7C-1)%5E2%24%20extra%20constraints%20-%20a%20polynomial%20number%2C%20instead%20of%20an%20exponential%20one%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20step_j%20%5Cgeq%20step_i%20%2B%201%20-%20(n-1)%20%5Ccdot%20(1%20-%20use_%7Bij%7D)%2C%20%5Cquad%20%5Cforall%20i%2Cj%20%5Cin%20%5C%7B2%2C..%2Cn%5C%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20with%20%24n%20%3D%20%7C%5Cmathcal%7BN%7D%7C%24.%20This%20scales%20much%20better%20than%20the%20previous%20approach%2C%20at%20the%20cost%20of%20a%20slightly%20less%20tight%20LP%20relaxation.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(CITIES_small%2C%20dist_small%2C%20mo%2C%20n_small%2C%20time%2C%20time_limit_slider%2C%20xp)%3A%0A%20%20%20%20%23%20Create%20problem%0A%20%20%20%20p_mtz%20%3D%20xp.problem()%0A%0A%20%20%20%20use_mtz%20%3D%20p_mtz.addVariables(n_small%2C%20n_small%2C%20vartype%3Dxp.binary%2C%20name%3D%22x%22)%0A%20%20%20%20step_mtz%20%3D%20p_mtz.addVariables(n_small%2C%20name%3D%22t%22)%0A%0A%20%20%20%20%23%20Degree%20constraints%0A%20%20%20%20p_mtz.addConstraint(xp.Sum(use_mtz%5Bi%2C%20%3A%5D)%20%3D%3D%201%20for%20i%20in%20CITIES_small)%0A%20%20%20%20p_mtz.addConstraint(xp.Sum(use_mtz%5B%3A%2C%20i%5D)%20%3D%3D%201%20for%20i%20in%20CITIES_small)%0A%0A%20%20%20%20%23%20Fix%20diagonals%20(i.e.%20city%20X%20-%3E%20city%20X)%20to%20zero%0A%20%20%20%20p_mtz.addConstraint(use_mtz%5Bi%2C%20i%5D%20%3D%3D%200%20for%20i%20in%20CITIES_small)%0A%0A%20%20%20%20%23%20Miller%2C%20Tucker%2C%20Zemlin%20subtour%20elimination%20constraints%0A%20%20%20%20p_mtz.addConstraint(%0A%20%20%20%20%20%20%20%20step_mtz%5Bj%5D%20%3E%3D%20step_mtz%5Bi%5D%20%2B%201%20-%20(n_small%20-%201)%20*%20(1%20-%20use_mtz%5Bi%2C%20j%5D)%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(1%2C%20n_small)%20for%20j%20in%20range(1%2C%20n_small)%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Objective%20function%0A%20%20%20%20p_mtz.setObjective(xp.Sum((dist_small%20*%20use_mtz).flatten()))%0A%0A%20%20%20%20p_mtz.controls.outputlog%20%3D%200%0A%20%20%20%20p_mtz.controls.timelimit%20%3D%20time_limit_slider.value%0A%20%20%20%20mtz_start%20%3D%20time.time()%0A%20%20%20%20p_mtz.optimize()%0A%20%20%20%20mtz_solve_time%20%3D%20time.time()%20-%20mtz_start%0A%0A%20%20%20%20sol_mtz%20%3D%20p_mtz.getSolution(use_mtz)%0A%20%20%20%20edges_mtz%20%3D%20%5B(i%2C%20j)%20for%20i%20in%20CITIES_small%20for%20j%20in%20CITIES_small%20if%20i%20!%3D%20j%20and%20sol_mtz%5Bi%2C%20j%5D%20%3E%200.5%5D%0A%20%20%20%20mtz_obj%20%3D%20p_mtz.attributes.objval%0A%20%20%20%20mo.show_code()%0A%20%20%20%20return%20edges_mtz%2C%20mtz_obj%2C%20mtz_solve_time%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20mtz_obj%2C%20mtz_solve_time%2C%20naive_error%2C%20naive_obj%2C%20naive_solve_time)%3A%0A%20%20%20%20if%20naive_error%20is%20None%3A%0A%20%20%20%20%20%20%20%20mtz_comparison_md%20%3D%20mo.md(f%22%22%22%0A%20%20%20%20%20%20%20%20**Objective%20value%20with%20the%20MTZ%20formulation%3A**%20%7Bmtz_obj%3A.1f%7D%20%26nbsp%3B%26nbsp%3B%20**Solve%20time%3A**%20%7Bmtz_solve_time%3A.2f%7Ds%20(compare%20with%20**%7Bnaive_obj%3A.1f%7D**%20in%20**%7Bnaive_solve_time%3A.2f%7Ds**%20from%20the%20upfront%20subtour%20elimination%20above%20-%20both%20formulations%20solve%20the%20same%20instance%20and%20should%20agree%20once%20neither%20one%20is%20cut%20short%20by%20the%20solver%20time%20limit).%0A%20%20%20%20%20%20%20%20%22%22%22)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20mtz_comparison_md%20%3D%20mo.md(f%22%22%22%0A%20%20%20%20%20%20%20%20**Objective%20value%20with%20the%20MTZ%20formulation%3A**%20%7Bmtz_obj%3A.1f%7D%20%26nbsp%3B%26nbsp%3B%20**Solve%20time%3A**%20%7Bmtz_solve_time%3A.2f%7Ds%20(no%20comparison%20available%20since%20the%20upfront%20subtour%20elimination%20above%20could%20not%20be%20solved%20-%20see%20the%20error%20above).%0A%20%20%20%20%20%20%20%20%22%22%22)%0A%20%20%20%20mtz_comparison_md%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(X_small%2C%20Y_small%2C%20edges_mtz%2C%20plot_tour)%3A%0A%20%20%20%20plot_tour(X_small%2C%20Y_small%2C%20edges_mtz%2C%20%22Miller-Tucker-Zemlin%20formulation%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%20%23%23%20MTZ%20at%20a%20larger%20scale%0A%0A%20%20%20%20Because%20MTZ%20only%20adds%20a%20polynomial%20number%20of%20constraints%2C%20it%20comfortably%20outgrows%20the%20**Number%20of%20cities**%20control%20above.%20The%20slider%20below%20lets%20you%20push%20the%20MTZ%20formulation%20on%20its%20own%2C%20independently%20of%20the%20naive%20comparison%2C%20using%20a%20fresh%20instance%20of%20the%20same%20size.%0A%0A%20%20%20%20**Values%20of%2050%20cities%20or%20more%20require%20a%20full%20Xpress%20license%3A%20at%20that%20point%20the%20model's%20rows%20plus%20columns%20exceeds%20the%20Community%20license's%20combined%20limit%20of%205000.**%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mtz_scale_n_slider%20%3D%20mo.ui.slider(15%2C%20100%2C%20value%3D30%2C%20step%3D1%2C%20label%3D%22Number%20of%20cities%20(MTZ%20formulation)%22%2C%20show_value%3DTrue)%0A%20%20%20%20mtz_scale_n_slider%0A%20%20%20%20return%20(mtz_scale_n_slider%2C)%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20license_error_callout%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20mtz_scale_n_slider%2C%0A%20%20%20%20np%2C%0A%20%20%20%20optimize_safe%2C%0A%20%20%20%20seed_slider%2C%0A%20%20%20%20xp%2C%0A)%3A%0A%20%20%20%20n_mtz_scale%20%3D%20mtz_scale_n_slider.value%0A%20%20%20%20CITIES_mtz_scale%20%3D%20range(n_mtz_scale)%0A%0A%20%20%20%20np.random.seed(seed_slider.value)%0A%20%20%20%20X_mtz_scale%20%3D%20100%20*%20np.random.rand(n_mtz_scale)%0A%20%20%20%20Y_mtz_scale%20%3D%20100%20*%20np.random.rand(n_mtz_scale)%0A%0A%20%20%20%20dist_mtz_scale%20%3D%20np.ceil(np.sqrt((X_mtz_scale.reshape(n_mtz_scale%2C%201)%20-%20X_mtz_scale.reshape(1%2C%20n_mtz_scale))%20**%202%20%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20(Y_mtz_scale.reshape(n_mtz_scale%2C%201)%20-%20Y_mtz_scale.reshape(1%2C%20n_mtz_scale))%20**%202))%0A%0A%20%20%20%20%23%20Create%20problem%0A%20%20%20%20p_mtz_scale%20%3D%20xp.problem()%0A%0A%20%20%20%20use_mtz_scale%20%3D%20p_mtz_scale.addVariables(n_mtz_scale%2C%20n_mtz_scale%2C%20vartype%3Dxp.binary%2C%20name%3D%22x%22)%0A%20%20%20%20step_mtz_scale%20%3D%20p_mtz_scale.addVariables(n_mtz_scale%2C%20name%3D%22t%22)%0A%0A%20%20%20%20%23%20Degree%20constraints%0A%20%20%20%20p_mtz_scale.addConstraint(xp.Sum(use_mtz_scale%5Bi%2C%20%3A%5D)%20%3D%3D%201%20for%20i%20in%20CITIES_mtz_scale)%0A%20%20%20%20p_mtz_scale.addConstraint(xp.Sum(use_mtz_scale%5B%3A%2C%20i%5D)%20%3D%3D%201%20for%20i%20in%20CITIES_mtz_scale)%0A%0A%20%20%20%20%23%20Fix%20diagonals%20(i.e.%20city%20X%20-%3E%20city%20X)%20to%20zero%0A%20%20%20%20p_mtz_scale.addConstraint(use_mtz_scale%5Bi%2C%20i%5D%20%3D%3D%200%20for%20i%20in%20CITIES_mtz_scale)%0A%0A%20%20%20%20%23%20Miller%2C%20Tucker%2C%20Zemlin%20subtour%20elimination%20constraints%0A%20%20%20%20p_mtz_scale.addConstraint(%0A%20%20%20%20%20%20%20%20step_mtz_scale%5Bj%5D%20%3E%3D%20step_mtz_scale%5Bi%5D%20%2B%201%20-%20(n_mtz_scale%20-%201)%20*%20(1%20-%20use_mtz_scale%5Bi%2C%20j%5D)%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(1%2C%20n_mtz_scale)%20for%20j%20in%20range(1%2C%20n_mtz_scale)%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Objective%20function%0A%20%20%20%20p_mtz_scale.setObjective(xp.Sum((dist_mtz_scale%20*%20use_mtz_scale).flatten()))%0A%0A%20%20%20%20p_mtz_scale.controls.outputlog%20%3D%200%0A%20%20%20%20%23%20optimize_safe()%20re-solves%20p_mtz_scale%2C%20catching%20a%20Community-license%20size%0A%20%20%20%20%23%20error%20so%20it%20renders%20as%20a%20clear%20message%20instead%20of%20crashing.%0A%20%20%20%20mtz_scale_error%2C%20mtz_scale_solve_time%20%3D%20optimize_safe(p_mtz_scale)%0A%0A%20%20%20%20if%20mtz_scale_error%20is%20None%3A%0A%20%20%20%20%20%20%20%20sol_mtz_scale%20%3D%20p_mtz_scale.getSolution(use_mtz_scale)%0A%20%20%20%20%20%20%20%20edges_mtz_scale%20%3D%20%5B(i%2C%20j)%20for%20i%20in%20CITIES_mtz_scale%20for%20j%20in%20CITIES_mtz_scale%20if%20i%20!%3D%20j%20and%20sol_mtz_scale%5Bi%2C%20j%5D%20%3E%200.5%5D%0A%20%20%20%20%20%20%20%20mtz_scale_obj%20%3D%20p_mtz_scale.attributes.objval%0A%20%20%20%20%20%20%20%20mtz_scale_callout%20%3D%20None%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20edges_mtz_scale%20%3D%20None%0A%20%20%20%20%20%20%20%20mtz_scale_obj%20%3D%20None%0A%20%20%20%20%20%20%20%20mtz_scale_callout%20%3D%20license_error_callout(mtz_scale_error%2C%2049)%0A%0A%20%20%20%20mo.show_code(mtz_scale_callout%2C%20position%3D%22above%22)%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20X_mtz_scale%2C%0A%20%20%20%20%20%20%20%20Y_mtz_scale%2C%0A%20%20%20%20%20%20%20%20edges_mtz_scale%2C%0A%20%20%20%20%20%20%20%20mtz_scale_obj%2C%0A%20%20%20%20%20%20%20%20mtz_scale_solve_time%2C%0A%20%20%20%20%20%20%20%20n_mtz_scale%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20mtz_scale_obj%2C%20mtz_scale_solve_time%2C%20n_mtz_scale)%3A%0A%20%20%20%20if%20mtz_scale_obj%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20mtz_scale_result_md%20%3D%20mo.md(f%22%22%22%0A%20%20%20%20%20%20%20%20**Objective%20value%20with%20the%20MTZ%20formulation%20(%7Bn_mtz_scale%7D%20cities)%3A**%20%7Bmtz_scale_obj%3A.1f%7D%20%26nbsp%3B%26nbsp%3B%20**Solve%20time%3A**%20%7Bmtz_scale_solve_time%3A.2f%7Ds.%0A%20%20%20%20%20%20%20%20%22%22%22)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20mtz_scale_result_md%20%3D%20None%0A%20%20%20%20mtz_scale_result_md%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(X_mtz_scale%2C%20Y_mtz_scale%2C%20edges_mtz_scale%2C%20n_mtz_scale%2C%20plot_tour)%3A%0A%20%20%20%20mtz_scale_fig%20%3D%20plot_tour(X_mtz_scale%2C%20Y_mtz_scale%2C%20edges_mtz_scale%2C%20f%22MTZ%20formulation%3A%20valid%20tour%20over%20%7Bn_mtz_scale%7D%20cities%22)%20if%20edges_mtz_scale%20is%20not%20None%20else%20None%0A%20%20%20%20mtz_scale_fig%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%20%23%23%20Using%20callbacks%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%20Neither%20of%20the%20two%20formulations%20above%20scales%20well%3A%20the%20first%20one%20because%20of%20the%20exponential%20number%20of%20constraints%2C%20the%20second%20because%20a%20dense%20set%20of%20MTZ%20constraints%20slows%20down%20the%20LP%20relaxation%20as%20the%20number%20of%20cities%20grows.%0A%0A%20%20%20%20%5BSolver%20callbacks%5D(https%3A%2F%2Fwww.fico.com%2Ffico-xpress-optimization%2Fdocs%2Flatest%2Fsolver%2Foptimizer%2Fpython%2FHTML%2FchCallbacks.html)%20let%20us%20do%20much%20better%3A%20we%20drop%20subtour%20elimination%20entirely%20from%20the%20model%20and%20instead%20register%20a%20**pre-intsol%20callback**%20with%20%5Bproblem.addPreIntsolCallback%5D(https%3A%2F%2Fwww.fico.com%2Ffico-xpress-optimization%2Fdocs%2Flatest%2Fsolver%2Foptimizer%2Fpython%2FHTML%2Fproblem.addPreIntsolCallback.html).%20The%20Optimizer%20calls%20this%20function%20every%20time%20the%20branch-and-bound%20finds%20a%20new%20integer-feasible%20solution%2C%20*before*%20accepting%20it.%20Our%20callback%3A%0A%0A%20%20%20%20*%20reconstructs%20the%20tour%20from%20the%20current%20solution%20using%20%5Bproblem.getCallbackSolution%5D(https%3A%2F%2Fwww.fico.com%2Ffico-xpress-optimization%2Fdocs%2Flatest%2Fsolver%2Foptimizer%2Fpython%2FHTML%2Fproblem.getCallbackSolution.html)%2C%0A%20%20%20%20*%20checks%20whether%20it%20is%20a%20single%20tour%20or%20contains%20subtours%2C%0A%20%20%20%20*%20if%20it%20contains%20subtours%2C%20either%20rejects%20the%20solution%20outright%20(if%20it%20came%20from%20a%20heuristic)%20or%20adds%20a%20cut%20for%20each%20subtour%20found%20via%20%5Bproblem.presolveRow%5D(https%3A%2F%2Fwww.fico.com%2Ffico-xpress-optimization%2Fdocs%2Flatest%2Fsolver%2Foptimizer%2Fpython%2FHTML%2Fproblem.presolveRow.html)%20and%20%5Bproblem.addCuts%5D(https%3A%2F%2Fwww.fico.com%2Ffico-xpress-optimization%2Fdocs%2Flatest%2Fsolver%2Foptimizer%2Fpython%2FHTML%2Fproblem.addCuts.html)%20(if%20it%20came%20from%20the%20LP%20relaxation%20at%20the%20current%20node).%0A%0A%20%20%20%20By%20default%20the%20Xpress%20Optimizer%20serializes%20calls%20into%20this%20callback%20across%20its%20B%26B%20worker%20threads%20(the%20%60MUTEXCALLBACKS%60%20control%2C%20on%20by%20default)%2C%20so%20the%20callback%20code%20below%20does%20not%20need%20to%20worry%20about%20being%20called%20concurrently%20from%20multiple%20threads%20-%20it%20always%20runs%20one%20call%20at%20a%20time%2C%20even%20though%20%60problem.optimize()%60%20itself%20uses%20several%20threads%20internally.%0A%0A%20%20%20%20The%20callback%20function%20is%20defined%20fresh%20inside%20the%20solve%20cell%20below%2C%20so%20a%20new%20instance%20of%20the%20callback%20is%20created%20(closing%20over%20the%20current%20%60use%60%20variable%20array)%20every%20time%20this%20cell%20re-runs%20-%20e.g.%20when%20the%20**Number%20of%20cities**%20control%20below%20changes.%0A%0A%20%20%20%20**Because%20the%20callback%20formulation%20scales%20much%20further%20than%20the%20naive%20and%20MTZ%20formulations%20above%2C%20it%20gets%20its%20own%2C%20wider-range%20control%20here%20rather%20than%20sharing%20the%20one%20at%20the%20top%20of%20the%20notebook.**%0A%0A%20%20%20%20**Values%20of%2070%20cities%20or%20more%20require%20a%20full%20Xpress%20license%3A%20at%20that%20point%20the%20model's%20rows%20plus%20columns%20exceeds%20the%20Community%20license's%20combined%20limit%20of%205000.**%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20callback_n_slider%20%3D%20mo.ui.slider(10%2C%20150%2C%20value%3D60%2C%20step%3D1%2C%20label%3D%22Number%20of%20cities%20(callback%20formulation)%22%2C%20show_value%3DTrue)%0A%20%20%20%20callback_n_slider%0A%20%20%20%20return%20(callback_n_slider%2C)%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20callback_n_slider%2C%0A%20%20%20%20license_error_callout%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20np%2C%0A%20%20%20%20optimize_safe%2C%0A%20%20%20%20seed_slider%2C%0A%20%20%20%20xp%2C%0A)%3A%0A%20%20%20%20n_cb%20%3D%20callback_n_slider.value%0A%20%20%20%20CITIES_cb%20%3D%20range(n_cb)%0A%0A%20%20%20%20np.random.seed(seed_slider.value)%0A%20%20%20%20X_cb%20%3D%20100%20*%20np.random.rand(n_cb)%0A%20%20%20%20Y_cb%20%3D%20100%20*%20np.random.rand(n_cb)%0A%0A%20%20%20%20dist_cb%20%3D%20np.ceil(np.sqrt((X_cb.reshape(n_cb%2C%201)%20-%20X_cb.reshape(1%2C%20n_cb))%20**%202%20%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20(Y_cb.reshape(n_cb%2C%201)%20-%20Y_cb.reshape(1%2C%20n_cb))%20**%202))%0A%0A%20%20%20%20%23%20Create%20problem%0A%20%20%20%20p_cb%20%3D%20xp.problem()%0A%0A%20%20%20%20use_cb%20%3D%20p_cb.addVariables(n_cb%2C%20n_cb%2C%20vartype%3Dxp.binary%2C%20name%3D%22x%22)%0A%0A%20%20%20%20%23%20Degree%20constraints%20(no%20subtour%20elimination%20at%20all%20-%20the%20callback%20below%20handles%20that)%0A%20%20%20%20p_cb.addConstraint(xp.Sum(use_cb%5Bi%2C%20%3A%5D)%20%3D%3D%201%20for%20i%20in%20CITIES_cb)%0A%20%20%20%20p_cb.addConstraint(xp.Sum(use_cb%5B%3A%2C%20i%5D)%20%3D%3D%201%20for%20i%20in%20CITIES_cb)%0A%20%20%20%20p_cb.addConstraint(use_cb%5Bi%2C%20i%5D%20%3D%3D%200%20for%20i%20in%20CITIES_cb)%0A%0A%20%20%20%20p_cb.setObjective(xp.Sum((dist_cb%20*%20use_cb).flatten()))%0A%0A%20%20%20%20def%20cb_preintsol(prob%2C%20data%2C%20soltype%2C%20cutoff)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Callback%20for%20checking%20if%20a%20MIP%20solution%20is%20acceptable.%0A%0A%20%20%20%20%20%20%20%20prob%3A%20Xpress%20problem%20object%0A%20%20%20%20%20%20%20%20data%3A%20data%20object%20%3D%20number%20of%20cities%0A%20%20%20%20%20%20%20%20soltype%3A%20type%20of%20MIP%20solution%20found.%200%20-%20LP%20relaxation%20is%20integer%0A%20%20%20%20%20%20%20%20%20%20%20%20feasible%2C%201%20-%20MIP%20solution%20found%20by%20a%20heuristic%2C%202%20-%20MIP%20solution%0A%20%20%20%20%20%20%20%20%20%20%20%20provided%20by%20the%20user.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20n%20%3D%20data%0A%20%20%20%20%20%20%20%20xsol%20%3D%20np.array(prob.getCallbackSolution(use_cb)).reshape(n%2C%20n)%0A%20%20%20%20%20%20%20%20tour%20%3D%20np.argmax(xsol%2C%20axis%3D1)%20%20%23%20index%20of%20the%20max%20(non-zero)%20element%20in%20each%20row%20%3D%20next%20city%20in%20the%20tour%0A%0A%20%20%20%20%20%20%20%20i%20%3D%200%0A%20%20%20%20%20%20%20%20ncities%20%3D%201%0A%20%20%20%20%20%20%20%20while%20tour%5Bi%5D%20!%3D%200%20and%20ncities%20%3C%20n%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20ncities%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20i%20%3D%20tour%5Bi%5D%0A%0A%20%20%20%20%20%20%20%20reject%20%3D%20False%0A%20%20%20%20%20%20%20%20if%20ncities%20%3C%20n%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20The%20tour%20does%20not%20pass%20through%20all%20the%20cities%3A%20it%20contains%20subtours.%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20soltype%20!%3D%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20Solution%20came%20from%20a%20heuristic%20or%20the%20user%3A%20reject%20outright%2C%20no%20cut%20needed.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20reject%20%3D%20True%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20Solution%20came%20from%20the%20LP%20relaxation%20at%20the%20current%20node%3A%20add%20a%20cut%20per%20subtour%20instead.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20unchecked%20%3D%20np.zeros(n)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20nsubtour%20%3D%200%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cut_mstart%20%3D%20%5B0%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cut_ind%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cut_coe%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cut_rhs%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20nnz%20%3D%200%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ncuts%20%3D%200%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20while%20np.min(unchecked)%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20nsubtour%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20firstcity%20%3D%20np.argmin(unchecked)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20i%20%3D%20firstcity%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20while%20True%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20unchecked%5Bi%5D%20%3D%20nsubtour%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20i%20%3D%20tour%5Bi%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20i%20%3D%3D%20firstcity%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20S%20%3D%20cities%20in%20this%20subtour%2C%20compS%20%3D%20every%20other%20city%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20S%20%3D%20np.where(unchecked%20%3D%3D%20nsubtour)%5B0%5D.tolist()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20compS%20%3D%20np.where(unchecked%20!%3D%20nsubtour)%5B0%5D.tolist()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20indices%20%3D%20%5Bi%20*%20n%20%2B%20j%20for%20i%20in%20S%20for%20j%20in%20compS%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20mcolsp%2C%20dvalp%2C%20drhsp%2C%20p_status%20%3D%20prob.presolveRow(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20rowtype%3D%22G%22%2C%20origcolind%3Dindices%2C%20origrowcoef%3Dnp.ones(len(indices))%2C%20origrhs%3D1%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20nnz%20%2B%3D%20len(mcolsp)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ncuts%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cut_ind.extend(mcolsp)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cut_coe.extend(dvalp)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cut_rhs.append(drhsp)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cut_mstart.append(nnz)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20ncuts%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20prob.addCuts(cuttype%3D%5B0%5D%20*%20ncuts%2C%20rowtype%3D%5B%22G%22%5D%20*%20ncuts%2C%20rhs%3Dcut_rhs%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20start%3Dcut_mstart%2C%20colind%3Dcut_ind%2C%20cutcoef%3Dcut_coe)%0A%0A%20%20%20%20%20%20%20%20return%20(reject%2C%20None)%0A%0A%20%20%20%20p_cb.addPreIntsolCallback(cb_preintsol%2C%20n_cb)%0A%0A%20%20%20%20p_cb.controls.outputlog%20%3D%200%0A%20%20%20%20%23%20optimize_safe()%20re-solves%20p_cb%2C%20catching%20a%20Community-license%20size%0A%20%20%20%20%23%20error%20so%20it%20renders%20as%20a%20clear%20message%20instead%20of%20crashing.%0A%20%20%20%20cb_error%2C%20cb_solve_time%20%3D%20optimize_safe(p_cb)%0A%0A%20%20%20%20if%20cb_error%20is%20None%3A%0A%20%20%20%20%20%20%20%20sol_cb%20%3D%20p_cb.getSolution(use_cb)%0A%20%20%20%20%20%20%20%20edges_cb%20%3D%20%5B(i%2C%20j)%20for%20i%20in%20CITIES_cb%20for%20j%20in%20CITIES_cb%20if%20i%20!%3D%20j%20and%20sol_cb%5Bi%2C%20j%5D%20%3E%200.5%5D%0A%20%20%20%20%20%20%20%20cb_obj%20%3D%20p_cb.attributes.objval%0A%20%20%20%20%20%20%20%20cb_callout%20%3D%20None%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20edges_cb%20%3D%20None%0A%20%20%20%20%20%20%20%20cb_obj%20%3D%20None%0A%20%20%20%20%20%20%20%20cb_callout%20%3D%20license_error_callout(cb_error%2C%2069)%0A%0A%20%20%20%20mo.show_code(cb_callout%2C%20position%3D%22above%22)%0A%20%20%20%20return%20X_cb%2C%20Y_cb%2C%20cb_obj%2C%20cb_solve_time%2C%20edges_cb%2C%20n_cb%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(cb_obj%2C%20cb_solve_time%2C%20mo%2C%20n_cb)%3A%0A%20%20%20%20if%20cb_obj%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20cb_result_md%20%3D%20mo.md(f%22%22%22%0A%20%20%20%20%20%20%20%20**Objective%20value%20with%20the%20callback%20formulation%20(%7Bn_cb%7D%20cities)%3A**%20%7Bcb_obj%3A.1f%7D%20%26nbsp%3B%26nbsp%3B%20**Solve%20time%3A**%20%7Bcb_solve_time%3A.2f%7Ds.%20Note%20this%20instance%20is%20typically%20larger%20than%20the%20ones%20the%20naive%20and%20MTZ%20demos%20above%20can%20handle%20in%20reasonable%20time%2C%20showing%20how%20much%20further%20relaxing%20subtour%20elimination%20into%20a%20callback%20lets%20the%20model%20scale.%0A%20%20%20%20%20%20%20%20%22%22%22)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20cb_result_md%20%3D%20None%0A%20%20%20%20cb_result_md%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(X_cb%2C%20Y_cb%2C%20edges_cb%2C%20n_cb%2C%20plot_tour)%3A%0A%20%20%20%20cb_fig%20%3D%20plot_tour(X_cb%2C%20Y_cb%2C%20edges_cb%2C%20f%22Callback%20formulation%3A%20valid%20tour%20over%20%7Bn_cb%7D%20cities%22)%20if%20edges_cb%20is%20not%20None%20else%20None%0A%20%20%20%20cb_fig%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