🚀 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)
30.6 ms ± 169 μ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 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,
'nbGranular': 20,
'mu': 25,
'lambda_': 40,
'nbElite': 4,
'nbClose': 5,
'nbIterPenaltyManagement': 100,
'targetFeasible': 0.2,
'penaltyDecrease': 0.85,
'penaltyIncrease': 1.2,
'seed': 1135034442,
'nbIter': 20000,
'nbIterTraces': 500,
'timeLimit': 1,
'useSwapStar': True,
'runtime': 1.000543211}
[18]:
wfn.length()
[18]:
243285.1091892355
[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: 0x3e191ebfad7f2979)
#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
9.76e-04s 0.00e+00d [DetectDominanceRelations]
9.90e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
2.36e-05s 0.00e+00d [ExtractEncodingFromLinear] #potential_supersets=355
2.21e-04s 0.00e+00d [DetectDuplicateColumns]
1.58e-04s 0.00e+00d [DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 6'368 nodes and 11'971 arcs.
[Symmetry] Symmetry computation done. time: 0.00055943 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] [8.6824e-05s] clauses:375 literals:750 vars:750 one_side_vars:750 simple_definition:0 singleton_clauses:0
[SAT presolve] [0.000155479s] clauses:375 literals:750 vars:750 one_side_vars:750 simple_definition:0 singleton_clauses:0
1.81e-04s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
2.16e-02s 1.04e-02d [Probe] #probed=3'380 #new_binary_clauses=845
7.22e-04s 5.46e-04d [MaxClique] Merged 635 constraints with 1'926 literals into 330 constraints with 1'316 literals
3.68e-04s 0.00e+00d [DetectDominanceRelations]
4.67e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
1.20e-03s 0.00e+00d [ProcessAtMostOneAndLinear] #num_changes=845
1.48e-04s 0.00e+00d [DetectDuplicateConstraints]
1.41e-04s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
2.67e-04s 1.46e-05d [DetectDominatedLinearConstraints] #relevant_constraints=193 #num_inclusions=96
3.91e-05s 0.00e+00d [DetectDifferentVariables]
3.67e-03s 3.73e-04d [ProcessSetPPC] #relevant_constraints=427 #num_inclusions=425
1.50e-04s 0.00e+00d [TransformClausesToExactlyOne] #num_amos=330
7.56e-04s 0.00e+00d [DetectEncodedComplexDomains]
2.95e-05s 0.00e+00d [FindAlmostIdenticalLinearConstraints]
5.32e-04s 2.83e-04d [FindBigAtMostOneAndLinearOverlap]
1.98e-04s 3.25e-04d [FindBigVerticalLinearOverlap]
2.62e-05s 1.24e-05d [FindBigHorizontalLinearOverlap] #linears=179
2.76e-05s 0.00e+00d [MergeClauses]
9.36e-04s 0.00e+00d [DetectDominanceRelations]
6.30e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
3.43e-04s 0.00e+00d [DetectDominanceRelations]
3.97e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
1.07e-04s 0.00e+00d [DetectDuplicateColumns]
1.56e-04s 0.00e+00d [DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 5'717 nodes and 9'866 arcs.
[Symmetry] Symmetry computation done. time: 0.000388603 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] [8.502e-06s] clauses:70 literals:140 vars:140 one_side_vars:140 simple_definition:0 singleton_clauses:0
[SAT presolve] [2.5283e-05s] clauses:70 literals:140 vars:140 one_side_vars:140 simple_definition:0 singleton_clauses:0
1.63e-04s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
8.99e-03s 3.44e-03d [Probe] #probed=1'690
2.86e-04s 3.69e-04d [MaxClique]
8.98e-04s 0.00e+00d [DetectDominanceRelations]
4.30e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
1.87e-04s 0.00e+00d [ProcessAtMostOneAndLinear]
1.76e-04s 0.00e+00d [DetectDuplicateConstraints]
1.56e-04s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
2.17e-04s 1.10e-05d [DetectDominatedLinearConstraints] #relevant_constraints=192 #num_inclusions=95
2.32e-05s 0.00e+00d [DetectDifferentVariables]
1.53e-04s 7.32e-06d [ProcessSetPPC] #relevant_constraints=426
2.80e-04s 0.00e+00d [TransformClausesToExactlyOne] #num_amos=330
1.11e-03s 0.00e+00d [DetectEncodedComplexDomains]
4.27e-05s 0.00e+00d [FindAlmostIdenticalLinearConstraints]
2.73e-04s 2.79e-04d [FindBigAtMostOneAndLinearOverlap]
1.94e-04s 3.25e-04d [FindBigVerticalLinearOverlap]
3.49e-05s 1.24e-05d [FindBigHorizontalLinearOverlap] #linears=179
1.90e-05s 0.00e+00d [MergeClauses]
3.37e-04s 0.00e+00d [DetectDominanceRelations]
3.75e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
4.49e-06s 0.00e+00d [MergeNoOverlap]
5.18e-06s 0.00e+00d [MergeNoOverlap2D]
2.50e-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: 0x8a183b8cbedf8015)
#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.000543924 dtime: 0.00104354
Preloading model.
#Bound 0.09s best:inf next:[160817.074,2309766.32] initial_domain
#1 0.09s best:243285.109 next:[160817.074,243285.109] 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]
#2 0.12s best:243274.296 next:[160817.074,243274.296] graph_cst_lns (d=5.00e-01 s=15 t=0.10 p=0.00 stall=0 h=base)
#Bound 0.12s best:243274.296 next:[162472.38,243274.296] am1_presolve (num_literals=750 num_am1=34 increase=1735714016 work_done=2720)
#Bound 0.12s best:243274.296 next:[188354.862,243274.296] quick_restart
#Bound 0.13s best:243274.296 next:[189781.728,243274.296] pseudo_costs
#Bound 0.18s best:243274.296 next:[223973.897,243274.296] lb_tree_search
#3 0.19s best:243250.13 next:[223973.897,243250.13] quick_restart_no_lp (fixed_bools=0/892)
#4 0.26s best:243249.495 next:[223973.897,243249.495] quick_restart_no_lp (fixed_bools=0/917)
#Bound 0.31s best:243249.495 next:[225201.873,243249.495] lb_tree_search
#Bound 0.32s best:243249.495 next:[225413.966,243249.495] max_lp
#5 0.39s best:243072.468 next:[225413.966,243072.468] rnd_cst_lns (d=7.07e-01 s=24 t=0.10 p=1.00 stall=1 h=base)
#6 0.64s best:242841.823 next:[225413.966,242841.823] rins_lp_lns (d=7.07e-01 s=23 t=0.10 p=1.00 stall=0 h=base)
#7 0.65s best:242664.161 next:[225413.966,242664.161] rins_lp_lns (d=7.07e-01 s=23 t=0.10 p=1.00 stall=0 h=base) [combined with: rnd_cst_lns (d=7.07e...]
#Bound 0.84s best:242664.161 next:[225975.405,242664.161] lb_tree_search
#Bound 0.99s best:242664.161 next:[226137.83,242664.161] max_lp
#Bound 1.00s best:242664.161 next:[226696.357,242664.161] lb_tree_search
#Bound 1.31s best:242664.161 next:[227141.98,242664.161] lb_tree_search
#8 1.52s best:241069.113 next:[227141.98,241069.113] lb_relax_lns_bool_h (d=5.00e-01 s=36 t=0.50 p=0.00 stall=0 h=base)
#Bound 1.80s best:241069.113 next:[227596.084,241069.113] lb_tree_search
#Bound 2.10s best:241069.113 next:[227911.461,241069.113] lb_tree_search
#Bound 2.84s best:241069.113 next:[228117.288,241069.113] lb_tree_search
#Bound 3.02s best:241069.113 next:[228215.698,241069.113] lb_tree_search
#Bound 3.05s best:241069.113 next:[228307.104,241069.113] lb_tree_search
#Bound 3.89s best:241069.113 next:[228429.974,241069.113] lb_tree_search
#Bound 4.01s best:241069.113 next:[228430.102,241069.113] lb_tree_search (nodes=5/5 rc=0 decisions=44 @root=14 restarts=0 lp_iters=[0, 0, 1'100, 193])
#9 4.13s best:240742.123 next:[228430.102,240742.123] graph_dec_lns (d=8.09e-01 s=98 t=0.10 p=0.62 stall=8 h=base)
#Bound 4.98s best:240742.123 next:[228511.31,240742.123] lb_tree_search
#Bound 5.04s best:240742.123 next:[228512.562,240742.123] lb_tree_search (nodes=5/5 rc=0 decisions=47 @root=16 restarts=0 lp_iters=[0, 0, 1'252, 193])
#Bound 5.15s best:240742.123 next:[228600.488,240742.123] lb_tree_search (nodes=5/5 rc=0 decisions=48 @root=16 restarts=0 lp_iters=[0, 0, 1'516, 193])
#Bound 5.16s best:240742.123 next:[228603.14,240742.123] lb_tree_search (nodes=5/5 rc=0 decisions=49 @root=16 restarts=0 lp_iters=[0, 0, 1'553, 193])
#Bound 5.22s best:240742.123 next:[228621.892,240742.123] lb_tree_search (nodes=5/5 rc=0 decisions=50 @root=16 restarts=0 lp_iters=[0, 0, 1'616, 193])
#Bound 5.26s best:240742.123 next:[228622.868,240742.123] lb_tree_search (nodes=5/5 rc=0 decisions=51 @root=16 restarts=0 lp_iters=[0, 0, 1'643, 193])
#Bound 5.30s best:240742.123 next:[228622.99,240742.123] lb_tree_search (nodes=5/5 rc=0 decisions=52 @root=16 restarts=0 lp_iters=[0, 0, 1'648, 193])
#Bound 5.43s best:240742.123 next:[228642.523,240742.123] lb_tree_search (nodes=5/5 rc=0 decisions=56 @root=16 restarts=0 lp_iters=[0, 0, 2'045, 193])
#Bound 5.87s best:240742.123 next:[228689.826,240742.123] lb_tree_search (nodes=9/9 rc=0 decisions=98 @root=16 restarts=0 lp_iters=[0, 0, 2'862, 373]) [skipped_logs=5]
#Bound 6.99s best:240742.123 next:[228874.714,240742.123] lb_tree_search (nodes=17/17 rc=2 decisions=159 @root=16 restarts=0 lp_iters=[0, 0, 5'141, 971]) [skipped_logs=9]
#Bound 8.00s best:240742.123 next:[228964.491,240742.123] lb_tree_search (nodes=28/28 rc=5 decisions=245 @root=16 restarts=0 lp_iters=[0, 0, 7'624, 1'348]) [skipped_logs=13]
#Bound 8.84s best:240742.123 next:[228989.705,240742.123] lb_tree_search (nodes=31/31 rc=5 decisions=304 @root=16 restarts=0 lp_iters=[0, 0, 9'624, 1'449]) [skipped_logs=7]
#Bound 9.97s best:240742.123 next:[229048.146,240742.123] lb_tree_search (nodes=37/37 rc=5 decisions=362 @root=16 restarts=0 lp_iters=[0, 0, 12'303, 1'850]) [skipped_logs=7]
#Bound 10.95s best:240742.123 next:[229140.957,240742.123] lb_tree_search (nodes=46/46 rc=5 decisions=416 @root=16 restarts=0 lp_iters=[0, 0, 15'016, 2'760]) [skipped_logs=10]
#Bound 11.96s best:240742.123 next:[229167.674,240742.123] lb_tree_search (nodes=54/54 rc=5 decisions=499 @root=16 restarts=0 lp_iters=[0, 0, 18'729, 3'255]) [skipped_logs=14]
#Bound 12.95s best:240742.123 next:[229178.894,240742.123] lb_tree_search (nodes=60/60 rc=5 decisions=583 @root=16 restarts=0 lp_iters=[0, 0, 22'414, 3'679]) [skipped_logs=9]
#10 13.45s best:240715.795 next:[229184.169,240715.795] rnd_cst_lns (d=7.82e-01 s=326 t=0.10 p=0.54 stall=9 h=base)
#11 13.55s best:240715.16 next:[229184.169,240715.16] quick_restart_no_lp (fixed_bools=0/1163)
#Bound 14.02s best:240715.16 next:[229188.86,240715.16] lb_tree_search (nodes=66/66 rc=5 decisions=663 @root=16 restarts=0 lp_iters=[0, 0, 26'538, 4'164]) [skipped_logs=8]
#Bound 14.92s best:240715.16 next:[229201.028,240715.16] lb_tree_search (nodes=70/70 rc=5 decisions=732 @root=16 restarts=0 lp_iters=[0, 0, 29'880, 4'392]) [skipped_logs=11]
#Bound 15.78s best:240715.16 next:[229232.501,240715.16] lb_tree_search (nodes=76/76 rc=5 decisions=805 @root=16 restarts=0 lp_iters=[0, 0, 33'372, 4'736]) [skipped_logs=7]
#Bound 16.94s best:240715.16 next:[229258.733,240715.16] lb_tree_search (nodes=85/85 rc=5 decisions=907 @root=16 restarts=0 lp_iters=[0, 0, 37'879, 5'290]) [skipped_logs=11]
#Bound 17.98s best:240715.16 next:[229283.658,240715.16] lb_tree_search (nodes=91/91 rc=5 decisions=984 @root=16 restarts=0 lp_iters=[0, 0, 41'848, 5'615]) [skipped_logs=10]
#Bound 18.06s best:240715.16 next:[229289.285,240715.16] lb_tree_search (nodes=92/92 rc=5 decisions=991 @root=16 restarts=0 lp_iters=[0, 0, 42'281, 5'674]) [skipped_logs=1]
Task timing n [ min, max] avg dev time n [ min, max] avg dev dtime
'core': 1 [ 19.89s, 19.89s] 19.89s 0.00ns 19.89s 2 [ 3.54ms, 12.21s] 6.11s 6.10s 12.21s
'default_lp': 1 [ 19.91s, 19.91s] 19.91s 0.00ns 19.91s 2 [118.08ms, 5.85s] 2.98s 2.87s 5.97s
'feasibility_pump': 95 [ 65.79us, 102.05ms] 3.81ms 10.16ms 361.54ms 93 [369.41us, 65.46ms] 1.09ms 6.71ms 101.06ms
'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': 44 [ 12.19ms, 536.99ms] 246.47ms 164.00ms 10.84s 44 [ 94.67us, 100.18ms] 62.65ms 44.45ms 2.76s
'graph_cst_lns': 43 [ 16.79ms, 525.29ms] 236.64ms 174.11ms 10.18s 41 [ 3.16us, 100.13ms] 54.31ms 42.98ms 2.23s
'graph_dec_lns': 40 [ 2.03ms, 532.77ms] 243.22ms 190.38ms 9.73s 39 [ 10.00ns, 100.18ms] 53.98ms 46.87ms 2.11s
'graph_var_lns': 42 [ 7.72ms, 495.48ms] 236.37ms 175.81ms 9.93s 42 [ 42.00ns, 100.26ms] 57.62ms 46.31ms 2.42s
'lb_relax_lns': 9 [248.38ms, 1.98s] 1.09s 691.34ms 9.80s 9 [ 59.71ms, 556.91ms] 312.96ms 218.58ms 2.82s
'lb_tree_search': 1 [ 19.90s, 19.90s] 19.90s 0.00ns 19.90s 2 [210.17ms, 9.21s] 4.71s 4.50s 9.42s
'ls': 50 [169.74ms, 333.57ms] 193.79ms 25.58ms 9.69s 50 [100.01ms, 100.03ms] 100.01ms 5.47us 5.00s
'ls_lin': 50 [142.97ms, 229.88ms] 189.86ms 17.60ms 9.49s 50 [100.01ms, 100.03ms] 100.01ms 5.25us 5.00s
'max_lp': 1 [ 19.91s, 19.91s] 19.91s 0.00ns 19.91s 2 [233.21ms, 7.17s] 3.70s 3.47s 7.41s
'no_lp': 1 [ 19.91s, 19.91s] 19.91s 0.00ns 19.91s 2 [ 4.06ms, 6.11s] 3.06s 3.05s 6.12s
'objective_lb_search': 1 [ 19.91s, 19.91s] 19.91s 0.00ns 19.91s 2 [120.92ms, 7.19s] 3.66s 3.54s 7.31s
'probing': 1 [ 19.91s, 19.91s] 19.91s 0.00ns 19.91s 2 [124.04ms, 6.01s] 3.07s 2.94s 6.13s
'pseudo_costs': 1 [ 19.93s, 19.93s] 19.93s 0.00ns 19.93s 2 [ 38.75ms, 7.06s] 3.55s 3.51s 7.10s
'quick_restart': 1 [ 19.91s, 19.91s] 19.91s 0.00ns 19.91s 2 [121.71ms, 6.20s] 3.16s 3.04s 6.33s
'quick_restart_no_lp': 1 [ 19.91s, 19.91s] 19.91s 0.00ns 19.91s 2 [ 4.06ms, 9.71s] 4.86s 4.85s 9.72s
'reduced_costs': 1 [ 19.91s, 19.91s] 19.91s 0.00ns 19.91s 2 [ 43.21ms, 8.13s] 4.08s 4.04s 8.17s
'rins/rens': 42 [ 3.57ms, 494.03ms] 227.52ms 208.71ms 9.56s 28 [ 1.08us, 100.12ms] 74.50ms 40.67ms 2.09s
'rnd_cst_lns': 39 [ 12.04ms, 534.97ms] 254.73ms 187.37ms 9.93s 39 [ 10.00ns, 100.25ms] 54.74ms 45.60ms 2.14s
'rnd_var_lns': 37 [ 13.15ms, 570.25ms] 259.51ms 178.64ms 9.60s 37 [146.00ns, 100.33ms] 56.84ms 43.38ms 2.10s
Search stats Bools Conflicts Branches Restarts BacktrackToRoot Backtrack BoolPropag IntegerPropag
'core': 879 355'918 652'593 249 3'626 357'395 5'269'135 14'624'816
'default_lp': 938 1'418 26'928 4 9'231 12'291 218'671 960'992
'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 23 42'877 0 19'760 22'198 207'874 796'887
'max_lp': 845 689 41'932 6 13'532 16'819 279'364 1'377'556
'no_lp': 845 233'924 369'258 186 21'183 271'830 14'034'793 42'157'034
'objective_lb_search': 929 1'575 7'901 1 3'441 5'149 114'893 500'479
'probing': 866 11 2'106 0 1'775 1'786 13'431 45'700
'pseudo_costs': 845 712 52'883 11 20'368 24'058 306'651 1'525'883
'quick_restart': 900 183 59'310 10 22'034 26'651 339'410 1'595'448
'quick_restart_no_lp': 1'310 48'884 1'105'370 4'351 32'087 91'261 6'377'626 22'234'675
'reduced_costs': 846 1'213 26'483 5 10'428 12'347 120'973 622'018
SAT formula Fixed Equiv Total VarLeft BinaryClauses PermanentClauses TemporaryClauses
'core': 0 0 879 879 188 1'839 11'265
'default_lp': 0 0 938 938 472 345 1'214
'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 540 4
'max_lp': 0 0 845 845 140 540 593
'no_lp': 0 0 845 845 140 2'673 3'269
'objective_lb_search': 0 0 929 929 392 117 1'181
'probing': 0 0 866 866 476 95 11
'pseudo_costs': 0 0 845 845 140 514 633
'quick_restart': 0 0 900 900 350 539 136
'quick_restart_no_lp': 0 0 1'310 1'310 3'242 1'769 12'914
'reduced_costs': 0 0 846 846 142 105 1'159
SAT stats ClassicMinim LitRemoved LitRemovedBinary LitLearned LitForgotten Subsumed
'core': 326'189 2'270'449 1'911'207 18'765'655 11'554'520 115'899
'default_lp': 1'088 30'219 55'356 134'445 0 160
'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': 12 27 203 321 0 16
'max_lp': 604 7'952 32'914 99'797 0 88
'no_lp': 228'792 2'354'541 221'740 19'150'167 1'655'871 207'609
'objective_lb_search': 1'510 116'831 18'632 66'118 0 351
'probing': 4 41 360 1'991 0 0
'pseudo_costs': 561 5'589 30'284 103'423 0 77
'quick_restart': 128 2'305 7'634 21'027 0 39
'quick_restart_no_lp': 41'101 892'843 1'046'519 4'861'358 2'783'242 8'102
'reduced_costs': 829 4'150 60'810 199'376 0 54
Vivification Clauses Decisions LitTrue Subsumed LitRemoved DecisionReused Conflicts
'core': 0 0 0 0 0 0 0
'default_lp': 2'137 13'615 0 46 320 1'907 5
'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'387 22'923 0 97 630 2'146 2
'max_lp': 4'427 25'997 0 97 634 5'109 2
'no_lp': 23'113 85'764 0 127 1'140 60'289 6
'objective_lb_search': 199 1'523 0 0 0 8 0
'probing': 0 0 0 0 0 0 0
'pseudo_costs': 4'853 29'865 0 64 417 4'467 2
'quick_restart': 5'614 34'906 0 101 694 5'410 5
'quick_restart_no_lp': 14'464 86'339 0 501 4'410 6'403 51
'reduced_costs': 982 7'685 0 1 6 0 0
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 112'618 2'312 0 3'281 0 0 199 0 0 224'956 810'835 355'918
'default_lp': 0 0 0 153 3 1 7 46 0 7 0 0 0 2'920 1'418
'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 16 0 1 0 97 0 0 0 0 0 6 23
'max_lp': 0 0 0 86 0 3 2 97 0 1 0 0 0 1'304 689
'no_lp': 0 0 0 207'244 138 2'524 365 127 0 11 0 0 17'887 473'261 233'924
'objective_lb_search': 0 0 0 334 0 21 17 0 0 0 0 0 0 3'187 1'575
'probing': 0 0 0 0 0 0 0 0 0 0 0 0 0 19 11
'pseudo_costs': 0 0 0 75 1 0 2 64 0 31 0 0 0 1'424 712
'quick_restart': 0 0 0 39 1 0 0 101 0 1 0 0 0 285 183
'quick_restart_no_lp': 0 0 4 7'504 155 43 598 501 32 115 0 0 25'445 99'146 48'884
'reduced_costs': 0 0 0 52 0 0 2 1 0 0 0 0 0 2'934 1'213
Lp stats Component Iterations AddedCuts OPTIMAL DUAL_F. DUAL_U.
'default_lp': 1 101'972 3'391 5'758 0 290
'lb_tree_search': 1 53'402 2'447 1'133 195 0
'max_lp': 1 77'968 3'186 3'117 241 77
'objective_lb_search': 1 136'226 1'940 5'615 1 47
'probing': 1 22'767 4'537 359 3 1
'pseudo_costs': 1 74'147 4'159 3'171 268 127
'quick_restart': 1 49'651 3'796 2'040 0 19
'reduced_costs': 1 124'894 2'764 3'428 562 181
Lp dimension Final dimension of first component
'default_lp': 852 rows, 1596 columns, 5402 entries
'lb_tree_search': 1341 rows, 1690 columns, 18019 entries
'max_lp': 1473 rows, 1690 columns, 16116 entries
'objective_lb_search': 1017 rows, 1596 columns, 6327 entries
'probing': 2671 rows, 1596 columns, 62512 entries
'pseudo_costs': 1431 rows, 1690 columns, 17390 entries
'quick_restart': 1594 rows, 1596 columns, 20103 entries
'reduced_costs': 947 rows, 1690 columns, 7846 entries
Lp debug CutPropag CutEqPropag Adjust Overflow Bad BadScaling
'default_lp': 0 0 6'030 0 5'620 0
'lb_tree_search': 0 0 1'328 0 34'595 0
'max_lp': 0 0 3'432 0 16'634 0
'objective_lb_search': 0 0 5'645 0 1'898 0
'probing': 0 11 350 0 61'026 0
'pseudo_costs': 0 0 3'525 0 20'957 0
'quick_restart': 0 7 2'047 0 25'274 0
'reduced_costs': 0 0 4'151 0 10'288 0
Lp pool Constraints Updates Simplif Merged Shortened Split Strengthened Cuts/Call
'default_lp': 6'191 33 0 0 0 15 37 3'391/7'588
'lb_tree_search': 5'599 285 0 0 0 376 5 2'447/4'509
'max_lp': 6'338 169 0 0 0 151 1 3'186/6'302
'objective_lb_search': 4'740 17 0 0 0 2 18 1'940/4'735
'probing': 7'337 443 0 0 0 1'805 102 4'537/8'124
'pseudo_costs': 7'311 180 0 0 0 158 7 4'159/8'575
'quick_restart': 6'596 181 0 0 0 287 96 3'796/7'435
'reduced_costs': 5'916 65 0 0 0 29 11 2'764/5'361
Lp Cut lb_tree_search default_lp max_lp quick_restart reduced_costs probing objective_lb_search pseudo_costs
CG_FF: 5 21 15 17 12 19 9 37
CG_K: 1 15 19 10 5 4 4 15
CG_KL: - 3 - 5 - 2 3 4
CG_R: 17 28 34 16 17 35 5 55
CG_RB: 70 61 49 41 53 82 19 81
CG_RBP: 7 21 25 23 5 50 6 30
IB: 142 1'508 917 1'118 1'114 755 1'152 1'366
MIR_1_FF: 109 125 105 248 88 254 53 172
MIR_1_K: 1 54 20 76 6 64 36 40
MIR_1_KL: 2 36 3 37 - 43 30 12
MIR_1_R: 1 2 3 3 - 2 - 1
MIR_1_RB: 49 72 69 131 49 135 29 95
MIR_1_RBP: 10 52 14 122 16 146 22 40
MIR_2_FF: 151 141 159 193 133 274 68 223
MIR_2_K: 9 55 28 72 12 87 22 42
MIR_2_KL: 2 17 3 20 4 34 8 13
MIR_2_R: 5 14 8 10 5 16 4 15
MIR_2_RB: 141 119 165 164 110 210 53 176
MIR_2_RBP: 39 68 42 98 28 186 32 58
MIR_3_FF: 176 109 162 112 132 160 49 166
MIR_3_K: 26 58 32 72 25 77 26 35
MIR_3_KL: 7 9 3 9 3 11 11 10
MIR_3_R: 9 9 16 4 8 15 1 17
MIR_3_RB: 149 90 155 85 125 138 40 154
MIR_3_RBP: 56 46 44 85 36 111 14 66
MIR_4_FF: 135 49 110 70 87 110 23 131
MIR_4_K: 30 39 34 48 22 42 11 46
MIR_4_KL: 3 - 1 4 4 9 3 8
MIR_4_R: 9 7 6 5 9 11 - 7
MIR_4_RB: 118 65 106 52 98 84 26 116
MIR_4_RBP: 54 29 36 52 30 57 9 49
MIR_5_FF: 109 42 86 48 53 57 4 81
MIR_5_K: 24 25 30 34 13 34 4 38
MIR_5_KL: 4 1 2 5 2 7 1 7
MIR_5_R: 4 6 7 5 6 5 - 8
MIR_5_RB: 94 42 69 34 56 53 12 65
MIR_5_RBP: 38 22 28 40 11 49 - 41
MIR_6_FF: 64 14 49 28 37 40 1 54
MIR_6_K: 15 10 20 26 17 42 7 24
MIR_6_KL: 16 4 10 10 8 15 - 13
MIR_6_R: 2 6 9 1 1 2 - 3
MIR_6_RB: 49 19 49 13 36 33 5 50
MIR_6_RBP: 29 9 29 24 16 41 2 25
ZERO_HALF_FF: 10 29 23 22 8 36 13 24
ZERO_HALF_K: - 8 3 11 - 9 5 14
ZERO_HALF_KL: - 3 1 3 1 5 - 1
ZERO_HALF_R: 376 186 325 404 228 669 89 346
ZERO_HALF_RB: 58 32 57 55 33 149 24 54
ZERO_HALF_RBP: 22 11 6 31 2 68 5 31
LNS stats Improv/Calls Closed Difficulty TimeLimit
'graph_arc_lns': 5/44 45% 2.46e-01 0.10
'graph_cst_lns': 6/41 49% 5.84e-01 0.10
'graph_dec_lns': 2/39 54% 8.36e-01 0.10
'graph_var_lns': 5/42 48% 5.43e-01 0.10
'lb_relax_lns': 3/9 44% 3.80e-01 0.50
'rins/rens': 37/42 52% 6.60e-01 0.10
'rnd_cst_lns': 6/39 56% 8.62e-01 0.10
'rnd_var_lns': 1/37 54% 8.27e-01 0.10
LS stats Batches Restarts/Perturbs LinMoves GenMoves CompoundMoves Bactracks WeightUpdates ScoreComputed
'ls_lin_restart': 6 6 76'206 0 0 0 13'305 2'617'328
'ls_lin_restart_compound': 6 5 0 96'266 7'910 44'170 624 2'586'583
'ls_lin_restart_compound_perturb': 5 5 0 82'025 6'441 37'778 719 2'246'909
'ls_lin_restart_decay': 10 10 153'430 0 0 0 2'623 3'465'559
'ls_lin_restart_decay_compound': 11 10 0 145'012 24'961 59'987 391 4'313'270
'ls_lin_restart_decay_compound_perturb': 2 2 0 25'798 5'359 10'217 62 793'919
'ls_lin_restart_decay_perturb': 4 3 61'142 0 0 0 1'038 1'387'983
'ls_lin_restart_perturb': 6 6 78'736 0 0 0 13'795 2'754'127
'ls_restart': 6 6 77'973 0 0 0 10'539 2'821'313
'ls_restart_compound': 2 2 0 34'092 2'606 15'742 255 981'218
'ls_restart_compound_perturb': 8 7 0 121'288 10'962 55'139 748 3'456'196
'ls_restart_decay': 10 10 154'000 0 0 0 2'664 3'495'179
'ls_restart_decay_compound': 8 8 0 106'454 19'593 43'412 292 3'072'494
'ls_restart_decay_compound_perturb': 6 6 0 82'487 15'745 33'364 204 2'458'820
'ls_restart_decay_perturb': 6 4 92'024 0 0 0 1'441 2'107'052
'ls_restart_perturb': 4 4 52'151 0 0 0 10'184 1'840'218
Solutions (11) Num Rank
'complete_hint': 2 [0,1]
'graph_cst_lns': 2 [1,2]
'graph_dec_lns': 2 [8,9]
'lb_relax_lns_bool_h': 2 [7,8]
'quick_restart_no_lp': 6 [2,11]
'rins_lp_lns': 4 [5,7]
'rnd_cst_lns': 4 [4,10]
Objective bounds Num
'am1_presolve': 1
'initial_domain': 1
'lb_tree_search': 156
'max_lp': 2
'pseudo_costs': 1
'quick_restart': 1
Solution repositories Added Queried Synchro
'alternative_path': 18 63 17
'best_solutions': 80 351 56
'fj solution hints': 0 0 0
'lp solutions': 171 42 143
'pump': 0 0
Clauses shared #Exported #Imported #BinaryRead #BinaryTotal
'core': 168 424 0 0
'default_lp': 5 265 0 0
'lb_tree_search': 0 540 0 0
'max_lp': 2 538 0 0
'no_lp': 359 223 0 0
'objective_lb_search': 0 0 0 0
'probing': 0 0 0 0
'pseudo_costs': 1 539 0 0
'quick_restart': 1 540 0 0
'quick_restart_no_lp': 141 420 0 0
'reduced_costs': 0 11 0 0
LRAT_status: NA
[Scaling] scaled_objective_bound: 229289 corrected_bound: 229289 delta: 2.15409e-06
CpSolverResponse summary:
status: FEASIBLE
objective: 240715.159901454
best_bound: 229289.2848744611
integers: 0
booleans: 0
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 0
restarts: 0
lp_iterations: 0
walltime: 20.0234
usertime: 20.0234
deterministic_time: 114.643
gap_integral: 1073.08
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.031379,
'bound': 229289.28487446107,
'objective': 240715.159901454,
'relgap': 0.04746637075816307,
'termination': 'FEASIBLE'}
[24]:
wfn.length()
[24]:
240742.12313570912
[25]:
wfn
[25]:
