{
"cells": [
{
"cell_type": "markdown",
"id": "9612296e-4f52-4a44-b368-da93e6d4fd9e",
"metadata": {},
"source": [
"# Ringed Topology Routing Example"
]
},
{
"cell_type": "markdown",
"id": "08de35e9-4d12-4fb5-b7d8-d1fade2629d9",
"metadata": {},
"source": [
"This notebook demonstrates how to design wind farm cable networks with **Ringed Topology** in `OptiWindNet` using `EWRouter`, `HGSRouter`, and `MILPRouter`."
]
},
{
"cell_type": "markdown",
"id": "522af311-f394-4dd4-8872-1b66cef26027",
"metadata": {},
"source": [
"## What is a Ringed Topology?"
]
},
{
"cell_type": "markdown",
"id": "067277dd",
"metadata": {},
"source": [
"In a **ringed topology**, turbine subtrees are connected into cycles (also called *closed* loops or *rings*) attached to a substation at both ends (or bridging two substations).\n",
"\n",
"Key properties of ringed networks in OptiWindNet:\n",
"* Each ring features a **zero-current link** (where cable load drops to `0`), drawn in a distinct style.\n",
"* Each of the ring's two feeders can carry up to the standard cable `capacity`, allowing a full ring to serve up to **2 × capacity** turbines.\n",
"* Rings enhance reliability: if a fault occurs along a ring, each turbine still retains an intact path to a substation."
]
},
{
"cell_type": "markdown",
"id": "714001e5",
"metadata": {},
"source": [
"## Load Data"
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "2c988d69",
"metadata": {},
"outputs": [],
"source": [
"from optiwindnet.api import WindFarmNetwork, EWRouter, HGSRouter, MILPRouter, ModelOptions, load_repository\n",
"%config InlineBackend.figure_formats = ['svg']"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "e47baf7b-d0a8-4e03-af67-72d52acee9a7",
"metadata": {},
"outputs": [],
"source": [
"locations = load_repository()"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "43925299",
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"wfn = WindFarmNetwork(L=locations.borssele, cables=3)\n",
"wfn"
]
},
{
"cell_type": "markdown",
"id": "4ee19cd6",
"metadata": {},
"source": [
"## 1. Ringed Topology with EWRouter\n",
"`EWRouter` provides a constructive heuristic variant (`method='ringed'`) that forms closed loops."
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "ff74713e-4bff-4d1f-987a-f80594e20222",
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"wfn.optimize(router=EWRouter(method='ringed'))\n",
"wfn"
]
},
{
"cell_type": "markdown",
"id": "fac63fe9",
"metadata": {},
"source": [
"## 2. Ringed Topology with HGSRouter\n",
"`HGSRouter` supports `ringed=True` to solve a closed CVRP formulation using Hybrid Genetic Search."
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "c956e9f7-11a7-4443-b8c1-be89fd2eb706",
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"wfn.optimize(router=HGSRouter(ringed=True, time_limit=1.0))\n",
"wfn"
]
},
{
"cell_type": "markdown",
"id": "c2e1dcff",
"metadata": {},
"source": [
"## 3. Ringed Topology with MILPRouter\n",
"`MILPRouter` supports exact mathematical optimization of ringed networks by specifying `topology='ringed'` in `ModelOptions`."
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "1eeecbf5-5cc7-4d4a-b520-62decb15c586",
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"IntegerBoundsPreprocessor 6288 rows, 4438 columns, 23122 entries with magnitude in [1.000000e+00, 6.000000e+00]\n",
"BoundPropagationPreprocessor 6288 rows, 4438 columns, 23122 entries with magnitude in [1.000000e+00, 6.000000e+00]\n",
"ImpliedIntegerPreprocessor 6288 rows, 4438 columns, 23122 entries with magnitude in [1.000000e+00, 6.000000e+00]\n",
"IntegerBoundsPreprocessor 6288 rows, 4438 columns, 23122 entries with magnitude in [1.000000e+00, 6.000000e+00]\n",
"ReduceCostOverExclusiveOrConstraintPreprocessor 6288 rows, 4438 columns, 23122 entries with magnitude in [1.000000e+00, 6.000000e+00]\n",
"\n",
"Scaling to pure integer problem.\n",
"Num integers: 4438/4438 (implied: 0 in_inequalities: 0 max_scaling: 0) [IP] \n",
"Maximum constraint coefficient relative error: 0\n",
"Maximum constraint worst-case activity error: 0\n",
"Constraint scaling factor range: [1, 1]\n",
"\n",
"Starting CP-SAT solver v9.15.6755\n",
"Parameters: max_time_in_seconds: 90 log_search_progress: true catch_sigint_signal: false relative_gap_limit: 0.005\n",
"Setting number of workers to 16\n",
"\n",
"Initial optimization model 'optiwindnet': (model_fingerprint: 0x895d041c558c1de)\n",
"#Variables: 4'438 (#bools: 2'163 in floating point objective) (3'921 primary variables)\n",
" - 2'392 Booleans in [0,1]\n",
" - 1'700 in [0,5]\n",
" - 346 in [0,6]\n",
"#kLinear2: 4'942\n",
"#kLinear3: 1\n",
"#kLinearN: 1'345 (#terms: 13'235)\n",
"\n",
"Starting presolve at 0.01s\n",
"The solution hint is complete and is feasible.\n",
"[Scaling] Floating point objective has 2163 terms with magnitude in [0.225196, 20056.2] average = 3176.32\n",
"[Scaling] Objective coefficient relative error: 2.74745e-07\n",
"[Scaling] Objective worst-case absolute error: 6.52751e-05\n",
"[Scaling] Objective scaling factor: 4.1943e+06\n",
" 1.10e-03s 0.00e+00d [DetectDominanceRelations] \n",
" 2.54e-02s 0.00e+00d [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
" 6.74e-05s 0.00e+00d [ExtractEncodingFromLinear] #potential_supersets=998 \n",
" 1.02e-03s 0.00e+00d [DetectDuplicateColumns] \n",
" 8.83e-04s 0.00e+00d [DetectDuplicateConstraints] \n",
"[Symmetry] Graph for symmetry has 15'668 nodes and 28'568 arcs.\n",
"[Symmetry] Symmetry computation done. time: 0.00221 dtime: 0.00277011\n",
"[SAT presolve] num removable Booleans: 0 / 2'046\n",
"[SAT presolve] num trivial clauses: 0\n",
"[SAT presolve] [0s] clauses:850 literals:1'700 vars:1'700 one_side_vars:1700 simple_definition:0 singleton_clauses:0\n",
"[SAT presolve] [3.7606e-05s] clauses:850 literals:1'700 vars:1'700 one_side_vars:1700 simple_definition:0 singleton_clauses:0\n",
"[SAT presolve] [7.1873e-05s] clauses:850 literals:1'700 vars:1'700 one_side_vars:1700 simple_definition:0 singleton_clauses:0\n",
" 6.25e-04s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements] \n",
" 5.76e-02s 3.10e-02d [Probe] #probed=8'530 #new_binary_clauses=2'046 \n",
" 1.82e-03s 2.97e-03d [MaxClique] Merged 1'675 constraints with 6'408 literals into 912 constraints with 4'882 literals\n",
" 1.22e-03s 0.00e+00d [DetectDominanceRelations] \n",
" 8.58e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1 \n",
" 3.50e-03s 0.00e+00d [ProcessAtMostOneAndLinear] #num_changes=2'046 \n",
" 5.04e-04s 0.00e+00d [DetectDuplicateConstraints] \n",
" 4.29e-04s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements] \n",
" 4.16e-04s 2.60e-05d [DetectDominatedLinearConstraints] #relevant_constraints=348 #num_inclusions=173 \n",
" 6.20e-05s 0.00e+00d [DetectDifferentVariables] \n",
" 5.57e-04s 2.41e-05d [ProcessSetPPC] #relevant_constraints=1'086 \n",
" 1.07e-03s 0.00e+00d [TransformClausesToExactlyOne] #num_amos=912 \n",
" 2.09e-03s 0.00e+00d [DetectEncodedComplexDomains] \n",
" 8.22e-05s 3.20e-07d [FindAlmostIdenticalLinearConstraints] #num_tested_pairs=3 \n",
" 1.04e-03s 1.78e-03d [FindBigAtMostOneAndLinearOverlap] \n",
" 7.88e-04s 1.83e-03d [FindBigVerticalLinearOverlap] \n",
" 4.43e-04s 1.22e-03d [FindBigHorizontalLinearOverlap] #linears=345 \n",
" 5.12e-05s 0.00e+00d [MergeClauses] \n",
" 9.91e-04s 0.00e+00d [DetectDominanceRelations] \n",
" 1.56e-02s 0.00e+00d [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
" 1.81e-03s 0.00e+00d [DetectDominanceRelations] \n",
" 9.07e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1 \n",
" 3.14e-04s 0.00e+00d [DetectDuplicateColumns] \n",
" 3.90e-04s 0.00e+00d [DetectDuplicateConstraints] \n",
"[Symmetry] Graph for symmetry has 13'986 nodes and 25'360 arcs.\n",
"[Symmetry] Symmetry computation done. time: 0.00178734 dtime: 0.00254392\n",
"[SAT presolve] num removable Booleans: 0 / 2'046\n",
"[SAT presolve] num trivial clauses: 0\n",
"[SAT presolve] [0s] clauses:87 literals:174 vars:174 one_side_vars:174 simple_definition:0 singleton_clauses:0\n",
"[SAT presolve] [4.0308e-05s] clauses:87 literals:174 vars:174 one_side_vars:174 simple_definition:0 singleton_clauses:0\n",
"[SAT presolve] [8.9962e-05s] clauses:87 literals:174 vars:174 one_side_vars:174 simple_definition:0 singleton_clauses:0\n",
" 4.83e-04s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements] \n",
" 2.52e-02s 9.87e-03d [Probe] #probed=4'438 \n",
" 1.22e-03s 2.01e-03d [MaxClique] \n",
" 1.43e-03s 0.00e+00d [DetectDominanceRelations] \n",
" 7.59e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1 \n",
" 8.13e-04s 0.00e+00d [ProcessAtMostOneAndLinear] \n",
" 7.69e-04s 0.00e+00d [DetectDuplicateConstraints] \n",
" 4.14e-04s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements] \n",
" 4.35e-04s 2.60e-05d [DetectDominatedLinearConstraints] #relevant_constraints=348 #num_inclusions=173 \n",
" 6.57e-05s 0.00e+00d [DetectDifferentVariables] \n",
" 4.76e-04s 2.41e-05d [ProcessSetPPC] #relevant_constraints=1'086 \n",
" 7.78e-04s 0.00e+00d [TransformClausesToExactlyOne] #num_amos=912 \n",
" 1.77e-03s 0.00e+00d [DetectEncodedComplexDomains] \n",
" 3.01e-04s 8.40e-07d [FindAlmostIdenticalLinearConstraints] #num_tested_pairs=7 \n",
" 1.81e-03s 1.78e-03d [FindBigAtMostOneAndLinearOverlap] \n",
" 6.52e-04s 1.83e-03d [FindBigVerticalLinearOverlap] \n",
" 4.37e-04s 1.22e-03d [FindBigHorizontalLinearOverlap] #linears=345 \n",
" 4.78e-05s 0.00e+00d [MergeClauses] \n",
" 1.06e-03s 0.00e+00d [DetectDominanceRelations] \n",
" 9.36e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1 \n",
" 1.90e-05s 0.00e+00d [MergeNoOverlap] \n",
" 1.76e-05s 0.00e+00d [MergeNoOverlap2D] \n",
" 8.36e-04s 0.00e+00d [ExpandObjective] #entries=23'308 #tight_variables=2'046 #tight_constraints=173 #expands=7 \n",
"\n",
"Presolve summary:\n",
" - 0 affine relations were detected.\n",
" - rule 'TODO linear inclusion: superset is equality' was applied 346 times.\n",
" - rule 'TODO linear2: convert ax + by != cte to clauses for large domains' was applied 12'276 times.\n",
" - rule 'at_most_one: dominated singleton' was applied 169 times.\n",
" - rule 'at_most_one: removed literals' was applied 4 times.\n",
" - rule 'at_most_one: singleton' was applied 4 times.\n",
" - rule 'at_most_one: transformed into max clique' was applied 1 time.\n",
" - rule 'bool_or: implications' was applied 850 times.\n",
" - rule 'deductions: 4092 stored' was applied 1 time.\n",
" - rule 'exactly_one: removed literals' was applied 169 times.\n",
" - rule 'exactly_one: simplified objective' was applied 172 times.\n",
" - rule 'exactly_one: singleton' was applied 169 times.\n",
" - rule 'linear + amo: extracted enforcement literal' was applied 2'046 times.\n",
" - rule 'linear2: contains a boolean' was applied 2'046 times.\n",
" - rule 'linear2: convert ax + by != cte to clauses' was applied 850 times.\n",
" - rule 'linear: positive at most one' was applied 656 times.\n",
" - rule 'linear: positive equal one' was applied 342 times.\n",
" - rule 'linear: singleton column' was applied 4 times.\n",
" - rule 'objective: expanded via tight equality' was applied 7 times.\n",
" - rule 'objective: shifted cost with exactly ones' was applied 173 times.\n",
" - rule 'objective: variable not used elsewhere' was applied 173 times.\n",
" - rule 'presolve: 173 unused variables removed.' was applied 1 time.\n",
" - rule 'presolve: iteration' was applied 2 times.\n",
" - rule 'variables: detect fully reified value encoding' was applied 2'046 times.\n",
" - rule 'variables: detect half reified value encoding' was applied 4'092 times.\n",
"\n",
"Presolved optimization model 'optiwindnet': (model_fingerprint: 0x4f856fef45902300)\n",
"#Variables: 4'092 (#bools: 1'873 in objective) (3'746 primary variables)\n",
" - 2'046 Booleans in [0,1]\n",
" - 1'700 in [0,5]\n",
" - 346 in [0,6]\n",
"#kAtMostOne: 825 (#literals: 4'708)\n",
"#kBoolAnd: 87 (#enforced: 87) (#literals: 174)\n",
"#kExactlyOne: 173 (#literals: 2'046)\n",
"#kLinear1: 4'092 (#enforced: 4'092)\n",
"#kLinear3: 1\n",
"#kLinearN: 347 (#terms: 6'135)\n",
"[Symmetry] Graph for symmetry has 13'640 nodes and 25'360 arcs.\n",
"[Symmetry] Symmetry computation done. time: 0.00114585 dtime: 0.00252726\n",
"\n",
"Preloading model.\n",
"#Bound 0.22s best:inf next:[47358.0431,7099169.41] initial_domain\n",
"#1 0.22s best:516373.361 next:[47358.0431,516373.361] complete_hint\n",
"#Model 0.23s var:4092/4092 constraints:5525/5525\n",
"\n",
"Starting search at 0.23s with 16 workers.\n",
"11 full problem subsolvers: [core, default_lp, lb_tree_search, max_lp, no_lp, objective_lb_search, probing, pseudo_costs, quick_restart, quick_restart_no_lp, reduced_costs]\n",
"5 first solution subsolvers: [fj(2), fs_random, fs_random_no_lp, fs_random_quick_restart_no_lp]\n",
"11 interleaved subsolvers: [feasibility_pump, graph_arc_lns, graph_cst_lns, graph_dec_lns, graph_var_lns, lb_relax_lns, ls, ls_lin, rins/rens, rnd_cst_lns, rnd_var_lns]\n",
"3 helper subsolvers: [neighborhood_helper, synchronization_agent, update_gap_integral]\n",
"\n",
"#2 0.26s best:515927.393 next:[47358.0431,515927.393] rnd_cst_lns (d=5.00e-01 s=12 t=0.10 p=0.00 stall=0 h=base) [hint]\n",
"#Bound 0.32s best:515927.393 next:[56493.0133,515927.393] am1_presolve (num_literals=1873 num_am1=44 increase=38314841694 work_done=10319)\n",
"#Bound 0.37s best:515927.393 next:[178725.096,515927.393] reduced_costs\n",
"#Bound 0.63s best:515927.393 next:[351535.643,515927.393] max_lp\n",
"#Bound 0.84s best:515927.393 next:[395145.982,515927.393] max_lp\n",
"#Bound 1.56s best:515927.393 next:[473457.975,515927.393] max_lp\n",
"#Bound 2.13s best:515927.393 next:[473600.181,515927.393] max_lp\n",
"#Bound 2.21s best:515927.393 next:[473875.819,515927.393] max_lp\n",
"#Bound 2.37s best:515927.393 next:[474022.89,515927.393] lb_tree_search\n",
"#Bound 3.04s best:515927.393 next:[474230.893,515927.393] max_lp\n",
"#Bound 3.16s best:515927.393 next:[474954.874,515927.393] max_lp\n",
"#Bound 4.08s best:515927.393 next:[475525.663,515927.393] max_lp\n",
"#Bound 4.23s best:515927.393 next:[476143.049,515927.393] max_lp\n",
"#Bound 5.34s best:515927.393 next:[476875.15,515927.393] max_lp\n",
"#Bound 5.56s best:515927.393 next:[477463.47,515927.393] max_lp\n",
"#Bound 6.71s best:515927.393 next:[477865.069,515927.393] max_lp\n",
"#Bound 6.98s best:515927.393 next:[478612.895,515927.393] max_lp\n",
"#Bound 8.18s best:515927.393 next:[479081.762,515927.393] max_lp\n",
"#Bound 8.42s best:515927.393 next:[479707.517,515927.393] max_lp\n",
"#Bound 9.86s best:515927.393 next:[479902.907,515927.393] lb_tree_search\n",
"#Bound 9.91s best:515927.393 next:[480237.756,515927.393] max_lp\n",
"#Bound 10.14s best:515927.393 next:[480530.694,515927.393] max_lp\n",
"#Bound 10.51s best:515927.393 next:[480831.853,515927.393] max_lp\n",
"#Bound 12.00s best:515927.393 next:[481057.716,515927.393] lb_tree_search\n",
"#Bound 12.15s best:515927.393 next:[481394.745,515927.393] max_lp\n",
"#Bound 12.50s best:515927.393 next:[481747.136,515927.393] max_lp\n",
"#Bound 12.75s best:515927.393 next:[481919.497,515927.393] max_lp\n",
"#3 14.53s best:515927.393 next:[481919.497,515927.393] graph_arc_lns (d=1.82e-01 s=244 t=0.10 p=0.46 stall=23 h=base)\n",
"#Bound 14.63s best:515927.393 next:[482362.926,515927.393] max_lp\n",
"#Bound 15.61s best:515927.393 next:[482704.918,515927.393] max_lp\n",
"#Bound 17.47s best:515927.393 next:[482991.585,515927.393] max_lp\n",
"#Bound 17.87s best:515927.393 next:[483079.277,515927.393] max_lp\n",
"#4 22.33s best:515927.393 next:[483079.277,515927.393] graph_var_lns (d=3.98e-01 s=412 t=0.10 p=0.49 stall=45 h=base)\n",
"#5 30.24s best:515927.393 next:[483079.277,515927.393] graph_var_lns (d=4.70e-01 s=568 t=0.10 p=0.50 stall=1 h=base)\n",
"#Bound 35.90s best:515927.393 next:[483272.626,515927.393] lb_tree_search\n",
"#Bound 35.96s best:515927.393 next:[483272.626,515927.393] lb_tree_search\n",
"#Bound 38.33s best:515927.393 next:[483688.433,515927.393] lb_tree_search\n",
"#Bound 40.00s best:515927.393 next:[483984.324,515927.393] lb_tree_search\n",
"#Bound 44.11s best:515927.393 next:[484346.037,515927.393] lb_tree_search\n",
"#Bound 50.04s best:515927.393 next:[484524.922,515927.393] lb_tree_search\n",
"#Bound 56.35s best:515927.393 next:[484755.288,515927.393] lb_tree_search\n",
"#6 63.81s best:515511.237 next:[484755.288,515511.237] graph_var_lns (d=4.68e-01 s=1191 t=0.10 p=0.50 stall=15 h=stalling)\n",
"#Bound 64.14s best:515511.237 next:[485093.606,515511.237] lb_tree_search\n",
"#Bound 64.47s best:515511.237 next:[485098.111,515511.237] lb_tree_search (nodes=19/19 rc=1 decisions=46 @root=17 restarts=0 lp_iters=[0, 0, 1'477, 4'031]) \n",
"#Bound 70.81s best:515511.237 next:[485197.392,515511.237] lb_tree_search\n",
"#Bound 70.87s best:515511.237 next:[485198.553,515511.237] lb_tree_search\n",
"#Bound 77.62s best:515511.237 next:[485442.148,515511.237] lb_tree_search\n",
"#Bound 77.72s best:515511.237 next:[485442.148,515511.237] lb_tree_search\n",
"#7 84.46s best:515391.833 next:[485442.148,515391.833] lb_relax_lns_bool_h (d=1.78e-01 s=1502 t=0.50 p=0.38 stall=8 h=base)\n",
"#Bound 85.31s best:515391.833 next:[485627.998,515391.833] lb_tree_search\n",
"\n",
"Task timing n [ min, max] avg dev time n [ min, max] avg dev dtime\n",
" 'core': 1 [ 1.50m, 1.50m] 1.50m 0.00ns 1.50m 2 [ 10.20ms, 1.02m] 30.48s 30.47s 1.02m\n",
" 'default_lp': 1 [ 1.50m, 1.50m] 1.50m 0.00ns 1.50m 2 [366.03ms, 17.34s] 8.85s 8.49s 17.71s\n",
" 'feasibility_pump': 399 [180.92us, 746.53ms] 98.77ms 203.80ms 39.41s 103 [945.91us, 368.41ms] 187.52ms 103.21ms 19.31s\n",
" 'fj': 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns\n",
" 'fj': 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns\n",
" 'fs_random': 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns\n",
" 'fs_random_no_lp': 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns\n",
" 'fs_random_quick_restart_no_lp': 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns\n",
" 'graph_arc_lns': 208 [ 8.31ms, 661.84ms] 197.81ms 144.50ms 41.14s 208 [ 10.00ns, 106.68ms] 59.88ms 46.92ms 12.45s\n",
" 'graph_cst_lns': 147 [ 15.01ms, 638.15ms] 277.32ms 205.14ms 40.77s 147 [ 42.00ns, 100.37ms] 57.09ms 45.91ms 8.39s\n",
" 'graph_dec_lns': 126 [ 15.77ms, 843.59ms] 334.04ms 254.99ms 42.09s 126 [ 10.00ns, 100.28ms] 55.43ms 47.54ms 6.98s\n",
" 'graph_var_lns': 196 [ 8.72ms, 543.18ms] 207.36ms 165.01ms 40.64s 196 [ 10.00ns, 100.31ms] 55.13ms 47.25ms 10.80s\n",
" 'lb_relax_lns': 10 [ 1.21s, 5.76s] 4.07s 1.20s 40.67s 9 [ 1.19s, 1.90s] 1.61s 216.34ms 14.45s\n",
" 'lb_tree_search': 1 [ 1.50m, 1.50m] 1.50m 0.00ns 1.50m 2 [ 5.41s, 5.79s] 5.60s 192.84ms 11.20s\n",
" 'ls': 232 [112.80ms, 289.25ms] 172.03ms 20.64ms 39.91s 232 [100.00ms, 100.10ms] 100.03ms 15.66us 23.21s\n",
" 'ls_lin': 234 [118.52ms, 304.68ms] 170.21ms 24.10ms 39.83s 234 [100.00ms, 100.07ms] 100.03ms 12.37us 23.41s\n",
" 'max_lp': 1 [ 1.50m, 1.50m] 1.50m 0.00ns 1.50m 2 [ 8.00s, 14.80s] 11.40s 3.40s 22.80s\n",
" 'no_lp': 1 [ 1.50m, 1.50m] 1.50m 0.00ns 1.50m 2 [ 11.32ms, 28.83s] 14.42s 14.41s 28.84s\n",
" 'objective_lb_search': 1 [ 1.50m, 1.50m] 1.50m 0.00ns 1.50m 2 [423.57ms, 15.87s] 8.15s 7.72s 16.30s\n",
" 'probing': 1 [ 1.50m, 1.50m] 1.50m 0.00ns 1.50m 2 [407.38ms, 13.85s] 7.13s 6.72s 14.26s\n",
" 'pseudo_costs': 1 [ 1.50m, 1.50m] 1.50m 0.00ns 1.50m 2 [134.66ms, 17.44s] 8.79s 8.65s 17.58s\n",
" 'quick_restart': 1 [ 1.50m, 1.50m] 1.50m 0.00ns 1.50m 2 [409.98ms, 15.68s] 8.04s 7.63s 16.09s\n",
" 'quick_restart_no_lp': 1 [ 1.50m, 1.50m] 1.50m 0.00ns 1.50m 2 [ 11.32ms, 30.88s] 15.44s 15.43s 30.89s\n",
" 'reduced_costs': 1 [ 1.50m, 1.50m] 1.50m 0.00ns 1.50m 2 [265.53ms, 32.37s] 16.32s 16.05s 32.64s\n",
" 'rins/rens': 143 [ 1.34ms, 617.59ms] 290.89ms 244.41ms 41.60s 105 [ 10.00ns, 100.17ms] 74.33ms 40.80ms 7.80s\n",
" 'rnd_cst_lns': 126 [ 19.05ms, 773.29ms] 324.17ms 230.12ms 40.85s 126 [998.50ns, 100.24ms] 56.75ms 46.14ms 7.15s\n",
" 'rnd_var_lns': 121 [ 25.85ms, 885.47ms] 344.64ms 258.31ms 41.70s 121 [221.00ns, 100.31ms] 55.82ms 45.63ms 6.75s\n",
"\n",
"Search stats Bools Conflicts Branches Restarts BacktrackToRoot Backtrack BoolPropag IntegerPropag\n",
" 'core': 2'090 211'377 674'002 1'110 5'199 214'130 38'549'442 79'705'439\n",
" 'default_lp': 2'132 4'243 62'448 4 22'198 27'547 1'009'226 3'956'952\n",
" 'fs_random': 0 0 0 0 0 0 0 0\n",
" 'fs_random_no_lp': 0 0 0 0 0 0 0 0\n",
" 'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0 0\n",
" 'lb_tree_search': 2'046 38 178'552 0 68'143 70'667 1'036'265 2'557'985\n",
" 'max_lp': 2'046 120 36'553 2 13'709 14'189 220'257 836'059\n",
" 'no_lp': 2'046 218'834 1'106'501 1'953 61'275 281'732 37'494'388 112'327'588\n",
" 'objective_lb_search': 2'154 3'616 108'715 8 40'234 46'450 1'408'980 5'370'218\n",
" 'probing': 2'087 10 4'849 0 4'257 4'267 53'828 139'634\n",
" 'pseudo_costs': 2'046 1'784 108'534 8 40'486 43'685 833'962 3'313'712\n",
" 'quick_restart': 2'101 162 133'857 11 53'269 56'221 814'695 3'066'253\n",
" 'quick_restart_no_lp': 2'748 88'873 5'417'099 7'983 101'432 213'925 23'681'898 78'259'632\n",
" 'reduced_costs': 2'047 870 158'270 12 58'516 61'531 955'118 3'803'251\n",
"\n",
"SAT formula Fixed Equiv Total VarLeft BinaryClauses PermanentClauses TemporaryClauses\n",
" 'core': 0 0 2'090 2'090 184 580 8'184\n",
" 'default_lp': 0 0 2'132 2'132 480 362 3'918\n",
" 'fs_random': 0 0 0 0 0 0 0\n",
" 'fs_random_no_lp': 0 0 0 0 0 0 0\n",
" 'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0\n",
" 'lb_tree_search': 0 0 2'046 2'046 180 370 3\n",
" 'max_lp': 0 0 2'046 2'046 180 359 108\n",
" 'no_lp': 0 0 2'046 2'046 180 470 13'204\n",
" 'objective_lb_search': 8 0 2'154 2'146 508 384 51\n",
" 'probing': 0 0 2'087 2'087 264 173 10\n",
" 'pseudo_costs': 0 0 2'046 2'046 180 374 1'611\n",
" 'quick_restart': 0 0 2'101 2'101 314 377 132\n",
" 'quick_restart_no_lp': 0 0 2'748 2'748 5'430 3'146 9'422\n",
" 'reduced_costs': 0 0 2'047 2'047 182 370 824\n",
"\n",
"SAT stats ClassicMinim LitRemoved LitRemovedBinary LitLearned LitForgotten Subsumed\n",
" 'core': 189'351 2'526'371 721'634 70'944'747 49'301'396 55'714\n",
" 'default_lp': 4'129 120'874 620'793 1'406'117 0 300\n",
" 'fs_random': 0 0 0 0 0 0\n",
" 'fs_random_no_lp': 0 0 0 0 0 0\n",
" 'fs_random_quick_restart_no_lp': 0 0 0 0 0 0\n",
" 'lb_tree_search': 1 1 56 642 0 32\n",
" 'max_lp': 108 765 40'035 49'932 0 10\n",
" 'no_lp': 196'226 8'583'352 6'862'697 55'748'804 31'741'929 70'926\n",
" 'objective_lb_search': 3'503 57'549 369'500 790'196 0 323\n",
" 'probing': 9 39 7'240 3'030 0 0\n",
" 'pseudo_costs': 1'691 36'849 467'119 640'994 0 165\n",
" 'quick_restart': 79 692 34'504 37'258 0 22\n",
" 'quick_restart_no_lp': 46'717 509'998 5'100'504 15'283'447 11'300'409 11'781\n",
" 'reduced_costs': 428 4'129 227'164 171'481 0 41\n",
"\n",
"Vivification Clauses Decisions LitTrue Subsumed LitRemoved DecisionReused Conflicts\n",
" 'core': 0 0 0 0 0 0 0\n",
" 'default_lp': 2'515 30'355 0 108 821 185 2\n",
" 'fs_random': 0 0 0 0 0 0 0\n",
" 'fs_random_no_lp': 0 0 0 0 0 0 0\n",
" 'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0\n",
" 'lb_tree_search': 9'262 116'468 0 127 1'103 635 1\n",
" 'max_lp': 1'786 22'254 0 116 888 115 0\n",
" 'no_lp': 8'533 116'133 0 449 5'065 3'423 6\n",
" 'objective_lb_search': 5'081 60'767 0 127 1'030 427 0\n",
" 'probing': 0 0 0 0 0 0 0\n",
" 'pseudo_costs': 5'091 62'827 0 125 1'057 411 0\n",
" 'quick_restart': 6'224 75'198 0 121 973 407 1\n",
" 'quick_restart_no_lp': 42'665 312'463 0 1'487 12'448 9'771 127\n",
" 'reduced_costs': 7'472 92'507 0 127 1'101 605 1\n",
"\n",
"Clause deletion at_true l_and_not(l) to_binary sub_conflict sub_extra sub_decisions sub_eager sub_vivify sub_probing sub_inpro blocked eliminated forgotten promoted conflicts\n",
" 'core': 0 0 0 52'418 2'451 0 3'296 0 0 2 0 0 144'963 552'855 211'377\n",
" 'default_lp': 0 0 0 297 6 1 3 108 0 0 0 0 0 9'093 4'243\n",
" 'fs_random': 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\n",
" 'fs_random_no_lp': 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\n",
" 'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\n",
" 'lb_tree_search': 0 0 0 32 0 0 0 127 0 0 0 0 0 6 38\n",
" 'max_lp': 0 0 0 10 0 0 0 116 0 0 0 0 0 227 120\n",
" 'no_lp': 0 0 0 67'224 440 248 3'702 449 0 2 0 0 133'507 470'127 218'834\n",
" 'objective_lb_search': 3'220 0 0 313 2 0 10 127 0 0 0 0 0 7'405 3'616\n",
" 'probing': 0 0 0 0 0 0 0 0 0 0 0 0 0 18 10\n",
" 'pseudo_costs': 0 0 0 162 2 0 3 125 0 0 0 0 0 3'620 1'784\n",
" 'quick_restart': 0 0 0 22 2 1 0 121 0 1 0 0 0 228 162\n",
" 'quick_restart_no_lp': 0 0 1 11'047 171 33 734 1'487 25 104 0 0 62'268 165'614 88'873\n",
" 'reduced_costs': 0 0 0 41 0 1 0 127 0 0 0 0 0 1'666 870\n",
"\n",
"Lp stats Component Iterations AddedCuts OPTIMAL DUAL_F. DUAL_U.\n",
" 'default_lp': 1 192'287 5'640 17'888 1 2\n",
" 'lb_tree_search': 1 31'153 7'319 705 14 0\n",
" 'max_lp': 1 77'271 7'655 2'456 41 0\n",
" 'objective_lb_search': 1 158'129 8'820 14'518 2 0\n",
" 'probing': 1 31'987 21'254 649 0 0\n",
" 'pseudo_costs': 1 150'828 8'105 9'931 321 15\n",
" 'quick_restart': 1 92'783 11'526 5'831 5 23\n",
" 'reduced_costs': 1 204'904 5'381 4'282 229 25\n",
"\n",
"Lp dimension Final dimension of first component\n",
" 'default_lp': 1869 rows, 3919 columns, 9973 entries\n",
" 'lb_tree_search': 3906 rows, 4092 columns, 57291 entries\n",
" 'max_lp': 3214 rows, 4092 columns, 38996 entries\n",
" 'objective_lb_search': 2484 rows, 3919 columns, 17014 entries\n",
" 'probing': 5791 rows, 3919 columns, 114092 entries\n",
" 'pseudo_costs': 2853 rows, 4092 columns, 21084 entries\n",
" 'quick_restart': 2881 rows, 3919 columns, 23650 entries\n",
" 'reduced_costs': 2858 rows, 4092 columns, 21310 entries\n",
"\n",
"Lp debug CutPropag CutEqPropag Adjust Overflow Bad BadScaling\n",
" 'default_lp': 0 0 17'844 0 6'866 0\n",
" 'lb_tree_search': 0 8 719 0 219'781 0\n",
" 'max_lp': 0 0 2'497 0 124'523 0\n",
" 'objective_lb_search': 0 0 14'467 0 10'589 0\n",
" 'probing': 0 2 610 0 210'529 0\n",
" 'pseudo_costs': 0 0 10'168 0 22'904 0\n",
" 'quick_restart': 0 1 5'802 0 30'624 0\n",
" 'reduced_costs': 0 0 4'451 0 18'829 0\n",
"\n",
"Lp pool Constraints Updates Simplif Merged Shortened Split Strengthened Cuts/Call\n",
" 'default_lp': 12'604 30 0 0 0 10 61 5'640/16'052\n",
" 'lb_tree_search': 14'890 1'510 0 0 0 1'745 32 7'319/14'717\n",
" 'max_lp': 15'226 892 0 0 0 941 29 7'655/15'614\n",
" 'objective_lb_search': 15'784 74 0 0 0 23 118 8'820/24'942\n",
" 'probing': 16'218 1'066 0 0 0 1'501 638 21'254/54'105\n",
" 'pseudo_costs': 15'676 115 0 0 0 30 22 8'105/18'450\n",
" 'quick_restart': 16'490 202 0 0 0 105 261 11'526/29'773\n",
" 'reduced_costs': 12'952 98 0 0 0 152 12 5'381/11'091\n",
"\n",
"Lp Cut default_lp max_lp quick_restart reduced_costs pseudo_costs lb_tree_search objective_lb_search probing\n",
" CG_FF: 31 21 79 16 31 11 53 69\n",
" CG_K: 14 12 42 8 13 4 29 47\n",
" CG_KL: - 3 5 - 1 - 2 5\n",
" CG_R: 46 62 79 33 49 60 65 117\n",
" CG_RB: 54 104 82 50 78 124 64 216\n",
" CG_RBP: 30 41 58 11 19 57 34 92\n",
" Clique: - 2 - 4 6 7 - -\n",
" IB: 2'105 1'224 2'709 2'895 4'248 462 2'126 1'404\n",
" MIR_1_FF: 265 308 1'158 141 270 352 588 3'824\n",
" MIR_1_K: 129 84 383 28 82 21 180 555\n",
" MIR_1_KL: 30 37 87 10 33 5 70 124\n",
" MIR_1_R: 1 12 10 2 7 16 10 26\n",
" MIR_1_RB: 53 123 131 94 125 140 105 178\n",
" MIR_1_RBP: 34 57 126 11 40 12 82 703\n",
" MIR_2_FF: 401 383 917 163 250 385 755 1'790\n",
" MIR_2_K: 185 74 387 30 100 24 300 716\n",
" MIR_2_KL: 71 19 113 9 25 5 97 120\n",
" MIR_2_R: 35 31 59 18 21 25 45 77\n",
" MIR_2_RB: 166 335 374 191 240 329 359 653\n",
" MIR_2_RBP: 129 57 199 18 50 49 189 393\n",
" MIR_3_FF: 118 482 430 199 285 518 386 1'033\n",
" MIR_3_K: 122 83 205 32 82 59 188 409\n",
" MIR_3_KL: 10 8 23 9 33 1 30 27\n",
" MIR_3_R: 30 51 97 43 46 51 85 205\n",
" MIR_3_RB: 129 377 280 159 252 336 281 525\n",
" MIR_3_RBP: 70 82 118 24 47 91 97 248\n",
" MIR_4_FF: 68 310 179 95 151 339 203 490\n",
" MIR_4_K: 89 106 127 30 67 108 97 250\n",
" MIR_4_KL: 2 3 14 3 8 1 12 15\n",
" MIR_4_R: 16 46 50 27 42 45 70 112\n",
" MIR_4_RB: 57 232 132 103 148 228 151 268\n",
" MIR_4_RBP: 50 117 101 25 30 177 58 220\n",
" MIR_5_FF: 26 129 62 43 66 115 59 160\n",
" MIR_5_K: 44 73 73 13 55 96 87 176\n",
" MIR_5_KL: 3 5 6 5 10 3 16 13\n",
" MIR_5_R: 8 29 14 9 14 31 17 41\n",
" MIR_5_RB: 21 150 61 48 88 124 70 121\n",
" MIR_5_RBP: 23 132 88 24 34 190 57 200\n",
" MIR_6_FF: 15 68 30 24 32 58 42 70\n",
" MIR_6_K: 55 76 64 18 26 84 44 129\n",
" MIR_6_KL: 6 5 9 - 1 9 15 17\n",
" MIR_6_R: 2 24 6 5 9 10 2 14\n",
" MIR_6_RB: 17 90 31 34 61 67 41 57\n",
" MIR_6_RBP: 22 103 79 14 18 142 39 190\n",
" ZERO_HALF_FF: 233 124 454 57 70 56 366 566\n",
" ZERO_HALF_K: 77 28 147 8 23 - 126 194\n",
" ZERO_HALF_KL: 16 4 51 - 4 - 33 24\n",
" ZERO_HALF_R: 388 1'463 1'189 505 560 1'940 690 3'540\n",
" ZERO_HALF_RB: 111 189 264 79 128 280 205 597\n",
" ZERO_HALF_RBP: 33 77 144 14 27 72 100 234\n",
"\n",
"LNS stats Improv/Calls Closed Difficulty TimeLimit\n",
" 'graph_arc_lns': 7/208 49% 1.24e-01 0.11\n",
" 'graph_cst_lns': 10/147 50% 4.34e-01 0.10\n",
" 'graph_dec_lns': 10/126 49% 6.48e-01 0.10\n",
" 'graph_var_lns': 9/196 49% 4.22e-01 0.10\n",
" 'lb_relax_lns': 1/9 44% 2.34e-01 0.50\n",
" 'rins/rens': 136/140 49% 1.64e-01 0.10\n",
" 'rnd_cst_lns': 10/126 50% 6.35e-01 0.10\n",
" 'rnd_var_lns': 13/121 50% 6.41e-01 0.10\n",
"\n",
"LS stats Batches Restarts/Perturbs LinMoves GenMoves CompoundMoves Bactracks WeightUpdates ScoreComputed\n",
" 'ls_lin_restart': 34 22 187'990 0 0 0 12'040 9'775'940\n",
" 'ls_lin_restart_compound': 26 21 0 126'113 7'769 59'158 760 5'800'729\n",
" 'ls_lin_restart_compound_perturb': 27 20 0 139'001 7'840 65'557 981 6'617'444\n",
" 'ls_lin_restart_decay': 25 21 162'903 0 0 0 1'743 4'467'716\n",
" 'ls_lin_restart_decay_compound': 43 25 0 220'120 27'585 96'223 644 10'099'558\n",
" 'ls_lin_restart_decay_compound_perturb': 34 22 0 163'861 19'838 71'979 558 6'735'299\n",
" 'ls_lin_restart_decay_perturb': 19 16 122'920 0 0 0 1'243 3'377'138\n",
" 'ls_lin_restart_perturb': 26 19 145'547 0 0 0 9'351 7'168'931\n",
" 'ls_restart': 28 19 155'499 0 0 0 9'752 7'776'336\n",
" 'ls_restart_compound': 41 23 0 214'481 18'610 97'904 995 9'184'383\n",
" 'ls_restart_compound_perturb': 23 20 0 101'823 4'771 48'503 721 4'958'512\n",
" 'ls_restart_decay': 31 23 200'446 0 0 0 1'895 5'599'536\n",
" 'ls_restart_decay_compound': 30 19 0 150'099 21'082 64'470 494 6'627'236\n",
" 'ls_restart_decay_compound_perturb': 17 12 0 87'360 8'828 39'243 266 3'790'123\n",
" 'ls_restart_decay_perturb': 23 18 150'963 0 0 0 1'487 4'180'421\n",
" 'ls_restart_perturb': 39 30 215'648 0 0 0 13'418 10'294'824\n",
"\n",
"Solutions (7) Num Rank\n",
" 'complete_hint': 2 [0,1]\n",
" 'graph_arc_lns': 2 [2,3]\n",
" 'graph_var_lns': 6 [3,6]\n",
" 'lb_relax_lns_bool_h': 2 [6,7]\n",
" 'rnd_cst_lns': 2 [1,2]\n",
"\n",
"Objective bounds Num\n",
" 'am1_presolve': 1\n",
" 'initial_domain': 1\n",
" 'lb_tree_search': 17\n",
" 'max_lp': 25\n",
" 'reduced_costs': 1\n",
"\n",
"Solution repositories Added Queried Synchro\n",
" 'alternative_path': 41 429 41\n",
" 'best_solutions': 216 1'087 131\n",
" 'fj solution hints': 0 0 0\n",
" 'lp solutions': 237 71 224\n",
" 'pump': 1'422 72\n",
"\n",
"Clauses shared #Exported #Imported #BinaryRead #BinaryTotal\n",
" 'core': 22 302 0 0\n",
" 'default_lp': 1 284 0 0\n",
" 'lb_tree_search': 0 321 0 0\n",
" 'max_lp': 0 300 0 0\n",
" 'no_lp': 90 239 0 0\n",
" 'objective_lb_search': 2 319 0 0\n",
" 'probing': 0 0 0 0\n",
" 'pseudo_costs': 1 320 0 0\n",
" 'quick_restart': 0 321 0 0\n",
" 'quick_restart_no_lp': 221 96 0 0\n",
" 'reduced_costs': 1 320 0 0\n",
"\n",
"LRAT_status: NA\n",
"[Scaling] scaled_objective_bound: 485628 corrected_bound: 485628 delta: -1.20554e-06\n",
"CpSolverResponse summary:\n",
"status: FEASIBLE\n",
"objective: 515391.8326607671\n",
"best_bound: 485627.9979077835\n",
"integers: 0\n",
"booleans: 0\n",
"conflicts: 0\n",
"branches: 0\n",
"propagations: 0\n",
"integer_propagations: 0\n",
"restarts: 0\n",
"lp_iterations: 0\n",
"walltime: 90.0445\n",
"usertime: 90.0445\n",
"deterministic_time: 410.036\n",
"gap_integral: 4238.64\n",
"solution_fingerprint: 0x764741a6404bcb58\n",
"\n"
]
},
{
"data": {
"text/plain": [
"TerseLinks(scope='topology', topology='ringed', T=173, R=2, links=203)"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"router_milp = MILPRouter(\n",
" solver_name='ortools.cp_sat',\n",
" time_limit=90,\n",
" mip_gap=0.005,\n",
" model_options=ModelOptions(topology='ringed'),\n",
" verbose=True,\n",
")\n",
"wfn.optimize(router=router_milp)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "4945a5d4",
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"wfn"
]
}
],
"metadata": {
"language_info": {
"name": "python"
}
},
"nbformat": 4,
"nbformat_minor": 5
}