Quickstart¶
[1]:
from optiwindnet.importer import load_repository
from optiwindnet.svg import svgplot
from optiwindnet.interarraylib import G_from_S
from optiwindnet.mesh import make_planar_embedding
from optiwindnet.pathfinding import PathFinder
[2]:
locations = load_repository()
Quickest (sub-second)¶
[3]:
from optiwindnet.heuristics import EW_presolver
[4]:
L = locations.doggerA
[6]:
%%timeit
P, A = make_planar_embedding(L)
17.6 ms ± 669 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)
[7]:
P, A = make_planar_embedding(L)
[8]:
%%timeit
S_pre = EW_presolver(A, capacity=8)
5.38 ms ± 39.9 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
[9]:
S_pre = EW_presolver(A, capacity=8)
[10]:
%%timeit
G_tentative = G_from_S(S_pre, A)
G_pre = PathFinder(G_tentative, planar=P, A=A).create_detours()
32.9 ms ± 829 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)
[11]:
G_tentative = G_from_S(S_pre, A)
G_pre = PathFinder(G_tentative, planar=P, A=A).create_detours()
[12]:
svgplot(G_pre)
[12]:
Quick (radial only, a second or two)¶
[21]:
from optiwindnet.baselines.hgs import hgs_multiroot
from optiwindnet.interarraylib import as_normalized
[22]:
L = locations.doggerA
P, A = make_planar_embedding(L)
S_hgs = hgs_multiroot(as_normalized(A), capacity=8, time_limit=2)
G_tentative = G_from_S(S_hgs, A)
G_hgs = PathFinder(G_tentative, planar=P, A=A).create_detours()
svgplot(G_hgs)
[22]:
With quality assurance (a few minutes)¶
[23]:
from optiwindnet.MILP import solver_factory, ModelOptions
[24]:
solver = solver_factory('ortools')
[25]:
ModelOptions.help()
topology in {"radial", "branched", "branched"} default: branched
Set the topology of subtrees in the solution.
feeder_route in {"straight", "segmented", "segmented"} default: segmented
If feeder routes must be "straight" or can be detoured ("segmented").
feeder_limit in {"unlimited", "specified", "minimum", "min_plus1", "min_plus2", "min_plus3", "unlimited"} default: unlimited
Whether to limit the maximum number of feeders, if set to "specified", additional kwarg "max_feeders" must be given.
balanced [bool] default: False
Whether to enforce balanced subtrees (subtree loads differ at most by one unit).
max_feeders [int] default: 0
Maximum number of feeders (used only if <feeder_limit = "specified">)
[27]:
solver.set_problem(
P, A, S_hgs.graph['capacity'], ModelOptions(
topology='branched',
feeder_route='segmented',
feeder_limit='unlimited'
), warmstart=S_hgs
)
[28]:
# required to get the log inside the notebook (goes only to console otherwise)
solver.solver.log_callback = print
solver.solve(
time_limit=40,
mip_gap=0.005,
verbose=True,
)
Starting CP-SAT solver v9.13.4784
Parameters: max_time_in_seconds: 40 log_search_progress: true relative_gap_limit: 0.005
Setting number of workers to 16
Initial optimization model '': (model_fingerprint: 0xd316c113856ac37a)
#Variables: 1'690 (#bools: 845 in floating point objective) (1'500 primary variables)
- 845 Booleans in [0,1]
- 750 in [0,7]
- 95 in [0,8]
#kAtMostOne: 635 (#literals: 1'926)
#kLinear1: 1'690 (#enforced: 1'690)
#kLinear3: 4
#kLinearN: 284 (#terms: 4'213)
Starting presolve at 0.01s
The solution hint is complete and is feasible.
[Scaling] Floating point objective has 845 terms with magnitude in [1409.66, 22631.9] average = 4594.28
[Scaling] Objective coefficient relative error: 1.60816e-10
[Scaling] Objective worst-case absolute error: 5.3597e-05
[Scaling] Objective scaling factor: 2.09715e+06
6.27e-04s 0.00e+00d [DetectDominanceRelations]
1.23e-02s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
1.29e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::ExtractEncodingFromLinear] #potential_supersets=730
4.26e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateColumns]
4.69e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 6'147 nodes and 11'750 arcs.
[Symmetry] Symmetry computation done. time: 0.0009121 dtime: 0.00111247
6.34e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
1.82e-02s 3.73e-03d [operations_research::sat::CpModelPresolver::Probe] #probed=1'690
1.36e-03s 3.73e-04d [MaxClique] Merged 635(1'926 literals) into 330(1'316 literals) at_most_ones.
6.54e-04s 0.00e+00d [DetectDominanceRelations]
6.41e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
7.86e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::ProcessAtMostOneAndLinear]
4.38e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
4.54e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
1.42e-03s 1.43e-05d [operations_research::sat::CpModelPresolver::DetectDominatedLinearConstraints] #relevant_constraints=193 #num_inclusions=96
1.26e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDifferentVariables]
8.16e-03s 3.72e-04d [operations_research::sat::CpModelPresolver::ProcessSetPPC] #relevant_constraints=427 #num_inclusions=425
1.24e-04s 1.90e-07d [operations_research::sat::CpModelPresolver::FindAlmostIdenticalLinearConstraints] #num_tested_pairs=2
7.10e-04s 2.82e-04d [operations_research::sat::CpModelPresolver::FindBigAtMostOneAndLinearOverlap]
5.96e-04s 3.25e-04d [operations_research::sat::CpModelPresolver::FindBigVerticalLinearOverlap]
1.16e-04s 1.24e-05d [operations_research::sat::CpModelPresolver::FindBigHorizontalLinearOverlap] #linears=179
5.16e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::MergeClauses]
6.44e-04s 0.00e+00d [DetectDominanceRelations]
6.08e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
6.67e-04s 0.00e+00d [DetectDominanceRelations]
5.83e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
2.67e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateColumns]
8.26e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 5'536 nodes and 9'685 arcs.
[Symmetry] Symmetry computation done. time: 0.000726 dtime: 0.00099964
[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] [0.0008596s] clauses:70 literals:140 vars:140 one_side_vars:140 simple_definition:0 singleton_clauses:0
[SAT presolve] [0.0013525s] clauses:70 literals:140 vars:140 one_side_vars:140 simple_definition:0 singleton_clauses:0
4.33e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
1.41e-02s 3.44e-03d [operations_research::sat::CpModelPresolver::Probe] #probed=1'690
6.75e-04s 3.63e-04d [MaxClique]
5.81e-04s 0.00e+00d [DetectDominanceRelations]
5.73e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
5.30e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::ProcessAtMostOneAndLinear]
4.33e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
4.72e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
8.86e-04s 1.07e-05d [operations_research::sat::CpModelPresolver::DetectDominatedLinearConstraints] #relevant_constraints=192 #num_inclusions=95
9.44e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDifferentVariables]
4.02e-04s 6.77e-06d [operations_research::sat::CpModelPresolver::ProcessSetPPC] #relevant_constraints=426
6.82e-05s 3.35e-07d [operations_research::sat::CpModelPresolver::FindAlmostIdenticalLinearConstraints] #num_tested_pairs=3
5.82e-04s 2.80e-04d [operations_research::sat::CpModelPresolver::FindBigAtMostOneAndLinearOverlap]
4.29e-04s 3.25e-04d [operations_research::sat::CpModelPresolver::FindBigVerticalLinearOverlap]
7.22e-05s 1.24e-05d [operations_research::sat::CpModelPresolver::FindBigHorizontalLinearOverlap] #linears=179
3.95e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::MergeClauses]
5.82e-04s 0.00e+00d [DetectDominanceRelations]
5.01e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
9.66e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::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 'at_most_one: transformed into max clique.' was applied 1 time.
- rule 'deductions: 1690 stored' was applied 1 time.
- rule 'exactly_one: simplified objective' was applied 95 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 '': (model_fingerprint: 0x40d2a73777224f0d)
#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'536 nodes and 9'685 arcs.
[Symmetry] Symmetry computation done. time: 0.0006928 dtime: 0.00099806
Preloading model.
#Bound 0.14s best:inf next:[160817.074,2309766.32] initial_domain
#1 0.14s best:242923.237 next:[160817.074,242923.237] complete_hint
#Model 0.15s var:1690/1690 constraints:2307/2307
Starting search at 0.15s 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.20s best:242923.237 next:[162472.38,242923.237] am1_presolve (num_literals=750 num_am1=34 increase=3471428032 work_done=2720)
#Bound 0.22s best:242923.237 next:[188354.862,242923.237] objective_lb_search
#Bound 0.23s best:242923.237 next:[189781.728,242923.237] pseudo_costs
#Bound 0.26s best:242923.237 next:[190315.748,242923.237] pseudo_costs
#Bound 0.29s best:242923.237 next:[223973.897,242923.237] max_lp
#2 0.39s best:242907.625 next:[223973.897,242907.625] quick_restart_no_lp (fixed_bools=0/920)
#3 0.42s best:242906.99 next:[223973.897,242906.99] quick_restart_no_lp (fixed_bools=0/922)
#Bound 0.49s best:242906.99 next:[225381.896,242906.99] max_lp
#Bound 0.72s best:242906.99 next:[226189.509,242906.99] max_lp
#Bound 0.95s best:242906.99 next:[226419.655,242906.99] lb_tree_search
#4 0.97s best:242073.91 next:[226419.655,242073.91] quick_restart_no_lp (fixed_bools=0/939)
#5 1.06s best:242073.275 next:[226419.655,242073.275] rnd_var_lns (d=8.14e-01 s=28 t=0.10 p=1.00 stall=2 h=base) [combined with: quick_restart_no_lp...]
#Bound 1.09s best:242073.275 next:[226640.236,242073.275] max_lp
#Bound 1.19s best:242073.275 next:[226846.723,242073.275] lb_tree_search
#6 1.40s best:241664.967 next:[226846.723,241664.967] quick_restart_no_lp (fixed_bools=0/947)
#7 1.45s best:241477.127 next:[226846.723,241477.127] graph_cst_lns (d=8.14e-01 s=31 t=0.10 p=1.00 stall=2 h=base) [combined with: quick_restart_no_lp...]
#Bound 1.78s best:241477.127 next:[227306.7,241477.127] max_lp
#8 2.07s best:240903 next:[227306.7,240903] lb_relax_lns_int_h (d=5.00e-01 s=35 t=0.50 p=0.00 stall=0 h=base)
#9 2.10s best:240715.16 next:[227306.7,240715.16] lb_relax_lns_int_h (d=5.00e-01 s=35 t=0.50 p=0.00 stall=0 h=base) [combined with: graph_cst_lns (d=8.1...]
#Bound 2.53s best:240715.16 next:[227328.91,240715.16] lb_tree_search
#Bound 2.83s best:240715.16 next:[227759.706,240715.16] max_lp
#Bound 3.28s best:240715.16 next:[227935.516,240715.16] max_lp
#Bound 3.38s best:240715.16 next:[228143.91,240715.16] max_lp
#Bound 3.86s best:240715.16 next:[228306.679,240715.16] max_lp
#Bound 3.97s best:240715.16 next:[228391.166,240715.16] max_lp
#Bound 5.31s best:240715.16 next:[228530.019,240715.16] max_lp
#Bound 8.13s best:240715.16 next:[228569.315,240715.16] max_lp
#Bound 9.62s best:240715.16 next:[228738.424,240715.16] max_lp
#Bound 11.14s best:240715.16 next:[228862.396,240715.16] max_lp
#Bound 12.87s best:240715.16 next:[228940.903,240715.16] max_lp
#Bound 19.89s best:240715.16 next:[228980.792,240715.16] lb_tree_search
#Bound 21.51s best:240715.16 next:[229059.794,240715.16] lb_tree_search
#Bound 23.39s best:240715.16 next:[229124.32,240715.16] lb_tree_search
#Bound 25.51s best:240715.16 next:[229188.68,240715.16] lb_tree_search
#Bound 27.49s best:240715.16 next:[229246.511,240715.16] lb_tree_search
#Bound 29.60s best:240715.16 next:[229314.219,240715.16] lb_tree_search
#Bound 31.63s best:240715.16 next:[229394.47,240715.16] lb_tree_search
#Bound 33.60s best:240715.16 next:[229432.805,240715.16] lb_tree_search
#Bound 35.51s best:240715.16 next:[229480.821,240715.16] lb_tree_search
#Bound 37.49s best:240715.16 next:[229519.37,240715.16] lb_tree_search
#Bound 39.66s best:240715.16 next:[229538.434,240715.16] lb_tree_search
Task timing n [ min, max] avg dev time n [ min, max] avg dev dtime
'core': 1 [ 39.86s, 39.86s] 39.86s 0.00ns 39.86s 1 [ 25.11s, 25.11s] 25.11s 0.00ns 25.11s
'default_lp': 1 [ 39.86s, 39.86s] 39.86s 0.00ns 39.86s 1 [ 10.13s, 10.13s] 10.13s 0.00ns 10.13s
'feasibility_pump': 172 [ 85.00us, 1.25s] 99.40ms 216.28ms 17.10s 34 [131.90ms, 507.85ms] 224.50ms 80.49ms 7.63s
'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': 62 [ 13.59ms, 996.60ms] 293.01ms 256.09ms 18.17s 62 [ 41.64us, 102.08ms] 54.82ms 47.11ms 3.40s
'graph_cst_lns': 46 [ 15.49ms, 2.45s] 372.67ms 412.95ms 17.14s 46 [405.00ns, 100.47ms] 61.02ms 45.27ms 2.81s
'graph_dec_lns': 57 [ 11.10ms, 1.59s] 315.69ms 295.77ms 17.99s 57 [ 10.00ns, 100.38ms] 55.20ms 46.35ms 3.15s
'graph_var_lns': 73 [ 14.16ms, 758.84ms] 265.20ms 197.86ms 19.36s 73 [ 10.00ns, 100.34ms] 57.51ms 45.64ms 4.20s
'lb_relax_lns': 16 [366.00ms, 2.05s] 1.36s 632.01ms 21.73s 16 [ 69.80ms, 588.85ms] 399.33ms 214.80ms 6.39s
'lb_tree_search': 1 [ 39.86s, 39.86s] 39.86s 0.00ns 39.86s 1 [ 4.83s, 4.83s] 4.83s 0.00ns 4.83s
'ls': 83 [176.84ms, 306.49ms] 208.06ms 22.12ms 17.27s 83 [100.00ms, 100.03ms] 100.01ms 6.48us 8.30s
'ls_lin': 81 [180.42ms, 262.31ms] 213.66ms 18.34ms 17.31s 81 [100.01ms, 100.04ms] 100.02ms 6.84us 8.10s
'max_lp': 1 [ 39.86s, 39.86s] 39.86s 0.00ns 39.86s 1 [ 10.01s, 10.01s] 10.01s 0.00ns 10.01s
'no_lp': 1 [ 39.86s, 39.86s] 39.86s 0.00ns 39.86s 1 [ 23.32s, 23.32s] 23.32s 0.00ns 23.32s
'objective_lb_search': 1 [ 39.86s, 39.86s] 39.86s 0.00ns 39.86s 1 [ 14.98s, 14.98s] 14.98s 0.00ns 14.98s
'probing': 1 [ 39.86s, 39.86s] 39.86s 0.00ns 39.86s 1 [ 3.26s, 3.26s] 3.26s 0.00ns 3.26s
'pseudo_costs': 1 [ 39.84s, 39.84s] 39.84s 0.00ns 39.84s 1 [ 8.83s, 8.83s] 8.83s 0.00ns 8.83s
'quick_restart': 1 [ 39.86s, 39.86s] 39.86s 0.00ns 39.86s 1 [ 10.16s, 10.16s] 10.16s 0.00ns 10.16s
'quick_restart_no_lp': 1 [ 39.86s, 39.86s] 39.86s 0.00ns 39.86s 1 [ 18.38s, 18.38s] 18.38s 0.00ns 18.38s
'reduced_costs': 1 [ 39.93s, 39.93s] 39.93s 0.00ns 39.93s 1 [ 11.50s, 11.50s] 11.50s 0.00ns 11.50s
'rins/rens': 70 [ 4.83ms, 509.71ms] 245.82ms 197.39ms 17.21s 55 [ 1.69us, 100.09ms] 69.88ms 42.79ms 3.84s
'rnd_cst_lns': 62 [ 27.40ms, 840.16ms] 299.58ms 196.85ms 18.57s 62 [576.00ns, 100.32ms] 59.22ms 43.72ms 3.67s
'rnd_var_lns': 63 [ 19.84ms, 911.98ms] 274.82ms 215.16ms 17.31s 61 [ 10.00ns, 100.67ms] 53.34ms 45.68ms 3.25s
Search stats Bools Conflicts Branches Restarts BoolPropag IntegerPropag
'core': 879 566'678 1'210'088 30'547 8'858'636 25'288'149
'default_lp': 972 1'412 33'666 15'098 228'109 932'314
'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': 845 0 46'907 25'985 190'933 512'548
'max_lp': 845 306 23'830 12'120 101'153 441'544
'no_lp': 845 298'457 435'599 33'208 19'861'043 67'217'215
'objective_lb_search': 900 971 26'908 13'653 151'595 624'826
'probing': 866 12 2'126 1'775 13'519 46'947
'pseudo_costs': 845 2'622 38'710 17'360 283'499 1'272'207
'quick_restart': 914 179 61'744 30'820 258'349 1'037'540
'quick_restart_no_lp': 1'486 78'624 1'679'169 50'481 11'117'906 35'752'775
'reduced_costs': 845 1'034 58'680 26'016 219'174 1'063'334
SAT stats ClassicMinim LitRemoved LitLearned LitForgotten Subsumed MClauses MDecisions MLitTrue MSubsumed MLitRemoved MReused
'core': 541'737 5'084'263 33'480'362 32'061'689 5'113 14'099 211'294 0 1'637 35'854 3'741
'default_lp': 1'338 76'893 127'783 0 1 1'646 12'436 0 9 60 0
'fs_random': 0 0 0 0 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0 0 0 0 0
'lb_tree_search': 0 0 0 0 0 2'660 21'000 0 0 0 0
'max_lp': 300 12'657 65'728 0 0 1'151 9'121 0 0 0 0
'no_lp': 296'296 3'220'227 24'730'966 23'204'043 725 9'760 60'601 0 114 1'447 6'859
'objective_lb_search': 956 75'330 37'682 0 1 1'402 10'728 0 5 39 26
'probing': 11 445 3'316 0 0 0 0 0 0 0 0
'pseudo_costs': 2'564 119'422 403'781 0 4 1'754 13'761 0 2 19 21
'quick_restart': 147 5'426 18'105 0 2 3'492 26'176 0 6 53 113
'quick_restart_no_lp': 73'092 3'037'081 7'794'413 6'103'085 336 26'668 162'624 0 2'518 23'067 1'773
'reduced_costs': 952 29'254 165'059 0 1 2'660 21'000 0 0 0 0
Lp stats Component Iterations AddedCuts OPTIMAL DUAL_F. DUAL_U.
'default_lp': 1 140'466 4'447 6'441 4 127
'lb_tree_search': 1 15'809 3'837 280 18 0
'max_lp': 1 61'093 4'484 2'191 117 47
'objective_lb_search': 1 154'618 4'292 3'744 1 46
'probing': 1 12'685 5'548 293 0 1
'pseudo_costs': 1 151'302 4'111 7'736 492 176
'quick_restart': 1 70'296 4'516 2'350 6 33
'reduced_costs': 1 114'557 4'714 3'413 348 214
Lp dimension Final dimension of first component
'default_lp': 1215 rows, 1596 columns, 9059 entries
'lb_tree_search': 2628 rows, 1690 columns, 81874 entries
'max_lp': 1599 rows, 1690 columns, 28902 entries
'objective_lb_search': 1349 rows, 1596 columns, 15256 entries
'probing': 2747 rows, 1596 columns, 67456 entries
'pseudo_costs': 1386 rows, 1690 columns, 12830 entries
'quick_restart': 1765 rows, 1596 columns, 24469 entries
'reduced_costs': 1001 rows, 1690 columns, 10228 entries
Lp debug CutPropag CutEqPropag Adjust Overflow Bad BadScaling
'default_lp': 0 7 6'549 0 10'945 0
'lb_tree_search': 0 0 296 0 99'875 0
'max_lp': 0 38 2'354 0 50'628 0
'objective_lb_search': 0 0 3'781 0 21'440 0
'probing': 0 16 283 0 99'038 0
'pseudo_costs': 0 0 8'365 0 11'043 0
'quick_restart': 0 4 2'372 0 40'331 0
'reduced_costs': 0 0 3'929 0 37'968 0
Lp pool Constraints Updates Simplif Merged Shortened Split Strenghtened Cuts/Call
'default_lp': 7'247 83 0 0 0 56 132 4'447/10'743
'lb_tree_search': 6'989 1'131 2 0 0 2'382 88 3'837/6'882
'max_lp': 7'636 530 2 0 0 1'105 78 4'484/8'394
'objective_lb_search': 7'092 156 2 0 0 89 104 4'292/9'126
'probing': 8'348 700 0 0 0 408 107 5'548/11'127
'pseudo_costs': 7'263 119 2 0 0 73 130 4'111/10'718
'quick_restart': 7'316 314 2 0 0 354 92 4'516/9'556
'reduced_costs': 7'866 355 2 0 0 462 108 4'714/9'152
Lp Cut pseudo_costs default_lp max_lp quick_restart lb_tree_search probing objective_lb_search reduced_costs
CG_FF: 39 33 23 18 10 28 28 32
CG_K: 19 18 14 5 7 14 14 8
CG_KL: 5 3 - 4 - 1 4 -
CG_R: 69 52 42 28 27 56 60 35
CG_RB: 103 104 83 75 55 163 109 104
CG_RBP: 43 67 18 35 20 73 53 26
Clique: - - 1 - - - - -
IB: 1'743 1'485 601 1'181 13 720 1'046 1'186
MIR_1_FF: 107 182 250 257 259 423 247 211
MIR_1_K: 26 70 30 70 32 60 60 24
MIR_1_KL: 6 28 10 37 14 44 29 4
MIR_1_R: 4 4 11 2 6 7 5 3
MIR_1_RB: 55 119 102 129 70 163 147 114
MIR_1_RBP: 25 87 44 117 34 155 82 40
MIR_2_FF: 130 218 262 224 236 292 227 258
MIR_2_K: 36 68 44 69 29 85 78 35
MIR_2_KL: 16 19 7 27 10 29 31 9
MIR_2_R: 7 16 27 11 11 18 17 11
MIR_2_RB: 154 166 262 142 199 234 185 238
MIR_2_RBP: 43 104 78 132 69 181 111 76
MIR_3_FF: 158 121 230 144 232 201 157 227
MIR_3_K: 47 69 44 85 32 115 69 51
MIR_3_KL: 13 7 1 10 11 18 15 8
MIR_3_R: 9 6 19 9 15 14 12 15
MIR_3_RB: 167 117 256 126 197 186 114 211
MIR_3_RBP: 43 78 85 121 75 150 92 74
MIR_4_FF: 102 94 165 102 203 147 84 160
MIR_4_K: 23 65 40 58 60 76 56 40
MIR_4_KL: 9 4 2 7 3 11 5 8
MIR_4_R: 15 9 13 8 8 10 7 12
MIR_4_RB: 107 92 167 75 146 103 74 150
MIR_4_RBP: 30 68 80 79 77 94 47 40
MIR_5_FF: 69 52 114 65 119 88 64 105
MIR_5_K: 16 54 31 52 68 70 45 43
MIR_5_KL: 9 3 5 8 7 10 3 12
MIR_5_R: 8 3 9 5 8 7 4 12
MIR_5_RB: 65 51 107 54 111 65 43 110
MIR_5_RBP: 15 45 58 55 59 69 46 27
MIR_6_FF: 44 33 95 66 84 49 31 50
MIR_6_K: 18 33 43 44 45 40 24 25
MIR_6_KL: 14 3 23 8 28 15 7 20
MIR_6_R: 4 1 11 4 9 5 2 4
MIR_6_RB: 52 29 83 26 73 36 31 59
MIR_6_RBP: 20 28 67 47 81 59 32 36
ZERO_HALF_FF: 49 71 16 32 10 28 46 28
ZERO_HALF_K: 11 18 2 11 2 13 12 4
ZERO_HALF_KL: 2 2 - 3 - 4 - -
ZERO_HALF_R: 292 356 642 512 744 902 501 589
ZERO_HALF_RB: 62 72 131 99 155 160 105 138
ZERO_HALF_RBP: 8 20 36 38 74 57 31 42
LNS stats Improv/Calls Closed Difficulty TimeLimit
'graph_arc_lns': 4/62 50% 4.01e-01 0.10
'graph_cst_lns': 2/46 48% 5.40e-01 0.10
'graph_dec_lns': 7/57 49% 7.04e-01 0.10
'graph_var_lns': 9/73 48% 5.11e-01 0.10
'lb_relax_lns': 6/16 38% 1.95e-01 0.50
'rins/rens': 64/70 49% 4.02e-01 0.10
'rnd_cst_lns': 6/62 50% 7.09e-01 0.10
'rnd_var_lns': 5/61 52% 8.06e-01 0.10
LS stats Batches Restarts/Perturbs LinMoves GenMoves CompoundMoves Bactracks WeightUpdates ScoreComputed
'ls_lin_restart': 3 3 38'390 0 0 0 5'912 1'391'272
'ls_lin_restart_compound': 4 3 0 61'428 6'667 27'377 163 1'789'106
'ls_lin_restart_compound_perturb': 15 7 0 236'842 19'723 108'529 853 6'819'607
'ls_lin_restart_decay': 9 5 139'674 0 0 0 2'206 3'209'952
'ls_lin_restart_decay_compound': 20 11 0 266'695 40'672 112'976 316 8'518'503
'ls_lin_restart_decay_compound_perturb': 13 7 0 174'744 28'348 73'173 201 5'400'694
'ls_lin_restart_decay_perturb': 8 6 121'763 0 0 0 2'008 2'765'413
'ls_lin_restart_perturb': 9 7 116'768 0 0 0 18'140 4'394'864
'ls_restart': 8 6 103'444 0 0 0 17'913 3'777'553
'ls_restart_compound': 8 7 0 123'167 11'496 55'817 667 3'504'794
'ls_restart_compound_perturb': 13 7 0 196'909 18'617 89'126 519 5'828'280
'ls_restart_decay': 15 6 230'956 0 0 0 3'604 5'293'279
'ls_restart_decay_compound': 6 2 0 82'350 13'864 34'229 100 2'765'772
'ls_restart_decay_compound_perturb': 4 4 0 55'076 9'887 22'583 141 1'784'858
'ls_restart_decay_perturb': 16 11 245'782 0 0 0 3'994 5'587'235
'ls_restart_perturb': 13 6 163'842 0 0 0 29'695 6'495'230
Solutions (9) Num Rank
'complete_hint': 1 [1,1]
'graph_cst_lns': 1 [7,7]
'lb_relax_lns_int_h': 2 [8,9]
'quick_restart_no_lp': 4 [2,6]
'rnd_var_lns': 1 [5,5]
Objective bounds Num
'am1_presolve': 1
'initial_domain': 1
'lb_tree_search': 14
'max_lp': 15
'objective_lb_search': 1
'pseudo_costs': 2
Solution repositories Added Queried Synchro
'feasible solutions': 107 1'049 78
'fj solution hints': 0 0 0
'lp solutions': 233 35 194
'pump': 668 35
Improving bounds shared Num Sym
'quick_restart': 1 0
Clauses shared Num
'quick_restart': 4
[Scaling] scaled_objective_bound: 229538 corrected_bound: 229538 delta: 1.82015e-07
CpSolverResponse summary:
status: FEASIBLE
objective: 240715.1599014539
best_bound: 229538.4338157741
integers: 0
booleans: 0
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 0
restarts: 0
lp_iterations: 0
walltime: 40.1469
usertime: 40.1469
deterministic_time: 195.263
gap_integral: 1823.33
solution_fingerprint: 0xd3c8e1a5f23ef7f0
[28]:
SolutionInfo(runtime=40.1469286, bound=229538.4338157741, objective=240715.1599014539, relgap=0.04643133440476055, termination='FEASIBLE')
[29]:
S, G = solver.get_solution()
[30]:
svgplot(G)
[30]:
