Example – IEA Wind 740-10-MW¶
IEA Wind TCP Task 55: The IEA Wind 740-10-MW Reference Offshore Wind Plants
https://www.osti.gov/biblio/2333634/
This notebook uses optiwindnet to route the collector system cables for the two wind power plants presented in the report above.
This example requires an additional package:
pip install pyyaml-include
[1]:
from pathlib import Path
import numpy as np
import yaml
import yaml_include
[23]:
from optiwindnet.interarraylib import L_from_site, G_from_S, as_normalized
from optiwindnet.svg import svgplot
from optiwindnet.mesh import make_planar_embedding
from optiwindnet.pathfinding import PathFinder
from optiwindnet.interface import assign_cables
from optiwindnet.MILP import solver_factory, ModelOptions
from optiwindnet.baselines.hgs import iterative_hgs_cvrp
Load layouts from files¶
[3]:
# Wind farms stored according to the windIO format
# https://windio.readthedocs.io/en/latest/
yaml.add_constructor(
"!include", yaml_include.Constructor(base_dir='data'))
def load_windIO(filepath):
fpath = Path(filepath)
with open(fpath, 'r') as f:
system = yaml.full_load(f)
coords = (system['wind_farm']['layouts']['initial_layout']
['coordinates'])
terminalC = np.c_[coords['x'], coords['y']]
coords = system['wind_farm']['electrical_substations']['coordinates']
rootC = np.c_[coords['x'], coords['y']]
coords = system['site']['boundaries']['polygons'][0]
borderC = np.c_[coords['x'], coords['y']]
T = terminalC.shape[0]
R = rootC.shape[0]
name_tokens = fpath.stem.split('_')
return L_from_site(
R=R, T=T,
VertexC=np.vstack((terminalC, borderC, rootC)),
border=np.arange(T, T + borderC.shape[0]),
name=' '.join(name_tokens),
handle=(f'{name_tokens[0].lower()}_'
f'{name_tokens[1][:4].lower()}_'
f'{name_tokens[2][:3].lower()}'),
)
[4]:
L_reg = load_windIO('data/IEA37_Borssele_Regular_System.yaml')
[5]:
L_irr = load_windIO('data/IEA37_Borssele_Irregular_System.yaml')
[6]:
svgplot(L_reg)
[6]:
[7]:
svgplot(L_irr)
[7]:
Additional design parameters¶
[8]:
cable_costs = [206, 287, 406] # [€/m] Costs per distance for each cable type
turbines_per_cable = [3, 5, 7]
[9]:
cables = [(capacity, cost) for capacity, cost in zip(turbines_per_cable, cable_costs)]
capacity = max(turbines_per_cable)
Choose the OR-Tools CP-Sat solver¶
[10]:
solver = solver_factory('ortools')
Regular layout¶
[11]:
P, A = make_planar_embedding(L_reg)
[12]:
# This meta-heuristic call is iterative and the time_limit applies
# to each iteration. About 97% of instances use a single iteration.
S_warm = iterative_hgs_cvrp(as_normalized(A), capacity=capacity, time_limit=1)
Check the total length of the warm-start solution:
[13]:
G_reg_warm = G_from_S(S_warm, A)
G_reg_warm.size(weight='length')
[13]:
139656.4789599965
[16]:
solver.set_problem(
P, A,
capacity=G_reg_warm.graph['capacity'],
model_options=ModelOptions(
topology="branched",
feeder_route="segmented",
feeder_limit="unlimited",
),
warmstart=G_reg_warm,
)
[17]:
# required to get the log inside the notebook (goes only to console otherwise)
solver.solver.log_callback = print
solver.solve(
mip_gap=0.005,
time_limit=5,
verbose=True,
)
Starting CP-SAT solver v9.13.4784
Parameters: max_time_in_seconds: 5 log_search_progress: true relative_gap_limit: 0.005
Setting number of workers to 16
Initial optimization model '': (model_fingerprint: 0x4383029b9db7c926)
#Variables: 1'540 (#bools: 770 in floating point objective) (1'392 primary variables)
- 770 Booleans in [0,1]
- 696 in [0,6]
- 74 in [0,7]
#kAtMostOne: 615 (#literals: 1'926)
#kLinear1: 1'540 (#enforced: 1'540)
#kLinear3: 2
#kLinearN: 223 (#terms: 3'844)
Starting presolve at 0.01s
The solution hint is complete, but it is infeasible! we will try to repair it.
[Scaling] Floating point objective has 770 terms with magnitude in [440.736, 14559.3] average = 2880.02
[Scaling] Objective coefficient relative error: 6.70633e-10
[Scaling] Objective worst-case absolute error: 7.704e-05
[Scaling] Objective scaling factor: 1.04858e+06
8.95e-04s 0.00e+00d [DetectDominanceRelations]
2.16e-02s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
1.13e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::ExtractEncodingFromLinear] #potential_supersets=689
5.73e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateColumns]
4.29e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 5'635 nodes and 10'919 arcs.
[Symmetry] Symmetry computation done. time: 0.0013307 dtime: 0.00131276
4.65e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
1.73e-02s 3.73e-03d [operations_research::sat::CpModelPresolver::Probe] #probed=1'540
8.48e-04s 3.93e-04d [MaxClique] Merged 615(1'926 literals) into 303(1'302 literals) at_most_ones.
6.09e-04s 0.00e+00d [DetectDominanceRelations]
5.03e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
6.91e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::ProcessAtMostOneAndLinear]
3.96e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
3.72e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
6.09e-04s 1.30e-05d [operations_research::sat::CpModelPresolver::DetectDominatedLinearConstraints] #relevant_constraints=151 #num_inclusions=75
4.78e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDifferentVariables]
8.91e-03s 3.02e-04d [operations_research::sat::CpModelPresolver::ProcessSetPPC] #relevant_constraints=379 #num_inclusions=377
2.28e-04s 9.20e-07d [operations_research::sat::CpModelPresolver::FindAlmostIdenticalLinearConstraints] #num_tested_pairs=8
6.18e-04s 2.40e-04d [operations_research::sat::CpModelPresolver::FindBigAtMostOneAndLinearOverlap]
4.71e-04s 2.84e-04d [operations_research::sat::CpModelPresolver::FindBigVerticalLinearOverlap]
8.04e-05s 1.15e-05d [operations_research::sat::CpModelPresolver::FindBigHorizontalLinearOverlap] #linears=148
3.89e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::MergeClauses]
5.67e-04s 0.00e+00d [DetectDominanceRelations]
4.57e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
9.03e-04s 0.00e+00d [DetectDominanceRelations]
7.96e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
4.44e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateColumns]
6.50e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 5'010 nodes and 8'901 arcs.
[Symmetry] Symmetry computation done. time: 0.0011942 dtime: 0.00112382
[SAT presolve] num removable Booleans: 0 / 770
[SAT presolve] num trivial clauses: 0
[SAT presolve] [0s] clauses:36 literals:72 vars:72 one_side_vars:72 simple_definition:0 singleton_clauses:0
[SAT presolve] [0.0005214s] clauses:36 literals:72 vars:72 one_side_vars:72 simple_definition:0 singleton_clauses:0
[SAT presolve] [0.0006735s] clauses:36 literals:72 vars:72 one_side_vars:72 simple_definition:0 singleton_clauses:0
4.19e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
1.22e-02s 3.44e-03d [operations_research::sat::CpModelPresolver::Probe] #probed=1'540
7.54e-04s 3.82e-04d [MaxClique]
8.30e-04s 0.00e+00d [DetectDominanceRelations]
1.09e-02s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
8.96e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::ProcessAtMostOneAndLinear]
5.97e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
5.29e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
6.37e-04s 9.79e-06d [operations_research::sat::CpModelPresolver::DetectDominatedLinearConstraints] #relevant_constraints=150 #num_inclusions=74
6.15e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDifferentVariables]
4.66e-04s 6.43e-06d [operations_research::sat::CpModelPresolver::ProcessSetPPC] #relevant_constraints=378
9.03e-05s 8.65e-07d [operations_research::sat::CpModelPresolver::FindAlmostIdenticalLinearConstraints] #num_tested_pairs=7
8.75e-04s 2.38e-04d [operations_research::sat::CpModelPresolver::FindBigAtMostOneAndLinearOverlap]
1.05e-03s 2.84e-04d [operations_research::sat::CpModelPresolver::FindBigVerticalLinearOverlap]
9.82e-05s 1.15e-05d [operations_research::sat::CpModelPresolver::FindBigHorizontalLinearOverlap] #linears=148
6.92e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::MergeClauses]
8.02e-04s 0.00e+00d [DetectDominanceRelations]
7.06e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
7.79e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::ExpandObjective] #entries=7'668 #tight_variables=770 #tight_constraints=74
Presolve summary:
- 0 affine relations were detected.
- rule 'TODO linear inclusion: superset is equality' was applied 149 times.
- rule 'at_most_one: transformed into max clique.' was applied 1 time.
- rule 'deductions: 1540 stored' was applied 1 time.
- rule 'exactly_one: simplified objective' was applied 74 times.
- rule 'linear: positive equal one' was applied 74 times.
- rule 'objective: shifted cost with exactly ones' was applied 74 times.
- rule 'presolve: 0 unused variables removed.' was applied 1 time.
- rule 'presolve: iteration' was applied 2 times.
- rule 'setppc: exactly_one included in linear' was applied 74 times.
- rule 'setppc: reduced linear coefficients' was applied 73 times.
- rule 'setppc: removed trivial linear constraint' was applied 1 time.
- rule 'variables: detect fully reified value encoding' was applied 770 times.
- rule 'variables: detect half reified value encoding' was applied 1'540 times.
Presolved optimization model '': (model_fingerprint: 0x3d33b4ecd3cc01e8)
#Variables: 1'540 (#bools: 696 in objective) (1'392 primary variables)
- 770 Booleans in [0,1]
- 696 in [0,6]
- 74 in [0,7]
#kAtMostOne: 267 (#literals: 1'230)
#kBoolAnd: 36 (#enforced: 36) (#literals: 72)
#kExactlyOne: 74 (#literals: 770)
#kLinear1: 1'540 (#enforced: 1'540)
#kLinear3: 2
#kLinearN: 148 (#terms: 2'304)
[Symmetry] Graph for symmetry has 5'010 nodes and 8'901 arcs.
[Symmetry] Symmetry computation done. time: 0.0011813 dtime: 0.00112552
Preloading model.
#Bound 0.15s best:inf next:[123610.947,1039461.48] initial_domain
The solution hint is complete, but it is infeasible! we will try to repair it.
#Model 0.16s var:1540/1540 constraints:2067/2067
Starting search at 0.16s with 16 workers.
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]
5 first solution subsolvers: [fj(2), fs_random, fs_random_no_lp, fs_random_quick_restart_no_lp]
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]
3 helper subsolvers: [neighborhood_helper, synchronization_agent, update_gap_integral]
#1 0.17s best:139656.479 next:[123610.947,139656.479] fj_restart(batch:1 lin{mvs:2 evals:45} #w_updates:0 #perturb:0)
#Bound 0.20s best:139656.479 next:[123610.951,139656.479] am1_presolve (num_literals=696 num_am1=20 increase=4458 work_done=2557)
#2 0.21s best:139650.831 next:[123610.951,139650.831] ls_restart_decay(batch:1 lin{mvs:8 evals:220} #w_updates:4 #perturb:0) (fixed_bools=0/770)
#3 0.23s best:139650.831 next:[123610.951,139650.831] graph_var_lns (d=5.00e-01 s=18 t=0.10 p=0.00 stall=0 h=base) (fixed_bools=0/770)
#4 0.24s best:139645.183 next:[123610.951,139645.183] graph_var_lns (d=5.00e-01 s=18 t=0.10 p=0.00 stall=0 h=base) [combined with: ls_restart_decay(bat...] (fixed_bools=0/770)
#Bound 0.25s best:139645.183 next:[131572.556,139645.183] default_lp
#Bound 0.25s best:139645.183 next:[131572.567,139645.183] objective_lb_search
#Bound 0.25s best:139645.183 next:[131572.568,139645.183] pseudo_costs
#Bound 0.28s best:139645.183 next:[135687.688,139645.183] lb_tree_search
#5 0.29s best:139645.183 next:[135687.688,139645.183] rnd_var_lns (d=7.07e-01 s=25 t=0.10 p=1.00 stall=1 h=base) [combined with: graph_var_lns (d=5.0...] (fixed_bools=0/770)
#Model 0.31s var:1530/1540 constraints:2057/2067
#Bound 0.41s best:139645.183 next:[135871.229,139645.183] max_lp
#Bound 0.43s best:139645.183 next:[135882.866,139645.183] lb_tree_search
#Bound 0.60s best:139645.183 next:[136015.862,139645.183] max_lp
#Bound 0.78s best:139645.183 next:[136058.598,139645.183] max_lp
#Model 0.79s var:1484/1540 constraints:2009/2067
#Bound 0.87s best:139645.183 next:[136111.239,139645.183] lb_tree_search
#Bound 0.96s best:139645.183 next:[136162.975,139645.183] max_lp
#Bound 1.19s best:139645.183 next:[136168.717,139645.183] lb_tree_search
#Bound 1.46s best:139645.183 next:[136206.419,139645.183] lb_tree_search
#Bound 1.58s best:139645.183 next:[136207.145,139645.183] max_lp
#Model 1.59s var:1480/1540 constraints:2005/2067
#Bound 1.85s best:139645.183 next:[136269.96,139645.183] max_lp
#Model 1.91s var:1478/1540 constraints:2003/2067
#Bound 2.05s best:139645.183 next:[136303.526,139645.183] probing
#Bound 2.24s best:139645.183 next:[136333.226,139645.183] probing
#Model 2.30s var:1474/1540 constraints:1999/2067
#Bound 2.44s best:139645.183 next:[136360.912,139645.183] probing
#Bound 2.50s best:139645.183 next:[136373.099,139645.183] probing
#Bound 2.51s best:139645.183 next:[136382.729,139645.183] quick_restart
#Bound 2.70s best:139645.183 next:[136416.162,139645.183] probing
#Bound 2.77s best:139645.183 next:[136433.875,139645.183] quick_restart
#Model 3.12s var:1472/1540 constraints:1996/2067
#Bound 3.19s best:139645.183 next:[136490.573,139645.183] quick_restart
#Bound 3.66s best:139645.183 next:[136524.393,139645.183] quick_restart [skipped_logs=0]
#Bound 4.97s best:139645.183 next:[136577.799,139645.183] quick_restart [skipped_logs=1]
Task timing n [ min, max] avg dev time n [ min, max] avg dev dtime
'core': 1 [ 4.85s, 4.85s] 4.85s 0.00ns 4.85s 1 [ 2.20s, 2.20s] 2.20s 0.00ns 2.20s
'default_lp': 1 [ 4.85s, 4.85s] 4.85s 0.00ns 4.85s 1 [964.65ms, 964.65ms] 964.65ms 0.00ns 964.65ms
'feasibility_pump': 23 [ 82.10us, 1.24s] 54.70ms 252.63ms 1.26s 1 [571.15ms, 571.15ms] 571.15ms 0.00ns 571.15ms
'fj': 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'fj': 1 [ 16.13ms, 16.13ms] 16.13ms 0.00ns 16.13ms 1 [ 9.26us, 9.26us] 9.26us 0.00ns 9.26us
'fs_random': 1 [ 17.37ms, 17.37ms] 17.37ms 0.00ns 17.37ms 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'fs_random_no_lp': 1 [ 17.89ms, 17.89ms] 17.89ms 0.00ns 17.89ms 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'fs_random_quick_restart_no_lp': 1 [ 17.15ms, 17.15ms] 17.15ms 0.00ns 17.15ms 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'graph_arc_lns': 7 [ 42.12ms, 532.88ms] 318.89ms 209.26ms 2.23s 7 [552.40us, 100.25ms] 58.08ms 48.51ms 406.59ms
'graph_cst_lns': 10 [ 28.70ms, 434.07ms] 219.32ms 167.88ms 2.19s 10 [ 27.34us, 100.11ms] 43.17ms 47.00ms 431.71ms
'graph_dec_lns': 10 [ 9.90ms, 576.45ms] 227.83ms 202.84ms 2.28s 10 [ 10.00ns, 100.41ms] 41.48ms 44.10ms 414.84ms
'graph_var_lns': 9 [ 43.66ms, 574.58ms] 252.11ms 188.67ms 2.27s 9 [446.40us, 100.35ms] 47.31ms 43.20ms 425.75ms
'lb_relax_lns': 2 [803.93ms, 1.97s] 1.38s 580.60ms 2.77s 2 [144.44ms, 547.28ms] 345.86ms 201.42ms 691.72ms
'lb_tree_search': 1 [ 4.85s, 4.85s] 4.85s 0.00ns 4.85s 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'ls': 12 [ 11.06ms, 279.57ms] 185.01ms 81.53ms 2.22s 12 [ 66.79us, 100.02ms] 83.37ms 37.20ms 1.00s
'ls_lin': 11 [ 36.62ms, 305.35ms] 196.07ms 75.88ms 2.16s 10 [ 34.58ms, 100.03ms] 93.47ms 19.63ms 934.72ms
'max_lp': 1 [ 4.85s, 4.85s] 4.85s 0.00ns 4.85s 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'no_lp': 1 [ 4.84s, 4.84s] 4.84s 0.00ns 4.84s 1 [ 1.46s, 1.46s] 1.46s 0.00ns 1.46s
'objective_lb_search': 1 [ 4.85s, 4.85s] 4.85s 0.00ns 4.85s 1 [ 1.14s, 1.14s] 1.14s 0.00ns 1.14s
'probing': 1 [ 4.85s, 4.85s] 4.85s 0.00ns 4.85s 1 [345.25ms, 345.25ms] 345.25ms 0.00ns 345.25ms
'pseudo_costs': 1 [ 4.85s, 4.85s] 4.85s 0.00ns 4.85s 1 [ 1.21s, 1.21s] 1.21s 0.00ns 1.21s
'quick_restart': 1 [ 4.85s, 4.85s] 4.85s 0.00ns 4.85s 1 [300.27ms, 300.27ms] 300.27ms 0.00ns 300.27ms
'quick_restart_no_lp': 1 [ 4.84s, 4.84s] 4.84s 0.00ns 4.84s 1 [ 1.52s, 1.52s] 1.52s 0.00ns 1.52s
'reduced_costs': 1 [ 4.85s, 4.85s] 4.85s 0.00ns 4.85s 1 [ 1.21s, 1.21s] 1.21s 0.00ns 1.21s
'rins/rens': 10 [ 12.33ms, 464.90ms] 228.09ms 177.86ms 2.28s 8 [108.86us, 100.06ms] 59.73ms 42.46ms 477.84ms
'rnd_cst_lns': 10 [ 11.42ms, 556.10ms] 221.73ms 211.10ms 2.22s 9 [195.00ns, 100.23ms] 45.97ms 48.46ms 413.73ms
'rnd_var_lns': 9 [ 19.41ms, 489.54ms] 252.22ms 156.13ms 2.27s 9 [134.00ns, 100.29ms] 49.77ms 41.53ms 447.93ms
Search stats Bools Conflicts Branches Restarts BoolPropag IntegerPropag
'core': 790 74'796 224'090 6'911 1'314'946 3'804'483
'default_lp': 777 43 1'922 1'541 14'070 52'862
'fs_random': 770 0 0 0 0 0
'fs_random_no_lp': 770 0 0 0 0 0
'fs_random_quick_restart_no_lp': 770 0 0 0 0 0
'lb_tree_search': 770 0 1'731 1'540 12'126 40'929
'max_lp': 770 0 1'549 1'540 11'842 39'525
'no_lp': 770 18'527 44'096 9'367 1'631'257 6'503'878
'objective_lb_search': 772 38 1'816 1'541 13'507 50'617
'probing': 771 12 1'764 1'545 12'578 44'358
'pseudo_costs': 770 50 1'958 1'542 15'252 58'536
'quick_restart': 770 10 1'769 1'541 12'478 43'774
'quick_restart_no_lp': 855 11'766 200'388 9'939 1'036'645 4'843'803
'reduced_costs': 772 80 5'576 3'080 26'998 151'073
SAT stats ClassicMinim LitRemoved LitLearned LitForgotten Subsumed MClauses MDecisions MLitTrue MSubsumed MLitRemoved MReused
'core': 70'604 678'184 3'805'298 2'901'843 1'007 1'045 10'440 0 111 1'747 175
'default_lp': 39 1'875 7'399 0 0 0 0 0 0 0 0
'fs_random': 0 0 0 0 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0 0 0 0 0
'lb_tree_search': 0 0 0 0 0 0 0 0 0 0 0
'max_lp': 0 0 0 0 0 0 0 0 0 0 0
'no_lp': 17'957 1'166'775 1'221'200 248'709 115 755 7'015 0 4 94 0
'objective_lb_search': 37 3'092 3'025 0 0 0 0 0 0 0 0
'probing': 11 706 2'823 0 0 0 0 0 0 0 0
'pseudo_costs': 48 3'274 8'142 0 0 0 0 0 0 0 0
'quick_restart': 8 528 2'475 0 0 0 0 0 0 0 0
'quick_restart_no_lp': 11'256 414'485 980'314 417'698 51 1'225 9'461 0 124 1'120 65
'reduced_costs': 68 3'121 18'430 0 2 148 1'326 0 0 0 0
Lp stats Component Iterations AddedCuts OPTIMAL DUAL_F. DUAL_U.
'default_lp': 1 11'289 2'905 372 1 7
'lb_tree_search': 1 4'953 1'771 115 2 0
'max_lp': 1 3'295 1'914 27 2 0
'objective_lb_search': 1 13'946 2'571 338 2 1
'probing': 1 5'629 3'749 202 0 0
'pseudo_costs': 1 15'013 3'483 292 79 3
'quick_restart': 1 5'948 3'455 198 0 0
'reduced_costs': 1 14'110 3'455 237 102 23
Lp dimension Final dimension of first component
'default_lp': 1523 rows, 1466 columns, 17945 entries
'lb_tree_search': 3238 rows, 1540 columns, 31769 entries
'max_lp': 3258 rows, 1540 columns, 31272 entries
'objective_lb_search': 1429 rows, 1466 columns, 16063 entries
'probing': 1760 rows, 1466 columns, 22873 entries
'pseudo_costs': 1780 rows, 1540 columns, 14856 entries
'quick_restart': 1789 rows, 1466 columns, 20277 entries
'reduced_costs': 1965 rows, 1540 columns, 18484 entries
Lp debug CutPropag CutEqPropag Adjust Overflow Bad BadScaling
'default_lp': 0 0 367 0 10'221 0
'lb_tree_search': 0 0 117 0 18'711 0
'max_lp': 0 14 29 0 24'348 0
'objective_lb_search': 0 0 325 0 10'172 0
'probing': 0 0 183 0 19'837 0
'pseudo_costs': 0 0 369 0 15'469 0
'quick_restart': 0 0 180 0 16'409 0
'reduced_costs': 0 0 322 0 13'644 0
Lp pool Constraints Updates Simplif Merged Shortened Split Strenghtened Cuts/Call
'default_lp': 5'484 72 1'035 0 927 9 65 2'905/5'854
'lb_tree_search': 4'608 253 1'270 0 1'012 126 65 1'771/3'552
'max_lp': 4'751 285 1'549 0 985 184 73 1'914/3'821
'objective_lb_search': 5'150 95 1'026 0 735 12 371 2'571/5'052
'probing': 6'328 175 2'667 0 1'450 152 348 3'749/7'582
'pseudo_costs': 6'316 131 2'261 4 1'416 60 121 3'483/6'470
'quick_restart': 6'032 152 2'548 2 1'490 141 190 3'455/7'031
'reduced_costs': 6'291 98 1'367 1 1'125 18 96 3'455/6'860
Lp Cut default_lp max_lp quick_restart reduced_costs pseudo_costs lb_tree_search probing objective_lb_search
CG_FF: 31 6 18 45 43 6 41 22
CG_K: 11 4 10 21 18 3 13 9
CG_KL: 4 - - 1 4 - 3 1
CG_R: 27 24 38 60 59 41 54 33
CG_RB: 78 73 76 122 129 80 124 81
CG_RBP: 27 11 33 35 34 37 57 40
Clique: - - - 2 1 - - -
IB: 651 - 654 691 724 3 587 581
MIR_1_FF: 128 67 139 125 110 48 186 122
MIR_1_K: 38 - 45 34 11 1 43 31
MIR_1_KL: 17 - 26 25 17 - 32 19
MIR_1_R: 1 2 4 - 4 1 1 2
MIR_1_RB: 76 38 93 67 81 41 93 54
MIR_1_RBP: 78 7 81 28 26 8 93 55
MIR_2_FF: 144 109 152 191 165 81 167 124
MIR_2_K: 73 4 77 38 51 3 75 57
MIR_2_KL: 21 - 20 22 20 - 17 24
MIR_2_R: 8 9 16 18 20 7 9 4
MIR_2_RB: 145 110 154 180 230 114 156 97
MIR_2_RBP: 84 34 97 35 49 19 112 94
MIR_3_FF: 98 121 127 156 165 97 132 75
MIR_3_K: 53 32 78 51 50 21 94 56
MIR_3_KL: 10 - 13 12 15 4 11 7
MIR_3_R: 6 11 14 16 13 15 12 6
MIR_3_RB: 114 101 109 168 220 120 119 95
MIR_3_RBP: 62 25 71 40 45 29 88 61
MIR_4_FF: 63 95 90 89 117 64 95 63
MIR_4_K: 38 42 75 53 40 28 75 38
MIR_4_KL: 5 3 6 6 15 4 10 6
MIR_4_R: 4 14 13 10 8 16 9 2
MIR_4_RB: 56 69 62 119 114 88 69 56
MIR_4_RBP: 39 44 65 30 43 32 90 36
MIR_5_FF: 39 66 50 48 61 47 83 36
MIR_5_K: 34 46 63 54 30 33 61 30
MIR_5_KL: 5 9 6 13 6 9 15 12
MIR_5_R: 3 9 10 4 4 14 6 1
MIR_5_RB: 34 57 25 54 69 59 51 43
MIR_5_RBP: 37 60 71 43 37 38 72 33
MIR_6_FF: 33 51 26 42 37 42 34 22
MIR_6_K: 26 31 50 52 36 46 44 21
MIR_6_KL: 7 14 5 11 12 11 15 8
MIR_6_R: 2 4 6 4 3 5 - -
MIR_6_RB: 18 46 22 39 53 40 27 21
MIR_6_RBP: 42 46 55 34 36 38 72 23
ZERO_HALF_FF: 43 24 69 60 44 12 57 35
ZERO_HALF_K: 15 1 10 13 5 - 18 16
ZERO_HALF_KL: 2 1 3 4 3 1 1 2
ZERO_HALF_R: 317 327 419 400 337 319 435 263
ZERO_HALF_RB: 36 56 86 73 58 34 55 38
ZERO_HALF_RBP: 22 11 23 17 11 12 36 16
LNS stats Improv/Calls Closed Difficulty TimeLimit
'graph_arc_lns': 0/7 43% 4.01e-01 0.10
'graph_cst_lns': 0/10 50% 6.61e-01 0.10
'graph_dec_lns': 0/10 70% 8.99e-01 0.10
'graph_var_lns': 1/9 56% 7.22e-01 0.10
'lb_relax_lns': 1/2 50% 5.38e-01 0.50
'rins/rens': 10/10 50% 6.61e-01 0.10
'rnd_cst_lns': 0/9 56% 7.81e-01 0.10
'rnd_var_lns': 1/9 56% 7.81e-01 0.10
LS stats Batches Restarts/Perturbs LinMoves GenMoves CompoundMoves Bactracks WeightUpdates ScoreComputed
'fj_restart': 1 1 2 0 0 0 0 50
'ls_lin_restart': 2 2 24'152 0 0 0 5'263 686'046
'ls_lin_restart_compound_perturb': 2 2 0 32'135 3'031 14'551 194 821'100
'ls_lin_restart_decay': 1 1 14'674 0 0 0 322 298'482
'ls_lin_restart_decay_compound': 2 2 0 25'474 4'079 10'693 67 693'682
'ls_lin_restart_decay_compound_perturb': 1 1 0 13'477 2'053 5'701 41 357'520
'ls_lin_restart_decay_perturb': 1 1 14'999 0 0 0 323 305'263
'ls_lin_restart_perturb': 2 2 4'512 0 0 0 657 127'815
'ls_restart': 1 1 11'505 0 0 0 1'971 339'636
'ls_restart_compound': 2 2 0 32'126 3'022 14'550 243 817'008
'ls_restart_compound_perturb': 2 2 0 34'714 3'211 15'750 216 889'019
'ls_restart_decay': 2 2 28 0 0 0 14 472
'ls_restart_decay_compound': 2 2 0 25'061 4'205 10'425 62 691'001
'ls_restart_decay_perturb': 1 1 14'710 0 0 0 307 299'061
'ls_restart_perturb': 2 2 23'823 0 0 0 4'912 700'671
Solutions (5) Num Rank
'fj_restart': 1 [1,1]
'graph_var_lns': 2 [3,4]
'ls_restart_decay': 1 [2,2]
'rnd_var_lns': 1 [5,5]
Objective bounds Num
'am1_presolve': 1
'default_lp': 1
'initial_domain': 1
'lb_tree_search': 5
'max_lp': 6
'objective_lb_search': 1
'probing': 5
'pseudo_costs': 1
'quick_restart': 6
Solution repositories Added Queried Synchro
'feasible solutions': 10 164 8
'fj solution hints': 0 0 0
'lp solutions': 15 8 11
'pump': 29 2
Improving bounds shared Num Sym
'max_lp': 52 0
'probing': 4 0
'pseudo_costs': 2 0
'quick_restart_no_lp': 10 0
'reduced_costs': 10 0
Clauses shared Num
'core': 13
'no_lp': 282
'quick_restart_no_lp': 5
[Scaling] scaled_objective_bound: 136578 corrected_bound: 136578 delta: 4.34869e-07
CpSolverResponse summary:
status: FEASIBLE
objective: 139645.18265364
best_bound: 136577.7989707413
integers: 1466
booleans: 770
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 0
restarts: 0
lp_iterations: 0
walltime: 5.12495
usertime: 5.12495
deterministic_time: 16.5727
gap_integral: 133.398
solution_fingerprint: 0xeec6f0babc106d38
[17]:
SolutionInfo(runtime=5.124953700000001, bound=136577.79897074128, objective=139645.18265364, relgap=0.021965553158440843, termination='FEASIBLE')
[18]:
S_reg, G_reg = solver.get_solution()
[19]:
assign_cables(G_reg, cables)
G_reg.size(weight='cost')
[19]:
40714260.58298516
[20]:
svgplot(G_reg)
[20]:
Irregular layout¶
[21]:
P, A = make_planar_embedding(L_irr)
[24]:
# This meta-heuristic call is iterative and the time_limit applies
# to each iteration. About 97% of instances use a single iteration.
S_warm = iterative_hgs_cvrp(as_normalized(A), capacity=capacity, time_limit=3)
Check the total length of the warm-start solution:
[25]:
G_irr_warm = G_from_S(S_warm, A)
G_irr_warm.size(weight='length')
[25]:
136451.2768186806
[26]:
solver.set_problem(
P, A,
capacity=G_irr_warm.graph['capacity'],
model_options=ModelOptions(
topology="branched",
feeder_route="segmented",
feeder_limit="unlimited",
),
warmstart=G_irr_warm,
)
[27]:
# required to get the log inside the notebook (goes only to console otherwise)
solver.solver.log_callback = print
solver.solve(
mip_gap=0.005,
time_limit=300,
verbose=True,
)
Starting CP-SAT solver v9.13.4784
Parameters: max_time_in_seconds: 300 log_search_progress: true relative_gap_limit: 0.005
Setting number of workers to 16
Initial optimization model '': (model_fingerprint: 0x68b2e1d9c4c26564)
#Variables: 1'192 (#bools: 596 in floating point objective) (1'044 primary variables)
- 596 Booleans in [0,1]
- 522 in [0,6]
- 74 in [0,7]
#kAtMostOne: 419 (#literals: 1'216)
#kLinear1: 1'192 (#enforced: 1'192)
#kLinear2: 4
#kLinear3: 5
#kLinearN: 216 (#terms: 2'957)
Starting presolve at 0.01s
The solution hint is complete and is feasible.
[Scaling] Floating point objective has 596 terms with magnitude in [539.378, 15073.7] average = 3460.13
[Scaling] Objective coefficient relative error: 4.51281e-10
[Scaling] Objective worst-case absolute error: 7.28067e-05
[Scaling] Objective scaling factor: 1.04858e+06
5.46e-04s 0.00e+00d [DetectDominanceRelations]
1.25e-02s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
8.31e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::ExtractEncodingFromLinear] #potential_supersets=493
5.01e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateColumns]
4.91e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 4'322 nodes and 8'135 arcs.
[Symmetry] Symmetry computation done. time: 0.0015477 dtime: 0.00078168
8.21e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
1.56e-02s 2.33e-03d [operations_research::sat::CpModelPresolver::Probe] #probed=1'192
7.86e-04s 2.24e-04d [MaxClique] Merged 419(1'216 literals) into 234(846 literals) at_most_ones.
5.12e-04s 0.00e+00d [DetectDominanceRelations]
5.05e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
6.66e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::ProcessAtMostOneAndLinear]
1.30e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
1.31e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
5.98e-04s 1.01e-05d [operations_research::sat::CpModelPresolver::DetectDominatedLinearConstraints] #relevant_constraints=151 #num_inclusions=75
5.49e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDifferentVariables]
6.58e-03s 1.92e-04d [operations_research::sat::CpModelPresolver::ProcessSetPPC] #relevant_constraints=310 #num_inclusions=308
1.60e-04s 1.00e-07d [operations_research::sat::CpModelPresolver::FindAlmostIdenticalLinearConstraints] #num_tested_pairs=2
6.53e-04s 1.82e-04d [operations_research::sat::CpModelPresolver::FindBigAtMostOneAndLinearOverlap]
2.96e-04s 2.07e-04d [operations_research::sat::CpModelPresolver::FindBigVerticalLinearOverlap]
5.31e-05s 8.71e-06d [operations_research::sat::CpModelPresolver::FindBigHorizontalLinearOverlap] #linears=136
2.59e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::MergeClauses]
1.07e-03s 0.00e+00d [DetectDominanceRelations]
4.73e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
6.11e-04s 0.00e+00d [DetectDominanceRelations]
6.08e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
4.37e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateColumns]
5.03e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 3'951 nodes and 6'799 arcs.
[Symmetry] Symmetry computation done. time: 0.001077 dtime: 0.00071227
[SAT presolve] num removable Booleans: 0 / 596
[SAT presolve] num trivial clauses: 0
[SAT presolve] [0s] clauses:76 literals:152 vars:152 one_side_vars:152 simple_definition:0 singleton_clauses:0
[SAT presolve] [0.0004182s] clauses:76 literals:152 vars:152 one_side_vars:152 simple_definition:0 singleton_clauses:0
[SAT presolve] [0.0008263s] clauses:76 literals:152 vars:152 one_side_vars:152 simple_definition:0 singleton_clauses:0
6.36e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
2.65e-02s 2.15e-03d [operations_research::sat::CpModelPresolver::Probe] #probed=1'192
1.11e-03s 2.18e-04d [MaxClique]
7.39e-04s 0.00e+00d [DetectDominanceRelations]
9.73e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
1.02e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::ProcessAtMostOneAndLinear]
6.77e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
1.08e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
7.76e-04s 7.55e-06d [operations_research::sat::CpModelPresolver::DetectDominatedLinearConstraints] #relevant_constraints=150 #num_inclusions=74
8.93e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDifferentVariables]
4.76e-04s 4.57e-06d [operations_research::sat::CpModelPresolver::ProcessSetPPC] #relevant_constraints=309
1.07e-04s 5.50e-08d [operations_research::sat::CpModelPresolver::FindAlmostIdenticalLinearConstraints] #num_tested_pairs=1
4.60e-03s 1.81e-04d [operations_research::sat::CpModelPresolver::FindBigAtMostOneAndLinearOverlap]
5.29e-04s 2.07e-04d [operations_research::sat::CpModelPresolver::FindBigVerticalLinearOverlap]
1.02e-04s 8.71e-06d [operations_research::sat::CpModelPresolver::FindBigHorizontalLinearOverlap] #linears=136
5.66e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::MergeClauses]
9.47e-04s 0.00e+00d [DetectDominanceRelations]
9.93e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
1.39e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::ExpandObjective] #entries=4'968 #tight_variables=596 #tight_constraints=74
Presolve summary:
- 0 affine relations were detected.
- rule 'TODO linear inclusion: superset is equality' was applied 149 times.
- rule 'at_most_one: transformed into max clique.' was applied 1 time.
- rule 'deductions: 1192 stored' was applied 1 time.
- rule 'exactly_one: simplified objective' was applied 74 times.
- rule 'linear: positive equal one' was applied 74 times.
- rule 'objective: shifted cost with exactly ones' was applied 74 times.
- rule 'presolve: 0 unused variables removed.' was applied 1 time.
- rule 'presolve: iteration' was applied 2 times.
- rule 'setppc: exactly_one included in linear' was applied 74 times.
- rule 'setppc: reduced linear coefficients' was applied 73 times.
- rule 'setppc: removed trivial linear constraint' was applied 1 time.
- rule 'variables: detect fully reified value encoding' was applied 596 times.
- rule 'variables: detect half reified value encoding' was applied 1'192 times.
Presolved optimization model '': (model_fingerprint: 0x60b6d94345cbc917)
#Variables: 1'192 (#bools: 522 in objective) (1'044 primary variables)
- 596 Booleans in [0,1]
- 522 in [0,6]
- 74 in [0,7]
#kAtMostOne: 158 (#literals: 694)
#kBoolAnd: 76 (#enforced: 76) (#literals: 152)
#kExactlyOne: 74 (#literals: 596)
#kLinear1: 1'192 (#enforced: 1'192)
#kLinear2: 4
#kLinear3: 1
#kLinearN: 145 (#terms: 1'777)
[Symmetry] Graph for symmetry has 3'951 nodes and 6'799 arcs.
[Symmetry] Symmetry computation done. time: 0.0015166 dtime: 0.00071123
Preloading model.
#Bound 0.23s best:inf next:[93516.0522,1236251.99] initial_domain
#1 0.23s best:136451.277 next:[93516.0522,136451.277] complete_hint
#Model 0.24s var:1192/1192 constraints:1650/1650
Starting search at 0.24s with 16 workers.
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]
5 first solution subsolvers: [fj(2), fs_random, fs_random_no_lp, fs_random_quick_restart_no_lp]
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]
3 helper subsolvers: [neighborhood_helper, synchronization_agent, update_gap_integral]
#Bound 0.29s best:136451.277 next:[95755.9972,136451.277] am1_presolve (num_literals=522 num_am1=19 increase=2348752631 work_done=1852)
#Bound 0.32s best:136451.277 next:[104424.449,136451.277] quick_restart
#Bound 0.33s best:136451.277 next:[106103.007,136451.277] pseudo_costs
#Bound 0.38s best:136451.277 next:[127628.142,136451.277] max_lp
#2 0.46s best:136417.955 next:[127628.142,136417.955] quick_restart_no_lp (fixed_bools=0/630)
#3 0.50s best:136208.855 next:[127628.142,136208.855] quick_restart_no_lp (fixed_bools=0/631)
#Bound 0.53s best:136208.855 next:[128596.989,136208.855] max_lp
#Bound 0.70s best:136208.855 next:[129028.386,136208.855] max_lp
#4 0.74s best:134786.792 next:[129028.386,134786.792] lb_relax_lns_int (d=5.00e-01 s=17 t=0.50 p=0.00 stall=0 h=base)
#Bound 0.77s best:134786.792 next:[129106.833,134786.792] lb_tree_search
#Bound 0.90s best:134786.792 next:[129486.13,134786.792] max_lp
#Model 0.98s var:1186/1192 constraints:1643/1650
#Bound 1.14s best:134786.792 next:[129727.228,134786.792] lb_tree_search
#Bound 1.14s best:134786.792 next:[130037.671,134786.792] max_lp
#Bound 1.49s best:134786.792 next:[130175.94,134786.792] max_lp
#Model 1.54s var:1176/1192 constraints:1631/1650
#Bound 2.26s best:134786.792 next:[130296.944,134786.792] max_lp
#Bound 3.01s best:134786.792 next:[130452.788,134786.792] max_lp
#Model 3.08s var:1174/1192 constraints:1629/1650
#Bound 3.14s best:134786.792 next:[130489.036,134786.792] lb_tree_search
#Bound 3.76s best:134786.792 next:[130529.451,134786.792] max_lp
#Bound 3.92s best:134786.792 next:[130695.989,134786.792] lb_tree_search
#Model 4.54s var:1148/1192 constraints:1603/1650
#Bound 4.81s best:134786.792 next:[130768.919,134786.792] lb_tree_search
#Model 4.87s var:1140/1192 constraints:1594/1650
#Bound 5.72s best:134786.792 next:[130836.431,134786.792] lb_tree_search
#Bound 6.58s best:134786.792 next:[130991.676,134786.792] lb_tree_search
#Bound 7.61s best:134786.792 next:[131103.489,134786.792] lb_tree_search
#Model 7.63s var:1132/1192 constraints:1586/1650
#Bound 8.51s best:134786.792 next:[131160.178,134786.792] lb_tree_search
#Model 8.52s var:1128/1192 constraints:1581/1650
#Bound 9.63s best:134786.792 next:[131246.99,134786.792] lb_tree_search
#Model 9.68s var:1122/1192 constraints:1575/1650
#Bound 10.69s best:134786.792 next:[131283.137,134786.792] lb_tree_search
#Model 10.80s var:1120/1192 constraints:1573/1650
#Bound 11.65s best:134786.792 next:[131307.808,134786.792] lb_tree_search
#Bound 12.72s best:134786.792 next:[131343.11,134786.792] lb_tree_search
#Bound 13.66s best:134786.792 next:[131374.805,134786.792] lb_tree_search
#Bound 14.95s best:134786.792 next:[131442.72,134786.792] lb_tree_search
#Model 14.99s var:1118/1192 constraints:1571/1650
#Bound 16.17s best:134786.792 next:[131472.095,134786.792] lb_tree_search
#Bound 17.21s best:134786.792 next:[131498.092,134786.792] lb_tree_search
#Model 17.27s var:1114/1192 constraints:1567/1650
#Bound 18.29s best:134786.792 next:[131512.53,134786.792] lb_tree_search
#Bound 19.37s best:134786.792 next:[131525.062,134786.792] lb_tree_search
#Bound 20.39s best:134786.792 next:[131549.126,134786.792] lb_tree_search
#Model 20.47s var:1110/1192 constraints:1563/1650
#Bound 21.53s best:134786.792 next:[131589.276,134786.792] lb_tree_search
#Model 21.64s var:1106/1192 constraints:1559/1650
#Bound 22.80s best:134786.792 next:[131613.318,134786.792] lb_tree_search
#Bound 24.00s best:134786.792 next:[131625.139,134786.792] lb_tree_search
#Bound 25.32s best:134786.792 next:[131655.562,134786.792] lb_tree_search
#Bound 26.54s best:134786.792 next:[131689.542,134786.792] lb_tree_search
#Model 26.61s var:1102/1192 constraints:1555/1650
#Bound 27.82s best:134786.792 next:[131715.442,134786.792] lb_tree_search
#Bound 29.28s best:134786.792 next:[131743.634,134786.792] lb_tree_search
#Bound 30.54s best:134786.792 next:[131751.036,134786.792] lb_tree_search
#Model 30.59s var:1100/1192 constraints:1553/1650
#Bound 32.07s best:134786.792 next:[131770.374,134786.792] lb_tree_search
#Bound 33.52s best:134786.792 next:[131777.072,134786.792] lb_tree_search
#Bound 35.06s best:134786.792 next:[131783.121,134786.792] lb_tree_search
#Bound 36.40s best:134786.792 next:[131787.522,134786.792] lb_tree_search
#Bound 37.57s best:134786.792 next:[131789.145,134786.792] lb_tree_search
#Bound 38.72s best:134786.792 next:[131791.627,134786.792] lb_tree_search
#Bound 40.09s best:134786.792 next:[131796.838,134786.792] lb_tree_search
#Bound 41.46s best:134786.792 next:[131808.263,134786.792] lb_tree_search
#Bound 42.81s best:134786.792 next:[131812.157,134786.792] lb_tree_search
#Model 43.55s var:1098/1192 constraints:1551/1650
#Bound 44.27s best:134786.792 next:[131815.012,134786.792] lb_tree_search
#Bound 45.78s best:134786.792 next:[131822.845,134786.792] lb_tree_search
#Model 45.82s var:1096/1192 constraints:1549/1650
#Bound 47.22s best:134786.792 next:[131831.651,134786.792] lb_tree_search
#Bound 48.60s best:134786.792 next:[131837.312,134786.792] lb_tree_search
#Model 48.66s var:1094/1192 constraints:1547/1650
#Bound 50.00s best:134786.792 next:[131842.498,134786.792] lb_tree_search
#Model 50.03s var:1092/1192 constraints:1545/1650
#Bound 51.33s best:134786.792 next:[131847.588,134786.792] lb_tree_search
#Bound 52.61s best:134786.792 next:[131852.584,134786.792] lb_tree_search
#Model 52.65s var:1090/1192 constraints:1543/1650
#Bound 53.89s best:134786.792 next:[131859.781,134786.792] lb_tree_search
#Bound 55.19s best:134786.792 next:[131867.351,134786.792] lb_tree_search
#Bound 56.48s best:134786.792 next:[131874.423,134786.792] lb_tree_search
#Model 56.59s var:1088/1192 constraints:1541/1650
#Bound 57.89s best:134786.792 next:[131883.613,134786.792] lb_tree_search
#Model 57.97s var:1084/1192 constraints:1537/1650
#Bound 59.36s best:134786.792 next:[131887.065,134786.792] lb_tree_search
#Model 59.37s var:1082/1192 constraints:1535/1650
#Bound 60.74s best:134786.792 next:[131890.845,134786.792] lb_tree_search
#Bound 62.17s best:134786.792 next:[131905.884,134786.792] lb_tree_search
#Bound 63.73s best:134786.792 next:[131909.972,134786.792] lb_tree_search
#Bound 65.31s best:134786.792 next:[131916.909,134786.792] lb_tree_search
#Model 65.39s var:1080/1192 constraints:1533/1650
#Bound 66.72s best:134786.792 next:[131918.266,134786.792] lb_tree_search
#Bound 68.12s best:134786.792 next:[131919.751,134786.792] lb_tree_search
#Bound 69.62s best:134786.792 next:[131938.675,134786.792] lb_tree_search
#Bound 71.03s best:134786.792 next:[131946.742,134786.792] lb_tree_search
#Model 71.05s var:1078/1192 constraints:1531/1650
#Bound 72.39s best:134786.792 next:[131951.543,134786.792] lb_tree_search
#Bound 73.91s best:134786.792 next:[131988.564,134786.792] lb_tree_search
#Model 73.98s var:1076/1192 constraints:1529/1650
#Bound 75.31s best:134786.792 next:[132021.491,134786.792] lb_tree_search
#Model 75.34s var:1074/1192 constraints:1527/1650
#Bound 76.73s best:134786.792 next:[132039.777,134786.792] lb_tree_search
#Bound 78.20s best:134786.792 next:[132049.91,134786.792] lb_tree_search
#Bound 79.58s best:134786.792 next:[132057.743,134786.792] lb_tree_search
#Bound 80.96s best:134786.792 next:[132061.791,134786.792] lb_tree_search
#Bound 82.38s best:134786.792 next:[132071.65,134786.792] lb_tree_search
#Model 82.39s var:1072/1192 constraints:1525/1650
#Bound 83.76s best:134786.792 next:[132073.096,134786.792] lb_tree_search
#Bound 85.19s best:134786.792 next:[132073.949,134786.792] lb_tree_search
#Bound 86.66s best:134786.792 next:[132081.769,134786.792] lb_tree_search
#Model 86.67s var:1070/1192 constraints:1523/1650
#Bound 88.03s best:134786.792 next:[132083.185,134786.792] lb_tree_search
#Model 88.07s var:1066/1192 constraints:1519/1650
#Bound 89.48s best:134786.792 next:[132087.492,134786.792] lb_tree_search
#Bound 90.97s best:134786.792 next:[132088.465,134786.792] lb_tree_search
#Bound 92.46s best:134786.792 next:[132090.554,134786.792] lb_tree_search
#Bound 93.89s best:134786.792 next:[132092.258,134786.792] lb_tree_search
#Bound 95.40s best:134786.792 next:[132095.89,134786.792] lb_tree_search
#Bound 97.11s best:134786.792 next:[132096.53,134786.792] lb_tree_search
#Bound 98.94s best:134786.792 next:[132104.233,134786.792] lb_tree_search
#Bound 100.67s best:134786.792 next:[132109.976,134786.792] lb_tree_search
#Bound 102.42s best:134786.792 next:[132113.281,134786.792] lb_tree_search
#Bound 104.22s best:134786.792 next:[132118.506,134786.792] lb_tree_search
#Bound 106.07s best:134786.792 next:[132124.201,134786.792] lb_tree_search
#Bound 107.81s best:134786.792 next:[132127.831,134786.792] lb_tree_search
#Bound 109.59s best:134786.792 next:[132135.881,134786.792] lb_tree_search
#Model 109.64s var:1064/1192 constraints:1517/1650
#Bound 111.42s best:134786.792 next:[132142.799,134786.792] lb_tree_search
#Bound 113.22s best:134786.792 next:[132147.664,134786.792] lb_tree_search
#Bound 114.92s best:134786.792 next:[132153.156,134786.792] lb_tree_search
#Bound 116.74s best:134786.792 next:[132157.466,134786.792] lb_tree_search
#Bound 118.66s best:134786.792 next:[132164.403,134786.792] lb_tree_search
#Bound 120.54s best:134786.792 next:[132168.38,134786.792] lb_tree_search
#Model 120.57s var:1062/1192 constraints:1515/1650
#Bound 122.22s best:134786.792 next:[132170.998,134786.792] lb_tree_search
#Bound 123.85s best:134786.792 next:[132171.871,134786.792] lb_tree_search
#Bound 125.72s best:134786.792 next:[132190.278,134786.792] lb_tree_search
#Bound 127.42s best:134786.792 next:[132192.065,134786.792] lb_tree_search
#Bound 129.17s best:134786.792 next:[132203.365,134786.792] lb_tree_search
#Bound 130.96s best:134786.792 next:[132205.934,134786.792] lb_tree_search
#Bound 132.80s best:134786.792 next:[132210.518,134786.792] lb_tree_search
#Bound 134.54s best:134786.792 next:[132213.031,134786.792] lb_tree_search
#Model 134.61s var:1060/1192 constraints:1513/1650
#Bound 136.35s best:134786.792 next:[132216.272,134786.792] lb_tree_search
#Bound 138.03s best:134786.792 next:[132220.588,134786.792] lb_tree_search
#Model 138.08s var:1058/1192 constraints:1511/1650
#Bound 139.78s best:134786.792 next:[132221.194,134786.792] lb_tree_search
#Bound 141.77s best:134786.792 next:[132223.591,134786.792] lb_tree_search
#Bound 143.71s best:134786.792 next:[132224.342,134786.792] lb_tree_search
#Bound 145.60s best:134786.792 next:[132224.484,134786.792] lb_tree_search
#Bound 147.32s best:134786.792 next:[132225.036,134786.792] lb_tree_search
#Bound 149.15s best:134786.792 next:[132229.169,134786.792] lb_tree_search
#Bound 150.86s best:134786.792 next:[132230.033,134786.792] lb_tree_search
#Bound 152.85s best:134786.792 next:[132233.136,134786.792] lb_tree_search
#Bound 154.70s best:134786.792 next:[132236.143,134786.792] lb_tree_search
#Bound 156.53s best:134786.792 next:[132241.42,134786.792] lb_tree_search
#Bound 158.39s best:134786.792 next:[132242.834,134786.792] lb_tree_search
#Bound 160.23s best:134786.792 next:[132244.462,134786.792] lb_tree_search
#Bound 162.09s best:134786.792 next:[132246.293,134786.792] lb_tree_search
#Bound 163.82s best:134786.792 next:[132247.47,134786.792] lb_tree_search
#Bound 165.59s best:134786.792 next:[132247.712,134786.792] lb_tree_search
#Bound 167.40s best:134786.792 next:[132250.929,134786.792] lb_tree_search
#Bound 169.18s best:134786.792 next:[132251.453,134786.792] lb_tree_search
#Bound 171.03s best:134786.792 next:[132254.344,134786.792] lb_tree_search
#Bound 172.89s best:134786.792 next:[132257.95,134786.792] lb_tree_search
#Bound 174.64s best:134786.792 next:[132259.252,134786.792] lb_tree_search
#Bound 176.43s best:134786.792 next:[132268.92,134786.792] lb_tree_search
#Model 176.54s var:1054/1192 constraints:1507/1650
#Bound 178.11s best:134786.792 next:[132269.087,134786.792] lb_tree_search
#Bound 179.84s best:134786.792 next:[132269.795,134786.792] lb_tree_search
#Bound 181.66s best:134786.792 next:[132275.144,134786.792] lb_tree_search
#Bound 183.41s best:134786.792 next:[132276.146,134786.792] lb_tree_search
#Bound 185.29s best:134786.792 next:[132277.663,134786.792] lb_tree_search
#Bound 187.33s best:134786.792 next:[132280.334,134786.792] lb_tree_search
#Bound 189.08s best:134786.792 next:[132282.904,134786.792] lb_tree_search
#Bound 190.97s best:134786.792 next:[132286.044,134786.792] lb_tree_search
#Model 191.01s var:1052/1192 constraints:1505/1650
#Bound 192.80s best:134786.792 next:[132288.016,134786.792] lb_tree_search
#Bound 194.63s best:134786.792 next:[132289.11,134786.792] lb_tree_search
#Bound 196.53s best:134786.792 next:[132289.819,134786.792] lb_tree_search
#Bound 198.47s best:134786.792 next:[132290.308,134786.792] lb_tree_search
#Bound 200.53s best:134786.792 next:[132292.842,134786.792] lb_tree_search
#Model 200.58s var:1050/1192 constraints:1503/1650
#Bound 202.50s best:134786.792 next:[132296.82,134786.792] lb_tree_search
#Bound 204.61s best:134786.792 next:[132298.104,134786.792] lb_tree_search
#Bound 206.56s best:134786.792 next:[132298.245,134786.792] lb_tree_search
#Model 206.57s var:1048/1192 constraints:1501/1650
#Bound 208.54s best:134786.792 next:[132299.487,134786.792] lb_tree_search
#Bound 210.47s best:134786.792 next:[132302.15,134786.792] lb_tree_search
#Bound 212.46s best:134786.792 next:[132302.27,134786.792] lb_tree_search
#Bound 214.33s best:134786.792 next:[132303.807,134786.792] lb_tree_search
#Bound 216.39s best:134786.792 next:[132305.003,134786.792] lb_tree_search
#Bound 218.82s best:134786.792 next:[132309.811,134786.792] lb_tree_search
#Bound 220.93s best:134786.792 next:[132309.815,134786.792] lb_tree_search
#Bound 222.98s best:134786.792 next:[132311.665,134786.792] lb_tree_search
#Bound 224.96s best:134786.792 next:[132314.068,134786.792] lb_tree_search
#Bound 226.82s best:134786.792 next:[132315.578,134786.792] lb_tree_search
#Bound 228.76s best:134786.792 next:[132317.718,134786.792] lb_tree_search
#Bound 231.06s best:134786.792 next:[132322.147,134786.792] lb_tree_search
#Bound 232.93s best:134786.792 next:[132322.175,134786.792] lb_tree_search
#Bound 235.04s best:134786.792 next:[132322.205,134786.792] lb_tree_search
#Bound 237.21s best:134786.792 next:[132322.259,134786.792] lb_tree_search
#Model 237.71s var:1046/1192 constraints:1499/1650
#Bound 241.86s best:134786.792 next:[132322.294,134786.792] lb_tree_search
#Bound 243.97s best:134786.792 next:[132322.842,134786.792] lb_tree_search
#Bound 245.94s best:134786.792 next:[132324.456,134786.792] lb_tree_search
#Bound 247.99s best:134786.792 next:[132324.481,134786.792] lb_tree_search
#Bound 249.94s best:134786.792 next:[132325.728,134786.792] lb_tree_search
#Bound 251.88s best:134786.792 next:[132327.38,134786.792] lb_tree_search
#Bound 253.67s best:134786.792 next:[132327.613,134786.792] lb_tree_search
#Bound 255.75s best:134786.792 next:[132327.69,134786.792] lb_tree_search
#Bound 257.64s best:134786.792 next:[132329.546,134786.792] lb_tree_search
#Bound 259.63s best:134786.792 next:[132330.568,134786.792] lb_tree_search
#Bound 261.43s best:134786.792 next:[132331.221,134786.792] lb_tree_search
#Bound 263.40s best:134786.792 next:[132332.943,134786.792] lb_tree_search
#Bound 265.36s best:134786.792 next:[132333.067,134786.792] lb_tree_search
#Bound 267.34s best:134786.792 next:[132333.415,134786.792] lb_tree_search
#Bound 269.20s best:134786.792 next:[132334.132,134786.792] lb_tree_search
#Bound 271.13s best:134786.792 next:[132334.169,134786.792] lb_tree_search
#Bound 273.03s best:134786.792 next:[132334.581,134786.792] lb_tree_search
#Bound 274.96s best:134786.792 next:[132334.809,134786.792] lb_tree_search
#Bound 276.95s best:134786.792 next:[132335.153,134786.792] lb_tree_search
#Bound 278.88s best:134786.792 next:[132335.486,134786.792] lb_tree_search
#Bound 280.80s best:134786.792 next:[132336.922,134786.792] lb_tree_search
#Bound 283.05s best:134786.792 next:[132336.941,134786.792] lb_tree_search
#Bound 285.08s best:134786.792 next:[132337.213,134786.792] lb_tree_search
#Bound 287.01s best:134786.792 next:[132339.528,134786.792] lb_tree_search
#Bound 290.87s best:134786.792 next:[132340.961,134786.792] lb_tree_search
#Bound 292.99s best:134786.792 next:[132340.979,134786.792] lb_tree_search
#Bound 295.26s best:134786.792 next:[132340.984,134786.792] lb_tree_search
#Bound 297.25s best:134786.792 next:[132341.006,134786.792] lb_tree_search
#Bound 299.30s best:134786.792 next:[132347.11,134786.792] lb_tree_search (nodes=2/2 rc=0 decisions=9 @root=174 restarts=0 lp_iters=[0, 0, 563, 132])
#Bound 299.50s best:134786.792 next:[132347.113,134786.792] lb_tree_search (nodes=2/2 rc=0 decisions=10 @root=174 restarts=0 lp_iters=[0, 0, 746, 132])
#Bound 299.63s best:134786.792 next:[132347.121,134786.792] lb_tree_search (nodes=3/3 rc=0 decisions=14 @root=174 restarts=0 lp_iters=[0, 0, 824, 139])
Task timing n [ min, max] avg dev time n [ min, max] avg dev dtime
'core': 1 [ 5.00m, 5.00m] 5.00m 0.00ns 5.00m 1 [ 3.19m, 3.19m] 3.19m 0.00ns 3.19m
'default_lp': 1 [ 5.00m, 5.00m] 5.00m 0.00ns 5.00m 1 [ 2.26m, 2.26m] 2.26m 0.00ns 2.26m
'feasibility_pump': 763 [ 57.70us, 766.41ms] 175.79ms 68.55ms 2.24m 703 [ 53.69ms, 281.09ms] 65.26ms 15.94ms 45.88s
'fj': 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'fj': 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'fs_random': 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'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
'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
'graph_arc_lns': 395 [ 12.87ms, 1.53s] 345.41ms 279.34ms 2.27m 395 [ 17.42us, 112.91ms] 62.14ms 46.60ms 24.54s
'graph_cst_lns': 385 [ 18.04ms, 1.17s] 350.24ms 246.09ms 2.25m 385 [981.00ns, 106.58ms] 63.48ms 43.22ms 24.44s
'graph_dec_lns': 374 [ 6.33ms, 1.61s] 366.99ms 285.20ms 2.29m 374 [ 10.00ns, 104.47ms] 62.46ms 44.26ms 23.36s
'graph_var_lns': 399 [ 14.14ms, 1.79s] 337.99ms 267.38ms 2.25m 399 [ 10.00ns, 108.44ms] 61.99ms 44.59ms 24.73s
'lb_relax_lns': 92 [212.12ms, 3.80s] 1.59s 1.08s 2.45m 92 [ 27.17ms, 553.74ms] 339.78ms 221.51ms 31.26s
'lb_tree_search': 1 [ 5.00m, 5.00m] 5.00m 0.00ns 5.00m 1 [ 29.67s, 29.67s] 29.67s 0.00ns 29.67s
'ls': 555 [179.65ms, 442.44ms] 242.03ms 34.53ms 2.24m 555 [ 40.54ms, 100.03ms] 99.90ms 2.52ms 55.45s
'ls_lin': 554 [ 89.64ms, 403.31ms] 242.28ms 33.92ms 2.24m 554 [ 2.11ms, 100.03ms] 99.83ms 4.16ms 55.31s
'max_lp': 1 [ 5.00m, 5.00m] 5.00m 0.00ns 5.00m 1 [ 2.37m, 2.37m] 2.37m 0.00ns 2.37m
'no_lp': 1 [ 5.00m, 5.00m] 5.00m 0.00ns 5.00m 1 [ 3.26m, 3.26m] 3.26m 0.00ns 3.26m
'objective_lb_search': 1 [ 5.00m, 5.00m] 5.00m 0.00ns 5.00m 1 [ 2.86m, 2.86m] 2.86m 0.00ns 2.86m
'probing': 1 [ 5.00m, 5.00m] 5.00m 0.00ns 5.00m 1 [ 32.03s, 32.03s] 32.03s 0.00ns 32.03s
'pseudo_costs': 1 [ 5.00m, 5.00m] 5.00m 0.00ns 5.00m 1 [ 2.21m, 2.21m] 2.21m 0.00ns 2.21m
'quick_restart': 1 [ 5.00m, 5.00m] 5.00m 0.00ns 5.00m 1 [ 2.08m, 2.08m] 2.08m 0.00ns 2.08m
'quick_restart_no_lp': 1 [ 5.00m, 5.00m] 5.00m 0.00ns 5.00m 1 [ 2.38m, 2.38m] 2.38m 0.00ns 2.38m
'reduced_costs': 1 [ 5.00m, 5.00m] 5.00m 0.00ns 5.00m 1 [ 2.33m, 2.33m] 2.33m 0.00ns 2.33m
'rins/rens': 509 [862.00us, 677.35ms] 266.49ms 202.32ms 2.26m 452 [187.00ns, 100.22ms] 64.02ms 43.82ms 28.94s
'rnd_cst_lns': 400 [ 30.07ms, 1.45s] 337.79ms 233.47ms 2.25m 395 [ 8.75us, 102.32ms] 63.15ms 41.82ms 24.94s
'rnd_var_lns': 396 [ 18.39ms, 1.24s] 340.39ms 226.17ms 2.25m 396 [101.00ns, 102.37ms] 62.61ms 42.10ms 24.79s
Search stats Bools Conflicts Branches Restarts BoolPropag IntegerPropag
'core': 1'183 2'352'892 5'311'719 41'502 234'478'412 216'134'992
'default_lp': 718 4'848 126'498 41'659 684'654 2'885'027
'fs_random': 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0
'lb_tree_search': 596 0 340'427 149'782 1'067'300 2'824'606
'max_lp': 596 6'697 83'740 29'664 427'856 2'388'131
'no_lp': 596 2'030'008 3'081'931 91'177 110'120'603 407'446'760
'objective_lb_search': 690 3'133 91'485 31'739 376'096 1'729'171
'probing': 617 14 1'491 1'274 10'049 34'493
'pseudo_costs': 596 8'167 107'959 38'488 600'580 3'218'857
'quick_restart': 694 976 214'216 78'987 873'844 3'942'110
'quick_restart_no_lp': 1'190 590'408 8'404'195 328'690 84'913'785 222'252'819
'reduced_costs': 618 6'732 136'726 43'457 479'972 2'935'470
SAT stats ClassicMinim LitRemoved LitLearned LitForgotten Subsumed MClauses MDecisions MLitTrue MSubsumed MLitRemoved MReused
'core': 1'896'460 20'579'097 172'025'299 165'302'536 63'066 33'300 636'489 0 8'613 223'090 28'939
'default_lp': 4'561 117'206 296'146 0 13 10'819 60'048 0 85 693 454
'fs_random': 0 0 0 0 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0 0 0 0 0
'lb_tree_search': 0 0 0 0 0 24'624 156'808 0 0 0 0
'max_lp': 6'564 301'588 650'938 0 7 5'097 32'943 0 9 111 36
'no_lp': 1'997'126 20'482'079 110'719'853 109'257'783 8'802 127'583 644'842 0 4'061 46'793 131'591
'objective_lb_search': 2'966 143'874 90'931 0 5 6'453 46'332 0 52 579 255
'probing': 10 494 1'881 0 0 0 0 0 0 0 0
'pseudo_costs': 7'952 265'632 722'331 0 14 6'679 44'589 0 20 187 72
'quick_restart': 888 24'866 58'472 0 3 17'814 103'895 0 35 286 1'694
'quick_restart_no_lp': 549'740 15'264'712 40'234'595 37'340'517 3'362 260'958 1'593'640 0 21'370 212'738 15'968
'reduced_costs': 6'659 278'460 570'253 0 0 7'668 51'657 0 1 5 899
Lp stats Component Iterations AddedCuts OPTIMAL DUAL_F. DUAL_U.
'default_lp': 1 908'072 9'706 19'960 10 315
'lb_tree_search': 1 21'284 5'814 463 13 0
'max_lp': 1 954'186 8'802 19'141 5'393 335
'objective_lb_search': 1 932'800 7'999 10'535 77 175
'probing': 1 46'910 5'984 775 6 1
'pseudo_costs': 1 994'757 8'828 23'018 5'456 571
'quick_restart': 1 510'695 7'079 8'858 32 82
'reduced_costs': 1 1'062'331 10'707 16'496 6'159 274
Lp dimension Final dimension of first component
'default_lp': 1283 rows, 1119 columns, 22735 entries
'lb_tree_search': 1942 rows, 1192 columns, 84145 entries
'max_lp': 1138 rows, 1192 columns, 19368 entries
'objective_lb_search': 1274 rows, 1119 columns, 24532 entries
'probing': 1317 rows, 1119 columns, 33308 entries
'pseudo_costs': 1312 rows, 1192 columns, 24200 entries
'quick_restart': 1641 rows, 1119 columns, 38553 entries
'reduced_costs': 1450 rows, 1192 columns, 27209 entries
Lp debug CutPropag CutEqPropag Adjust Overflow Bad BadScaling
'default_lp': 0 21 20'249 0 137'353 0
'lb_tree_search': 0 29 476 0 983'455 0
'max_lp': 0 26 24'835 0 175'551 0
'objective_lb_search': 0 6 10'748 0 159'420 0
'probing': 0 17 773 0 733'147 0
'pseudo_costs': 0 14 28'987 0 128'598 0
'quick_restart': 0 16 8'962 0 304'088 0
'reduced_costs': 0 17 22'909 0 158'978 0
Lp pool Constraints Updates Simplif Merged Shortened Split Strenghtened Cuts/Call
'default_lp': 11'657 1'183 17'387 0 7'586 3'266 377 9'706/25'333
'lb_tree_search': 8'060 5'874 43'401 0 11'372 33'277 139 5'814/11'513
'max_lp': 11'047 1'980 15'865 1 9'029 3'056 203 8'802/22'797
'objective_lb_search': 9'950 1'320 17'253 0 9'791 1'714 351 7'999/18'005
'probing': 7'935 2'786 3'242 0 2'866 510 224 5'984/10'898
'pseudo_costs': 11'074 1'441 15'576 0 7'215 2'328 327 8'828/23'813
'quick_restart': 9'030 1'887 29'055 0 8'778 9'046 283 7'079/15'030
'reduced_costs': 11'953 1'838 19'728 0 9'258 4'266 338 10'707/26'406
Lp Cut max_lp quick_restart reduced_costs default_lp pseudo_costs lb_tree_search probing objective_lb_search
CG_FF: 68 17 126 67 81 8 16 28
CG_K: 35 7 69 21 37 5 8 12
CG_KL: 8 2 12 7 13 - 2 2
CG_R: 118 26 218 109 126 18 46 62
CG_RB: 181 60 354 201 212 55 78 124
CG_RBP: 82 24 131 86 85 10 34 56
Clique: 6 - 2 - 5 - - -
IB: 1'452 1'196 1'494 1'615 1'739 40 687 1'048
MIR_1_FF: 327 393 408 529 358 167 438 450
MIR_1_K: 79 126 79 152 102 16 95 115
MIR_1_KL: 32 40 30 49 34 12 40 52
MIR_1_R: 19 10 31 7 16 17 16 9
MIR_1_RB: 153 165 289 247 166 92 139 217
MIR_1_RBP: 126 359 138 230 114 519 450 214
MIR_1_RLT: - - 1 - 6 - - -
MIR_2_FF: 392 322 540 432 447 239 334 379
MIR_2_K: 141 151 145 205 182 37 118 135
MIR_2_KL: 38 34 62 34 50 20 53 29
MIR_2_R: 62 39 140 53 52 47 26 31
MIR_2_RB: 280 247 529 371 316 224 226 301
MIR_2_RBP: 179 285 242 273 171 141 261 243
MIR_3_FF: 402 207 470 304 387 201 221 289
MIR_3_K: 176 228 176 234 183 65 98 238
MIR_3_KL: 29 10 28 16 37 16 23 15
MIR_3_R: 49 17 93 30 52 24 18 25
MIR_3_RB: 269 129 425 264 278 162 158 177
MIR_3_RBP: 180 310 197 295 210 175 186 334
MIR_4_FF: 282 157 354 263 259 168 138 212
MIR_4_K: 209 224 160 277 179 157 85 234
MIR_4_KL: 12 9 16 20 25 10 13 9
MIR_4_R: 37 11 68 25 38 29 13 20
MIR_4_RB: 223 85 340 197 194 135 91 133
MIR_4_RBP: 265 311 197 323 211 290 129 330
MIR_5_FF: 189 98 235 188 195 124 136 156
MIR_5_K: 172 152 140 205 158 174 61 157
MIR_5_KL: 17 23 41 26 25 20 17 19
MIR_5_R: 27 8 54 16 36 18 9 13
MIR_5_RB: 134 44 213 83 142 85 68 74
MIR_5_RBP: 213 244 191 253 189 323 119 231
MIR_6_FF: 132 64 141 131 131 98 90 79
MIR_6_K: 144 96 116 168 122 159 55 92
MIR_6_KL: 60 26 62 35 55 33 41 32
MIR_6_R: 18 3 39 20 15 10 5 10
MIR_6_RB: 82 38 165 70 98 62 37 53
MIR_6_RBP: 246 194 210 218 198 351 134 201
ZERO_HALF_FF: 49 33 115 60 63 16 28 52
ZERO_HALF_K: 11 8 19 22 14 - 7 11
ZERO_HALF_KL: 12 - 2 3 8 6 2 -
ZERO_HALF_R: 1'166 670 1'198 1'049 862 959 770 1'022
ZERO_HALF_RB: 128 105 132 125 107 160 100 175
ZERO_HALF_RBP: 91 72 70 98 45 117 65 99
LNS stats Improv/Calls Closed Difficulty TimeLimit
'graph_arc_lns': 38/395 50% 4.71e-01 0.11
'graph_cst_lns': 51/385 50% 6.87e-01 0.11
'graph_dec_lns': 47/374 50% 7.84e-01 0.10
'graph_var_lns': 33/399 50% 6.52e-01 0.11
'lb_relax_lns': 39/92 48% 3.57e-01 0.51
'rins/rens': 444/507 50% 4.96e-01 0.10
'rnd_cst_lns': 63/395 50% 7.90e-01 0.10
'rnd_var_lns': 48/396 50% 7.76e-01 0.10
LS stats Batches Restarts/Perturbs LinMoves GenMoves CompoundMoves Bactracks WeightUpdates ScoreComputed
'ls_lin_restart': 34 14 514'355 0 0 0 141'241 19'139'991
'ls_lin_restart_compound': 95 24 0 2'082'015 110'327 985'679 6'413 45'466'959
'ls_lin_restart_compound_perturb': 42 23 0 844'335 73'429 385'388 2'455 20'244'767
'ls_lin_restart_decay': 101 30 1'937'859 0 0 0 42'265 38'056'302
'ls_lin_restart_decay_compound': 52 18 0 986'886 133'721 426'459 780 25'632'412
'ls_lin_restart_decay_compound_perturb': 69 25 0 1'278'900 180'541 549'021 1'124 33'395'679
'ls_lin_restart_decay_perturb': 105 32 2'015'536 0 0 0 43'821 39'666'520
'ls_lin_restart_perturb': 56 32 868'390 0 0 0 250'864 29'958'261
'ls_restart': 86 30 1'308'800 0 0 0 344'404 47'512'678
'ls_restart_compound': 129 29 0 2'809'974 135'787 1'336'861 7'372 61'234'050
'ls_restart_compound_perturb': 36 19 0 731'861 61'152 335'289 2'600 17'411'179
'ls_restart_decay': 41 24 789'260 0 0 0 17'647 15'608'810
'ls_restart_decay_compound': 62 28 0 1'133'664 164'970 484'234 1'140 29'826'617
'ls_restart_decay_compound_perturb': 47 20 0 882'408 124'297 378'946 803 22'929'470
'ls_restart_decay_perturb': 78 23 1'500'194 0 0 0 33'046 29'418'964
'ls_restart_perturb': 76 25 1'142'795 0 0 0 323'834 42'074'599
Solutions (4) Num Rank
'complete_hint': 1 [1,1]
'lb_relax_lns_int': 1 [4,4]
'quick_restart_no_lp': 2 [2,3]
Objective bounds Num
'am1_presolve': 1
'initial_domain': 1
'lb_tree_search': 181
'max_lp': 9
'pseudo_costs': 1
'quick_restart': 1
Solution repositories Added Queried Synchro
'feasible solutions': 1'374 6'681 749
'fj solution hints': 0 0 0
'lp solutions': 673 247 632
'pump': 14'647 262
Improving bounds shared Num Sym
'default_lp': 3 0
'lb_tree_search': 98 0
'max_lp': 38 0
'probing': 2 0
'quick_restart': 9 0
'quick_restart_no_lp': 33 0
Clauses shared Num
'core': 22
'max_lp': 1
'no_lp': 1
'objective_lb_search': 2
'probing': 510
'pseudo_costs': 8
'quick_restart': 4
'quick_restart_no_lp': 28
'reduced_costs': 2
[Scaling] scaled_objective_bound: 132347 corrected_bound: 132347 delta: 1.60889e-06
CpSolverResponse summary:
status: FEASIBLE
objective: 134786.7922581253
best_bound: 132347.1214535837
integers: 0
booleans: 0
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 0
restarts: 0
lp_iterations: 0
walltime: 300.513
usertime: 300.513
deterministic_time: 1801.62
gap_integral: 14088.4
solution_fingerprint: 0xed06b28162413d6f
[27]:
SolutionInfo(runtime=300.5127943, bound=132347.12145358368, objective=134786.79225812532, relgap=0.018100221569703367, termination='FEASIBLE')
[28]:
S_irr, G_irr = solver.get_solution()
[29]:
assign_cables(G_irr, cables)
G_irr.size(weight='cost')
[29]:
43091183.191651106
[30]:
svgplot(G_irr)
[30]:
Layouts’ edge list¶
These lists of 3-tuples has all the edges and their cable type (as an index to the turbines_per_cable list), i.e. (coordinate_A, coordinate_B, cable_type).
Negative node indices represent substations, the node indices ranging from 0 to 73 represent the WT in the order they were given.
If the layout has contours or detours, indices will go beyond the number of coordinates (WT, SS, borders) provided, and the mapping of these additional indices to indices to the provided coordinates is presented.
[31]:
G_reg.edges(data='cable')
[31]:
EdgeDataView([(72, 71, 0), (73, 66, 0), (67, 57, 2), (67, 68, 1), (68, 69, 1), (45, -1, 2), (45, 44, 1), (65, 66, 1), (65, 80, 1), (18, 19, 0), (26, 17, 1), (26, 25, 1), (44, 31, 0), (44, 43, 0), (33, -1, 2), (33, 23, 2), (70, 61, 0), (70, 63, 0), (61, 69, 0), (5, 4, 0), (5, 9, 1), (10, 11, 0), (51, 62, 0), (51, 60, 1), (62, 53, 0), (8, 14, 0), (8, 3, 0), (9, 15, 1), (40, 29, 0), (41, 52, 0), (41, 54, 0), (14, 22, 1), (22, 23, 1), (39, 52, 1), (39, 50, 1), (34, 25, 2), (34, -1, 2), (57, -1, 2), (66, 71, 0), (53, 64, 0), (15, 24, 2), (19, 28, 0), (3, 2, 0), (6, 7, 0), (11, 16, 0), (16, 17, 0), (-1, 56, 2), (-1, 47, 2), (-1, 46, 2), (-1, 24, 2), (-1, 58, 2), (-1, 32, 2), (-1, 49, 2), (46, 35, 2), (27, 28, 0), (27, 36, 1), (36, 35, 1), (48, 37, 1), (48, 47, 1), (7, 12, 0), (12, 13, 0), (42, 31, 0), (59, 58, 2), (59, 60, 1), (38, 29, 0), (38, 37, 0), (20, 13, 1), (20, 21, 1), (49, 50, 2), (21, 32, 2), (31, 30, 0), (0, 1, 0), (1, 4, 0), (56, 80, 1), (54, 55, 0)])
Mapping of contour/detour node to the index of its VertexC coordinate :
[32]:
if G_reg.graph.get('C') or G_reg.graph.get('D'):
R, T, B = (G_reg.graph[k] for k in 'RTB')
print(dict(enumerate(
(n.item() for n in G_reg.graph['fnT'][T + B:-R]),
start=T + B
)))
{80: 76}
[33]:
G_irr.edges(data='cable')
[33]:
EdgeDataView([(15, 21, 0), (15, 3, 0), (21, 66, 0), (58, 65, 0), (58, 61, 1), (65, 48, 0), (65, 47, 0), (16, 29, 1), (16, 17, 0), (29, 53, 1), (36, 62, 0), (36, 35, 0), (62, 69, 1), (42, 8, 1), (42, 25, 2), (37, 51, 1), (37, 20, 1), (70, 67, 2), (70, -1, 2), (5, 9, 0), (5, 32, 0), (10, 24, 0), (40, 55, 0), (40, 57, 0), (41, -1, 2), (41, 51, 2), (34, 1, 0), (34, 20, 0), (49, 54, 2), (49, -1, 2), (53, 28, 2), (46, 50, 0), (46, 44, 0), (22, 67, 1), (22, 44, 1), (23, 43, 0), (43, 7, 0), (31, 26, 0), (31, 56, 0), (56, 30, 1), (68, 14, 1), (68, 73, 2), (13, 26, 0), (-1, 60, 2), (-1, 55, 1), (-1, 39, 2), (-1, 28, 2), (-1, 33, 2), (-1, 25, 2), (-1, 80, 2), (-1, 81, 2), (71, 64, 2), (71, 81, 2), (64, 61, 1), (27, 52, 0), (27, 38, 0), (52, 59, 0), (60, 59, 2), (3, 12, 1), (50, 0, 0), (9, 19, 0), (11, 18, 0), (45, 33, 2), (45, 12, 1), (2, 8, 1), (2, 7, 0), (73, 80, 2), (69, 63, 1), (57, 72, 0), (39, 63, 2), (32, 14, 1), (18, 59, 0), (17, 24, 0), (6, 35, 0), (54, 30, 1), (20, 4, 0)])
Mapping of contour/detour node to the index of its VertexC coordinate :
[34]:
if G_irr.graph.get('C') or G_irr.graph.get('D'):
R, T, B = (G_irr.graph[k] for k in 'RTB')
print(dict(enumerate(
(n.item() for n in G_irr.graph['fnT'][T + B:-R]),
start=T + B
)))
{80: 28, 81: 76}