Þ¥bonds€¬cell_resultsÞÙ$fff3fe40-b944-46ed-aea1-3d550ed5fbb0Š¦queued¤logs§running¦output†¤bodyÚ&
find_suboptimal_edge 
find_suboptimal_edge(f, g, C)::Union{Nothing,CartesianIndex}

Returns the position of an existing suboptimal edge.

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÙÃL.DY’°persist_js_state·has_pluto_hook_features§cell_idÙ$fff3fe40-b944-46ed-aea1-3d550ed5fbb0¹depends_on_disabled_cells§runtimeÎaû‡µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$3be07e02-b95f-44a2-9491-f39a1a1c2617Š¦queued¤logs§running¦output†¤body…¦prefix´BenchmarkTools.Trial¨elements’’’ÚÀBenchmarkTools.Trial: 10000 samples with 8 evaluations. Range (min … max): 3.822 μs … 1.625 ms ┊ GC (min … max): 0.00% … 99.36% Time (median): 4.031 μs ┊ GC (median): 0.00% Time (mean ± σ): 5.360 μs ± 28.269 μs ┊ GC (mean ± σ): 10.37% ± 1.98% ▂██▇▄▃▂▂ â–â–▃▂▃▄▃▃▃▂▂■▂ ██████████▇▇▇▆▆▅▄▅▅▆▆▅▅▅▅▄▄▄▃▃▃▄▄▃▄▅▄▄▇▆▇███████████████▇▆ â–ˆ 3.82 μs Histogram: log(frequency) by time 8.15 μs < Memory estimate: 7.67 KiB, allocs estimate: 182.ªtext/plain’’Ú±BenchmarkTools.Trial: 10000 samples with 1 evaluation. Range (min … max): 12.102 μs … 332.970 μs ┊ GC (min … max): 0.00% … 0.00% Time (median): 19.005 μs ┊ GC (median): 0.00% Time (mean ± σ): 19.245 μs ± 4.400 μs ┊ GC (mean ± σ): 0.00% ± 0.00% â–‚â–„ ▃█■█▆■â–â–▂▂▂▃▂▂▂▂â–â–â–â–▂██▇▃▅███▄▃▇███▄▃▅▇▆▄▂▂▂▂▂â–â–â–â–‚â–â–â–â–â–â–â–â–â–â–â–â–â–â–â–â– â–ƒ 12.1 μs Histogram: frequency by time 29.6 μs < Memory estimate: 6.42 KiB, allocs estimate: 110.ªtext/plain¤type¥Array¬prefix_short ¨objectid°648e593c2c02d261¤mimeÙ!application/vnd.pluto.tree+object¬rootassigneeÀ²last_run_timestampËAÙÃL3¾þm°persist_js_state·has_pluto_hook_features§cell_idÙ$3be07e02-b95f-44a2-9491-f39a1a1c2617¹depends_on_disabled_cells§runtimeÏC×[$µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$521f7c7a-823d-4873-8484-66c17825b966Š¦queued¤logs§running¦output†¤bodyÙ=

OptimalTransport.jl API

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÙÃL £|l°persist_js_state·has_pluto_hook_features§cell_idÙ$521f7c7a-823d-4873-8484-66c17825b966¹depends_on_disabled_cells§runtimeζäµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$9bef5380-7275-42de-99cc-597aa72b0abcŠ¦queued¤logs§running¦output†¤bodyÙA

Graph & Cycle detection

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÙÃL £K{°persist_js_state·has_pluto_hook_features§cell_idÙ$9bef5380-7275-42de-99cc-597aa72b0abc¹depends_on_disabled_cells§runtimeν•µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$a05afd19-3bae-4479-b8f0-86f373094113Š¦queued¤logs§running¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÙÃL/:ÎO°persist_js_state·has_pluto_hook_features§cell_idÙ$a05afd19-3bae-4479-b8f0-86f373094113¹depends_on_disabled_cells§runtimeÎu„´µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$5584d358-eab9-48fa-a880-62080674df12Š¦queued¤logs§running¦output†¤bodyÚMŒ ¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÙÃL3ز5°persist_js_state·has_pluto_hook_features§cell_idÙ$5584d358-eab9-48fa-a880-62080674df12¹depends_on_disabled_cells§runtimeÍ/(µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$3e4a5f6d-d4ef-4372-9762-388b92f0755bŠ¦queued¤logs§running¦output†¤bodyÙN

Obtaining a Dual Pair Complementary to P

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÙÃL £2'°persist_js_state·has_pluto_hook_features§cell_idÙ$3e4a5f6d-d4ef-4372-9762-388b92f0755b¹depends_on_disabled_cells§runtimeκ_µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$e7aea362-3595-45d2-bb0a-512e241c17bcŠ¦queued¤logs§running¦output†¤bodyƒ¨elements’’’…¦prefix®CartesianIndex¨elements”’’´CartesianIndex(1, 3)ªtext/plain’’´CartesianIndex(3, 3)ªtext/plain’’´CartesianIndex(3, 1)ªtext/plain’’´CartesianIndex(1, 1)ªtext/plain¤type¥Array¬prefix_short ¨objectid°6cb57d2e3d154071Ù!application/vnd.pluto.tree+object’’…¦prefix§Float64¨elements”’’£1.2ªtext/plain’’£1.0ªtext/plain’’£1.0ªtext/plain’’£1.1ªtext/plain¤type¥Array¬prefix_short ¨objectid°e599978eaedd757cÙ!application/vnd.pluto.tree+object¤type¥Tuple¨objectid°f6f50a741cf897f9¤mimeÙ!application/vnd.pluto.tree+object¬rootassigneeÀ²last_run_timestampËAÙÃL.©îN°persist_js_state·has_pluto_hook_features§cell_idÙ$e7aea362-3595-45d2-bb0a-512e241c17bc¹depends_on_disabled_cells§runtimeÎغµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$32b4c5a4-f5e4-457d-b09d-531215fda61bŠ¦queued¤logs§running¦output†¤bodyÚØ
find_feasible_dual

Tries to find a feasible solution $(f, g)$ to the dual problem given a plan $P$.

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÙÃL.D×°persist_js_state·has_pluto_hook_features§cell_idÙ$32b4c5a4-f5e4-457d-b09d-531215fda61b¹depends_on_disabled_cells§runtimeÎFó+µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$cb5ecc78-6ffc-44ea-94cd-d80d8b079423Š¦queued¤logs§running¦output†¤bodyÙ.

Packages

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÙÃL ¤¾­°persist_js_state·has_pluto_hook_features§cell_idÙ$cb5ecc78-6ffc-44ea-94cd-d80d8b079423¹depends_on_disabled_cells§runtimeÎ6ÿµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$c8cd4eff-8702-42a2-8b40-8a789ea4a37fŠ¦queued¤logs§running¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÙÃL-2¨T°persist_js_state·has_pluto_hook_features§cell_idÙ$c8cd4eff-8702-42a2-8b40-8a789ea4a37f¹depends_on_disabled_cells§runtimeÎ&c³µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$187de006-8830-11ec-3fb7-297fcaedd55eŠ¦queued¤logs§running¦output†¤bodyÚ
north_west 
north_west(μ, ν)

Finds an initial transport plan that respect the marginal constraints $(\mu,\nu)$.

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÙÃL-œ¹¦°persist_js_state·has_pluto_hook_features§cell_idÙ$187de006-8830-11ec-3fb7-297fcaedd55e¹depends_on_disabled_cells§runtimeÎN}›µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$c147499e-bb03-428a-8acf-49722fd54c7eŠ¦queued¤logs§running¦output†¤bodyÙ@

Putting it all together...

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÙÃL £cаpersist_js_state·has_pluto_hook_features§cell_idÙ$c147499e-bb03-428a-8acf-49722fd54c7e¹depends_on_disabled_cells§runtimeζ¼µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$96ab200e-603d-4c87-9cc1-c37dbda6ace4Š¦queued¤logs§running¦output†¤bodyƒ¨elements’’’…¦prefix®CartesianIndex¨elements”’’´CartesianIndex(2, 3)ªtext/plain’’´CartesianIndex(3, 3)ªtext/plain’’´CartesianIndex(3, 1)ªtext/plain’’´CartesianIndex(2, 1)ªtext/plain¤type¥Array¬prefix_short ¨objectid°21b6f40cdab6cb7aÙ!application/vnd.pluto.tree+object’’…¦prefix§Float64¨elements”’’£0.0ªtext/plain’’¨0.333333ªtext/plain’’£0.0ªtext/plain’’¨0.333333ªtext/plain¤type¥Array¬prefix_short ¨objectid°94fa88b4413df2cfÙ!application/vnd.pluto.tree+object¤type¥Tuple¨objectid°5ca8dd86d8cac9ae¤mimeÙ!application/vnd.pluto.tree+object¬rootassigneeÀ²last_run_timestampËAÙÃL.»û/°persist_js_state·has_pluto_hook_features§cell_idÙ$96ab200e-603d-4c87-9cc1-c37dbda6ace4¹depends_on_disabled_cells§runtimeÎM¿µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$aa5810ed-b4a0-41fa-bdfd-95df64edf677Š¦queued¤logs§running¦output†¤bodyÙ$emd (generic function with 1 method)¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÙÃL/L‚0°persist_js_state·has_pluto_hook_features§cell_idÙ$aa5810ed-b4a0-41fa-bdfd-95df64edf677¹depends_on_disabled_cells§runtimeÎ>ĵpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$b73c42fd-7a52-45d0-b9a3-ede4dcc61e36Š¦queued¤logs§running¦output†¤bodyÙk3×3 Matrix{Float64}: 0.25 0.0 0.0 0.0 0.25 0.0 0.0833333 0.0833333 0.333333¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÙÃL/€‘ó°persist_js_state·has_pluto_hook_features§cell_idÙ$b73c42fd-7a52-45d0-b9a3-ede4dcc61e36¹depends_on_disabled_cells§runtimeÎÐðóµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$4b2c7693-7873-42b3-85d3-79712fee730dŠ¦queued¤logs§running¦output†¤bodyÙ%emd2 (generic function with 1 method)¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÙÃL/‰Tz°persist_js_state·has_pluto_hook_features§cell_idÙ$4b2c7693-7873-42b3-85d3-79712fee730d¹depends_on_disabled_cells§runtimeÎÞIµpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$1030d263-d188-49d0-b9da-5d02810bba9bŠ¦queued¤logs§running¦output†¤bodyÚ{
(north_west(μ, ν))[1] == P == P ==
¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÙÃL.A Õ°persist_js_state·has_pluto_hook_features§cell_idÙ$1030d263-d188-49d0-b9da-5d02810bba9b¹depends_on_disabled_cells§runtimeÎ'>iµpublished_object_keys’Ù5eb27072a-8a3b-11ef-370b-812543c54790/e2bb37d017f82f33Ù5eb27072a-8a3b-11ef-370b-812543c54790/eeaeaa7a973499cf¸depends_on_skipped_cells§erroredÂÙ$1ba4e1d2-a260-4f48-866c-821e53c30506Š¦queued¤logs§running¦output†¤bodyÙ¾

The Network Simplex

This is a textbook implementation of the Network Simplex algorithm from the book "Computational Optimal Transport".

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÙÃL £Å°persist_js_state·has_pluto_hook_features§cell_idÙ$1ba4e1d2-a260-4f48-866c-821e53c30506¹depends_on_disabled_cells§runtimeÎÙ[µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$aac9efe0-d6a1-4587-99ec-46e0f1411c85Š¦queued¤logs§running¦output†¤bodyÙ.collect_cycle (generic function with 1 method)¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÙÃL.Q³³°persist_js_state·has_pluto_hook_features§cell_idÙ$aac9efe0-d6a1-4587-99ec-46e0f1411c85¹depends_on_disabled_cells§runtimeÎ@)µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$1ee92bf4-835f-4c62-9bd5-5d96a86e9d8bŠ¦queued¤logs§running¦output†¤bodyƒ¨elements–’’´CartesianIndex(1, 2)ªtext/plain’’…¦prefix§Float64¨elements“’’£0.0ªtext/plain’’£0.0ªtext/plain’’£0.0ªtext/plain¤type¥Array¬prefix_short ¨objectid°820e838415a0efc7Ù!application/vnd.pluto.tree+object’’…¦prefix§Float64¨elements“’’£1.0ªtext/plain’’£1.0ªtext/plain’’£1.0ªtext/plain¤type¥Array¬prefix_short ¨objectid°6e2ed4fc6de19374Ù!application/vnd.pluto.tree+object’’£0.0ªtext/plain’’£1.0ªtext/plain’’£0.0ªtext/plain¤type¥Tuple¨objectid°8a086e232e932865¤mimeÙ!application/vnd.pluto.tree+object¬rootassigneeÀ²last_run_timestampËAÙÃL.ºöˆ°persist_js_state·has_pluto_hook_features§cell_idÙ$1ee92bf4-835f-4c62-9bd5-5d96a86e9d8b¹depends_on_disabled_cells§runtimeÎ6µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$d29bbd55-4b0c-4fa0-8bd7-d9b85d7d7a10Š¦queued¤logs§running¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÙÃL-UÚ°persist_js_state·has_pluto_hook_features§cell_idÙ$d29bbd55-4b0c-4fa0-8bd7-d9b85d7d7a10¹depends_on_disabled_cells§runtimeεpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$616cfde6-190b-403b-8d1c-da2f4eb385adŠ¦queued¤logs§running¦output†¤body ¤mimeªtext/plain¬rootassigneeÀ²last_run_timestampËAÙÃL3Ãaž°persist_js_state·has_pluto_hook_features§cell_idÙ$616cfde6-190b-403b-8d1c-da2f4eb385ad¹depends_on_disabled_cells§runtimeÎÖd.µpublished_object_keys¸depends_on_skipped_cells§erroredÂÙ$65dd721e-20aa-4a2b-abb4-46f04d922aeeŠ¦queued¤logs§running¦output†¤bodyÙ@

The North-West Corner rule

¤mime©text/html¬rootassigneeÀ²last_run_timestampËAÙÃL £ΰpersist_js_state·has_pluto_hook_features§cell_idÙ$65dd721e-20aa-4a2b-abb4-46f04d922aee¹depends_on_disabled_cells§runtimeÎÓµpublished_object_keys¸depends_on_skipped_cells§errored±cell_dependenciesÞÙ$fff3fe40-b944-46ed-aea1-3d550ed5fbb0„´precedence_heuristic §cell_idÙ$fff3fe40-b944-46ed-aea1-3d550ed5fbb0´downstream_cells_map´find_suboptimal_edge’Ù$1ee92bf4-835f-4c62-9bd5-5d96a86e9d8bÙ$aa5810ed-b4a0-41fa-bdfd-95df64edf677²upstream_cells_map¤@doc¥Tuple£pop¦isless®CartesianIndex©@inboundsº#___this_pluto_module_name¡>£Any§nothing¡<©eachindex¡-¡+¥UnionÙ$3be07e02-b95f-44a2-9491-f39a1a1c2617„´precedence_heuristic §cell_idÙ$3be07e02-b95f-44a2-9491-f39a1a1c2617´downstream_cells_map€²upstream_cells_map…¥randn¤emd2‘Ù$4b2c7693-7873-42b3-85d3-79712fee730d¡/¤fill¹BenchmarkTools.@benchmarkÙ$521f7c7a-823d-4873-8484-66c17825b966„´precedence_heuristic §cell_idÙ$521f7c7a-823d-4873-8484-66c17825b966´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$9bef5380-7275-42de-99cc-597aa72b0abc„´precedence_heuristic §cell_idÙ$9bef5380-7275-42de-99cc-597aa72b0abc´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$a05afd19-3bae-4479-b8f0-86f373094113„´precedence_heuristic §cell_idÙ$a05afd19-3bae-4479-b8f0-86f373094113´downstream_cells_mapƒ¤GLPK‘Ù$616cfde6-190b-403b-8d1c-da2f4eb385ad®BenchmarkTools°OptimalTransport‘Ù$616cfde6-190b-403b-8d1c-da2f4eb385ad²upstream_cells_map€Ù$5584d358-eab9-48fa-a880-62080674df12„´precedence_heuristic §cell_idÙ$5584d358-eab9-48fa-a880-62080674df12´downstream_cells_map€²upstream_cells_map¯TableOfContentsÙ$3e4a5f6d-d4ef-4372-9762-388b92f0755b„´precedence_heuristic §cell_idÙ$3e4a5f6d-d4ef-4372-9762-388b92f0755b´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$e7aea362-3595-45d2-bb0a-512e241c17bc„´precedence_heuristic §cell_idÙ$e7aea362-3595-45d2-bb0a-512e241c17bc´downstream_cells_map€²upstream_cells_mapƒ­collect_cycle‘Ù$aac9efe0-d6a1-4587-99ec-46e0f1411c85®CartesianIndex¤BoolÙ$32b4c5a4-f5e4-457d-b09d-531215fda61b„´precedence_heuristic §cell_idÙ$32b4c5a4-f5e4-457d-b09d-531215fda61b´downstream_cells_map²find_feasible_dual’Ù$1ee92bf4-835f-4c62-9bd5-5d96a86e9d8bÙ$aa5810ed-b4a0-41fa-bdfd-95df64edf677²upstream_cells_mapÞ¤@doc¡:¥@view¥Tuple¡>¥zeros¦islessº#___this_pluto_module_name¤size£Any§findall¡<¡-¥push!£Int¦eltype¡+¥Union£âˆˆ¢in£SetÙ$cb5ecc78-6ffc-44ea-94cd-d80d8b079423„´precedence_heuristic §cell_idÙ$cb5ecc78-6ffc-44ea-94cd-d80d8b079423´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$c8cd4eff-8702-42a2-8b40-8a789ea4a37f„´precedence_heuristic§cell_idÙ$c8cd4eff-8702-42a2-8b40-8a789ea4a37f´downstream_cells_map‚§PlutoUI©PlutoTest‘Ù$1030d263-d188-49d0-b9da-5d02810bba9b²upstream_cells_map€Ù$187de006-8830-11ec-3fb7-297fcaedd55e„´precedence_heuristic §cell_idÙ$187de006-8830-11ec-3fb7-297fcaedd55e´downstream_cells_mapªnorth_west“Ù$1030d263-d188-49d0-b9da-5d02810bba9bÙ$1ee92bf4-835f-4c62-9bd5-5d96a86e9d8bÙ$aa5810ed-b4a0-41fa-bdfd-95df64edf677²upstream_cells_mapÞ¤@doc¥Tuple¡>¥zeros¦islessº#___this_pluto_module_name£Any¦length¡<¢<=¡-¦falses£min¦eltype¡+¥Union¢==Ù$c147499e-bb03-428a-8acf-49722fd54c7e„´precedence_heuristic §cell_idÙ$c147499e-bb03-428a-8acf-49722fd54c7e´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$96ab200e-603d-4c87-9cc1-c37dbda6ace4„´precedence_heuristic §cell_idÙ$96ab200e-603d-4c87-9cc1-c37dbda6ace4´downstream_cells_map€²upstream_cells_mapƒ­collect_cycle‘Ù$aac9efe0-d6a1-4587-99ec-46e0f1411c85®CartesianIndex¤BoolÙ$aa5810ed-b4a0-41fa-bdfd-95df64edf677„´precedence_heuristic §cell_idÙ$aa5810ed-b4a0-41fa-bdfd-95df64edf677´downstream_cells_map£emd’Ù$b73c42fd-7a52-45d0-b9a3-ede4dcc61e36Ù$4b2c7693-7873-42b3-85d3-79712fee730d²upstream_cells_mapÞ¥@goto§@assert£rem´find_suboptimal_edge‘Ù$fff3fe40-b944-46ed-aea1-3d550ed5fbb0¤dual¢==©isnothing³Base.AssertionErrorªnorth_west‘Ù$187de006-8830-11ec-3fb7-297fcaedd55e¡:ªBase.throw¥@view¡%£end¥begin¤Base¦@label­collect_cycle‘Ù$aac9efe0-d6a1-4587-99ec-46e0f1411c85¦argmin¡-©enumerate¡+¡*²find_feasible_dual‘Ù$32b4c5a4-f5e4-457d-b09d-531215fda61bÙ$b73c42fd-7a52-45d0-b9a3-ede4dcc61e36„´precedence_heuristic §cell_idÙ$b73c42fd-7a52-45d0-b9a3-ede4dcc61e36´downstream_cells_map€²upstream_cells_map‚¡/£emd‘Ù$aa5810ed-b4a0-41fa-bdfd-95df64edf677Ù$4b2c7693-7873-42b3-85d3-79712fee730d„´precedence_heuristic §cell_idÙ$4b2c7693-7873-42b3-85d3-79712fee730d´downstream_cells_map¤emd2’Ù$3be07e02-b95f-44a2-9491-f39a1a1c2617Ù$616cfde6-190b-403b-8d1c-da2f4eb385ad²upstream_cells_mapƒ£sum¡*£emd‘Ù$aa5810ed-b4a0-41fa-bdfd-95df64edf677Ù$1030d263-d188-49d0-b9da-5d02810bba9b„´precedence_heuristic §cell_idÙ$1030d263-d188-49d0-b9da-5d02810bba9b´downstream_cells_map€²upstream_cells_mapÞ¤Core·PlutoTest.Test.Returned³PlutoTest.WrongCallºPlutoTest.Base.catch_stack±PlutoTest.rethrow¥@test¯PlutoTest.push!¹PlutoTest.catch_backtrace­PlutoTest.===³PlutoTest.ErrorCall´PlutoTest.Test.Threw¶PlutoTest.Test.do_test¹PlutoTest.unwrap_computed¢==ªnorth_west‘Ù$187de006-8830-11ec-3fb7-297fcaedd55e¯PlutoTest.throw»PlutoTest.CapturedException©PlutoTest‘Ù$c8cd4eff-8702-42a2-8b40-8a789ea4a37f²PlutoTest.ComputedµPlutoTest.CorrectCall´PlutoTest.stacktrace­PlutoTest.isaÙ#PlutoTest.PartialEvaluatedException®PlutoTest.lastªCore._exprÙ$1ba4e1d2-a260-4f48-866c-821e53c30506„´precedence_heuristic §cell_idÙ$1ba4e1d2-a260-4f48-866c-821e53c30506´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindexÙ$aac9efe0-d6a1-4587-99ec-46e0f1411c85„´precedence_heuristic §cell_idÙ$aac9efe0-d6a1-4587-99ec-46e0f1411c85´downstream_cells_map­collect_cycle“Ù$e7aea362-3595-45d2-bb0a-512e241c17bcÙ$96ab200e-603d-4c87-9cc1-c37dbda6ace4Ù$aa5810ed-b4a0-41fa-bdfd-95df64edf677²upstream_cells_mapÞ¡:¥@view¡>¤pop!¦isless®CartesianIndex§Float64¤size£end§nothing§findall¡<¡-¥push!£Int¡+£âˆˆ§isempty¢==¢in£SetÙ$1ee92bf4-835f-4c62-9bd5-5d96a86e9d8b„´precedence_heuristic §cell_idÙ$1ee92bf4-835f-4c62-9bd5-5d96a86e9d8b´downstream_cells_map€²upstream_cells_mapˆ´find_suboptimal_edge‘Ù$fff3fe40-b944-46ed-aea1-3d550ed5fbb0ªnorth_west‘Ù$187de006-8830-11ec-3fb7-297fcaedd55e¡I¡/¦Matrix§Float64²find_feasible_dual‘Ù$32b4c5a4-f5e4-457d-b09d-531215fda61b¤fillÙ$d29bbd55-4b0c-4fa0-8bd7-d9b85d7d7a10„´precedence_heuristic§cell_idÙ$d29bbd55-4b0c-4fa0-8bd7-d9b85d7d7a10´downstream_cells_map­LinearAlgebra²upstream_cells_map€Ù$616cfde6-190b-403b-8d1c-da2f4eb385ad„´precedence_heuristic §cell_idÙ$616cfde6-190b-403b-8d1c-da2f4eb385ad´downstream_cells_map€²upstream_cells_map£â‰ˆ¥randn¤emd2‘Ù$4b2c7693-7873-42b3-85d3-79712fee730d®GLPK.Optimizer¤GLPK‘Ù$a05afd19-3bae-4479-b8f0-86f373094113§@assert¡:µOptimalTransport.emd2¥throw¡/®AssertionError°OptimalTransport‘Ù$a05afd19-3bae-4479-b8f0-86f373094113¤fillÙ$65dd721e-20aa-4a2b-abb4-46f04d922aee„´precedence_heuristic §cell_idÙ$65dd721e-20aa-4a2b-abb4-46f04d922aee´downstream_cells_map€²upstream_cells_map‚§@md_str¨getindex´cell_execution_orderÜÙ$d29bbd55-4b0c-4fa0-8bd7-d9b85d7d7a10Ù$c8cd4eff-8702-42a2-8b40-8a789ea4a37fÙ$1ba4e1d2-a260-4f48-866c-821e53c30506Ù$65dd721e-20aa-4a2b-abb4-46f04d922aeeÙ$187de006-8830-11ec-3fb7-297fcaedd55eÙ$1030d263-d188-49d0-b9da-5d02810bba9bÙ$3e4a5f6d-d4ef-4372-9762-388b92f0755bÙ$32b4c5a4-f5e4-457d-b09d-531215fda61bÙ$fff3fe40-b944-46ed-aea1-3d550ed5fbb0Ù$9bef5380-7275-42de-99cc-597aa72b0abcÙ$aac9efe0-d6a1-4587-99ec-46e0f1411c85Ù$e7aea362-3595-45d2-bb0a-512e241c17bcÙ$1ee92bf4-835f-4c62-9bd5-5d96a86e9d8bÙ$96ab200e-603d-4c87-9cc1-c37dbda6ace4Ù$a05afd19-3bae-4479-b8f0-86f373094113Ù$c147499e-bb03-428a-8acf-49722fd54c7eÙ$aa5810ed-b4a0-41fa-bdfd-95df64edf677Ù$b73c42fd-7a52-45d0-b9a3-ede4dcc61e36Ù$521f7c7a-823d-4873-8484-66c17825b966Ù$4b2c7693-7873-42b3-85d3-79712fee730dÙ$3be07e02-b95f-44a2-9491-f39a1a1c2617Ù$616cfde6-190b-403b-8d1c-da2f4eb385adÙ$cb5ecc78-6ffc-44ea-94cd-d80d8b079423Ù$5584d358-eab9-48fa-a880-62080674df12´last_hot_reload_timeË©shortpath²network_simplex.jl®process_status¥ready¤pathÙ8/home/runner/work/Notebooks/Notebooks/network_simplex.jl­pluto_version¨v0.19.47®last_save_timeËAÙÃL  ˜žªcell_orderÜÙ$1ba4e1d2-a260-4f48-866c-821e53c30506Ù$65dd721e-20aa-4a2b-abb4-46f04d922aeeÙ$187de006-8830-11ec-3fb7-297fcaedd55eÙ$1030d263-d188-49d0-b9da-5d02810bba9bÙ$3e4a5f6d-d4ef-4372-9762-388b92f0755bÙ$32b4c5a4-f5e4-457d-b09d-531215fda61bÙ$fff3fe40-b944-46ed-aea1-3d550ed5fbb0Ù$9bef5380-7275-42de-99cc-597aa72b0abcÙ$e7aea362-3595-45d2-bb0a-512e241c17bcÙ$aac9efe0-d6a1-4587-99ec-46e0f1411c85Ù$1ee92bf4-835f-4c62-9bd5-5d96a86e9d8bÙ$96ab200e-603d-4c87-9cc1-c37dbda6ace4Ù$a05afd19-3bae-4479-b8f0-86f373094113Ù$3be07e02-b95f-44a2-9491-f39a1a1c2617Ù$616cfde6-190b-403b-8d1c-da2f4eb385adÙ$b73c42fd-7a52-45d0-b9a3-ede4dcc61e36Ù$c147499e-bb03-428a-8acf-49722fd54c7eÙ$aa5810ed-b4a0-41fa-bdfd-95df64edf677Ù$521f7c7a-823d-4873-8484-66c17825b966Ù$4b2c7693-7873-42b3-85d3-79712fee730dÙ$cb5ecc78-6ffc-44ea-94cd-d80d8b079423Ù$5584d358-eab9-48fa-a880-62080674df12Ù$d29bbd55-4b0c-4fa0-8bd7-d9b85d7d7a10Ù$c8cd4eff-8702-42a2-8b40-8a789ea4a37f±published_objects‚Ù5eb27072a-8a3b-11ef-370b-812543c54790/e2bb37d017f82f33ÙB3×3 Matrix{Float64}: 0.2 0.0 0.0 0.3 0.1 0.1 0.0 0.0 0.3Ù5eb27072a-8a3b-11ef-370b-812543c54790/eeaeaa7a973499cf¤true¥nbpkgŠ¯install_time_nsÏL‰­K¬instantiatedòinstalled_versions†¤GLPK¥1.1.3­LinearAlgebra¦stdlib§PlutoUI¦0.7.60©PlutoTest¥0.2.2®BenchmarkTools¥1.3.2°OptimalTransport¦0.3.19°terminal_outputs‡¤GLPKÚ)§ Instantiating... === ┌ Warning: The active manifest file has dependencies that were resolved with a different julia version (1.8.2). Unexpected behavior may occur. â”” @ /tmp/jl_oDhDHt/Manifest.toml:0  Installed DiffRules ──────── v1.12.1 Installed Parsers ────────── v2.5.0  Installed PlutoUI ────────── v0.7.48  Installed ForwardDiff ────── v0.10.32  Installed NNlib ──────────── v0.8.10  Installed GLPK ───────────── v1.1.0  Installed Distributions ──── v0.25.77  Installed MathOptInterface ─ v1.9.0  Resolving... === ┌ Info: Operation failed. Updating registries and trying again... │  exception = │  Unsatisfiable requirements detected for package SortingAlgorithms [a2af1166]: │  SortingAlgorithms [a2af1166] log: │  ├─possible versions are: 0.3.0 - 1.2.1 or uninstalled │  ├─restricted to versions 1.0.1 by an explicit requirement, leaving only versions: 1.0.1 â””  └─restricted by julia compatibility requirements to versions: 1.1.0 - 1.2.1 or uninstalled — no versions left Resolving... === ┌ Warning: Operation failed. Removing Manifest and trying again... │  exception = │  Unsatisfiable requirements detected for package SortingAlgorithms [a2af1166]: │  SortingAlgorithms [a2af1166] log: │  ├─possible versions are: 0.3.0 - 1.2.1 or uninstalled │  ├─restricted to versions 1.0.1 by an explicit requirement, leaving only versions: 1.0.1 │  └─restricted by julia compatibility requirements to versions: 1.1.0 - 1.2.1 or uninstalled — no versions left â”” @ Pluto ~/.julia/packages/Pluto/6smog/src/packages/Packages.jl:494 Resolving... ===  Installed GLPK ─ v1.1.3 Updating `/tmp/jl_oDhDHt/Project.toml`  ⌅ [6e4b80f9] + BenchmarkTools v1.3.2 ⌅ [60bf3e95] + GLPK v1.1.3 [7e02d93a] + OptimalTransport v0.3.19 [cb4044da] + PlutoTest v0.2.2 [7f904dfe] + PlutoUI v0.7.60 [37e2e46d] ~ LinearAlgebra ⇒ v1.11.0  Updating `/tmp/jl_oDhDHt/Manifest.toml` [6e696c72] + AbstractPlutoDingetjes v1.3.2 ⌅ [79e6a3ab] + Adapt v3.7.2 [66dad0bd] + AliasTables v1.1.3 [a9b6321e] + Atomix v0.1.0 ⌅ [6e4b80f9] + BenchmarkTools v1.3.2 [fa961155] + CEnum v0.5.0 [d360d2e6] + ChainRulesCore v1.25.0 [523fee87] + CodecBzip2 v0.8.4 [944b1d66] + CodecZlib v0.7.6 [3da002f7] + ColorTypes v0.11.5 [bbf7d656] + CommonSubexpressions v0.3.1 [34da2185] + Compat v4.16.0 [9a962f9c] + DataAPI v1.16.0 [864edb3b] + DataStructures v0.18.20 [163ba53b] + DiffResults v1.1.0 [b552c78f] + DiffRules v1.15.1 [b4f34e82] + Distances v0.10.11 [31c24e10] + Distributions v0.25.112 [ffbed154] + DocStringExtensions v0.9.3 [24df6009] + ExactOptimalTransport v0.2.5 [1a297f60] + FillArrays v1.13.0 [53c48c17] + FixedPointNumbers v0.8.5 [f6369f11] + ForwardDiff v0.10.36 ⌅ [60bf3e95] + GLPK v1.1.3 ⌃ [46192b85] + GPUArraysCore v0.1.5 [34004b35] + HypergeometricFunctions v0.3.24 [47d2ed2b] + Hyperscript v0.0.5 [ac1192a8] + HypertextLiteral v0.9.5 [b5f81e59] + IOCapture v0.2.5 [92d709cd] + IrrationalConstants v0.2.2 [42fd0dbc] + IterativeSolvers v0.9.4 [692b3bcd] + JLLWrappers v1.6.1 [682c06a0] + JSON v0.21.4 [63c18a36] + KernelAbstractions v0.9.28 [929cbde3] + LLVM v9.1.2 [2ab3a3ac] + LogExpFunctions v0.3.28 [6c6e2e6c] + MIMEs v0.1.4 [1914dd2f] + MacroTools v0.5.13 [b8f27783] + MathOptInterface v1.31.2 [e1d29d7a] + Missings v1.2.0 [d8a4904e] + MutableArithmetics v1.5.1 ⌅ [872c559c] + NNlib v0.8.21 [77ba4419] + NaNMath v1.0.2 [7e02d93a] + OptimalTransport v0.3.19 [bac558e1] + OrderedCollections v1.6.3 [90014a1f] + PDMats v0.11.31 [69de0a69] + Parsers v2.8.1 [cb4044da] + PlutoTest v0.2.2 [7f904dfe] + PlutoUI v0.7.60 [aea7be01] + PrecompileTools v1.2.1 [21216c6a] + Preferences v1.4.3 [43287f4e] + PtrArrays v1.2.1 [1fd47b50] + QuadGK v2.11.1 [3cdcf5f2] + RecipesBase v1.3.4 [189a3867] + Reexport v1.2.2 [ae029012] + Requires v1.3.0 [79098fc4] + Rmath v0.8.0 [a2af1166] + SortingAlgorithms v1.2.1 [276daf66] + SpecialFunctions v2.4.0 [90137ffa] + StaticArrays v1.9.7 [1e83bf80] + StaticArraysCore v1.4.3 [10745b16] + Statistics v1.11.1 [82ae8749] + StatsAPI v1.7.0 [2913bbd2] + StatsBase v0.34.3 [4c63d2b9] + StatsFuns v1.3.2 [3bb67fe8] + TranscodingStreams v0.11.3 [410a4b4d] + Tricks v0.1.9 [5c2747f8] + URIs v1.5.1 [013be700] + UnsafeAtomics v0.2.1 [d80eeb9a] + UnsafeAtomicsLLVM v0.2.1 [6e34b625] + Bzip2_jll v1.0.8+1 [e8aa6df9] + GLPK_jll v5.0.1+0 [dad2f222] + LLVMExtra_jll v0.0.34+0 [efe28fd5] + OpenSpecFun_jll v0.5.5+0 [f50d1b31] + Rmath_jll v0.5.1+0 [0dad84c5] + ArgTools v1.1.2 [56f22d72] + Artifacts v1.11.0 [2a0f44e3] + Base64 v1.11.0 [ade2ca70] + Dates v1.11.0 [f43a241f] + Downloads v1.6.0 [7b1f6079] + FileWatching v1.11.0 [b77e0a4c] + InteractiveUtils v1.11.0 [4af54fe1] + LazyArtifacts v1.11.0 [b27032c2] + LibCURL v0.6.4 [76f85450] + LibGit2 v1.11.0 [8f399da3] + Libdl v1.11.0 [37e2e46d] + LinearAlgebra v1.11.0 [56ddb016] + Logging v1.11.0 [d6f4376e] + Markdown v1.11.0 [a63ad114] + Mmap v1.11.0 [ca575930] + NetworkOptions v1.2.0 [44cfe95a] + Pkg v1.11.0 [de0858da] + Printf v1.11.0 [9abbd945] + Profile v1.11.0 [9a3f8284] + Random v1.11.0 [ea8e919c] + SHA v0.7.0 [9e88b42a] + Serialization v1.11.0 [2f01184e] + SparseArrays v1.11.0 [4607b0f0] + SuiteSparse [fa267f1f] + TOML v1.0.3 [a4e569a6] + Tar v1.10.0 [8dfed614] + Test v1.11.0 [cf7118a7] + UUIDs v1.11.0 [4ec0a83e] + Unicode v1.11.0 [e66e0078] + CompilerSupportLibraries_jll v1.1.1+0 [781609d7] + GMP_jll v6.3.0+0 [deac9b47] + LibCURL_jll v8.6.0+0 [e37daf67] + LibGit2_jll v1.7.2+0 [29816b5a] + LibSSH2_jll v1.11.0+1 [c8ffd9c3] + MbedTLS_jll v2.28.6+0 [14a3606d] + MozillaCACerts_jll v2023.12.12 [4536629a] + OpenBLAS_jll v0.3.27+1 [05823500] + OpenLibm_jll v0.8.1+2 [bea87d4a] + SuiteSparse_jll v7.7.0+0 [83775a58] + Zlib_jll v1.2.13+1 [8e850b90] + libblastrampoline_jll v5.11.0+0 [8e850ede] + nghttp2_jll v1.59.0+0 [3f19e933] + p7zip_jll v17.4.0+2  Info Packages marked with ⌃ and ⌅ have new versions available. Those with ⌃ may be upgradable, but those with ⌅ are restricted by compatibility constraints from upgrading. To see why use `status --outdated -m` Instantiating... === Precompiling... ===  Activating project at `/tmp/jl_oDhDHt` Precompiling project... 2069.6 ms ✓ BenchmarkTools 3026.9 ms ✓ PlutoTest 114333.0 ms ✓ MathOptInterface 3610.9 ms ✓ ExactOptimalTransport 5661.8 ms ✓ OptimalTransport 9560.8 ms ✓ GLPK 6 dependencies successfully precompiled in 127 seconds. 123 already precompiled.ªnbpkg_syncÚ)§ Instantiating... === ┌ Warning: The active manifest file has dependencies that were resolved with a different julia version (1.8.2). Unexpected behavior may occur. â”” @ /tmp/jl_oDhDHt/Manifest.toml:0  Installed DiffRules ──────── v1.12.1 Installed Parsers ────────── v2.5.0  Installed PlutoUI ────────── v0.7.48  Installed ForwardDiff ────── v0.10.32  Installed NNlib ──────────── v0.8.10  Installed GLPK ───────────── v1.1.0  Installed Distributions ──── v0.25.77  Installed MathOptInterface ─ v1.9.0  Resolving... === ┌ Info: Operation failed. Updating registries and trying again... │  exception = │  Unsatisfiable requirements detected for package SortingAlgorithms [a2af1166]: │  SortingAlgorithms [a2af1166] log: │  ├─possible versions are: 0.3.0 - 1.2.1 or uninstalled │  ├─restricted to versions 1.0.1 by an explicit requirement, leaving only versions: 1.0.1 â””  └─restricted by julia compatibility requirements to versions: 1.1.0 - 1.2.1 or uninstalled — no versions left Resolving... === ┌ Warning: Operation failed. Removing Manifest and trying again... │  exception = │  Unsatisfiable requirements detected for package SortingAlgorithms [a2af1166]: │  SortingAlgorithms [a2af1166] log: │  ├─possible versions are: 0.3.0 - 1.2.1 or uninstalled │  ├─restricted to versions 1.0.1 by an explicit requirement, leaving only versions: 1.0.1 │  └─restricted by julia compatibility requirements to versions: 1.1.0 - 1.2.1 or uninstalled — no versions left â”” @ Pluto ~/.julia/packages/Pluto/6smog/src/packages/Packages.jl:494 Resolving... ===  Installed GLPK ─ v1.1.3 Updating `/tmp/jl_oDhDHt/Project.toml`  ⌅ [6e4b80f9] + BenchmarkTools v1.3.2 ⌅ [60bf3e95] + GLPK v1.1.3 [7e02d93a] + OptimalTransport v0.3.19 [cb4044da] + PlutoTest v0.2.2 [7f904dfe] + PlutoUI v0.7.60 [37e2e46d] ~ LinearAlgebra ⇒ v1.11.0  Updating `/tmp/jl_oDhDHt/Manifest.toml` [6e696c72] + AbstractPlutoDingetjes v1.3.2 ⌅ [79e6a3ab] + Adapt v3.7.2 [66dad0bd] + AliasTables v1.1.3 [a9b6321e] + Atomix v0.1.0 ⌅ [6e4b80f9] + BenchmarkTools v1.3.2 [fa961155] + CEnum v0.5.0 [d360d2e6] + ChainRulesCore v1.25.0 [523fee87] + CodecBzip2 v0.8.4 [944b1d66] + CodecZlib v0.7.6 [3da002f7] + ColorTypes v0.11.5 [bbf7d656] + CommonSubexpressions v0.3.1 [34da2185] + Compat v4.16.0 [9a962f9c] + DataAPI v1.16.0 [864edb3b] + DataStructures v0.18.20 [163ba53b] + DiffResults v1.1.0 [b552c78f] + DiffRules v1.15.1 [b4f34e82] + Distances v0.10.11 [31c24e10] + Distributions v0.25.112 [ffbed154] + DocStringExtensions v0.9.3 [24df6009] + ExactOptimalTransport v0.2.5 [1a297f60] + FillArrays v1.13.0 [53c48c17] + FixedPointNumbers v0.8.5 [f6369f11] + ForwardDiff v0.10.36 ⌅ [60bf3e95] + GLPK v1.1.3 ⌃ [46192b85] + GPUArraysCore v0.1.5 [34004b35] + HypergeometricFunctions v0.3.24 [47d2ed2b] + Hyperscript v0.0.5 [ac1192a8] + HypertextLiteral v0.9.5 [b5f81e59] + IOCapture v0.2.5 [92d709cd] + IrrationalConstants v0.2.2 [42fd0dbc] + IterativeSolvers v0.9.4 [692b3bcd] + JLLWrappers v1.6.1 [682c06a0] + JSON v0.21.4 [63c18a36] + KernelAbstractions v0.9.28 [929cbde3] + LLVM v9.1.2 [2ab3a3ac] + LogExpFunctions v0.3.28 [6c6e2e6c] + MIMEs v0.1.4 [1914dd2f] + MacroTools v0.5.13 [b8f27783] + MathOptInterface v1.31.2 [e1d29d7a] + Missings v1.2.0 [d8a4904e] + MutableArithmetics v1.5.1 ⌅ [872c559c] + NNlib v0.8.21 [77ba4419] + NaNMath v1.0.2 [7e02d93a] + OptimalTransport v0.3.19 [bac558e1] + OrderedCollections v1.6.3 [90014a1f] + PDMats v0.11.31 [69de0a69] + Parsers v2.8.1 [cb4044da] + PlutoTest v0.2.2 [7f904dfe] + PlutoUI v0.7.60 [aea7be01] + PrecompileTools v1.2.1 [21216c6a] + Preferences v1.4.3 [43287f4e] + PtrArrays v1.2.1 [1fd47b50] + QuadGK v2.11.1 [3cdcf5f2] + RecipesBase v1.3.4 [189a3867] + Reexport v1.2.2 [ae029012] + Requires v1.3.0 [79098fc4] + Rmath v0.8.0 [a2af1166] + SortingAlgorithms v1.2.1 [276daf66] + SpecialFunctions v2.4.0 [90137ffa] + StaticArrays v1.9.7 [1e83bf80] + StaticArraysCore v1.4.3 [10745b16] + Statistics v1.11.1 [82ae8749] + StatsAPI v1.7.0 [2913bbd2] + StatsBase v0.34.3 [4c63d2b9] + StatsFuns v1.3.2 [3bb67fe8] + TranscodingStreams v0.11.3 [410a4b4d] + Tricks v0.1.9 [5c2747f8] + URIs v1.5.1 [013be700] + UnsafeAtomics v0.2.1 [d80eeb9a] + UnsafeAtomicsLLVM v0.2.1 [6e34b625] + Bzip2_jll v1.0.8+1 [e8aa6df9] + GLPK_jll v5.0.1+0 [dad2f222] + LLVMExtra_jll v0.0.34+0 [efe28fd5] + OpenSpecFun_jll v0.5.5+0 [f50d1b31] + Rmath_jll v0.5.1+0 [0dad84c5] + ArgTools v1.1.2 [56f22d72] + Artifacts v1.11.0 [2a0f44e3] + Base64 v1.11.0 [ade2ca70] + Dates v1.11.0 [f43a241f] + Downloads v1.6.0 [7b1f6079] + FileWatching v1.11.0 [b77e0a4c] + InteractiveUtils v1.11.0 [4af54fe1] + LazyArtifacts v1.11.0 [b27032c2] + LibCURL v0.6.4 [76f85450] + LibGit2 v1.11.0 [8f399da3] + Libdl v1.11.0 [37e2e46d] + LinearAlgebra v1.11.0 [56ddb016] + Logging v1.11.0 [d6f4376e] + Markdown v1.11.0 [a63ad114] + Mmap v1.11.0 [ca575930] + NetworkOptions v1.2.0 [44cfe95a] + Pkg v1.11.0 [de0858da] + Printf v1.11.0 [9abbd945] + Profile v1.11.0 [9a3f8284] + Random v1.11.0 [ea8e919c] + SHA v0.7.0 [9e88b42a] + Serialization v1.11.0 [2f01184e] + SparseArrays v1.11.0 [4607b0f0] + SuiteSparse [fa267f1f] + TOML v1.0.3 [a4e569a6] + Tar v1.10.0 [8dfed614] + Test v1.11.0 [cf7118a7] + UUIDs v1.11.0 [4ec0a83e] + Unicode v1.11.0 [e66e0078] + CompilerSupportLibraries_jll v1.1.1+0 [781609d7] + GMP_jll v6.3.0+0 [deac9b47] + LibCURL_jll v8.6.0+0 [e37daf67] + LibGit2_jll v1.7.2+0 [29816b5a] + LibSSH2_jll v1.11.0+1 [c8ffd9c3] + MbedTLS_jll v2.28.6+0 [14a3606d] + MozillaCACerts_jll v2023.12.12 [4536629a] + OpenBLAS_jll v0.3.27+1 [05823500] + OpenLibm_jll v0.8.1+2 [bea87d4a] + SuiteSparse_jll v7.7.0+0 [83775a58] + Zlib_jll v1.2.13+1 [8e850b90] + libblastrampoline_jll v5.11.0+0 [8e850ede] + nghttp2_jll v1.59.0+0 [3f19e933] + p7zip_jll v17.4.0+2  Info Packages marked with ⌃ and ⌅ have new versions available. Those with ⌃ may be upgradable, but those with ⌅ are restricted by compatibility constraints from upgrading. To see why use `status --outdated -m` Instantiating... === Precompiling... ===  Activating project at `/tmp/jl_oDhDHt` Precompiling project... 2069.6 ms ✓ BenchmarkTools 3026.9 ms ✓ PlutoTest 114333.0 ms ✓ MathOptInterface 3610.9 ms ✓ ExactOptimalTransport 5661.8 ms ✓ OptimalTransport 9560.8 ms ✓ GLPK 6 dependencies successfully precompiled in 127 seconds. 123 already precompiled.­LinearAlgebraÚ)§ Instantiating... === ┌ Warning: The active manifest file has dependencies that were resolved with a different julia version (1.8.2). Unexpected behavior may occur. â”” @ /tmp/jl_oDhDHt/Manifest.toml:0  Installed DiffRules ──────── v1.12.1 Installed Parsers ────────── v2.5.0  Installed PlutoUI ────────── v0.7.48  Installed ForwardDiff ────── v0.10.32  Installed NNlib ──────────── v0.8.10  Installed GLPK ───────────── v1.1.0  Installed Distributions ──── v0.25.77  Installed MathOptInterface ─ v1.9.0  Resolving... === ┌ Info: Operation failed. Updating registries and trying again... │  exception = │  Unsatisfiable requirements detected for package SortingAlgorithms [a2af1166]: │  SortingAlgorithms [a2af1166] log: │  ├─possible versions are: 0.3.0 - 1.2.1 or uninstalled │  ├─restricted to versions 1.0.1 by an explicit requirement, leaving only versions: 1.0.1 â””  └─restricted by julia compatibility requirements to versions: 1.1.0 - 1.2.1 or uninstalled — no versions left Resolving... === ┌ Warning: Operation failed. Removing Manifest and trying again... │  exception = │  Unsatisfiable requirements detected for package SortingAlgorithms [a2af1166]: │  SortingAlgorithms [a2af1166] log: │  ├─possible versions are: 0.3.0 - 1.2.1 or uninstalled │  ├─restricted to versions 1.0.1 by an explicit requirement, leaving only versions: 1.0.1 │  └─restricted by julia compatibility requirements to versions: 1.1.0 - 1.2.1 or uninstalled — no versions left â”” @ Pluto ~/.julia/packages/Pluto/6smog/src/packages/Packages.jl:494 Resolving... ===  Installed GLPK ─ v1.1.3 Updating `/tmp/jl_oDhDHt/Project.toml`  ⌅ [6e4b80f9] + BenchmarkTools v1.3.2 ⌅ [60bf3e95] + GLPK v1.1.3 [7e02d93a] + OptimalTransport v0.3.19 [cb4044da] + PlutoTest v0.2.2 [7f904dfe] + PlutoUI v0.7.60 [37e2e46d] ~ LinearAlgebra ⇒ v1.11.0  Updating `/tmp/jl_oDhDHt/Manifest.toml` [6e696c72] + AbstractPlutoDingetjes v1.3.2 ⌅ [79e6a3ab] + Adapt v3.7.2 [66dad0bd] + AliasTables v1.1.3 [a9b6321e] + Atomix v0.1.0 ⌅ [6e4b80f9] + BenchmarkTools v1.3.2 [fa961155] + CEnum v0.5.0 [d360d2e6] + ChainRulesCore v1.25.0 [523fee87] + CodecBzip2 v0.8.4 [944b1d66] + CodecZlib v0.7.6 [3da002f7] + ColorTypes v0.11.5 [bbf7d656] + CommonSubexpressions v0.3.1 [34da2185] + Compat v4.16.0 [9a962f9c] + DataAPI v1.16.0 [864edb3b] + DataStructures v0.18.20 [163ba53b] + DiffResults v1.1.0 [b552c78f] + DiffRules v1.15.1 [b4f34e82] + Distances v0.10.11 [31c24e10] + Distributions v0.25.112 [ffbed154] + DocStringExtensions v0.9.3 [24df6009] + ExactOptimalTransport v0.2.5 [1a297f60] + FillArrays v1.13.0 [53c48c17] + FixedPointNumbers v0.8.5 [f6369f11] + ForwardDiff v0.10.36 ⌅ [60bf3e95] + GLPK v1.1.3 ⌃ [46192b85] + GPUArraysCore v0.1.5 [34004b35] + HypergeometricFunctions v0.3.24 [47d2ed2b] + Hyperscript v0.0.5 [ac1192a8] + HypertextLiteral v0.9.5 [b5f81e59] + IOCapture v0.2.5 [92d709cd] + IrrationalConstants v0.2.2 [42fd0dbc] + IterativeSolvers v0.9.4 [692b3bcd] + JLLWrappers v1.6.1 [682c06a0] + JSON v0.21.4 [63c18a36] + KernelAbstractions v0.9.28 [929cbde3] + LLVM v9.1.2 [2ab3a3ac] + LogExpFunctions v0.3.28 [6c6e2e6c] + MIMEs v0.1.4 [1914dd2f] + MacroTools v0.5.13 [b8f27783] + MathOptInterface v1.31.2 [e1d29d7a] + Missings v1.2.0 [d8a4904e] + MutableArithmetics v1.5.1 ⌅ [872c559c] + NNlib v0.8.21 [77ba4419] + NaNMath v1.0.2 [7e02d93a] + OptimalTransport v0.3.19 [bac558e1] + OrderedCollections v1.6.3 [90014a1f] + PDMats v0.11.31 [69de0a69] + Parsers v2.8.1 [cb4044da] + PlutoTest v0.2.2 [7f904dfe] + PlutoUI v0.7.60 [aea7be01] + PrecompileTools v1.2.1 [21216c6a] + Preferences v1.4.3 [43287f4e] + PtrArrays v1.2.1 [1fd47b50] + QuadGK v2.11.1 [3cdcf5f2] + RecipesBase v1.3.4 [189a3867] + Reexport v1.2.2 [ae029012] + Requires v1.3.0 [79098fc4] + Rmath v0.8.0 [a2af1166] + SortingAlgorithms v1.2.1 [276daf66] + SpecialFunctions v2.4.0 [90137ffa] + StaticArrays v1.9.7 [1e83bf80] + StaticArraysCore v1.4.3 [10745b16] + Statistics v1.11.1 [82ae8749] + StatsAPI v1.7.0 [2913bbd2] + StatsBase v0.34.3 [4c63d2b9] + StatsFuns v1.3.2 [3bb67fe8] + TranscodingStreams v0.11.3 [410a4b4d] + Tricks v0.1.9 [5c2747f8] + URIs v1.5.1 [013be700] + UnsafeAtomics v0.2.1 [d80eeb9a] + UnsafeAtomicsLLVM v0.2.1 [6e34b625] + Bzip2_jll v1.0.8+1 [e8aa6df9] + GLPK_jll v5.0.1+0 [dad2f222] + LLVMExtra_jll v0.0.34+0 [efe28fd5] + OpenSpecFun_jll v0.5.5+0 [f50d1b31] + Rmath_jll v0.5.1+0 [0dad84c5] + ArgTools v1.1.2 [56f22d72] + Artifacts v1.11.0 [2a0f44e3] + Base64 v1.11.0 [ade2ca70] + Dates v1.11.0 [f43a241f] + Downloads v1.6.0 [7b1f6079] + FileWatching v1.11.0 [b77e0a4c] + InteractiveUtils v1.11.0 [4af54fe1] + LazyArtifacts v1.11.0 [b27032c2] + LibCURL v0.6.4 [76f85450] + LibGit2 v1.11.0 [8f399da3] + Libdl v1.11.0 [37e2e46d] + LinearAlgebra v1.11.0 [56ddb016] + Logging v1.11.0 [d6f4376e] + Markdown v1.11.0 [a63ad114] + Mmap v1.11.0 [ca575930] + NetworkOptions v1.2.0 [44cfe95a] + Pkg v1.11.0 [de0858da] + Printf v1.11.0 [9abbd945] + Profile v1.11.0 [9a3f8284] + Random v1.11.0 [ea8e919c] + SHA v0.7.0 [9e88b42a] + Serialization v1.11.0 [2f01184e] + SparseArrays v1.11.0 [4607b0f0] + SuiteSparse [fa267f1f] + TOML v1.0.3 [a4e569a6] + Tar v1.10.0 [8dfed614] + Test v1.11.0 [cf7118a7] + UUIDs v1.11.0 [4ec0a83e] + Unicode v1.11.0 [e66e0078] + CompilerSupportLibraries_jll v1.1.1+0 [781609d7] + GMP_jll v6.3.0+0 [deac9b47] + LibCURL_jll v8.6.0+0 [e37daf67] + LibGit2_jll v1.7.2+0 [29816b5a] + LibSSH2_jll v1.11.0+1 [c8ffd9c3] + MbedTLS_jll v2.28.6+0 [14a3606d] + MozillaCACerts_jll v2023.12.12 [4536629a] + OpenBLAS_jll v0.3.27+1 [05823500] + OpenLibm_jll v0.8.1+2 [bea87d4a] + SuiteSparse_jll v7.7.0+0 [83775a58] + Zlib_jll v1.2.13+1 [8e850b90] + libblastrampoline_jll v5.11.0+0 [8e850ede] + nghttp2_jll v1.59.0+0 [3f19e933] + p7zip_jll v17.4.0+2  Info Packages marked with ⌃ and ⌅ have new versions available. Those with ⌃ may be upgradable, but those with ⌅ are restricted by compatibility constraints from upgrading. To see why use `status --outdated -m` Instantiating... === Precompiling... ===  Activating project at `/tmp/jl_oDhDHt` Precompiling project... 2069.6 ms ✓ BenchmarkTools 3026.9 ms ✓ PlutoTest 114333.0 ms ✓ MathOptInterface 3610.9 ms ✓ ExactOptimalTransport 5661.8 ms ✓ OptimalTransport 9560.8 ms ✓ GLPK 6 dependencies successfully precompiled in 127 seconds. 123 already precompiled.§PlutoUIÚ)§ Instantiating... === ┌ Warning: The active manifest file has dependencies that were resolved with a different julia version (1.8.2). Unexpected behavior may occur. â”” @ /tmp/jl_oDhDHt/Manifest.toml:0  Installed DiffRules ──────── v1.12.1 Installed Parsers ────────── v2.5.0  Installed PlutoUI ────────── v0.7.48  Installed ForwardDiff ────── v0.10.32  Installed NNlib ──────────── v0.8.10  Installed GLPK ───────────── v1.1.0  Installed Distributions ──── v0.25.77  Installed MathOptInterface ─ v1.9.0  Resolving... === ┌ Info: Operation failed. Updating registries and trying again... │  exception = │  Unsatisfiable requirements detected for package SortingAlgorithms [a2af1166]: │  SortingAlgorithms [a2af1166] log: │  ├─possible versions are: 0.3.0 - 1.2.1 or uninstalled │  ├─restricted to versions 1.0.1 by an explicit requirement, leaving only versions: 1.0.1 â””  └─restricted by julia compatibility requirements to versions: 1.1.0 - 1.2.1 or uninstalled — no versions left Resolving... === ┌ Warning: Operation failed. Removing Manifest and trying again... │  exception = │  Unsatisfiable requirements detected for package SortingAlgorithms [a2af1166]: │  SortingAlgorithms [a2af1166] log: │  ├─possible versions are: 0.3.0 - 1.2.1 or uninstalled │  ├─restricted to versions 1.0.1 by an explicit requirement, leaving only versions: 1.0.1 │  └─restricted by julia compatibility requirements to versions: 1.1.0 - 1.2.1 or uninstalled — no versions left â”” @ Pluto ~/.julia/packages/Pluto/6smog/src/packages/Packages.jl:494 Resolving... ===  Installed GLPK ─ v1.1.3 Updating `/tmp/jl_oDhDHt/Project.toml`  ⌅ [6e4b80f9] + BenchmarkTools v1.3.2 ⌅ [60bf3e95] + GLPK v1.1.3 [7e02d93a] + OptimalTransport v0.3.19 [cb4044da] + PlutoTest v0.2.2 [7f904dfe] + PlutoUI v0.7.60 [37e2e46d] ~ LinearAlgebra ⇒ v1.11.0  Updating `/tmp/jl_oDhDHt/Manifest.toml` [6e696c72] + AbstractPlutoDingetjes v1.3.2 ⌅ [79e6a3ab] + Adapt v3.7.2 [66dad0bd] + AliasTables v1.1.3 [a9b6321e] + Atomix v0.1.0 ⌅ [6e4b80f9] + BenchmarkTools v1.3.2 [fa961155] + CEnum v0.5.0 [d360d2e6] + ChainRulesCore v1.25.0 [523fee87] + CodecBzip2 v0.8.4 [944b1d66] + CodecZlib v0.7.6 [3da002f7] + ColorTypes v0.11.5 [bbf7d656] + CommonSubexpressions v0.3.1 [34da2185] + Compat v4.16.0 [9a962f9c] + DataAPI v1.16.0 [864edb3b] + DataStructures v0.18.20 [163ba53b] + DiffResults v1.1.0 [b552c78f] + DiffRules v1.15.1 [b4f34e82] + Distances v0.10.11 [31c24e10] + Distributions v0.25.112 [ffbed154] + DocStringExtensions v0.9.3 [24df6009] + ExactOptimalTransport v0.2.5 [1a297f60] + FillArrays v1.13.0 [53c48c17] + FixedPointNumbers v0.8.5 [f6369f11] + ForwardDiff v0.10.36 ⌅ [60bf3e95] + GLPK v1.1.3 ⌃ [46192b85] + GPUArraysCore v0.1.5 [34004b35] + HypergeometricFunctions v0.3.24 [47d2ed2b] + Hyperscript v0.0.5 [ac1192a8] + HypertextLiteral v0.9.5 [b5f81e59] + IOCapture v0.2.5 [92d709cd] + IrrationalConstants v0.2.2 [42fd0dbc] + IterativeSolvers v0.9.4 [692b3bcd] + JLLWrappers v1.6.1 [682c06a0] + JSON v0.21.4 [63c18a36] + KernelAbstractions v0.9.28 [929cbde3] + LLVM v9.1.2 [2ab3a3ac] + LogExpFunctions v0.3.28 [6c6e2e6c] + MIMEs v0.1.4 [1914dd2f] + MacroTools v0.5.13 [b8f27783] + MathOptInterface v1.31.2 [e1d29d7a] + Missings v1.2.0 [d8a4904e] + MutableArithmetics v1.5.1 ⌅ [872c559c] + NNlib v0.8.21 [77ba4419] + NaNMath v1.0.2 [7e02d93a] + OptimalTransport v0.3.19 [bac558e1] + OrderedCollections v1.6.3 [90014a1f] + PDMats v0.11.31 [69de0a69] + Parsers v2.8.1 [cb4044da] + PlutoTest v0.2.2 [7f904dfe] + PlutoUI v0.7.60 [aea7be01] + PrecompileTools v1.2.1 [21216c6a] + Preferences v1.4.3 [43287f4e] + PtrArrays v1.2.1 [1fd47b50] + QuadGK v2.11.1 [3cdcf5f2] + RecipesBase v1.3.4 [189a3867] + Reexport v1.2.2 [ae029012] + Requires v1.3.0 [79098fc4] + Rmath v0.8.0 [a2af1166] + SortingAlgorithms v1.2.1 [276daf66] + SpecialFunctions v2.4.0 [90137ffa] + StaticArrays v1.9.7 [1e83bf80] + StaticArraysCore v1.4.3 [10745b16] + Statistics v1.11.1 [82ae8749] + StatsAPI v1.7.0 [2913bbd2] + StatsBase v0.34.3 [4c63d2b9] + StatsFuns v1.3.2 [3bb67fe8] + TranscodingStreams v0.11.3 [410a4b4d] + Tricks v0.1.9 [5c2747f8] + URIs v1.5.1 [013be700] + UnsafeAtomics v0.2.1 [d80eeb9a] + UnsafeAtomicsLLVM v0.2.1 [6e34b625] + Bzip2_jll v1.0.8+1 [e8aa6df9] + GLPK_jll v5.0.1+0 [dad2f222] + LLVMExtra_jll v0.0.34+0 [efe28fd5] + OpenSpecFun_jll v0.5.5+0 [f50d1b31] + Rmath_jll v0.5.1+0 [0dad84c5] + ArgTools v1.1.2 [56f22d72] + Artifacts v1.11.0 [2a0f44e3] + Base64 v1.11.0 [ade2ca70] + Dates v1.11.0 [f43a241f] + Downloads v1.6.0 [7b1f6079] + FileWatching v1.11.0 [b77e0a4c] + InteractiveUtils v1.11.0 [4af54fe1] + LazyArtifacts v1.11.0 [b27032c2] + LibCURL v0.6.4 [76f85450] + LibGit2 v1.11.0 [8f399da3] + Libdl v1.11.0 [37e2e46d] + LinearAlgebra v1.11.0 [56ddb016] + Logging v1.11.0 [d6f4376e] + Markdown v1.11.0 [a63ad114] + Mmap v1.11.0 [ca575930] + NetworkOptions v1.2.0 [44cfe95a] + Pkg v1.11.0 [de0858da] + Printf v1.11.0 [9abbd945] + Profile v1.11.0 [9a3f8284] + Random v1.11.0 [ea8e919c] + SHA v0.7.0 [9e88b42a] + Serialization v1.11.0 [2f01184e] + SparseArrays v1.11.0 [4607b0f0] + SuiteSparse [fa267f1f] + TOML v1.0.3 [a4e569a6] + Tar v1.10.0 [8dfed614] + Test v1.11.0 [cf7118a7] + UUIDs v1.11.0 [4ec0a83e] + Unicode v1.11.0 [e66e0078] + CompilerSupportLibraries_jll v1.1.1+0 [781609d7] + GMP_jll v6.3.0+0 [deac9b47] + LibCURL_jll v8.6.0+0 [e37daf67] + LibGit2_jll v1.7.2+0 [29816b5a] + LibSSH2_jll v1.11.0+1 [c8ffd9c3] + MbedTLS_jll v2.28.6+0 [14a3606d] + MozillaCACerts_jll v2023.12.12 [4536629a] + OpenBLAS_jll v0.3.27+1 [05823500] + OpenLibm_jll v0.8.1+2 [bea87d4a] + SuiteSparse_jll v7.7.0+0 [83775a58] + Zlib_jll v1.2.13+1 [8e850b90] + libblastrampoline_jll v5.11.0+0 [8e850ede] + nghttp2_jll v1.59.0+0 [3f19e933] + p7zip_jll v17.4.0+2  Info Packages marked with ⌃ and ⌅ have new versions available. Those with ⌃ may be upgradable, but those with ⌅ are restricted by compatibility constraints from upgrading. To see why use `status --outdated -m` Instantiating... === Precompiling... ===  Activating project at `/tmp/jl_oDhDHt` Precompiling project... 2069.6 ms ✓ BenchmarkTools 3026.9 ms ✓ PlutoTest 114333.0 ms ✓ MathOptInterface 3610.9 ms ✓ ExactOptimalTransport 5661.8 ms ✓ OptimalTransport 9560.8 ms ✓ GLPK 6 dependencies successfully precompiled in 127 seconds. 123 already precompiled.©PlutoTestÚ)§ Instantiating... === ┌ Warning: The active manifest file has dependencies that were resolved with a different julia version (1.8.2). Unexpected behavior may occur. â”” @ /tmp/jl_oDhDHt/Manifest.toml:0  Installed DiffRules ──────── v1.12.1 Installed Parsers ────────── v2.5.0  Installed PlutoUI ────────── v0.7.48  Installed ForwardDiff ────── v0.10.32  Installed NNlib ──────────── v0.8.10  Installed GLPK ───────────── v1.1.0  Installed Distributions ──── v0.25.77  Installed MathOptInterface ─ v1.9.0  Resolving... === ┌ Info: Operation failed. Updating registries and trying again... │  exception = │  Unsatisfiable requirements detected for package SortingAlgorithms [a2af1166]: │  SortingAlgorithms [a2af1166] log: │  ├─possible versions are: 0.3.0 - 1.2.1 or uninstalled │  ├─restricted to versions 1.0.1 by an explicit requirement, leaving only versions: 1.0.1 â””  └─restricted by julia compatibility requirements to versions: 1.1.0 - 1.2.1 or uninstalled — no versions left Resolving... === ┌ Warning: Operation failed. Removing Manifest and trying again... │  exception = │  Unsatisfiable requirements detected for package SortingAlgorithms [a2af1166]: │  SortingAlgorithms [a2af1166] log: │  ├─possible versions are: 0.3.0 - 1.2.1 or uninstalled │  ├─restricted to versions 1.0.1 by an explicit requirement, leaving only versions: 1.0.1 │  └─restricted by julia compatibility requirements to versions: 1.1.0 - 1.2.1 or uninstalled — no versions left â”” @ Pluto ~/.julia/packages/Pluto/6smog/src/packages/Packages.jl:494 Resolving... ===  Installed GLPK ─ v1.1.3 Updating `/tmp/jl_oDhDHt/Project.toml`  ⌅ [6e4b80f9] + BenchmarkTools v1.3.2 ⌅ [60bf3e95] + GLPK v1.1.3 [7e02d93a] + OptimalTransport v0.3.19 [cb4044da] + PlutoTest v0.2.2 [7f904dfe] + PlutoUI v0.7.60 [37e2e46d] ~ LinearAlgebra ⇒ v1.11.0  Updating `/tmp/jl_oDhDHt/Manifest.toml` [6e696c72] + AbstractPlutoDingetjes v1.3.2 ⌅ [79e6a3ab] + Adapt v3.7.2 [66dad0bd] + AliasTables v1.1.3 [a9b6321e] + Atomix v0.1.0 ⌅ [6e4b80f9] + BenchmarkTools v1.3.2 [fa961155] + CEnum v0.5.0 [d360d2e6] + ChainRulesCore v1.25.0 [523fee87] + CodecBzip2 v0.8.4 [944b1d66] + CodecZlib v0.7.6 [3da002f7] + ColorTypes v0.11.5 [bbf7d656] + CommonSubexpressions v0.3.1 [34da2185] + Compat v4.16.0 [9a962f9c] + DataAPI v1.16.0 [864edb3b] + DataStructures v0.18.20 [163ba53b] + DiffResults v1.1.0 [b552c78f] + DiffRules v1.15.1 [b4f34e82] + Distances v0.10.11 [31c24e10] + Distributions v0.25.112 [ffbed154] + DocStringExtensions v0.9.3 [24df6009] + ExactOptimalTransport v0.2.5 [1a297f60] + FillArrays v1.13.0 [53c48c17] + FixedPointNumbers v0.8.5 [f6369f11] + ForwardDiff v0.10.36 ⌅ [60bf3e95] + GLPK v1.1.3 ⌃ [46192b85] + GPUArraysCore v0.1.5 [34004b35] + HypergeometricFunctions v0.3.24 [47d2ed2b] + Hyperscript v0.0.5 [ac1192a8] + HypertextLiteral v0.9.5 [b5f81e59] + IOCapture v0.2.5 [92d709cd] + IrrationalConstants v0.2.2 [42fd0dbc] + IterativeSolvers v0.9.4 [692b3bcd] + JLLWrappers v1.6.1 [682c06a0] + JSON v0.21.4 [63c18a36] + KernelAbstractions v0.9.28 [929cbde3] + LLVM v9.1.2 [2ab3a3ac] + LogExpFunctions v0.3.28 [6c6e2e6c] + MIMEs v0.1.4 [1914dd2f] + MacroTools v0.5.13 [b8f27783] + MathOptInterface v1.31.2 [e1d29d7a] + Missings v1.2.0 [d8a4904e] + MutableArithmetics v1.5.1 ⌅ [872c559c] + NNlib v0.8.21 [77ba4419] + NaNMath v1.0.2 [7e02d93a] + OptimalTransport v0.3.19 [bac558e1] + OrderedCollections v1.6.3 [90014a1f] + PDMats v0.11.31 [69de0a69] + Parsers v2.8.1 [cb4044da] + PlutoTest v0.2.2 [7f904dfe] + PlutoUI v0.7.60 [aea7be01] + PrecompileTools v1.2.1 [21216c6a] + Preferences v1.4.3 [43287f4e] + PtrArrays v1.2.1 [1fd47b50] + QuadGK v2.11.1 [3cdcf5f2] + RecipesBase v1.3.4 [189a3867] + Reexport v1.2.2 [ae029012] + Requires v1.3.0 [79098fc4] + Rmath v0.8.0 [a2af1166] + SortingAlgorithms v1.2.1 [276daf66] + SpecialFunctions v2.4.0 [90137ffa] + StaticArrays v1.9.7 [1e83bf80] + StaticArraysCore v1.4.3 [10745b16] + Statistics v1.11.1 [82ae8749] + StatsAPI v1.7.0 [2913bbd2] + StatsBase v0.34.3 [4c63d2b9] + StatsFuns v1.3.2 [3bb67fe8] + TranscodingStreams v0.11.3 [410a4b4d] + Tricks v0.1.9 [5c2747f8] + URIs v1.5.1 [013be700] + UnsafeAtomics v0.2.1 [d80eeb9a] + UnsafeAtomicsLLVM v0.2.1 [6e34b625] + Bzip2_jll v1.0.8+1 [e8aa6df9] + GLPK_jll v5.0.1+0 [dad2f222] + LLVMExtra_jll v0.0.34+0 [efe28fd5] + OpenSpecFun_jll v0.5.5+0 [f50d1b31] + Rmath_jll v0.5.1+0 [0dad84c5] + ArgTools v1.1.2 [56f22d72] + Artifacts v1.11.0 [2a0f44e3] + Base64 v1.11.0 [ade2ca70] + Dates v1.11.0 [f43a241f] + Downloads v1.6.0 [7b1f6079] + FileWatching v1.11.0 [b77e0a4c] + InteractiveUtils v1.11.0 [4af54fe1] + LazyArtifacts v1.11.0 [b27032c2] + LibCURL v0.6.4 [76f85450] + LibGit2 v1.11.0 [8f399da3] + Libdl v1.11.0 [37e2e46d] + LinearAlgebra v1.11.0 [56ddb016] + Logging v1.11.0 [d6f4376e] + Markdown v1.11.0 [a63ad114] + Mmap v1.11.0 [ca575930] + NetworkOptions v1.2.0 [44cfe95a] + Pkg v1.11.0 [de0858da] + Printf v1.11.0 [9abbd945] + Profile v1.11.0 [9a3f8284] + Random v1.11.0 [ea8e919c] + SHA v0.7.0 [9e88b42a] + Serialization v1.11.0 [2f01184e] + SparseArrays v1.11.0 [4607b0f0] + SuiteSparse [fa267f1f] + TOML v1.0.3 [a4e569a6] + Tar v1.10.0 [8dfed614] + Test v1.11.0 [cf7118a7] + UUIDs v1.11.0 [4ec0a83e] + Unicode v1.11.0 [e66e0078] + CompilerSupportLibraries_jll v1.1.1+0 [781609d7] + GMP_jll v6.3.0+0 [deac9b47] + LibCURL_jll v8.6.0+0 [e37daf67] + LibGit2_jll v1.7.2+0 [29816b5a] + LibSSH2_jll v1.11.0+1 [c8ffd9c3] + MbedTLS_jll v2.28.6+0 [14a3606d] + MozillaCACerts_jll v2023.12.12 [4536629a] + OpenBLAS_jll v0.3.27+1 [05823500] + OpenLibm_jll v0.8.1+2 [bea87d4a] + SuiteSparse_jll v7.7.0+0 [83775a58] + Zlib_jll v1.2.13+1 [8e850b90] + libblastrampoline_jll v5.11.0+0 [8e850ede] + nghttp2_jll v1.59.0+0 [3f19e933] + p7zip_jll v17.4.0+2  Info Packages marked with ⌃ and ⌅ have new versions available. Those with ⌃ may be upgradable, but those with ⌅ are restricted by compatibility constraints from upgrading. To see why use `status --outdated -m` Instantiating... === Precompiling... ===  Activating project at `/tmp/jl_oDhDHt` Precompiling project... 2069.6 ms ✓ BenchmarkTools 3026.9 ms ✓ PlutoTest 114333.0 ms ✓ MathOptInterface 3610.9 ms ✓ ExactOptimalTransport 5661.8 ms ✓ OptimalTransport 9560.8 ms ✓ GLPK 6 dependencies successfully precompiled in 127 seconds. 123 already precompiled.®BenchmarkToolsÚ)§ Instantiating... === ┌ Warning: The active manifest file has dependencies that were resolved with a different julia version (1.8.2). Unexpected behavior may occur. â”” @ /tmp/jl_oDhDHt/Manifest.toml:0  Installed DiffRules ──────── v1.12.1 Installed Parsers ────────── v2.5.0  Installed PlutoUI ────────── v0.7.48  Installed ForwardDiff ────── v0.10.32  Installed NNlib ──────────── v0.8.10  Installed GLPK ───────────── v1.1.0  Installed Distributions ──── v0.25.77  Installed MathOptInterface ─ v1.9.0  Resolving... === ┌ Info: Operation failed. Updating registries and trying again... │  exception = │  Unsatisfiable requirements detected for package SortingAlgorithms [a2af1166]: │  SortingAlgorithms [a2af1166] log: │  ├─possible versions are: 0.3.0 - 1.2.1 or uninstalled │  ├─restricted to versions 1.0.1 by an explicit requirement, leaving only versions: 1.0.1 â””  └─restricted by julia compatibility requirements to versions: 1.1.0 - 1.2.1 or uninstalled — no versions left Resolving... === ┌ Warning: Operation failed. Removing Manifest and trying again... │  exception = │  Unsatisfiable requirements detected for package SortingAlgorithms [a2af1166]: │  SortingAlgorithms [a2af1166] log: │  ├─possible versions are: 0.3.0 - 1.2.1 or uninstalled │  ├─restricted to versions 1.0.1 by an explicit requirement, leaving only versions: 1.0.1 │  └─restricted by julia compatibility requirements to versions: 1.1.0 - 1.2.1 or uninstalled — no versions left â”” @ Pluto ~/.julia/packages/Pluto/6smog/src/packages/Packages.jl:494 Resolving... ===  Installed GLPK ─ v1.1.3 Updating `/tmp/jl_oDhDHt/Project.toml`  ⌅ [6e4b80f9] + BenchmarkTools v1.3.2 ⌅ [60bf3e95] + GLPK v1.1.3 [7e02d93a] + OptimalTransport v0.3.19 [cb4044da] + PlutoTest v0.2.2 [7f904dfe] + PlutoUI v0.7.60 [37e2e46d] ~ LinearAlgebra ⇒ v1.11.0  Updating `/tmp/jl_oDhDHt/Manifest.toml` [6e696c72] + AbstractPlutoDingetjes v1.3.2 ⌅ [79e6a3ab] + Adapt v3.7.2 [66dad0bd] + AliasTables v1.1.3 [a9b6321e] + Atomix v0.1.0 ⌅ [6e4b80f9] + BenchmarkTools v1.3.2 [fa961155] + CEnum v0.5.0 [d360d2e6] + ChainRulesCore v1.25.0 [523fee87] + CodecBzip2 v0.8.4 [944b1d66] + CodecZlib v0.7.6 [3da002f7] + ColorTypes v0.11.5 [bbf7d656] + CommonSubexpressions v0.3.1 [34da2185] + Compat v4.16.0 [9a962f9c] + DataAPI v1.16.0 [864edb3b] + DataStructures v0.18.20 [163ba53b] + DiffResults v1.1.0 [b552c78f] + DiffRules v1.15.1 [b4f34e82] + Distances v0.10.11 [31c24e10] + Distributions v0.25.112 [ffbed154] + DocStringExtensions v0.9.3 [24df6009] + ExactOptimalTransport v0.2.5 [1a297f60] + FillArrays v1.13.0 [53c48c17] + FixedPointNumbers v0.8.5 [f6369f11] + ForwardDiff v0.10.36 ⌅ [60bf3e95] + GLPK v1.1.3 ⌃ [46192b85] + GPUArraysCore v0.1.5 [34004b35] + HypergeometricFunctions v0.3.24 [47d2ed2b] + Hyperscript v0.0.5 [ac1192a8] + HypertextLiteral v0.9.5 [b5f81e59] + IOCapture v0.2.5 [92d709cd] + IrrationalConstants v0.2.2 [42fd0dbc] + IterativeSolvers v0.9.4 [692b3bcd] + JLLWrappers v1.6.1 [682c06a0] + JSON v0.21.4 [63c18a36] + KernelAbstractions v0.9.28 [929cbde3] + LLVM v9.1.2 [2ab3a3ac] + LogExpFunctions v0.3.28 [6c6e2e6c] + MIMEs v0.1.4 [1914dd2f] + MacroTools v0.5.13 [b8f27783] + MathOptInterface v1.31.2 [e1d29d7a] + Missings v1.2.0 [d8a4904e] + MutableArithmetics v1.5.1 ⌅ [872c559c] + NNlib v0.8.21 [77ba4419] + NaNMath v1.0.2 [7e02d93a] + OptimalTransport v0.3.19 [bac558e1] + OrderedCollections v1.6.3 [90014a1f] + PDMats v0.11.31 [69de0a69] + Parsers v2.8.1 [cb4044da] + PlutoTest v0.2.2 [7f904dfe] + PlutoUI v0.7.60 [aea7be01] + PrecompileTools v1.2.1 [21216c6a] + Preferences v1.4.3 [43287f4e] + PtrArrays v1.2.1 [1fd47b50] + QuadGK v2.11.1 [3cdcf5f2] + RecipesBase v1.3.4 [189a3867] + Reexport v1.2.2 [ae029012] + Requires v1.3.0 [79098fc4] + Rmath v0.8.0 [a2af1166] + SortingAlgorithms v1.2.1 [276daf66] + SpecialFunctions v2.4.0 [90137ffa] + StaticArrays v1.9.7 [1e83bf80] + StaticArraysCore v1.4.3 [10745b16] + Statistics v1.11.1 [82ae8749] + StatsAPI v1.7.0 [2913bbd2] + StatsBase v0.34.3 [4c63d2b9] + StatsFuns v1.3.2 [3bb67fe8] + TranscodingStreams v0.11.3 [410a4b4d] + Tricks v0.1.9 [5c2747f8] + URIs v1.5.1 [013be700] + UnsafeAtomics v0.2.1 [d80eeb9a] + UnsafeAtomicsLLVM v0.2.1 [6e34b625] + Bzip2_jll v1.0.8+1 [e8aa6df9] + GLPK_jll v5.0.1+0 [dad2f222] + LLVMExtra_jll v0.0.34+0 [efe28fd5] + OpenSpecFun_jll v0.5.5+0 [f50d1b31] + Rmath_jll v0.5.1+0 [0dad84c5] + ArgTools v1.1.2 [56f22d72] + Artifacts v1.11.0 [2a0f44e3] + Base64 v1.11.0 [ade2ca70] + Dates v1.11.0 [f43a241f] + Downloads v1.6.0 [7b1f6079] + FileWatching v1.11.0 [b77e0a4c] + InteractiveUtils v1.11.0 [4af54fe1] + LazyArtifacts v1.11.0 [b27032c2] + LibCURL v0.6.4 [76f85450] + LibGit2 v1.11.0 [8f399da3] + Libdl v1.11.0 [37e2e46d] + LinearAlgebra v1.11.0 [56ddb016] + Logging v1.11.0 [d6f4376e] + Markdown v1.11.0 [a63ad114] + Mmap v1.11.0 [ca575930] + NetworkOptions v1.2.0 [44cfe95a] + Pkg v1.11.0 [de0858da] + Printf v1.11.0 [9abbd945] + Profile v1.11.0 [9a3f8284] + Random v1.11.0 [ea8e919c] + SHA v0.7.0 [9e88b42a] + Serialization v1.11.0 [2f01184e] + SparseArrays v1.11.0 [4607b0f0] + SuiteSparse [fa267f1f] + TOML v1.0.3 [a4e569a6] + Tar v1.10.0 [8dfed614] + Test v1.11.0 [cf7118a7] + UUIDs v1.11.0 [4ec0a83e] + Unicode v1.11.0 [e66e0078] + CompilerSupportLibraries_jll v1.1.1+0 [781609d7] + GMP_jll v6.3.0+0 [deac9b47] + LibCURL_jll v8.6.0+0 [e37daf67] + LibGit2_jll v1.7.2+0 [29816b5a] + LibSSH2_jll v1.11.0+1 [c8ffd9c3] + MbedTLS_jll v2.28.6+0 [14a3606d] + MozillaCACerts_jll v2023.12.12 [4536629a] + OpenBLAS_jll v0.3.27+1 [05823500] + OpenLibm_jll v0.8.1+2 [bea87d4a] + SuiteSparse_jll v7.7.0+0 [83775a58] + Zlib_jll v1.2.13+1 [8e850b90] + libblastrampoline_jll v5.11.0+0 [8e850ede] + nghttp2_jll v1.59.0+0 [3f19e933] + p7zip_jll v17.4.0+2  Info Packages marked with ⌃ and ⌅ have new versions available. Those with ⌃ may be upgradable, but those with ⌅ are restricted by compatibility constraints from upgrading. To see why use `status --outdated -m` Instantiating... === Precompiling... ===  Activating project at `/tmp/jl_oDhDHt` Precompiling project... 2069.6 ms ✓ BenchmarkTools 3026.9 ms ✓ PlutoTest 114333.0 ms ✓ MathOptInterface 3610.9 ms ✓ ExactOptimalTransport 5661.8 ms ✓ OptimalTransport 9560.8 ms ✓ GLPK 6 dependencies successfully precompiled in 127 seconds. 123 already precompiled.°OptimalTransportÚ)§ Instantiating... === ┌ Warning: The active manifest file has dependencies that were resolved with a different julia version (1.8.2). Unexpected behavior may occur. â”” @ /tmp/jl_oDhDHt/Manifest.toml:0  Installed DiffRules ──────── v1.12.1 Installed Parsers ────────── v2.5.0  Installed PlutoUI ────────── v0.7.48  Installed ForwardDiff ────── v0.10.32  Installed NNlib ──────────── v0.8.10  Installed GLPK ───────────── v1.1.0  Installed Distributions ──── v0.25.77  Installed MathOptInterface ─ v1.9.0  Resolving... === ┌ Info: Operation failed. Updating registries and trying again... │  exception = │  Unsatisfiable requirements detected for package SortingAlgorithms [a2af1166]: │  SortingAlgorithms [a2af1166] log: │  ├─possible versions are: 0.3.0 - 1.2.1 or uninstalled │  ├─restricted to versions 1.0.1 by an explicit requirement, leaving only versions: 1.0.1 â””  └─restricted by julia compatibility requirements to versions: 1.1.0 - 1.2.1 or uninstalled — no versions left Resolving... === ┌ Warning: Operation failed. Removing Manifest and trying again... │  exception = │  Unsatisfiable requirements detected for package SortingAlgorithms [a2af1166]: │  SortingAlgorithms [a2af1166] log: │  ├─possible versions are: 0.3.0 - 1.2.1 or uninstalled │  ├─restricted to versions 1.0.1 by an explicit requirement, leaving only versions: 1.0.1 │  └─restricted by julia compatibility requirements to versions: 1.1.0 - 1.2.1 or uninstalled — no versions left â”” @ Pluto ~/.julia/packages/Pluto/6smog/src/packages/Packages.jl:494 Resolving... ===  Installed GLPK ─ v1.1.3 Updating `/tmp/jl_oDhDHt/Project.toml`  ⌅ [6e4b80f9] + BenchmarkTools v1.3.2 ⌅ [60bf3e95] + GLPK v1.1.3 [7e02d93a] + OptimalTransport v0.3.19 [cb4044da] + PlutoTest v0.2.2 [7f904dfe] + PlutoUI v0.7.60 [37e2e46d] ~ LinearAlgebra ⇒ v1.11.0  Updating `/tmp/jl_oDhDHt/Manifest.toml` [6e696c72] + AbstractPlutoDingetjes v1.3.2 ⌅ [79e6a3ab] + Adapt v3.7.2 [66dad0bd] + AliasTables v1.1.3 [a9b6321e] + Atomix v0.1.0 ⌅ [6e4b80f9] + BenchmarkTools v1.3.2 [fa961155] + CEnum v0.5.0 [d360d2e6] + ChainRulesCore v1.25.0 [523fee87] + CodecBzip2 v0.8.4 [944b1d66] + CodecZlib v0.7.6 [3da002f7] + ColorTypes v0.11.5 [bbf7d656] + CommonSubexpressions v0.3.1 [34da2185] + Compat v4.16.0 [9a962f9c] + DataAPI v1.16.0 [864edb3b] + DataStructures v0.18.20 [163ba53b] + DiffResults v1.1.0 [b552c78f] + DiffRules v1.15.1 [b4f34e82] + Distances v0.10.11 [31c24e10] + Distributions v0.25.112 [ffbed154] + DocStringExtensions v0.9.3 [24df6009] + ExactOptimalTransport v0.2.5 [1a297f60] + FillArrays v1.13.0 [53c48c17] + FixedPointNumbers v0.8.5 [f6369f11] + ForwardDiff v0.10.36 ⌅ [60bf3e95] + GLPK v1.1.3 ⌃ [46192b85] + GPUArraysCore v0.1.5 [34004b35] + HypergeometricFunctions v0.3.24 [47d2ed2b] + Hyperscript v0.0.5 [ac1192a8] + HypertextLiteral v0.9.5 [b5f81e59] + IOCapture v0.2.5 [92d709cd] + IrrationalConstants v0.2.2 [42fd0dbc] + IterativeSolvers v0.9.4 [692b3bcd] + JLLWrappers v1.6.1 [682c06a0] + JSON v0.21.4 [63c18a36] + KernelAbstractions v0.9.28 [929cbde3] + LLVM v9.1.2 [2ab3a3ac] + LogExpFunctions v0.3.28 [6c6e2e6c] + MIMEs v0.1.4 [1914dd2f] + MacroTools v0.5.13 [b8f27783] + MathOptInterface v1.31.2 [e1d29d7a] + Missings v1.2.0 [d8a4904e] + MutableArithmetics v1.5.1 ⌅ [872c559c] + NNlib v0.8.21 [77ba4419] + NaNMath v1.0.2 [7e02d93a] + OptimalTransport v0.3.19 [bac558e1] + OrderedCollections v1.6.3 [90014a1f] + PDMats v0.11.31 [69de0a69] + Parsers v2.8.1 [cb4044da] + PlutoTest v0.2.2 [7f904dfe] + PlutoUI v0.7.60 [aea7be01] + PrecompileTools v1.2.1 [21216c6a] + Preferences v1.4.3 [43287f4e] + PtrArrays v1.2.1 [1fd47b50] + QuadGK v2.11.1 [3cdcf5f2] + RecipesBase v1.3.4 [189a3867] + Reexport v1.2.2 [ae029012] + Requires v1.3.0 [79098fc4] + Rmath v0.8.0 [a2af1166] + SortingAlgorithms v1.2.1 [276daf66] + SpecialFunctions v2.4.0 [90137ffa] + StaticArrays v1.9.7 [1e83bf80] + StaticArraysCore v1.4.3 [10745b16] + Statistics v1.11.1 [82ae8749] + StatsAPI v1.7.0 [2913bbd2] + StatsBase v0.34.3 [4c63d2b9] + StatsFuns v1.3.2 [3bb67fe8] + TranscodingStreams v0.11.3 [410a4b4d] + Tricks v0.1.9 [5c2747f8] + URIs v1.5.1 [013be700] + UnsafeAtomics v0.2.1 [d80eeb9a] + UnsafeAtomicsLLVM v0.2.1 [6e34b625] + Bzip2_jll v1.0.8+1 [e8aa6df9] + GLPK_jll v5.0.1+0 [dad2f222] + LLVMExtra_jll v0.0.34+0 [efe28fd5] + OpenSpecFun_jll v0.5.5+0 [f50d1b31] + Rmath_jll v0.5.1+0 [0dad84c5] + ArgTools v1.1.2 [56f22d72] + Artifacts v1.11.0 [2a0f44e3] + Base64 v1.11.0 [ade2ca70] + Dates v1.11.0 [f43a241f] + Downloads v1.6.0 [7b1f6079] + FileWatching v1.11.0 [b77e0a4c] + InteractiveUtils v1.11.0 [4af54fe1] + LazyArtifacts v1.11.0 [b27032c2] + LibCURL v0.6.4 [76f85450] + LibGit2 v1.11.0 [8f399da3] + Libdl v1.11.0 [37e2e46d] + LinearAlgebra v1.11.0 [56ddb016] + Logging v1.11.0 [d6f4376e] + Markdown v1.11.0 [a63ad114] + Mmap v1.11.0 [ca575930] + NetworkOptions v1.2.0 [44cfe95a] + Pkg v1.11.0 [de0858da] + Printf v1.11.0 [9abbd945] + Profile v1.11.0 [9a3f8284] + Random v1.11.0 [ea8e919c] + SHA v0.7.0 [9e88b42a] + Serialization v1.11.0 [2f01184e] + SparseArrays v1.11.0 [4607b0f0] + SuiteSparse [fa267f1f] + TOML v1.0.3 [a4e569a6] + Tar v1.10.0 [8dfed614] + Test v1.11.0 [cf7118a7] + UUIDs v1.11.0 [4ec0a83e] + Unicode v1.11.0 [e66e0078] + CompilerSupportLibraries_jll v1.1.1+0 [781609d7] + GMP_jll v6.3.0+0 [deac9b47] + LibCURL_jll v8.6.0+0 [e37daf67] + LibGit2_jll v1.7.2+0 [29816b5a] + LibSSH2_jll v1.11.0+1 [c8ffd9c3] + MbedTLS_jll v2.28.6+0 [14a3606d] + MozillaCACerts_jll v2023.12.12 [4536629a] + OpenBLAS_jll v0.3.27+1 [05823500] + OpenLibm_jll v0.8.1+2 [bea87d4a] + SuiteSparse_jll v7.7.0+0 [83775a58] + Zlib_jll v1.2.13+1 [8e850b90] + libblastrampoline_jll v5.11.0+0 [8e850ede] + nghttp2_jll v1.59.0+0 [3f19e933] + p7zip_jll v17.4.0+2  Info Packages marked with ⌃ and ⌅ have new versions available. Those with ⌃ may be upgradable, but those with ⌅ are restricted by compatibility constraints from upgrading. To see why use `status --outdated -m` Instantiating... === Precompiling... ===  Activating project at `/tmp/jl_oDhDHt` Precompiling project... 2069.6 ms ✓ BenchmarkTools 3026.9 ms ✓ PlutoTest 114333.0 ms ✓ MathOptInterface 3610.9 ms ✓ ExactOptimalTransport 5661.8 ms ✓ OptimalTransport 9560.8 ms ✓ GLPK 6 dependencies successfully precompiled in 127 seconds. 123 already precompiled.§enabled÷restart_recommended_msgÀ´restart_required_msgÀ­busy_packages¶waiting_for_permissionÂÙ,waiting_for_permission_but_probably_disabled«cell_inputsÞÙ$fff3fe40-b944-46ed-aea1-3d550ed5fbb0„§cell_idÙ$fff3fe40-b944-46ed-aea1-3d550ed5fbb0¤codeÚ3""" find_suboptimal_edge(f, g, C)::Union{Nothing,CartesianIndex} Returns the position of an existing suboptimal edge. """ function find_suboptimal_edge(f, g, C) for i in eachindex(f), j in eachindex(g) @inbounds if f[i] + g[j] - C[i, j] > 1e-14 return CartesianIndex(i, j) end end nothing end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$3be07e02-b95f-44a2-9491-f39a1a1c2617„§cell_idÙ$3be07e02-b95f-44a2-9491-f39a1a1c2617¤codeÙêlet na = 3 nb = 3 a = fill(1/na, na) b = fill(1/nb, nb) C = randn(na, nb) emd2 b1 = @BenchmarkTools.benchmark emd2($a,$b,$C) b2 = @BenchmarkTools.benchmark OptimalTransport.emd2($a, $b, $C, GLPK.Optimizer()) [b1,b2] end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$521f7c7a-823d-4873-8484-66c17825b966„§cell_idÙ$521f7c7a-823d-4873-8484-66c17825b966¤codeÙ$md""" ## OptimalTransport.jl API """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$9bef5380-7275-42de-99cc-597aa72b0abc„§cell_idÙ$9bef5380-7275-42de-99cc-597aa72b0abc¤codeÙ#md""" # Graph & Cycle detection """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$a05afd19-3bae-4479-b8f0-86f373094113„§cell_idÙ$a05afd19-3bae-4479-b8f0-86f373094113¤codeÙ-import OptimalTransport, GLPK, BenchmarkTools¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$5584d358-eab9-48fa-a880-62080674df12„§cell_idÙ$5584d358-eab9-48fa-a880-62080674df12¤code±TableOfContents()¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$3e4a5f6d-d4ef-4372-9762-388b92f0755b„§cell_idÙ$3e4a5f6d-d4ef-4372-9762-388b92f0755b¤codeÙ5md""" ## Obtaining a Dual Pair Complementary to P """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$e7aea362-3595-45d2-bb0a-512e241c17bc„§cell_idÙ$e7aea362-3595-45d2-bb0a-512e241c17bc¤codeÙpcollect_cycle( Bool.([ 1 0 1 0 0 0 1 0 1 ]), [ 1.1 0 1.2 0 0 0 1 0 1 ], CartesianIndex(1, 1), )¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$32b4c5a4-f5e4-457d-b09d-531215fda61b„§cell_idÙ$32b4c5a4-f5e4-457d-b09d-531215fda61b¤codeÚ@""" Tries to find a feasible solution \$(f, g)\$ to the dual problem given a plan \$P\$. - `G` (the graph associated with the transport plan) is an adjacency matrix of the bi-partite network. - `C` is the cost matrix """ function find_feasible_dual(G, C) f = zeros(eltype(C), size(C, 1)) g = zeros(eltype(C), size(C, 2)) explored = Set{Int}() nμ = size(C, 1) function dfs(i) i ∈ explored && return push!(explored, i) if i > nμ # i is in g i -= nμ neighbors = findall(@view G[:,i]) for j in neighbors j ∈ explored && continue f[j] = C[j,i] - g[i] dfs(j) end else # i is in f neighbors = findall(@view G[i,:]) for j in neighbors (j + nμ) ∈ explored && continue g[j] = C[i,j] - f[i] dfs(j + nμ) end end end for i in 1:nμ dfs(i) end f, g end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$cb5ecc78-6ffc-44ea-94cd-d80d8b079423„§cell_idÙ$cb5ecc78-6ffc-44ea-94cd-d80d8b079423¤code·md""" #### Packages """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$c8cd4eff-8702-42a2-8b40-8a789ea4a37f„§cell_idÙ$c8cd4eff-8702-42a2-8b40-8a789ea4a37f¤code¸using PlutoTest, PlutoUI¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$187de006-8830-11ec-3fb7-297fcaedd55e„§cell_idÙ$187de006-8830-11ec-3fb7-297fcaedd55e¤codeÚ """ north_west(μ, ν) Finds an initial transport plan that respect the marginal constraints \$(\\mu,\\nu)\$. """ function north_west(μ, ν) P = zeros(eltype(μ), (length(μ), length(ν))) G = falses((length(μ), length(ν))) i, j = 1, 1 r, c = μ[i], ν[j] while i <= length(μ) && j <= length(ν) P[i, j] = t = min(r, c) G[i, j] = t > 0 r -= t c -= t if r == 0 i += 1 if i <= length(μ) r = μ[i] end elseif c == 0 j += 1 if j <= length(ν) c = ν[j] end end end P, G end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$c147499e-bb03-428a-8acf-49722fd54c7e„§cell_idÙ$c147499e-bb03-428a-8acf-49722fd54c7e¤codeÙ&md""" # Putting it all together... """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$96ab200e-603d-4c87-9cc1-c37dbda6ace4„§cell_idÙ$96ab200e-603d-4c87-9cc1-c37dbda6ace4¤codeÙÅlet G = Bool.([ 0 1 1 1 0 1 1 0 1 ]) P = [ 0.0 0.333333 0.0 0.333333 0.0 0.0 0.0 0.0 0.333333 ] collect_cycle(G, P, CartesianIndex(2, 3)) end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$aa5810ed-b4a0-41fa-bdfd-95df64edf677„§cell_idÙ$aa5810ed-b4a0-41fa-bdfd-95df64edf677¤codeÚ†function emd(a, b, C) # Initialize P, G = north_west(a, b) @label dual # Find feasible dual pair f, g = find_feasible_dual(G, C) # Is there a sub-optimal edge ? edge = find_suboptimal_edge(f, g, C) # 3.5.2 Network Simplex update # We have reached the optimum if isnothing(edge) return P end # Add the violating edge G[edge] = true cycle = collect_cycle(G, P, edge) # Two cases can then arise: if isnothing(cycle) # (a) G is (still) a forest @goto dual else # (b) G now has a cycle indices, costs = cycle # Sub-optimal edge is either at the beginning or end of the # cycle. @assert indices[end] == edge || indices[begin] == edge k⃰ = if indices[end] == edge k = argmin(@view costs[begin:2:end]) 1 + (k - 1) * 2 elseif indices[begin] == edge k = argmin(@view costs[begin+1:2:end]) 2k end θ = costs[k⃰] arity = k⃰ % 2 for (i, idx) in enumerate(indices) if i % 2 == arity P[idx] -= θ else P[idx] += θ end end # We then close the update by removing (iâ‚–â­‘â‚Šâ‚, jâ‚–â­‘) from G G[indices[k⃰]] = false @assert P[indices[k⃰]] == 0. @goto dual end end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$b73c42fd-7a52-45d0-b9a3-ede4dcc61e36„§cell_idÙ$b73c42fd-7a52-45d0-b9a3-ede4dcc61e36¤codeÙSlet C = [ 0 1 1 1 0 1 1 1 2 ] emd([1/4, 1/4, 1/2], [1/3, 1/3, 1/3], C) end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$4b2c7693-7873-42b3-85d3-79712fee730d„§cell_idÙ$4b2c7693-7873-42b3-85d3-79712fee730d¤codeÙ?function emd2(μ, ν, C) γ = emd(μ, ν, C) sum(γ .* C) end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$1030d263-d188-49d0-b9da-5d02810bba9b„§cell_idÙ$1030d263-d188-49d0-b9da-5d02810bba9b¤codeÙxlet P = [ .2 0. 0. .3 .1 .1 0. 0. .3 ] μ, ν = [.2, .5, .3], [.5, .1, 4] @test north_west(μ, ν)[1] == P end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$1ba4e1d2-a260-4f48-866c-821e53c30506„§cell_idÙ$1ba4e1d2-a260-4f48-866c-821e53c30506¤codeÙ”md""" # The Network Simplex This is a textbook implementation of the Network Simplex algorithm from the book "Computational Optimal Transport". """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÃÙ$aac9efe0-d6a1-4587-99ec-46e0f1411c85„§cell_idÙ$aac9efe0-d6a1-4587-99ec-46e0f1411c85¤codeÚVfunction collect_cycle(G, P, edge) n = size(G, 1) costs = Float64[] indices = CartesianIndex[] stack = Int[] explored = Set{Int}() function dfs(i) if false && i ∈ explored return false end if i ∈ stack return true end parent = isempty(stack) ? -1 : stack[end] push!(stack, i) if i > n for j in findall(@view G[:,i-n]) if j == parent # pass elseif dfs(j) idx = CartesianIndex(j,i-n) push!(indices, idx) push!(costs, P[idx]) return true end end else for j in findall(@view G[i,:]) if j+n == parent # pass elseif dfs(j + n) idx = CartesianIndex(i,j) push!(indices, idx) push!(costs, P[idx]) return true end end end pop!(stack) push!(explored, i) return false end if dfs(edge[1]) indices, costs else nothing end end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$1ee92bf4-835f-4c62-9bd5-5d96a86e9d8b„§cell_idÙ$1ee92bf4-835f-4c62-9bd5-5d96a86e9d8b¤codeÙólet na = 2 nb = na = 3 a = fill(1/na, na) b = fill(1/nb, nb) C = Matrix{Float64}(I, na, nb) P, G = north_west(a, b) f, g = find_feasible_dual(G, C) edge = find_suboptimal_edge(f, g, C) edge, f, g, f[edge[1]], g[edge[2]], C[edge] end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$d29bbd55-4b0c-4fa0-8bd7-d9b85d7d7a10„§cell_idÙ$d29bbd55-4b0c-4fa0-8bd7-d9b85d7d7a10¤code³using LinearAlgebra¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$616cfde6-190b-403b-8d1c-da2f4eb385ad„§cell_idÙ$616cfde6-190b-403b-8d1c-da2f4eb385ad¤codeÙ»for _ in 1:3 na = 20 nb = 20 a = fill(1/na, na) b = fill(1/nb, nb) C = randn(na, nb) c1 = emd2(a,b,C) c2 = OptimalTransport.emd2(a, b, C, GLPK.Optimizer()) @assert c1 ≈ c2 end¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedÂÙ$65dd721e-20aa-4a2b-abb4-46f04d922aee„§cell_idÙ$65dd721e-20aa-4a2b-abb4-46f04d922aee¤codeÙ'md""" ## The North-West Corner rule """¨metadataƒ©show_logsèdisabled®skip_as_script«code_foldedënotebook_idÙ$eb27072a-8a3b-11ef-370b-812543c54790«in_temp_dir¨metadata€