🚀 Quick Start¶
This notebook shows the minimum steps needed to run a electrical network optimization in a wind farm via OptiWindNet.
Steps¶
An network optimization via OptiWindNet involves two components:
A
WindFarmNetworkcontaining the problem data.A
Routerdescribing the method used to solve it.
The network optimization can be performed using following steps:
Create a
WindFarmNetworkinstanceDefine a router
Run the optimization and get the results
1. Create a WindFarmNetwork instance¶
The WindFarmNetwork component stores the turbine layout and runs optimization (storing the optimized network after running an optimization). See WindFarmNetwork and Router for some of the important methods and functionalities provided by this component.
[1]:
from optiwindnet.api import WindFarmNetwork
[2]:
import matplotlib.pyplot as plt
# Display figures as SVG in Jupyter notebooks
%config InlineBackend.figure_formats = ['svg']
Load location data¶
Note: For details about OptiWindNet’s
load_repository(), check Load repositories containing location data.
[3]:
from optiwindnet.api import load_repository
locations = load_repository()
L = locations.doggerA
Initialize a WindFarmNetwork instance with a prebuilt L and a desired maximum cable capacity (See Data Input for various input formats.)
[4]:
wfn = WindFarmNetwork(L=L, cables=8)
We can plot the location to make sure wfn is created with the correct data.
Tip. In a notebook, just put
wfnas the last line of a cell for plotting G.
Before optimization (no
Gyet), it renders the location geometryL.If
Gexists (e.g. after aoptimize()is run), it automatically rendersG.We could use
wfn.plot_location()for plotting the location geometry. For more details look into the notebook about plotting
[5]:
wfn
[5]:
2. Define a Router¶
Three built-in routers are available in OptiWindNet :
Router |
Speed |
Accuracy |
Notes |
|---|---|---|---|
EWRouter |
⭐⭐⭐ |
⭐ |
Very fast heuristic |
HGSRouter |
⭐⭐ |
⭐⭐ |
Radial or ringed topology |
MILPRouter |
⭐ |
⭐⭐⭐ |
Exact MILP solver |
See WindFarmNetwork and Router for details about routers.
EWRouter¶
To use this router, simply create an instance of the EWRouter class. All arguments are optional, making it quick and easy to get started with minimal configuration.
[6]:
from optiwindnet.api import EWRouter
[7]:
ew_router = EWRouter()
HGSRouter¶
To use this router, create an instance of the HGSRouter class. The only required argument is time_limit, which defines how long the optimization is allowed to run (in seconds).
[8]:
from optiwindnet.api import HGSRouter
[9]:
hgs_router = HGSRouter(time_limit=1)
MILPRouter¶
To use this router, create an instance of the MILPRouter class. You must provide:
solver_name: the MILP solver to use (e.g.,'ortools.cp_sat','gurobi','cbc')time_limit: maximum time allowed for solving (in seconds)mip_gap: acceptable optimality gap (e.g.,0.005= 0.5%)
Optional arguments:
verbose(default: False): set toTrueto display solver progress and detailed logssolver_options: dictionary of solver-specific parametersmodel_options: advanced model settings (e.g., topology, feeder configuration)
[10]:
from optiwindnet.api import MILPRouter
[11]:
milp_router = MILPRouter(solver_name='ortools.cp_sat', time_limit=20, mip_gap=0.005, verbose=True)
3. Run the optimization¶
EWRouter (very fast)¶
[12]:
%%timeit
res_ew = wfn.optimize(router=ew_router)
33.3 ms ± 694 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)
[13]:
wfn.solution_info()
[13]:
{'router': 'EWRouter', 'capacity': 8, 'method': 'biased_EW', 'iterations': 84}
[14]:
wfn.length()
[14]:
261192.1342444766
Plot optimized network
Note: we could use
wfn.plot()for plotting the optimized network. For more details look into the notebook about plotting
[15]:
wfn
[15]:
Note: When calling
.optimize()multiple times on the sameWindFarmNetworkinstance, the previously stored solution and related information (e.g., network graph, cost, length) will be overwritten. You can verify this by checking the updated total length or by re-plotting the optimized network and comparing it to the earlier result.
HGSRouter (fast - radial or ringed topology)¶
[16]:
res_hgs = wfn.optimize(router=hgs_router)
[17]:
wfn.solution_info()
[17]:
{'router': 'HGSRouter',
'capacity': 8,
'solver_name': 'HGS-CVRP',
'complete': False,
'feeders_above_min': None,
'feeders_exact': False,
'nbGranular': 20,
'mu': 25,
'lambda_': 40,
'nbElite': 4,
'nbClose': 5,
'nbIterPenaltyManagement': 100,
'targetFeasible': 0.2,
'penaltyDecrease': 0.85,
'penaltyIncrease': 1.2,
'seed': 625878960,
'nbIter': 20000,
'nbIterTraces': 500,
'timeLimit': 1,
'useSwapStar': True,
'runtime': 1.000364848}
[18]:
wfn.length()
[18]:
243320.14066103278
[19]:
wfn
[19]:
Note that the HGSRouter may produce a network with radial or ringed topology.
In a radial or ringed topology, each turbine has at most two connections (maximum degree of 2). Contrast that with the branched topology, where there is no limit on the number of connections of each turbine. See the figure below for an illustrative example.
[20]:
from optiwindnet.synthetic import toyfarm
from optiwindnet.api import ModelOptions
[21]:
fig, (axl, axm, axr) = plt.subplots(1, 3, facecolor='none')
wfn_toy = WindFarmNetwork(L=toyfarm(), cables=4)
opt_milp = dict(mip_gap=0.001, time_limit=5, solver_name='ortools.cp_sat')
axl.set_title('Radial', color='#888888')
wfn_toy.optimize(
router=MILPRouter(
**opt_milp,
model_options=ModelOptions(
topology='radial',
feeder_limit='minimum',
)
)
)
wfn_toy.plot(ax=axl, infobox=False)
axm.set_title('Branched', color='#888888');
wfn_toy.optimize(
router=MILPRouter(
**opt_milp,
model_options=ModelOptions(
topology='branched',
feeder_limit='minimum',
)
)
)
wfn_toy.plot(ax=axm, infobox=False);
axr.set_title('Ringed', color='#888888');
wfn_toy.optimize(
router=MILPRouter(
**opt_milp,
model_options=ModelOptions(
topology='ringed',
feeder_limit='minimum',
)
)
)
wfn_toy.plot(ax=axr, infobox=False);
MILPRouter¶
(high-quality solutions with guarantees, may take several minutes)
Note:
if a
WindFarmNetworkalready has a solution,MILPRouterwill use it as a warm start.To avoid warm-starting, create a new
WindFarmNetworkand run MILP directly.Set
verbose=Trueto see warm-start messages in the logs (The log messages of the MILP router provide information about warm-start).
[22]:
res_milp = wfn.optimize(router=milp_router)
IntegerBoundsPreprocessor 2613 rows, 1690 columns, 9531 entries with magnitude in [1.000000e+00, 8.000000e+00]
BoundPropagationPreprocessor 2613 rows, 1690 columns, 9531 entries with magnitude in [1.000000e+00, 8.000000e+00]
ImpliedIntegerPreprocessor 2613 rows, 1690 columns, 9531 entries with magnitude in [1.000000e+00, 8.000000e+00]
IntegerBoundsPreprocessor 2613 rows, 1690 columns, 9531 entries with magnitude in [1.000000e+00, 8.000000e+00]
ReduceCostOverExclusiveOrConstraintPreprocessor 2613 rows, 1690 columns, 9531 entries with magnitude in [1.000000e+00, 8.000000e+00]
Scaling to pure integer problem.
Num integers: 1690/1690 (implied: 0 in_inequalities: 0 max_scaling: 0) [IP]
Maximum constraint coefficient relative error: 0
Maximum constraint worst-case activity error: 0
Constraint scaling factor range: [1, 1]
Starting CP-SAT solver v9.15.6755
Parameters: max_time_in_seconds: 20 log_search_progress: true catch_sigint_signal: false relative_gap_limit: 0.005
Setting number of workers to 16
Initial optimization model 'optiwindnet': (model_fingerprint: 0x7487615e246e660e)
#Variables: 1'690 (#bools: 750 in floating point objective) (1'500 primary variables)
- 845 Booleans in [0,1]
- 750 in [0,7]
- 95 in [0,8]
#kLinear2: 2'065
#kLinear3: 4
#kLinearN: 544 (#terms: 5'389)
Starting presolve at 0.00s
The solution hint is complete and is feasible.
[Scaling] Floating point objective has 750 terms with magnitude in [0.00903211, 21204.4] average = 3140.28
[Scaling] Objective coefficient relative error: 1.87515e-05
[Scaling] Objective worst-case absolute error: 9.16404e-05
[Scaling] Objective scaling factor: 1.04858e+06
4.03e-04s 0.00e+00d [DetectDominanceRelations]
9.35e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
2.45e-05s 0.00e+00d [ExtractEncodingFromLinear] #potential_supersets=355
2.10e-04s 0.00e+00d [DetectDuplicateColumns]
1.57e-04s 0.00e+00d [DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 6'368 nodes and 11'971 arcs.
[Symmetry] Symmetry computation done. time: 0.000595891 dtime: 0.00116108
[SAT presolve] num removable Booleans: 0 / 845
[SAT presolve] num trivial clauses: 0
[SAT presolve] [0s] clauses:375 literals:750 vars:750 one_side_vars:750 simple_definition:0 singleton_clauses:0
[SAT presolve] [1.7854e-05s] clauses:375 literals:750 vars:750 one_side_vars:750 simple_definition:0 singleton_clauses:0
[SAT presolve] [3.2907e-05s] clauses:375 literals:750 vars:750 one_side_vars:750 simple_definition:0 singleton_clauses:0
1.70e-04s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
1.92e-02s 1.04e-02d [Probe] #probed=3'380 #new_binary_clauses=845
3.96e-04s 5.46e-04d [MaxClique] Merged 635 constraints with 1'926 literals into 330 constraints with 1'316 literals
3.53e-04s 0.00e+00d [DetectDominanceRelations]
3.59e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
1.17e-03s 0.00e+00d [ProcessAtMostOneAndLinear] #num_changes=845
1.86e-04s 0.00e+00d [DetectDuplicateConstraints]
1.75e-04s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
2.82e-04s 1.46e-05d [DetectDominatedLinearConstraints] #relevant_constraints=193 #num_inclusions=96
2.29e-05s 0.00e+00d [DetectDifferentVariables]
3.20e-03s 3.73e-04d [ProcessSetPPC] #relevant_constraints=427 #num_inclusions=425
1.55e-04s 0.00e+00d [TransformClausesToExactlyOne] #num_amos=330
1.12e-03s 0.00e+00d [DetectEncodedComplexDomains]
6.59e-05s 0.00e+00d [FindAlmostIdenticalLinearConstraints]
2.65e-04s 2.83e-04d [FindBigAtMostOneAndLinearOverlap]
1.70e-04s 3.25e-04d [FindBigVerticalLinearOverlap]
2.30e-05s 1.24e-05d [FindBigHorizontalLinearOverlap] #linears=179
1.09e-05s 0.00e+00d [MergeClauses]
3.38e-04s 0.00e+00d [DetectDominanceRelations]
4.93e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
3.31e-04s 0.00e+00d [DetectDominanceRelations]
3.38e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
8.40e-05s 0.00e+00d [DetectDuplicateColumns]
1.44e-04s 0.00e+00d [DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 5'717 nodes and 9'866 arcs.
[Symmetry] Symmetry computation done. time: 0.000423838 dtime: 0.00104477
[SAT presolve] num removable Booleans: 0 / 845
[SAT presolve] num trivial clauses: 0
[SAT presolve] [0s] clauses:70 literals:140 vars:140 one_side_vars:140 simple_definition:0 singleton_clauses:0
[SAT presolve] [4.488e-05s] clauses:70 literals:140 vars:140 one_side_vars:140 simple_definition:0 singleton_clauses:0
[SAT presolve] [0.000147403s] clauses:70 literals:140 vars:140 one_side_vars:140 simple_definition:0 singleton_clauses:0
1.64e-04s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
8.11e-03s 3.44e-03d [Probe] #probed=1'690
6.60e-04s 3.69e-04d [MaxClique]
3.49e-04s 0.00e+00d [DetectDominanceRelations]
3.25e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
1.69e-04s 0.00e+00d [ProcessAtMostOneAndLinear]
1.59e-04s 0.00e+00d [DetectDuplicateConstraints]
1.50e-04s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
2.16e-04s 1.10e-05d [DetectDominatedLinearConstraints] #relevant_constraints=192 #num_inclusions=95
2.02e-05s 0.00e+00d [DetectDifferentVariables]
1.59e-04s 7.32e-06d [ProcessSetPPC] #relevant_constraints=426
1.40e-04s 0.00e+00d [TransformClausesToExactlyOne] #num_amos=330
5.33e-04s 0.00e+00d [DetectEncodedComplexDomains]
2.64e-05s 0.00e+00d [FindAlmostIdenticalLinearConstraints]
2.54e-04s 2.79e-04d [FindBigAtMostOneAndLinearOverlap]
1.90e-04s 3.25e-04d [FindBigVerticalLinearOverlap]
3.00e-05s 1.24e-05d [FindBigHorizontalLinearOverlap] #linears=179
1.31e-05s 0.00e+00d [MergeClauses]
6.93e-04s 0.00e+00d [DetectDominanceRelations]
4.33e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
4.67e-06s 0.00e+00d [MergeNoOverlap]
5.43e-06s 0.00e+00d [MergeNoOverlap2D]
2.69e-04s 0.00e+00d [ExpandObjective] #entries=7'754 #tight_variables=845 #tight_constraints=95
Presolve summary:
- 0 affine relations were detected.
- rule 'TODO linear inclusion: superset is equality' was applied 191 times.
- rule 'TODO linear2: convert ax + by != cte to clauses for large domains' was applied 5'070 times.
- rule 'at_most_one: transformed into max clique' was applied 1 time.
- rule 'bool_or: implications' was applied 375 times.
- rule 'deductions: 1690 stored' was applied 1 time.
- rule 'linear + amo: extracted enforcement literal' was applied 845 times.
- rule 'linear2: contains a boolean' was applied 845 times.
- rule 'linear2: convert ax + by != cte to clauses' was applied 375 times.
- rule 'linear: positive at most one' was applied 260 times.
- rule 'linear: positive equal one' was applied 95 times.
- rule 'objective: shifted cost with exactly ones' was applied 95 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 95 times.
- rule 'setppc: reduced linear coefficients' was applied 94 times.
- rule 'setppc: removed trivial linear constraint' was applied 1 time.
- rule 'variables: detect fully reified value encoding' was applied 845 times.
- rule 'variables: detect half reified value encoding' was applied 1'690 times.
Presolved optimization model 'optiwindnet': (model_fingerprint: 0xd237d61048a95a8d)
#Variables: 1'690 (#bools: 750 in objective) (1'500 primary variables)
- 845 Booleans in [0,1]
- 750 in [0,7]
- 95 in [0,8]
#kAtMostOne: 260 (#literals: 1'176)
#kBoolAnd: 70 (#enforced: 70) (#literals: 140)
#kExactlyOne: 95 (#literals: 845)
#kLinear1: 1'690 (#enforced: 1'690)
#kLinear3: 4
#kLinearN: 188 (#terms: 2'523)
[Symmetry] Graph for symmetry has 5'717 nodes and 9'866 arcs.
[Symmetry] Symmetry computation done. time: 0.000465869 dtime: 0.00104354
Preloading model.
#Bound 0.08s best:inf next:[160817.074,2309766.32] initial_domain
#1 0.08s best:243320.141 next:[160817.074,243320.141] complete_hint
#Model 0.08s var:1690/1690 constraints:2307/2307
Starting search at 0.08s 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]
#2 0.11s best:243309.328 next:[160817.074,243309.328] graph_cst_lns (d=5.00e-01 s=15 t=0.10 p=0.00 stall=0 h=base)
#Bound 0.11s best:243309.328 next:[162472.38,243309.328] am1_presolve (num_literals=750 num_am1=34 increase=1735714016 work_done=2720)
#Bound 0.12s best:243309.328 next:[188354.862,243309.328] quick_restart
#Bound 0.12s best:243309.328 next:[189781.728,243309.328] pseudo_costs
#Bound 0.17s best:243309.328 next:[223973.897,243309.328] max_lp
#3 0.18s best:243285.162 next:[223973.897,243285.162] quick_restart_no_lp (fixed_bools=0/893)
#4 0.26s best:243284.527 next:[223973.897,243284.527] quick_restart_no_lp (fixed_bools=0/897)
#Bound 0.29s best:243284.527 next:[225413.966,243284.527] max_lp
#5 0.36s best:243107.5 next:[225413.966,243107.5] rnd_cst_lns (d=7.07e-01 s=24 t=0.10 p=1.00 stall=1 h=base)
#6 0.48s best:242876.219 next:[225413.966,242876.219] graph_cst_lns (d=7.07e-01 s=25 t=0.10 p=1.00 stall=0 h=base)
#7 0.49s best:242699.192 next:[225413.966,242699.192] graph_cst_lns (d=7.07e-01 s=25 t=0.10 p=1.00 stall=0 h=base) [combined with: rnd_cst_lns (d=7.07e...]
#Bound 0.82s best:242699.192 next:[225975.405,242699.192] lb_tree_search
#Bound 0.89s best:242699.192 next:[226137.83,242699.192] max_lp
#8 0.94s best:241720.961 next:[226137.83,241720.961] graph_var_lns (d=7.07e-01 s=28 t=0.10 p=1.00 stall=1 h=base)
#9 0.94s best:241312.653 next:[226137.83,241312.653] graph_var_lns (d=7.07e-01 s=28 t=0.10 p=1.00 stall=1 h=base) [combined with: graph_cst_lns (d=7.0...]
#Bound 0.97s best:241312.653 next:[226496.905,241312.653] lb_tree_search
#Bound 1.10s best:241312.653 next:[226803.2,241312.653] max_lp
#Bound 1.29s best:241312.653 next:[227186.181,241312.653] max_lp
#Bound 1.39s best:241312.653 next:[227264.405,241312.653] lb_tree_search
#Bound 1.75s best:241312.653 next:[227586.163,241312.653] lb_tree_search
#10 2.45s best:241104.144 next:[227586.163,241104.144] graph_var_lns (d=7.87e-01 s=58 t=0.10 p=0.75 stall=2 h=base)
#Bound 2.59s best:241104.144 next:[227859.194,241104.144] lb_tree_search
#Bound 3.48s best:241104.144 next:[228044.72,241104.144] lb_tree_search
#Bound 4.53s best:241104.144 next:[228274.283,241104.144] lb_tree_search
#Bound 5.66s best:241104.144 next:[228522.889,241104.144] lb_tree_search
#Bound 6.67s best:241104.144 next:[228749.07,241104.144] lb_tree_search
#Bound 6.77s best:241104.144 next:[228752.961,241104.144] lb_tree_search (nodes=2/2 rc=0 decisions=36 @root=17 restarts=0 lp_iters=[0, 0, 1'041, 6])
#Bound 7.90s best:241104.144 next:[228929.002,241104.144] lb_tree_search
#Bound 7.96s best:241104.144 next:[228929.469,241104.144] lb_tree_search (nodes=2/2 rc=0 decisions=39 @root=19 restarts=0 lp_iters=[0, 0, 1'180, 6])
#Bound 8.07s best:241104.144 next:[228983.391,241104.144] lb_tree_search
#Bound 8.08s best:241104.144 next:[229013.13,241104.144] lb_tree_search (nodes=2/2 rc=0 decisions=40 @root=19 restarts=0 lp_iters=[0, 0, 1'426, 6])
#Bound 8.14s best:241104.144 next:[229013.887,241104.144] lb_tree_search
#Bound 8.14s best:241104.144 next:[229022.33,241104.144] lb_tree_search (nodes=2/2 rc=0 decisions=42 @root=20 restarts=0 lp_iters=[0, 0, 1'478, 6])
#Bound 8.19s best:241104.144 next:[229022.334,241104.144] lb_tree_search (nodes=2/2 rc=0 decisions=44 @root=21 restarts=0 lp_iters=[0, 0, 1'480, 6])
#Bound 9.28s best:241104.144 next:[229153.725,241104.144] lb_tree_search
#Bound 9.34s best:241104.144 next:[229154.135,241104.144] lb_tree_search (nodes=3/3 rc=0 decisions=53 @root=22 restarts=0 lp_iters=[0, 0, 1'606, 52])
#Bound 9.45s best:241104.144 next:[229154.23,241104.144] lb_tree_search (nodes=3/3 rc=0 decisions=56 @root=22 restarts=0 lp_iters=[0, 0, 1'892, 52])
#Bound 9.57s best:241104.144 next:[229206.921,241104.144] lb_tree_search (nodes=3/3 rc=0 decisions=57 @root=22 restarts=0 lp_iters=[0, 0, 2'123, 52])
#Bound 9.96s best:241104.144 next:[229220.262,241104.144] lb_tree_search (nodes=5/5 rc=0 decisions=71 @root=22 restarts=0 lp_iters=[0, 0, 2'811, 97]) [skipped_logs=4]
#Bound 10.90s best:241104.144 next:[229322.493,241104.144] lb_tree_search (nodes=10/10 rc=0 decisions=100 @root=22 restarts=0 lp_iters=[0, 0, 4'777, 391]) [skipped_logs=7]
#Bound 13.51s best:241104.144 next:[229339.838,241104.144] lb_tree_search
#Bound 13.56s best:241104.144 next:[229353.242,241104.144] lb_tree_search (nodes=10/10 rc=0 decisions=111 @root=23 restarts=0 lp_iters=[0, 0, 5'393, 391])
#Bound 13.95s best:241104.144 next:[229385.061,241104.144] lb_tree_search (nodes=10/10 rc=0 decisions=125 @root=23 restarts=0 lp_iters=[0, 0, 5'804, 391]) [skipped_logs=9]
#Bound 14.40s best:241104.144 next:[229490.076,241104.144] lb_tree_search (nodes=11/11 rc=0 decisions=136 @root=23 restarts=0 lp_iters=[0, 0, 6'493, 583]) [skipped_logs=6]
#Bound 16.44s best:241104.144 next:[229492.365,241104.144] lb_tree_search (nodes=12/12 rc=0 decisions=161 @root=24 restarts=0 lp_iters=[0, 0, 7'408, 599])
#Bound 16.98s best:241104.144 next:[229597.702,241104.144] lb_tree_search (nodes=12/12 rc=0 decisions=174 @root=24 restarts=0 lp_iters=[0, 0, 8'623, 599]) [skipped_logs=4]
#Bound 18.02s best:241104.144 next:[229667.069,241104.144] lb_tree_search (nodes=14/14 rc=0 decisions=198 @root=24 restarts=0 lp_iters=[0, 0, 10'606, 718]) [skipped_logs=5]
#Bound 18.92s best:241104.144 next:[229712.397,241104.144] lb_tree_search (nodes=16/16 rc=0 decisions=221 @root=24 restarts=0 lp_iters=[0, 0, 12'110, 1'244]) [skipped_logs=3]
#Bound 19.50s best:241104.144 next:[229770.813,241104.144] lb_tree_search (nodes=20/20 rc=0 decisions=238 @root=24 restarts=0 lp_iters=[0, 0, 13'371, 1'472]) [skipped_logs=4]
Task timing n [ min, max] avg dev time n [ min, max] avg dev dtime
'core': 1 [ 19.95s, 19.95s] 19.95s 0.00ns 19.95s 2 [ 3.54ms, 10.98s] 5.49s 5.49s 10.98s
'default_lp': 1 [ 19.93s, 19.93s] 19.93s 0.00ns 19.93s 2 [122.92ms, 5.92s] 3.02s 2.90s 6.05s
'feasibility_pump': 95 [ 77.02us, 102.07ms] 4.03ms 10.16ms 382.41ms 92 [369.41us, 65.46ms] 1.09ms 6.75ms 100.68ms
'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': 46 [ 10.72ms, 442.54ms] 218.63ms 150.46ms 10.06s 46 [ 13.43us, 100.31ms] 59.93ms 44.99ms 2.76s
'graph_cst_lns': 39 [ 13.87ms, 585.93ms] 264.88ms 179.57ms 10.33s 39 [ 16.21us, 100.18ms] 59.37ms 44.58ms 2.32s
'graph_dec_lns': 46 [ 1.44ms, 531.19ms] 226.11ms 204.39ms 10.40s 42 [ 10.00ns, 100.13ms] 50.18ms 47.86ms 2.11s
'graph_var_lns': 41 [ 5.92ms, 514.86ms] 238.41ms 173.29ms 9.77s 41 [ 1.06us, 100.22ms] 56.95ms 44.80ms 2.34s
'lb_relax_lns': 9 [264.55ms, 1.98s] 1.15s 762.69ms 10.39s 9 [ 61.09ms, 601.44ms] 349.92ms 247.68ms 3.15s
'lb_tree_search': 1 [ 19.91s, 19.91s] 19.91s 0.00ns 19.91s 2 [201.77ms, 7.50s] 3.85s 3.65s 7.70s
'ls': 48 [ 62.49ms, 289.33ms] 198.39ms 33.27ms 9.52s 48 [ 34.56ms, 100.03ms] 98.65ms 9.35ms 4.74s
'ls_lin': 48 [166.81ms, 239.34ms] 200.42ms 17.42ms 9.62s 48 [100.01ms, 100.03ms] 100.01ms 5.78us 4.80s
'max_lp': 1 [ 19.93s, 19.93s] 19.93s 0.00ns 19.93s 2 [223.52ms, 6.94s] 3.58s 3.36s 7.17s
'no_lp': 1 [ 19.92s, 19.92s] 19.92s 0.00ns 19.92s 2 [ 4.25ms, 5.18s] 2.59s 2.59s 5.18s
'objective_lb_search': 1 [ 19.91s, 19.91s] 19.91s 0.00ns 19.91s 2 [123.03ms, 7.75s] 3.94s 3.82s 7.88s
'probing': 1 [ 19.93s, 19.93s] 19.93s 0.00ns 19.93s 2 [128.07ms, 5.44s] 2.78s 2.65s 5.56s
'pseudo_costs': 1 [ 19.92s, 19.92s] 19.92s 0.00ns 19.92s 2 [ 45.05ms, 6.78s] 3.41s 3.37s 6.83s
'quick_restart': 1 [ 19.93s, 19.93s] 19.93s 0.00ns 19.93s 2 [126.01ms, 7.71s] 3.92s 3.79s 7.84s
'quick_restart_no_lp': 1 [ 20.02s, 20.02s] 20.02s 0.00ns 20.02s 2 [ 4.25ms, 10.00s] 5.00s 5.00s 10.00s
'reduced_costs': 1 [ 19.92s, 19.92s] 19.92s 0.00ns 19.92s 2 [ 50.40ms, 7.42s] 3.74s 3.68s 7.47s
'rins/rens': 33 [ 3.86ms, 585.85ms] 287.71ms 206.99ms 9.49s 30 [321.97us, 100.12ms] 66.79ms 42.85ms 2.00s
'rnd_cst_lns': 41 [ 10.08ms, 581.69ms] 243.15ms 190.33ms 9.97s 41 [ 10.00ns, 100.27ms] 51.02ms 45.82ms 2.09s
'rnd_var_lns': 44 [ 5.44ms, 526.19ms] 217.35ms 194.18ms 9.56s 38 [ 10.00ns, 100.19ms] 52.43ms 46.94ms 1.99s
Search stats Bools Conflicts Branches Restarts BacktrackToRoot Backtrack BoolPropag IntegerPropag
'core': 879 350'535 710'727 308 5'879 355'147 5'482'252 15'469'051
'default_lp': 956 1'863 26'070 4 9'298 12'552 247'027 1'045'372
'fs_random': 0 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0 0
'lb_tree_search': 845 15 61'936 0 29'233 31'831 261'513 818'949
'max_lp': 845 636 30'346 5 12'913 14'644 155'502 767'026
'no_lp': 845 215'924 408'174 375 48'638 272'751 15'052'350 43'538'709
'objective_lb_search': 931 1'002 41'155 7 15'212 18'581 253'960 1'152'314
'probing': 866 10 2'062 0 1'775 1'785 13'539 46'515
'pseudo_costs': 845 1'612 35'016 5 11'807 14'625 254'561 1'229'670
'quick_restart': 874 166 55'870 11 22'833 25'278 274'080 1'347'496
'quick_restart_no_lp': 1'239 47'890 1'067'951 4'277 32'663 91'056 6'121'476 21'956'789
'reduced_costs': 845 640 61'438 10 21'402 24'180 284'963 1'486'603
SAT formula Fixed Equiv Total VarLeft BinaryClauses PermanentClauses TemporaryClauses
'core': 0 0 879 879 188 1'483 13'261
'default_lp': 0 0 956 956 594 335 1'648
'fs_random': 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0
'lb_tree_search': 0 0 845 845 140 386 4
'max_lp': 0 0 845 845 140 325 523
'no_lp': 0 0 845 845 140 893 2'328
'objective_lb_search': 7 0 931 924 514 394 104
'probing': 0 0 866 866 476 95 10
'pseudo_costs': 0 0 845 845 140 386 1'366
'quick_restart': 0 0 874 874 222 475 106
'quick_restart_no_lp': 0 0 1'239 1'239 3'292 1'613 12'109
'reduced_costs': 0 0 845 845 140 474 584
SAT stats ClassicMinim LitRemoved LitRemovedBinary LitLearned LitForgotten Subsumed
'core': 322'103 2'238'804 1'869'393 18'383'427 10'798'367 120'086
'default_lp': 1'704 24'078 129'416 180'210 0 194
'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': 5 7 27 211 0 9
'max_lp': 546 7'324 36'050 102'924 0 106
'no_lp': 211'024 1'922'926 326'809 17'547'034 1'498'809 194'157
'objective_lb_search': 915 39'616 13'753 38'735 0 218
'probing': 5 57 664 1'820 0 0
'pseudo_costs': 1'367 35'978 63'704 206'908 0 228
'quick_restart': 122 2'326 3'089 8'640 0 46
'quick_restart_no_lp': 40'172 894'424 1'092'688 4'599'888 2'690'728 7'978
'reduced_costs': 393 2'358 36'550 90'072 0 49
Vivification Clauses Decisions LitTrue Subsumed LitRemoved DecisionReused Conflicts
'core': 2'852 41'304 0 379 7'427 3'678 12
'default_lp': 1'840 12'556 0 58 426 678 0
'fs_random': 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0
'lb_tree_search': 4'715 34'292 0 96 739 1'061 0
'max_lp': 2'197 15'248 0 60 446 712 2
'no_lp': 17'102 104'792 0 161 1'548 15'149 5
'objective_lb_search': 3'579 24'687 0 114 906 1'557 3
'probing': 0 0 0 0 0 0 0
'pseudo_costs': 2'929 19'608 0 104 801 1'442 1
'quick_restart': 4'815 34'054 0 109 920 1'839 3
'quick_restart_no_lp': 13'180 82'575 0 485 4'561 4'369 50
'reduced_costs': 5'020 34'921 0 115 938 2'240 3
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
'core': 0 0 0 116'710 2'014 1 3'376 379 0 245 0 0 213'488 791'044 350'535
'default_lp': 0 0 0 185 0 0 9 58 1 4 0 0 0 3'939 1'863
'fs_random': 0 0 0 0 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 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
'lb_tree_search': 0 0 0 9 0 1 0 96 0 0 0 0 0 5 15
'max_lp': 0 0 0 98 1 0 8 60 0 0 0 0 0 1'391 636
'no_lp': 0 0 0 193'554 120 703 603 161 0 9 0 0 17'938 435'872 215'924
'objective_lb_search': 646 0 1 205 1 1 13 114 0 1 0 0 0 1'877 1'002
'probing': 0 0 0 0 0 0 0 0 0 0 0 0 0 17 10
'pseudo_costs': 0 0 0 221 6 2 7 104 0 0 0 0 0 3'542 1'612
'quick_restart': 0 0 0 45 1 0 1 109 0 1 0 0 0 199 166
'quick_restart_no_lp': 0 0 6 7'465 121 24 513 485 50 148 0 0 25'465 96'754 47'890
'reduced_costs': 0 0 0 49 0 0 0 115 0 1 0 0 0 1'249 640
Lp stats Component Iterations AddedCuts OPTIMAL DUAL_F. DUAL_U.
'default_lp': 1 123'050 2'773 6'966 1 95
'lb_tree_search': 1 22'911 2'958 409 49 0
'max_lp': 1 62'358 3'237 2'733 154 119
'objective_lb_search': 1 97'710 3'302 3'664 1 78
'probing': 1 20'833 4'278 338 4 3
'pseudo_costs': 1 115'322 2'917 4'927 491 406
'quick_restart': 1 49'851 3'929 1'307 2 14
'reduced_costs': 1 71'376 3'209 2'089 249 110
Lp dimension Final dimension of first component
'default_lp': 925 rows, 1596 columns, 5341 entries
'lb_tree_search': 2204 rows, 1690 columns, 49844 entries
'max_lp': 1241 rows, 1690 columns, 12420 entries
'objective_lb_search': 1259 rows, 1596 columns, 12536 entries
'probing': 2613 rows, 1596 columns, 61811 entries
'pseudo_costs': 1015 rows, 1690 columns, 7918 entries
'quick_restart': 1743 rows, 1596 columns, 27561 entries
'reduced_costs': 1459 rows, 1690 columns, 19474 entries
Lp debug CutPropag CutEqPropag Adjust Overflow Bad BadScaling
'default_lp': 0 0 7'041 0 2'806 0
'lb_tree_search': 0 0 458 0 58'858 0
'max_lp': 0 0 3'000 0 17'537 0
'objective_lb_search': 0 3 3'724 0 10'903 0
'probing': 0 8 332 0 58'059 0
'pseudo_costs': 0 0 5'767 0 6'621 0
'quick_restart': 0 4 1'312 0 28'683 0
'reduced_costs': 0 0 2'425 0 28'924 0
Lp pool Constraints Updates Simplif Merged Shortened Split Strengthened Cuts/Call
'default_lp': 5'573 11 0 0 0 0 35 2'773/6'863
'lb_tree_search': 6'110 531 0 0 0 972 5 2'958/5'647
'max_lp': 6'389 164 0 0 0 192 0 3'237/6'103
'objective_lb_search': 6'102 96 0 0 0 69 43 3'302/6'725
'probing': 7'078 428 0 0 0 1'173 204 4'278/7'770
'pseudo_costs': 6'069 53 0 0 0 14 0 2'917/6'567
'quick_restart': 6'729 224 0 0 0 235 85 3'929/7'361
'reduced_costs': 6'361 345 0 0 0 282 3 3'209/6'037
Lp Cut reduced_costs pseudo_costs lb_tree_search objective_lb_search default_lp max_lp quick_restart probing
CG_FF: 12 17 4 15 19 13 16 17
CG_K: 3 3 1 15 11 10 6 14
CG_KL: 1 3 2 3 7 - 5 5
CG_R: 12 29 18 31 24 24 29 36
CG_RB: 54 60 41 60 52 58 71 59
CG_RBP: 6 20 12 34 22 18 34 35
IB: 1'028 1'460 41 1'064 1'349 870 997 745
MIR_1_FF: 145 89 149 187 98 128 271 306
MIR_1_K: 10 10 - 62 42 24 61 60
MIR_1_KL: 4 2 5 32 21 2 35 44
MIR_1_R: 4 3 4 2 - 7 3 1
MIR_1_RB: 75 56 60 77 45 73 131 144
MIR_1_RBP: 22 11 19 56 35 25 95 138
MIR_2_FF: 145 131 200 172 105 162 213 241
MIR_2_K: 18 26 7 69 63 34 66 93
MIR_2_KL: 4 6 3 22 19 3 32 29
MIR_2_R: 10 10 8 6 7 13 5 8
MIR_2_RB: 152 83 208 130 94 178 173 201
MIR_2_RBP: 38 31 41 78 48 55 127 148
MIR_3_FF: 118 87 193 103 81 146 99 146
MIR_3_K: 24 27 31 46 50 31 53 99
MIR_3_KL: 2 4 7 6 11 3 10 9
MIR_3_R: 12 8 6 3 1 19 4 9
MIR_3_RB: 148 85 164 89 66 153 94 138
MIR_3_RBP: 52 25 51 54 33 73 85 141
MIR_4_FF: 84 57 170 69 39 119 80 74
MIR_4_K: 21 25 42 43 25 34 50 59
MIR_4_KL: - 2 6 6 6 4 5 9
MIR_4_R: 6 10 12 8 6 12 1 6
MIR_4_RB: 91 59 126 78 36 119 66 67
MIR_4_RBP: 37 21 70 32 23 51 58 70
MIR_5_FF: 48 35 104 27 15 64 43 51
MIR_5_K: 17 13 43 26 16 21 40 36
MIR_5_KL: 3 4 11 - 3 2 5 9
MIR_5_R: 3 5 7 5 2 8 6 3
MIR_5_RB: 59 40 84 27 18 81 28 46
MIR_5_RBP: 18 14 58 22 10 26 31 60
MIR_6_FF: 44 27 72 16 11 50 31 48
MIR_6_K: 20 22 35 18 12 33 29 43
MIR_6_KL: 14 11 19 5 3 13 7 6
MIR_6_R: 1 2 3 2 2 6 1 1
MIR_6_RB: 29 37 54 10 18 36 10 22
MIR_6_RBP: 28 22 45 17 7 38 24 40
ZERO_HALF_FF: 17 15 8 30 31 19 31 23
ZERO_HALF_K: 1 1 - 16 4 9 9 7
ZERO_HALF_KL: 1 1 1 3 3 - 1 5
ZERO_HALF_R: 447 167 582 340 142 307 546 585
ZERO_HALF_RB: 105 36 111 53 26 58 82 108
ZERO_HALF_RBP: 16 5 20 33 12 5 30 34
LNS stats Improv/Calls Closed Difficulty TimeLimit
'graph_arc_lns': 2/46 46% 2.28e-01 0.10
'graph_cst_lns': 4/39 49% 5.66e-01 0.10
'graph_dec_lns': 2/42 52% 8.04e-01 0.10
'graph_var_lns': 5/41 51% 6.89e-01 0.10
'lb_relax_lns': 5/9 44% 3.18e-01 0.50
'rins/rens': 23/33 45% 2.99e-01 0.10
'rnd_cst_lns': 6/41 51% 7.24e-01 0.10
'rnd_var_lns': 4/38 53% 7.80e-01 0.10
LS stats Batches Restarts/Perturbs LinMoves GenMoves CompoundMoves Bactracks WeightUpdates ScoreComputed
'ls_lin_restart': 5 5 64'385 0 0 0 10'782 2'274'450
'ls_lin_restart_compound': 4 3 0 58'225 5'433 26'391 321 1'729'292
'ls_lin_restart_compound_perturb': 8 5 0 114'384 11'706 51'332 294 3'602'889
'ls_lin_restart_decay': 7 6 106'435 0 0 0 1'772 2'413'601
'ls_lin_restart_decay_compound': 6 4 0 74'581 12'241 31'165 164 2'395'396
'ls_lin_restart_decay_compound_perturb': 5 4 0 65'437 11'941 26'740 131 1'882'263
'ls_lin_restart_decay_perturb': 9 6 137'054 0 0 0 2'246 3'104'485
'ls_lin_restart_perturb': 4 3 50'849 0 0 0 8'122 1'859'546
'ls_restart': 10 8 117'948 0 0 0 20'760 4'252'947
'ls_restart_compound': 6 3 0 93'141 8'891 42'122 281 2'695'674
'ls_restart_compound_perturb': 6 5 0 95'363 9'197 43'074 575 2'711'566
'ls_restart_decay': 7 7 106'066 0 0 0 1'800 2'423'619
'ls_restart_decay_compound': 6 5 0 75'964 13'260 31'342 225 2'472'973
'ls_restart_decay_compound_perturb': 4 1 0 59'178 9'176 24'995 29 1'696'819
'ls_restart_decay_perturb': 2 2 30'346 0 0 0 515 688'298
'ls_restart_perturb': 7 5 87'238 0 0 0 13'713 3'251'735
Solutions (10) Num Rank
'complete_hint': 2 [0,1]
'graph_cst_lns': 6 [1,7]
'graph_var_lns': 6 [7,10]
'quick_restart_no_lp': 4 [2,4]
'rnd_cst_lns': 2 [4,5]
Objective bounds Num
'am1_presolve': 1
'initial_domain': 1
'lb_tree_search': 74
'max_lp': 5
'pseudo_costs': 1
'quick_restart': 1
Solution repositories Added Queried Synchro
'alternative_path': 18 124 18
'best_solutions': 92 274 61
'fj solution hints': 0 0 0
'lp solutions': 163 33 122
'pump': 0 0
Clauses shared #Exported #Imported #BinaryRead #BinaryTotal
'core': 228 322 0 0
'default_lp': 0 284 0 0
'lb_tree_search': 0 386 0 0
'max_lp': 2 284 0 0
'no_lp': 355 290 0 0
'objective_lb_search': 1 385 0 0
'probing': 0 0 0 0
'pseudo_costs': 2 385 0 0
'quick_restart': 12 478 0 0
'quick_restart_no_lp': 144 358 0 0
'reduced_costs': 1 488 0 0
LRAT_status: NA
[Scaling] scaled_objective_bound: 229771 corrected_bound: 229771 delta: 2.19746e-06
CpSolverResponse summary:
status: FEASIBLE
objective: 241104.1441382699
best_bound: 229770.8128485464
integers: 0
booleans: 0
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 0
restarts: 0
lp_iterations: 0
walltime: 20.1097
usertime: 20.1097
deterministic_time: 111.065
gap_integral: 1039.52
solution_fingerprint: 0xee4c149db2925d59
[23]:
wfn.solution_info()
[23]:
{'router': 'MILPRouter',
'capacity': 8,
'solver_name': 'ortools.cp_sat',
'mip_gap': 0.005,
'time_limit': 20,
'topology': <Topology.BRANCHED: 'branched'>,
'feeder_route': <FeederRoute.SEGMENTED: 'segmented'>,
'feeder_limit': <FeederLimit.UNLIMITED: 'unlimited'>,
'balanced': False,
'runtime': 20.118368,
'bound': 229770.81284854643,
'objective': 241104.1441382699,
'relgap': 0.04700595806940577,
'termination': 'FEASIBLE'}
[24]:
wfn.length()
[24]:
241104.1441382698
[25]:
wfn
[25]:
