🚀 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 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)
42.5 ms ± 9.89 ms per loop (mean ± std. dev. of 7 runs, 1 loop 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 only solutions)¶
[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': 1192292722,
'nbIter': 20000,
'nbIterTraces': 500,
'timeLimit': 1,
'useSwapStar': True,
'runtime': 1.000530305}
[18]:
wfn.length()
[18]:
243074.2848236982
[19]:
wfn
[19]:
Note that the HGSRouter always produces a network with radial topology.
A radial topology means that each turbine has at most two connections (maximum degree of 2). Contrast that with the default 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, axr) = plt.subplots(1, 2, 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)
axr.set_title('Branched', color='#888888');
wfn_toy.optimize(
router=MILPRouter(**opt_milp,
model_options=ModelOptions(topology='branched', 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: 0xfdc70ec361bce877)
#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.64e-04s 0.00e+00d [DetectDominanceRelations]
1.05e-02s 0.00e+00d [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
4.34e-05s 0.00e+00d [ExtractEncodingFromLinear] #potential_supersets=355
4.62e-04s 0.00e+00d [DetectDuplicateColumns]
1.91e-04s 0.00e+00d [DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 6'368 nodes and 11'971 arcs.
[Symmetry] Symmetry computation done. time: 0.000668215 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.7987e-05s] clauses:375 literals:750 vars:750 one_side_vars:750 simple_definition:0 singleton_clauses:0
[SAT presolve] [3.5018e-05s] clauses:375 literals:750 vars:750 one_side_vars:750 simple_definition:0 singleton_clauses:0
2.72e-04s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
2.20e-02s 1.04e-02d [Probe] #probed=3'380 #new_binary_clauses=845
5.54e-04s 5.46e-04d [MaxClique] Merged 635 constraints with 1'926 literals into 330 constraints with 1'316 literals
7.89e-04s 0.00e+00d [DetectDominanceRelations]
4.99e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
1.69e-03s 0.00e+00d [ProcessAtMostOneAndLinear] #num_changes=845
1.76e-04s 0.00e+00d [DetectDuplicateConstraints]
1.62e-04s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
2.87e-04s 1.46e-05d [DetectDominatedLinearConstraints] #relevant_constraints=193 #num_inclusions=96
3.35e-05s 0.00e+00d [DetectDifferentVariables]
3.79e-03s 3.73e-04d [ProcessSetPPC] #relevant_constraints=427 #num_inclusions=425
1.78e-04s 0.00e+00d [TransformClausesToExactlyOne] #num_amos=330
6.31e-04s 0.00e+00d [DetectEncodedComplexDomains]
1.71e-04s 0.00e+00d [FindAlmostIdenticalLinearConstraints]
2.91e-04s 2.83e-04d [FindBigAtMostOneAndLinearOverlap]
2.15e-04s 3.25e-04d [FindBigVerticalLinearOverlap]
2.72e-05s 1.24e-05d [FindBigHorizontalLinearOverlap] #linears=179
1.28e-05s 0.00e+00d [MergeClauses]
3.86e-04s 0.00e+00d [DetectDominanceRelations]
6.45e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
6.34e-04s 0.00e+00d [DetectDominanceRelations]
3.39e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
1.12e-04s 0.00e+00d [DetectDuplicateColumns]
3.12e-04s 0.00e+00d [DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 5'717 nodes and 9'866 arcs.
[Symmetry] Symmetry computation done. time: 0.000667768 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] [1.0851e-05s] clauses:70 literals:140 vars:140 one_side_vars:140 simple_definition:0 singleton_clauses:0
[SAT presolve] [3.5888e-05s] clauses:70 literals:140 vars:140 one_side_vars:140 simple_definition:0 singleton_clauses:0
2.21e-04s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
9.34e-03s 3.44e-03d [Probe] #probed=1'690
3.75e-04s 3.69e-04d [MaxClique]
4.25e-04s 0.00e+00d [DetectDominanceRelations]
3.80e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
2.08e-04s 0.00e+00d [ProcessAtMostOneAndLinear]
4.09e-04s 0.00e+00d [DetectDuplicateConstraints]
1.88e-04s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
2.59e-04s 1.10e-05d [DetectDominatedLinearConstraints] #relevant_constraints=192 #num_inclusions=95
3.87e-05s 0.00e+00d [DetectDifferentVariables]
1.62e-04s 7.32e-06d [ProcessSetPPC] #relevant_constraints=426
1.66e-04s 0.00e+00d [TransformClausesToExactlyOne] #num_amos=330
7.96e-04s 0.00e+00d [DetectEncodedComplexDomains]
4.36e-05s 0.00e+00d [FindAlmostIdenticalLinearConstraints]
2.89e-04s 2.79e-04d [FindBigAtMostOneAndLinearOverlap]
1.99e-04s 3.25e-04d [FindBigVerticalLinearOverlap]
3.08e-05s 1.24e-05d [FindBigHorizontalLinearOverlap] #linears=179
1.22e-05s 0.00e+00d [MergeClauses]
3.98e-04s 0.00e+00d [DetectDominanceRelations]
3.08e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
5.66e-06s 0.00e+00d [MergeNoOverlap]
6.21e-06s 0.00e+00d [MergeNoOverlap2D]
3.14e-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: 0x2c18320fdb1eb53c)
#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.000500931 dtime: 0.00104354
Preloading model.
#Bound 0.09s best:inf next:[160817.074,2309766.32] initial_domain
#1 0.09s best:242923.237 next:[160817.074,242923.237] complete_hint
#Model 0.09s var:1690/1690 constraints:2307/2307
Starting search at 0.09s 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.13s best:242923.237 next:[162472.38,242923.237] am1_presolve (num_literals=750 num_am1=34 increase=1735714016 work_done=2720)
#Bound 0.13s best:242923.237 next:[188354.862,242923.237] default_lp
#Bound 0.13s best:242923.237 next:[189781.728,242923.237] reduced_costs
#Bound 0.18s best:242923.237 next:[223973.897,242923.237] lb_tree_search
#2 0.20s best:242907.625 next:[223973.897,242907.625] quick_restart_no_lp (fixed_bools=0/901)
#3 0.21s best:242906.99 next:[223973.897,242906.99] quick_restart_no_lp (fixed_bools=0/901)
#Bound 0.34s best:242906.99 next:[225413.966,242906.99] max_lp
#4 0.38s best:242073.91 next:[225413.966,242073.91] graph_var_lns (d=7.07e-01 s=24 t=0.10 p=1.00 stall=1 h=base)
#5 0.53s best:241885.435 next:[225413.966,241885.435] graph_arc_lns (d=5.00e-01 s=14 t=0.10 p=0.00 stall=0 h=base) [combined with: graph_var_lns (d=7.0...]
#6 0.62s best:241665.602 next:[225413.966,241665.602] graph_cst_lns (d=7.07e-01 s=25 t=0.10 p=1.00 stall=1 h=base)
#7 0.63s best:241477.127 next:[225413.966,241477.127] graph_cst_lns (d=7.07e-01 s=25 t=0.10 p=1.00 stall=1 h=base) [combined with: graph_arc_lns (d=5.0...]
#Bound 0.90s best:241477.127 next:[225975.405,241477.127] lb_tree_search
#Bound 0.91s best:241477.127 next:[226137.83,241477.127] max_lp
#Bound 1.05s best:241477.127 next:[226750.888,241477.127] lb_tree_search
#Bound 1.10s best:241477.127 next:[226769.281,241477.127] lb_tree_search (nodes=1/1 rc=0 decisions=55 @root=2 restarts=0 lp_iters=[0, 0, 68, 7])
#Bound 1.11s best:241477.127 next:[226809.158,241477.127] max_lp
#Bound 1.29s best:241477.127 next:[227055.05,241477.127] lb_tree_search
#Bound 1.30s best:241477.127 next:[227055.22,241477.127] lb_tree_search
#Bound 1.33s best:241477.127 next:[227243.958,241477.127] max_lp
#Bound 1.41s best:241477.127 next:[227473.456,241477.127] max_lp
#Bound 1.47s best:241477.127 next:[227502.077,241477.127] max_lp
#Bound 1.55s best:241477.127 next:[227565.717,241477.127] lb_tree_search
#Bound 1.59s best:241477.127 next:[227567.568,241477.127] lb_tree_search (nodes=2/2 rc=0 decisions=73 @root=6 restarts=0 lp_iters=[0, 0, 200, 12])
#8 1.63s best:240715.16 next:[227567.568,240715.16] lb_relax_lns_int_h (d=5.00e-01 s=35 t=0.50 p=0.00 stall=0 h=base)
#Bound 1.69s best:240715.16 next:[227717.228,240715.16] lb_tree_search
#Bound 1.70s best:240715.16 next:[227831.057,240715.16] lb_tree_search (nodes=2/2 rc=0 decisions=74 @root=6 restarts=0 lp_iters=[0, 0, 527, 12])
#Bound 1.71s best:240715.16 next:[227836.523,240715.16] lb_tree_search
#Bound 2.25s best:240715.16 next:[227960.022,240715.16] max_lp
#Bound 2.30s best:240715.16 next:[228026.776,240715.16] lb_tree_search
#Bound 2.42s best:240715.16 next:[228088.08,240715.16] lb_tree_search (nodes=2/2 rc=0 decisions=78 @root=10 restarts=0 lp_iters=[0, 0, 730, 12]) [skipped_logs=3]
#Bound 3.42s best:240715.16 next:[228352.508,240715.16] lb_tree_search (nodes=2/2 rc=0 decisions=82 @root=12 restarts=0 lp_iters=[0, 0, 1'076, 12]) [skipped_logs=3]
#Bound 4.97s best:240715.16 next:[228607.596,240715.16] lb_tree_search (nodes=5/5 rc=1 decisions=149 @root=14 restarts=0 lp_iters=[0, 0, 2'002, 82]) [skipped_logs=8]
#Bound 6.00s best:240715.16 next:[228819.679,240715.16] lb_tree_search (nodes=12/12 rc=2 decisions=262 @root=14 restarts=0 lp_iters=[0, 0, 4'491, 323]) [skipped_logs=11]
#Bound 7.03s best:240715.16 next:[229025.048,240715.16] lb_tree_search (nodes=18/18 rc=2 decisions=330 @root=14 restarts=0 lp_iters=[0, 0, 6'712, 651]) [skipped_logs=11]
#Bound 7.99s best:240715.16 next:[229100.375,240715.16] lb_tree_search (nodes=27/27 rc=7 decisions=430 @root=14 restarts=0 lp_iters=[0, 0, 8'354, 1'062]) [skipped_logs=8]
#Bound 8.85s best:240715.16 next:[229180.74,240715.16] lb_tree_search (nodes=39/39 rc=8 decisions=546 @root=14 restarts=0 lp_iters=[0, 0, 9'780, 2'184]) [skipped_logs=7]
#Bound 9.88s best:240715.16 next:[229200.989,240715.16] lb_tree_search (nodes=47/47 rc=13 decisions=608 @root=14 restarts=0 lp_iters=[0, 0, 11'967, 2'255]) [skipped_logs=4]
#Bound 10.52s best:240715.16 next:[229227.749,240715.16] lb_tree_search (nodes=49/49 rc=13 decisions=654 @root=14 restarts=0 lp_iters=[0, 0, 13'477, 2'403]) [skipped_logs=4]
#Bound 12.00s best:240715.16 next:[229249.686,240715.16] lb_tree_search (nodes=49/49 rc=13 decisions=670 @root=16 restarts=0 lp_iters=[0, 0, 14'356, 2'403]) [skipped_logs=2]
#Bound 13.07s best:240715.16 next:[229281.793,240715.16] lb_tree_search (nodes=49/49 rc=14 decisions=714 @root=16 restarts=0 lp_iters=[0, 0, 16'940, 2'403]) [skipped_logs=6]
#Bound 13.91s best:240715.16 next:[229334.409,240715.16] lb_tree_search (nodes=50/50 rc=18 decisions=767 @root=16 restarts=0 lp_iters=[0, 0, 19'407, 2'682]) [skipped_logs=10]
#Bound 14.96s best:240715.16 next:[229361.736,240715.16] lb_tree_search (nodes=53/53 rc=19 decisions=856 @root=16 restarts=0 lp_iters=[0, 0, 22'350, 2'751]) [skipped_logs=5]
#Bound 16.00s best:240715.16 next:[229372.865,240715.16] lb_tree_search (nodes=55/55 rc=19 decisions=930 @root=16 restarts=0 lp_iters=[0, 0, 25'349, 3'021]) [skipped_logs=6]
#Bound 16.91s best:240715.16 next:[229408.359,240715.16] lb_tree_search (nodes=61/61 rc=22 decisions=989 @root=16 restarts=0 lp_iters=[0, 0, 28'042, 3'401]) [skipped_logs=10]
#Bound 17.01s best:240715.16 next:[229412.003,240715.16] lb_tree_search (nodes=61/61 rc=22 decisions=997 @root=16 restarts=0 lp_iters=[0, 0, 28'525, 3'401]) [skipped_logs=0]
Task timing n [ min, max] avg dev time n [ min, max] avg dev dtime
'core': 1 [ 19.92s, 19.92s] 19.92s 0.00ns 19.92s 2 [ 3.54ms, 9.49s] 4.75s 4.74s 9.49s
'default_lp': 1 [ 19.91s, 19.91s] 19.91s 0.00ns 19.91s 2 [119.19ms, 4.60s] 2.36s 2.24s 4.72s
'feasibility_pump': 92 [ 71.60us, 203.56ms] 5.06ms 20.83ms 465.58ms 88 [374.50us, 65.46ms] 1.13ms 6.90ms 99.14ms
'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': 41 [826.00ns, 541.30ms] 223.72ms 192.67ms 9.17s 34 [ 40.25us, 100.21ms] 57.11ms 44.65ms 1.94s
'graph_cst_lns': 26 [ 16.82ms, 1.15s] 368.47ms 262.22ms 9.58s 26 [ 10.42us, 100.18ms] 64.25ms 41.65ms 1.67s
'graph_dec_lns': 35 [ 1.59ms, 896.72ms] 301.91ms 245.19ms 10.57s 31 [ 10.00ns, 100.14ms] 58.50ms 44.56ms 1.81s
'graph_var_lns': 33 [ 7.91ms, 582.98ms] 279.18ms 201.79ms 9.21s 33 [ 10.00ns, 100.16ms] 58.10ms 45.82ms 1.92s
'lb_relax_lns': 6 [403.57ms, 2.75s] 1.57s 804.28ms 9.40s 6 [103.74ms, 562.83ms] 407.59ms 211.51ms 2.45s
'lb_tree_search': 1 [ 19.92s, 19.92s] 19.92s 0.00ns 19.92s 2 [203.40ms, 7.59s] 3.90s 3.69s 7.79s
'ls': 41 [116.35ms, 409.43ms] 222.45ms 61.41ms 9.12s 41 [ 57.67ms, 100.03ms] 98.98ms 6.53ms 4.06s
'ls_lin': 38 [ 48.73ms, 511.01ms] 238.76ms 73.93ms 9.07s 38 [ 22.85ms, 100.02ms] 97.98ms 12.35ms 3.72s
'max_lp': 1 [ 19.92s, 19.92s] 19.92s 0.00ns 19.92s 2 [202.61ms, 7.52s] 3.86s 3.66s 7.72s
'no_lp': 1 [ 19.91s, 19.91s] 19.91s 0.00ns 19.91s 2 [ 4.18ms, 7.36s] 3.68s 3.68s 7.37s
'objective_lb_search': 1 [ 19.91s, 19.91s] 19.91s 0.00ns 19.91s 2 [125.81ms, 7.07s] 3.60s 3.47s 7.19s
'probing': 1 [ 19.92s, 19.92s] 19.92s 0.00ns 19.92s 2 [126.27ms, 4.83s] 2.48s 2.35s 4.96s
'pseudo_costs': 1 [ 19.91s, 19.91s] 19.91s 0.00ns 19.91s 2 [ 39.39ms, 4.51s] 2.28s 2.24s 4.55s
'quick_restart': 1 [ 19.92s, 19.92s] 19.92s 0.00ns 19.92s 2 [120.24ms, 6.12s] 3.12s 3.00s 6.24s
'quick_restart_no_lp': 1 [ 19.92s, 19.92s] 19.92s 0.00ns 19.92s 2 [ 4.18ms, 8.51s] 4.26s 4.25s 8.51s
'reduced_costs': 1 [ 19.91s, 19.91s] 19.91s 0.00ns 19.91s 2 [ 41.65ms, 6.38s] 3.21s 3.17s 6.42s
'rins/rens': 29 [ 5.23ms, 1.10s] 357.45ms 304.14ms 10.37s 24 [332.18us, 100.12ms] 69.16ms 43.79ms 1.66s
'rnd_cst_lns': 34 [ 11.93ms, 827.07ms] 355.84ms 224.51ms 12.10s 34 [136.00ns, 100.21ms] 65.38ms 41.44ms 2.22s
'rnd_var_lns': 32 [ 11.73ms, 806.28ms] 309.91ms 237.65ms 9.92s 32 [146.00ns, 100.18ms] 55.82ms 45.89ms 1.79s
Search stats Bools Conflicts Branches Restarts BacktrackToRoot Backtrack BoolPropag IntegerPropag
'core': 879 294'875 620'647 323 5'540 299'354 4'654'881 13'144'334
'default_lp': 942 1'782 12'436 2 5'171 7'337 163'768 676'405
'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 16 48'145 0 23'255 25'195 196'043 671'555
'max_lp': 845 294 32'149 3 13'115 14'384 155'069 754'679
'no_lp': 845 93'952 305'215 900 35'438 131'805 9'231'958 29'673'774
'objective_lb_search': 908 922 20'866 5 10'353 12'312 127'771 572'862
'probing': 866 10 2'066 0 1'775 1'785 13'468 45'751
'pseudo_costs': 845 1'532 25'568 5 10'699 12'969 162'245 790'738
'quick_restart': 890 189 49'660 11 20'213 22'575 217'786 1'033'943
'quick_restart_no_lp': 1'223 42'945 960'027 3'821 27'952 78'991 5'401'563 19'339'685
'reduced_costs': 846 696 46'121 8 16'733 18'726 189'549 977'734
SAT formula Fixed Equiv Total VarLeft BinaryClauses PermanentClauses TemporaryClauses
'core': 0 0 879 879 188 1'437 9'339
'default_lp': 0 0 942 942 528 117 1'586
'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 304 5
'max_lp': 0 0 845 845 140 301 240
'no_lp': 0 0 845 845 140 377 7'667
'objective_lb_search': 3 0 908 905 434 117 570
'probing': 0 0 866 866 484 95 9
'pseudo_costs': 0 0 845 845 140 181 1'349
'quick_restart': 0 0 890 890 316 300 124
'quick_restart_no_lp': 0 0 1'223 1'223 2'824 1'384 8'045
'reduced_costs': 0 0 846 846 150 301 642
SAT stats ClassicMinim LitRemoved LitRemovedBinary LitLearned LitForgotten Subsumed
'core': 268'313 1'828'598 1'826'727 16'064'250 9'605'580 97'829
'default_lp': 1'618 15'321 132'480 221'695 0 167
'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': 6 13 93 307 0 11
'max_lp': 250 5'104 9'721 28'842 0 45
'no_lp': 86'218 2'856'898 1'406'241 7'205'909 3'045'969 43'735
'objective_lb_search': 871 43'464 16'496 52'938 0 157
'probing': 8 37 619 2'332 0 1
'pseudo_costs': 1'315 15'479 143'000 265'258 0 178
'quick_restart': 125 2'031 6'049 15'192 0 48
'quick_restart_no_lp': 36'237 753'977 941'504 4'147'465 2'710'017 7'198
'reduced_costs': 451 3'976 33'570 97'848 0 42
Vivification Clauses Decisions LitTrue Subsumed LitRemoved DecisionReused Conflicts
'core': 2'438 36'525 0 331 6'117 3'588 8
'default_lp': 404 3'109 0 2 14 10 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': 3'060 24'786 0 98 747 401 3
'max_lp': 2'295 18'835 0 107 910 715 3
'no_lp': 7'299 78'097 0 221 2'678 4'517 6
'objective_lb_search': 1'045 8'111 0 1 10 3 1
'probing': 0 0 0 0 0 0 0
'pseudo_costs': 1'295 10'342 0 12 120 113 1
'quick_restart': 3'434 28'144 0 114 987 894 6
'quick_restart_no_lp': 10'889 71'509 0 479 4'472 3'519 61
'reduced_costs': 2'843 23'401 0 109 948 752 7
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 94'936 1'747 2 2'893 331 0 197 0 0 184'273 675'232 294'875
'default_lp': 0 0 0 163 1 0 4 2 0 1 0 0 0 3'802 1'782
'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 11 0 0 0 98 0 0 0 0 0 5 16
'max_lp': 0 0 0 44 1 0 1 107 0 1 0 0 0 558 294
'no_lp': 0 0 0 42'520 266 291 1'215 221 0 113 0 0 41'637 211'607 93'952
'objective_lb_search': 181 0 0 153 2 5 4 1 0 0 0 0 0 1'857 922
'probing': 0 0 0 1 0 0 0 0 0 0 0 0 0 18 10
'pseudo_costs': 0 0 0 167 2 0 11 12 0 0 0 0 0 3'393 1'532
'quick_restart': 0 0 0 45 0 0 3 114 0 1 0 0 0 240 189
'quick_restart_no_lp': 0 0 5 6'685 109 27 513 479 39 108 0 0 25'503 86'602 42'945
'reduced_costs': 0 0 0 41 1 0 1 109 0 2 0 0 0 1'441 696
Lp stats Component Iterations AddedCuts OPTIMAL DUAL_F. DUAL_U.
'default_lp': 1 109'010 2'176 6'400 1 76
'lb_tree_search': 1 40'163 2'442 836 143 0
'max_lp': 1 55'010 2'610 1'446 181 33
'objective_lb_search': 1 99'320 2'981 3'673 0 48
'probing': 1 20'683 4'409 329 0 0
'pseudo_costs': 1 87'322 2'792 4'751 317 192
'quick_restart': 1 47'913 3'833 1'716 2 23
'reduced_costs': 1 78'141 3'216 2'320 323 156
Lp dimension Final dimension of first component
'default_lp': 850 rows, 1596 columns, 4828 entries
'lb_tree_search': 1448 rows, 1690 columns, 19018 entries
'max_lp': 1490 rows, 1690 columns, 18629 entries
'objective_lb_search': 976 rows, 1596 columns, 8390 entries
'probing': 2602 rows, 1596 columns, 56231 entries
'pseudo_costs': 792 rows, 1690 columns, 5658 entries
'quick_restart': 1567 rows, 1596 columns, 19384 entries
'reduced_costs': 1443 rows, 1690 columns, 15647 entries
Lp debug CutPropag CutEqPropag Adjust Overflow Bad BadScaling
'default_lp': 0 0 6'460 0 2'137 0
'lb_tree_search': 0 0 979 0 34'628 0
'max_lp': 0 0 1'658 0 24'169 0
'objective_lb_search': 0 0 3'712 0 7'356 0
'probing': 0 2 315 0 53'783 0
'pseudo_costs': 0 0 5'214 0 5'504 0
'quick_restart': 0 0 1'728 0 23'374 0
'reduced_costs': 0 0 2'753 0 17'865 0
Lp pool Constraints Updates Simplif Merged Shortened Split Strengthened Cuts/Call
'default_lp': 4'976 2 0 0 0 0 69 2'176/5'136
'lb_tree_search': 5'594 350 0 0 0 509 3 2'442/4'486
'max_lp': 5'762 264 0 0 0 278 0 2'610/4'675
'objective_lb_search': 5'781 37 0 0 0 35 59 2'981/6'113
'probing': 7'209 414 0 0 0 1'079 69 4'409/7'949
'pseudo_costs': 5'944 28 0 0 0 13 2 2'792/6'011
'quick_restart': 6'633 187 0 0 0 186 84 3'833/7'331
'reduced_costs': 6'368 158 0 0 0 153 3 3'216/6'388
Lp Cut default_lp reduced_costs pseudo_costs objective_lb_search max_lp quick_restart lb_tree_search probing
CG_FF: 13 19 30 16 9 15 2 25
CG_K: 11 6 20 11 1 5 1 9
CG_KL: 6 3 3 3 - 4 - 4
CG_R: 17 33 31 24 19 17 11 33
CG_RB: 29 62 53 62 40 64 47 68
CG_RBP: 12 22 28 22 5 22 3 36
IB: 1'245 1'143 1'486 1'075 441 1'074 180 765
MIR_1_FF: 58 98 69 143 107 240 115 296
MIR_1_K: 38 9 13 62 9 61 4 65
MIR_1_KL: 20 1 2 28 4 37 1 51
MIR_1_R: 1 2 1 1 - 6 1 5
MIR_1_RB: 21 57 42 98 61 126 51 128
MIR_1_RBP: 21 21 11 69 12 101 14 134
MIR_2_FF: 66 146 103 137 161 203 165 245
MIR_2_K: 35 17 12 64 13 73 6 83
MIR_2_KL: 11 3 2 22 3 23 5 26
MIR_2_R: 2 6 7 10 4 10 7 13
MIR_2_RB: 69 144 98 119 138 173 138 193
MIR_2_RBP: 34 36 24 70 44 108 32 148
MIR_3_FF: 46 130 89 80 148 108 174 165
MIR_3_K: 32 24 17 51 17 80 18 89
MIR_3_KL: 9 6 2 7 3 11 1 12
MIR_3_R: 5 13 11 3 7 5 5 11
MIR_3_RB: 49 120 93 94 142 119 156 144
MIR_3_RBP: 23 53 23 57 47 96 39 130
MIR_4_FF: 26 84 60 46 137 56 138 87
MIR_4_K: 15 14 14 36 29 42 33 57
MIR_4_KL: 6 5 - 2 1 6 3 6
MIR_4_R: 2 9 7 8 10 2 7 9
MIR_4_RB: 34 86 71 51 105 55 119 89
MIR_4_RBP: 16 28 11 26 47 56 57 99
MIR_5_FF: 11 64 19 19 74 48 89 64
MIR_5_K: 12 23 11 18 34 46 26 44
MIR_5_KL: - 8 1 2 - 4 4 4
MIR_5_R: 1 10 3 4 12 5 10 6
MIR_5_RB: 15 59 34 26 61 33 70 46
MIR_5_RBP: 4 30 9 19 43 38 30 41
MIR_6_FF: 5 45 23 13 49 24 53 39
MIR_6_K: 8 16 5 16 25 28 19 39
MIR_6_KL: 2 15 3 1 15 7 19 7
MIR_6_R: - 6 3 1 7 2 5 5
MIR_6_RB: 9 36 24 17 50 17 43 25
MIR_6_RBP: 3 22 8 20 42 30 35 32
ZERO_HALF_FF: 17 29 13 29 11 19 9 28
ZERO_HALF_K: 8 10 1 8 1 11 - 7
ZERO_HALF_KL: 3 2 - 1 - 2 1 4
ZERO_HALF_R: 89 353 162 221 341 402 414 647
ZERO_HALF_RB: 12 60 32 47 75 86 66 108
ZERO_HALF_RBP: 5 28 8 22 6 33 16 38
LNS stats Improv/Calls Closed Difficulty TimeLimit
'graph_arc_lns': 3/34 50% 4.06e-01 0.10
'graph_cst_lns': 6/26 50% 6.59e-01 0.10
'graph_dec_lns': 1/31 52% 7.68e-01 0.10
'graph_var_lns': 3/33 48% 5.97e-01 0.10
'lb_relax_lns': 3/6 33% 2.86e-01 0.50
'rins/rens': 24/29 45% 3.03e-01 0.10
'rnd_cst_lns': 3/34 47% 5.90e-01 0.10
'rnd_var_lns': 3/32 50% 7.02e-01 0.10
LS stats Batches Restarts/Perturbs LinMoves GenMoves CompoundMoves Bactracks WeightUpdates ScoreComputed
'ls_lin_restart': 3 3 38'237 0 0 0 6'886 1'367'918
'ls_lin_restart_compound': 5 4 0 65'963 6'145 29'906 335 1'867'830
'ls_lin_restart_compound_perturb': 4 3 0 59'936 5'977 26'973 361 1'686'084
'ls_lin_restart_decay': 2 2 30'954 0 0 0 532 716'237
'ls_lin_restart_decay_compound': 3 3 0 39'558 5'416 17'061 121 1'225'603
'ls_lin_restart_decay_compound_perturb': 6 5 0 83'554 14'596 34'469 122 2'717'370
'ls_lin_restart_decay_perturb': 5 4 77'542 0 0 0 1'255 1'767'446
'ls_lin_restart_perturb': 10 6 127'571 0 0 0 20'615 4'827'555
'ls_restart': 4 3 51'287 0 0 0 10'921 1'890'001
'ls_restart_compound': 4 1 0 53'834 4'771 24'529 57 1'691'864
'ls_restart_compound_perturb': 7 6 0 109'599 10'880 49'333 646 3'096'374
'ls_restart_decay': 4 4 61'623 0 0 0 1'060 1'396'051
'ls_restart_decay_compound': 8 5 0 109'343 17'996 45'664 149 3'418'028
'ls_restart_decay_compound_perturb': 5 4 0 66'405 11'536 27'422 124 1'997'744
'ls_restart_decay_perturb': 4 3 61'998 0 0 0 1'036 1'408'946
'ls_restart_perturb': 5 5 64'967 0 0 0 9'967 2'399'154
Solutions (8) Num Rank
'complete_hint': 2 [0,1]
'graph_arc_lns': 2 [4,5]
'graph_cst_lns': 4 [5,7]
'graph_var_lns': 2 [3,4]
'lb_relax_lns_int_h': 2 [7,8]
'quick_restart_no_lp': 4 [1,3]
Objective bounds Num
'am1_presolve': 1
'default_lp': 1
'initial_domain': 1
'lb_tree_search': 126
'max_lp': 7
'reduced_costs': 1
Solution repositories Added Queried Synchro
'alternative_path': 21 96 21
'best_solutions': 68 222 46
'fj solution hints': 0 0 0
'lp solutions': 140 29 110
'pump': 0 0
Clauses shared #Exported #Imported #BinaryRead #BinaryTotal
'core': 220 155 0 0
'default_lp': 1 0 0 0
'lb_tree_search': 0 307 0 0
'max_lp': 0 306 0 0
'no_lp': 47 261 0 0
'objective_lb_search': 0 16 0 0
'probing': 0 0 0 0
'pseudo_costs': 0 95 0 0
'quick_restart': 1 306 0 0
'quick_restart_no_lp': 149 169 0 0
'reduced_costs': 0 307 0 0
LRAT_status: NA
[Scaling] scaled_objective_bound: 229412 corrected_bound: 229412 delta: 2.18779e-06
CpSolverResponse summary:
status: FEASIBLE
objective: 240715.159901454
best_bound: 229412.0033964992
integers: 0
booleans: 0
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 0
restarts: 0
lp_iterations: 0
walltime: 20.0252
usertime: 20.0252
deterministic_time: 98.3159
gap_integral: 919.01
solution_fingerprint: 0x91194cc2586fc39b
[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.035444,
'bound': 229412.0033964992,
'objective': 240715.159901454,
'relgap': 0.04695656272576343,
'termination': 'FEASIBLE'}
[24]:
wfn.length()
[24]:
240866.20757545892
[25]:
wfn
[25]:
