Mathematical Optimization (MILP)¶
OR-tools example¶
[1]:
from optiwindnet.importer import load_repository
from optiwindnet.svg import svgplot
from optiwindnet.mesh import make_planar_embedding
from optiwindnet.interarraylib import G_from_S, as_normalized
from optiwindnet.heuristics import EW_presolver
from optiwindnet.baselines.hgs import hgs_multiroot
from optiwindnet.MILP import solver_factory, ModelOptions
Initialize Moray East¶
[2]:
locations = load_repository()
[3]:
L = locations.morayeast
svgplot(L)
[3]:
Optimize Moray East¶
[4]:
P, A = make_planar_embedding(L)
Get a heuristic solution¶
[5]:
S_ew = EW_presolver(A, capacity=7)
G_ew = G_from_S(S_ew, A)
svgplot(G_ew)
[5]:
Get a meta-heuristic solution¶
[6]:
S_hgs = hgs_multiroot(as_normalized(A), capacity=7, time_limit=0.5)
print(S_hgs.graph['solution_time'])
G_hgs = G_from_S(S_hgs, A)
svgplot(G_hgs)
(0.18, 0.02, 0.02)
[6]:
Use MILP solver to refine solution¶
[7]:
solver = solver_factory('ortools')
[8]:
solver.set_problem(
P, A, S_ew.graph['capacity'],
ModelOptions(
topology='branched',
feeder_route='segmented',
feeder_limit='unlimited'
), warmstart=S_ew
)
[9]:
# 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.14.6206
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: 0x7dc9778332972bf1)
#Variables: 2'440 (#bools: 1'220 in floating point objective) (2'240 primary variables)
- 1'220 Booleans in [0,1]
- 920 in [0,6]
- 300 in [0,7]
#kAtMostOne: 784 (#literals: 2'340)
#kLinear1: 2'440 (#enforced: 2'440)
#kLinearN: 303 (#terms: 6'100)
Starting presolve at 0.02s
The solution hint is complete and is feasible.
[Scaling] Floating point objective has 1220 terms with magnitude in [1119.02, 18596.1] average = 3976.33
[Scaling] Objective coefficient relative error: 2.09617e-10
[Scaling] Objective worst-case absolute error: 7.84164e-05
[Scaling] Objective scaling factor: 2.09715e+06
1.62e-03s 0.00e+00d [DetectDominanceRelations]
3.15e-02s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
2.51e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::ExtractEncodingFromLinear] #potential_supersets=884
6.59e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateColumns]
7.53e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 8'552 nodes and 16'365 arcs.
[Symmetry] Symmetry computation done. time: 0.0024371 dtime: 0.0015471
9.54e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
2.78e-02s 5.99e-03d [operations_research::sat::CpModelPresolver::Probe] #probed=2'440
1.35e-03s 5.12e-04d [MaxClique] Merged 784(2'340 literals) into 417(1'606 literals) at_most_ones.
1.21e-03s 0.00e+00d [DetectDominanceRelations]
8.26e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
1.07e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::ProcessAtMostOneAndLinear]
7.06e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
5.76e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
8.68e-04s 2.04e-05d [operations_research::sat::CpModelPresolver::DetectDominatedLinearConstraints] #relevant_constraints=203 #num_inclusions=101
7.95e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDifferentVariables]
1.17e-02s 6.48e-04d [operations_research::sat::CpModelPresolver::ProcessSetPPC] #relevant_constraints=519 #num_inclusions=517
1.32e-04s 3.90e-07d [operations_research::sat::CpModelPresolver::FindAlmostIdenticalLinearConstraints] #num_tested_pairs=4
2.42e-03s 1.23e-03d [operations_research::sat::CpModelPresolver::FindBigAtMostOneAndLinearOverlap]
1.10e-03s 1.24e-03d [operations_research::sat::CpModelPresolver::FindBigVerticalLinearOverlap]
5.98e-04s 6.15e-04d [operations_research::sat::CpModelPresolver::FindBigHorizontalLinearOverlap] #linears=200
4.26e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::MergeClauses]
7.89e-04s 0.00e+00d [DetectDominanceRelations]
6.64e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
8.21e-04s 0.00e+00d [DetectDominanceRelations]
1.12e-02s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
3.30e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateColumns]
9.30e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 7'817 nodes and 13'677 arcs.
[Symmetry] Symmetry computation done. time: 0.0013441 dtime: 0.00140954
[SAT presolve] num removable Booleans: 0 / 1220
[SAT presolve] num trivial clauses: 0
[SAT presolve] [0s] clauses:93 literals:186 vars:186 one_side_vars:186 simple_definition:0 singleton_clauses:0
[SAT presolve] [0.0009149s] clauses:93 literals:186 vars:186 one_side_vars:186 simple_definition:0 singleton_clauses:0
[SAT presolve] [0.0012883s] clauses:93 literals:186 vars:186 one_side_vars:186 simple_definition:0 singleton_clauses:0
1.58e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
2.37e-02s 5.55e-03d [operations_research::sat::CpModelPresolver::Probe] #probed=2'440
2.47e-03s 5.00e-04d [MaxClique]
9.81e-04s 0.00e+00d [DetectDominanceRelations]
9.16e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
6.60e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::ProcessAtMostOneAndLinear]
5.54e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
5.49e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
7.23e-04s 1.50e-05d [operations_research::sat::CpModelPresolver::DetectDominatedLinearConstraints] #relevant_constraints=202 #num_inclusions=100
5.21e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDifferentVariables]
5.23e-04s 9.21e-06d [operations_research::sat::CpModelPresolver::ProcessSetPPC] #relevant_constraints=518
7.59e-05s 2.95e-07d [operations_research::sat::CpModelPresolver::FindAlmostIdenticalLinearConstraints] #num_tested_pairs=3
2.11e-03s 1.23e-03d [operations_research::sat::CpModelPresolver::FindBigAtMostOneAndLinearOverlap]
1.05e-03s 1.24e-03d [operations_research::sat::CpModelPresolver::FindBigVerticalLinearOverlap]
8.17e-04s 6.15e-04d [operations_research::sat::CpModelPresolver::FindBigHorizontalLinearOverlap] #linears=200
1.83e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::MergeClauses]
9.90e-04s 0.00e+00d [DetectDominanceRelations]
1.08e-02s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
1.74e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::ExpandObjective] #entries=14'058 #tight_variables=1'220 #tight_constraints=100
Presolve summary:
- 0 affine relations were detected.
- rule 'TODO linear inclusion: superset is equality' was applied 201 times.
- rule 'at_most_one: transformed into max clique.' was applied 1 time.
- rule 'deductions: 2440 stored' was applied 1 time.
- rule 'exactly_one: simplified objective' was applied 100 times.
- rule 'linear: positive equal one' was applied 100 times.
- rule 'objective: shifted cost with exactly ones' was applied 100 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 100 times.
- rule 'setppc: reduced linear coefficients' was applied 99 times.
- rule 'setppc: removed trivial linear constraint' was applied 1 time.
- rule 'variables: detect fully reified value encoding' was applied 1'220 times.
- rule 'variables: detect half reified value encoding' was applied 2'440 times.
Presolved optimization model '': (model_fingerprint: 0x14428ef2f8030c8a)
#Variables: 2'440 (#bools: 1'120 in objective) (2'240 primary variables)
- 1'220 Booleans in [0,1]
- 920 in [0,6]
- 300 in [0,7]
#kAtMostOne: 324 (#literals: 1'420)
#kBoolAnd: 93 (#enforced: 93) (#literals: 186)
#kExactlyOne: 100 (#literals: 1'220)
#kLinear1: 2'440 (#enforced: 2'440)
#kLinearN: 202 (#terms: 3'660)
[Symmetry] Graph for symmetry has 7'817 nodes and 13'677 arcs.
[Symmetry] Symmetry computation done. time: 0.0009349 dtime: 0.00140622
Preloading model.
#Bound 0.24s best:inf next:[115871.04,3301478.29] initial_domain
#1 0.24s best:150853.103 next:[115871.04,150853.103] complete_hint
#Model 0.26s var:2440/2440 constraints:3159/3159
Starting search at 0.26s 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.34s best:150853.103 next:[119116.745,150853.103] am1_presolve (num_literals=1120 num_am1=33 increase=6806735150 work_done=3885)
#Bound 0.38s best:150853.103 next:[124581.312,150853.103] default_lp
#Bound 0.38s best:150853.103 next:[126580.195,150853.103] reduced_costs
#Bound 0.45s best:150853.103 next:[139019.159,150853.103] max_lp
#2 0.54s best:150849.39 next:[139019.159,150849.39] quick_restart_no_lp (fixed_bools=0/1273)
#3 0.60s best:150848.875 next:[139019.159,150848.875] quick_restart_no_lp (fixed_bools=0/1276)
#Bound 0.64s best:150848.875 next:[139718.612,150848.875] max_lp
#Bound 0.66s best:150848.875 next:[139738.713,150848.875] lb_tree_search
#4 0.67s best:150441.034 next:[139738.713,150441.034] graph_arc_lns (d=5.00e-01 s=14 t=0.10 p=0.00 stall=0 h=base)
#5 0.71s best:150436.806 next:[139738.713,150436.806] graph_arc_lns (d=5.00e-01 s=14 t=0.10 p=0.00 stall=0 h=base) [combined with: quick_restart_no_lp...]
#6 0.87s best:150436.238 next:[139738.713,150436.238] quick_restart_no_lp (fixed_bools=0/1282)
#Bound 0.88s best:150436.238 next:[140067.505,150436.238] max_lp
#7 0.96s best:149943.262 next:[140067.505,149943.262] quick_restart_no_lp (fixed_bools=0/1283)
#Bound 1.14s best:149943.262 next:[140209.817,149943.262] max_lp
#Bound 1.15s best:149943.262 next:[140262.393,149943.262] lb_tree_search
#8 1.28s best:149186.01 next:[140262.393,149186.01] graph_dec_lns (d=8.14e-01 s=31 t=0.10 p=1.00 stall=2 h=base)
#Bound 1.42s best:149186.01 next:[140381.593,149186.01] max_lp
#Bound 1.71s best:149186.01 next:[140417.167,149186.01] lb_tree_search
#9 2.09s best:144964.373 next:[140417.167,144964.373] reduced_costs (fixed_bools=0/1224)
#10 2.38s best:143769.429 next:[140417.167,143769.429] graph_arc_lns (d=4.62e-01 s=45 t=0.10 p=0.50 stall=1 h=base)
#Bound 2.46s best:143769.429 next:[140508.753,143769.429] max_lp
#Model 2.60s var:2414/2440 constraints:3133/3159
#11 2.68s best:143410.332 next:[140508.753,143410.332] rnd_var_lns (d=7.21e-01 s=51 t=0.10 p=0.67 stall=3 h=base)
#12 2.94s best:143409.891 next:[140508.753,143409.891] graph_arc_lns (d=6.41e-01 s=50 t=0.10 p=0.67 stall=0 h=base) [combined with: rnd_var_lns (d=7.21e...]
#13 3.11s best:143408.808 next:[140508.753,143408.808] rnd_var_lns (d=8.08e-01 s=54 t=0.10 p=0.75 stall=0 h=base)
#14 3.13s best:143408.367 next:[140508.753,143408.367] rnd_var_lns (d=8.08e-01 s=54 t=0.10 p=0.75 stall=0 h=base) [combined with: graph_arc_lns (d=6.4...]
#Bound 3.19s best:143408.367 next:[140711.485,143408.367] max_lp
#Bound 3.82s best:143408.367 next:[140843.922,143408.367] max_lp
#Model 4.80s var:2396/2440 constraints:3114/3159
#Bound 5.21s best:143408.367 next:[140916.593,143408.367] max_lp
#Model 5.79s var:2394/2440 constraints:3112/3159
#Model 5.84s var:1992/2440 constraints:2704/3159
#Bound 6.23s best:143408.367 next:[140928.7,143408.367] lb_tree_search
#Bound 6.73s best:143408.367 next:[141122.272,143408.367] reduced_costs
#Bound 7.60s best:143408.367 next:[141123.718,143408.367] lb_tree_search
#Bound 8.00s best:143408.367 next:[141217.436,143408.367] reduced_costs
#Bound 8.93s best:143408.367 next:[141287.003,143408.367] reduced_costs
#Bound 10.17s best:143408.367 next:[141371.184,143408.367] reduced_costs
#Bound 11.23s best:143408.367 next:[141492.613,143408.367] reduced_costs
#Model 11.87s var:1948/2440 constraints:2656/3159
#Bound 12.18s best:143408.367 next:[141586.669,143408.367] reduced_costs
#Bound 13.13s best:143408.367 next:[141634.159,143408.367] reduced_costs
#15 13.48s best:143300.547 next:[141634.159,143300.547] graph_var_lns (d=6.18e-01 s=212 t=0.10 p=0.50 stall=18 h=base)
#16 13.50s best:143300.106 next:[141634.159,143300.106] graph_var_lns (d=6.18e-01 s=212 t=0.10 p=0.50 stall=18 h=base) [combined with: rnd_var_lns (d=8.08e...]
#Model 13.57s var:1870/2440 constraints:2570/3159
#Bound 14.33s best:143300.106 next:[141655.593,143300.106] reduced_costs
#Model 14.57s var:1864/2440 constraints:2563/3159
#Bound 15.22s best:143300.106 next:[141705.282,143300.106] reduced_costs
#Bound 16.54s best:143300.106 next:[141727.243,143300.106] reduced_costs
#Model 17.13s var:1852/2440 constraints:2550/3159
#Bound 17.82s best:143300.106 next:[141745.936,143300.106] reduced_costs
#Bound 18.90s best:143300.106 next:[141766.479,143300.106] reduced_costs
#Bound 20.24s best:143300.106 next:[141779.376,143300.106] reduced_costs
#Bound 21.58s best:143300.106 next:[141815.794,143300.106] reduced_costs
#Bound 22.62s best:143300.106 next:[141828.749,143300.106] reduced_costs
#Bound 23.62s best:143300.106 next:[141834.431,143300.106] reduced_costs
#Model 23.69s var:1622/2440 constraints:2300/3159
#Model 26.32s var:1596/2440 constraints:2267/3159
#Bound 27.77s best:143300.106 next:[141834.476,143300.106] reduced_costs
#Bound 28.94s best:143300.106 next:[141864.433,143300.106] reduced_costs
#Bound 30.07s best:143300.106 next:[141872.122,143300.106] reduced_costs
#Bound 31.02s best:143300.106 next:[141877.569,143300.106] reduced_costs
#Bound 31.87s best:143300.106 next:[141882.253,143300.106] reduced_costs
#Bound 32.90s best:143300.106 next:[141886.997,143300.106] reduced_costs
#Model 32.95s var:1546/2440 constraints:2207/3159
#Bound 33.80s best:143300.106 next:[141892.451,143300.106] reduced_costs
#Model 35.54s var:1540/2440 constraints:2201/3159
#Model 37.71s var:1526/2440 constraints:2186/3159
#Model 38.26s var:1524/2440 constraints:2184/3159
Task timing n [ min, max] avg dev time n [ min, max] avg dev dtime
'core': 1 [ 39.74s, 39.74s] 39.74s 0.00ns 39.74s 1 [ 26.91s, 26.91s] 26.91s 0.00ns 26.91s
'default_lp': 1 [ 39.74s, 39.74s] 39.74s 0.00ns 39.74s 1 [ 10.84s, 10.84s] 10.84s 0.00ns 10.84s
'feasibility_pump': 15 [ 24.62ms, 2.41s] 1.11s 639.02ms 16.58s 14 [272.54ms, 1.14s] 509.44ms 269.75ms 7.13s
'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': 56 [ 14.50ms, 1.41s] 300.36ms 245.41ms 16.82s 56 [ 38.50us, 100.43ms] 59.84ms 45.24ms 3.35s
'graph_cst_lns': 54 [ 13.87ms, 732.46ms] 306.76ms 196.90ms 16.56s 54 [395.00ns, 100.35ms] 61.06ms 43.90ms 3.30s
'graph_dec_lns': 56 [ 15.61ms, 984.97ms] 303.81ms 219.30ms 17.01s 56 [ 10.00ns, 100.25ms] 56.37ms 45.78ms 3.16s
'graph_var_lns': 55 [ 14.48ms, 754.79ms] 335.98ms 211.38ms 18.48s 55 [117.00ns, 100.27ms] 64.99ms 43.12ms 3.57s
'lb_relax_lns': 16 [331.04ms, 3.03s] 1.59s 886.48ms 25.36s 16 [ 80.59ms, 617.84ms] 386.82ms 209.35ms 6.19s
'lb_tree_search': 1 [ 39.78s, 39.78s] 39.78s 0.00ns 39.78s 1 [ 2.99s, 2.99s] 2.99s 0.00ns 2.99s
'ls': 85 [ 62.75ms, 295.18ms] 195.61ms 27.70ms 16.63s 85 [ 32.69ms, 100.07ms] 99.23ms 7.26ms 8.43s
'ls_lin': 83 [168.54ms, 405.52ms] 200.42ms 33.99ms 16.63s 83 [100.00ms, 100.05ms] 100.02ms 8.69us 8.30s
'max_lp': 1 [ 39.78s, 39.78s] 39.78s 0.00ns 39.78s 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'no_lp': 1 [ 39.78s, 39.78s] 39.78s 0.00ns 39.78s 1 [ 17.87s, 17.87s] 17.87s 0.00ns 17.87s
'objective_lb_search': 1 [ 39.78s, 39.78s] 39.78s 0.00ns 39.78s 1 [ 5.63s, 5.63s] 5.63s 0.00ns 5.63s
'probing': 1 [ 39.78s, 39.78s] 39.78s 0.00ns 39.78s 1 [ 3.03s, 3.03s] 3.03s 0.00ns 3.03s
'pseudo_costs': 1 [ 39.78s, 39.78s] 39.78s 0.00ns 39.78s 1 [ 5.67s, 5.67s] 5.67s 0.00ns 5.67s
'quick_restart': 1 [ 39.73s, 39.73s] 39.73s 0.00ns 39.73s 1 [ 9.74s, 9.74s] 9.74s 0.00ns 9.74s
'quick_restart_no_lp': 1 [ 39.74s, 39.74s] 39.74s 0.00ns 39.74s 1 [ 16.52s, 16.52s] 16.52s 0.00ns 16.52s
'reduced_costs': 1 [ 39.74s, 39.74s] 39.74s 0.00ns 39.74s 1 [ 8.83s, 8.83s] 8.83s 0.00ns 8.83s
'rins/rens': 53 [ 11.36ms, 840.99ms] 325.41ms 266.75ms 17.25s 39 [146.73us, 100.19ms] 77.55ms 38.56ms 3.02s
'rnd_cst_lns': 55 [ 27.70ms, 912.61ms] 318.62ms 216.29ms 17.52s 55 [605.00ns, 100.24ms] 55.75ms 44.40ms 3.07s
'rnd_var_lns': 54 [ 26.57ms, 1.25s] 365.40ms 291.23ms 19.73s 54 [239.00ns, 100.36ms] 56.13ms 46.11ms 3.03s
Search stats Bools Conflicts Branches Restarts BoolPropag IntegerPropag
'core': 1'253 353'352 881'321 30'736 5'751'345 15'800'080
'default_lp': 1'284 714 11'404 5'579 69'930 449'899
'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': 1'220 0 3'003 2'442 19'743 69'019
'max_lp': 1'220 0 2'440 2'440 18'989 64'691
'no_lp': 1'220 239'490 284'553 7'441 21'036'041 68'498'749
'objective_lb_search': 1'233 52 6'625 4'206 34'801 200'371
'probing': 1'241 12 3'046 2'525 20'739 76'556
'pseudo_costs': 1'220 411 19'841 10'125 113'950 759'262
'quick_restart': 1'220 49 12'827 6'724 52'321 385'973
'quick_restart_no_lp': 1'471 63'279 1'725'373 37'552 7'605'593 39'225'321
'reduced_costs': 1'224 95 10'809 5'057 40'711 289'081
SAT stats ClassicMinim LitRemoved LitLearned LitForgotten Subsumed MClauses MDecisions MLitTrue MSubsumed MLitRemoved MReused
'core': 332'608 4'574'344 47'553'698 43'790'160 3'438 4'925 31'645 0 78 772 101
'default_lp': 690 71'126 109'710 0 1 419 3'122 0 0 0 0
'fs_random': 0 0 0 0 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0 0 0 0 0
'lb_tree_search': 0 0 0 0 0 0 0 0 0 0 0
'max_lp': 0 0 0 0 0 0 0 0 0 0 0
'no_lp': 234'979 3'977'928 31'524'183 28'614'558 1'809 400 4'480 0 0 0 0
'objective_lb_search': 51 6'032 8'147 0 0 200 1'670 0 0 0 0
'probing': 12 552 5'819 0 0 0 0 0 0 0 0
'pseudo_costs': 396 36'516 87'840 0 0 800 7'232 0 0 0 0
'quick_restart': 49 3'127 6'241 0 0 647 4'784 0 0 2 30
'quick_restart_no_lp': 59'774 1'685'236 7'673'484 5'076'941 319 11'091 78'273 0 1'154 10'791 618
'reduced_costs': 88 4'473 12'132 0 0 421 2'838 0 0 0 14
Lp stats Component Iterations AddedCuts OPTIMAL DUAL_F. DUAL_U.
'default_lp': 1 97'306 5'617 2'885 0 18
'lb_tree_search': 1 12'343 3'983 281 2 0
'max_lp': 1 8'441 3'973 58 0 0
'objective_lb_search': 1 26'049 7'209 479 0 0
'probing': 1 14'433 6'158 294 1 0
'pseudo_costs': 1 51'257 5'493 1'391 227 16
'quick_restart': 1 35'830 6'145 524 3 1
'reduced_costs': 1 38'204 6'088 483 181 17
Lp dimension Final dimension of first component
'default_lp': 964 rows, 2343 columns, 9929 entries
'lb_tree_search': 2757 rows, 2440 columns, 58083 entries
'max_lp': 4419 rows, 2440 columns, 62702 entries
'objective_lb_search': 3083 rows, 2343 columns, 65842 entries
'probing': 3126 rows, 2343 columns, 82449 entries
'pseudo_costs': 2510 rows, 2440 columns, 51172 entries
'quick_restart': 2751 rows, 2343 columns, 62041 entries
'reduced_costs': 2824 rows, 2440 columns, 49236 entries
Lp debug CutPropag CutEqPropag Adjust Overflow Bad BadScaling
'default_lp': 0 2 2'886 0 40'453 0
'lb_tree_search': 0 9 283 0 142'407 0
'max_lp': 0 0 58 0 123'802 0
'objective_lb_search': 0 8 459 0 108'130 0
'probing': 0 1 270 0 82'626 0
'pseudo_costs': 0 0 1'592 0 101'779 0
'quick_restart': 0 0 512 0 83'340 0
'reduced_costs': 0 0 647 0 110'491 0
Lp pool Constraints Updates Simplif Merged Shortened Split Strenghtened Cuts/Call
'default_lp': 9'612 674 25'446 0 14'025 186 397 5'617/11'891
'lb_tree_search': 8'360 2'474 48'608 2 16'385 1'203 412 3'983/6'585
'max_lp': 8'352 1'791 18'555 0 10'727 520 325 3'973/6'650
'objective_lb_search': 11'202 1'662 44'601 2 21'968 642 492 7'209/14'153
'probing': 10'152 995 5'879 1 3'488 749 419 6'158/12'171
'pseudo_costs': 9'871 1'391 48'875 1 14'092 616 549 5'493/10'428
'quick_restart': 10'140 1'673 32'342 0 18'032 274 419 6'145/12'716
'reduced_costs': 10'467 1'675 62'535 0 22'993 782 415 6'088/12'451
Lp Cut default_lp quick_restart reduced_costs max_lp pseudo_costs lb_tree_search probing objective_lb_search
CG_FF: 50 45 61 17 25 17 52 48
CG_K: 39 25 24 4 17 6 42 37
CG_KL: 16 7 11 - 6 - 11 10
CG_R: 97 76 97 34 29 27 81 112
CG_RB: 133 150 174 72 87 54 138 165
CG_RBP: 75 61 47 30 26 15 63 106
Clique: - - 1 - 1 - - -
IB: 1'405 1'138 1'088 5 1'332 59 1'050 1'086
MIR_1_FF: 283 462 336 394 305 406 376 587
MIR_1_K: 90 146 59 28 60 53 110 145
MIR_1_KL: 49 45 38 15 19 12 39 67
MIR_1_R: 15 38 17 12 19 34 14 24
MIR_1_RB: 67 92 110 60 81 55 115 125
MIR_1_RBP: 110 133 144 188 179 321 174 169
MIR_2_FF: 295 365 374 316 329 288 344 468
MIR_2_K: 149 126 61 22 46 33 132 144
MIR_2_KL: 42 61 38 19 34 16 49 45
MIR_2_R: 22 17 16 36 27 32 35 20
MIR_2_RB: 160 227 259 178 152 145 240 260
MIR_2_RBP: 121 170 92 135 96 100 152 161
MIR_3_FF: 216 260 341 301 273 263 286 318
MIR_3_K: 104 114 49 49 44 37 142 162
MIR_3_KL: 28 41 26 19 22 16 40 43
MIR_3_R: 21 20 26 31 25 22 33 25
MIR_3_RB: 163 158 214 155 140 138 191 224
MIR_3_RBP: 96 106 64 75 72 79 126 133
MIR_4_FF: 153 177 282 237 237 222 182 241
MIR_4_K: 80 90 45 34 43 44 105 151
MIR_4_KL: 13 15 15 12 13 15 26 29
MIR_4_R: 14 16 17 20 18 25 17 19
MIR_4_RB: 97 112 176 122 121 102 117 166
MIR_4_RBP: 56 72 51 62 70 62 92 139
MIR_5_FF: 125 138 187 133 158 175 132 178
MIR_5_K: 71 96 53 37 42 30 95 100
MIR_5_KL: 31 22 40 27 28 35 31 23
MIR_5_R: 6 9 21 9 11 8 13 12
MIR_5_RB: 55 73 136 73 76 67 75 98
MIR_5_RBP: 75 86 82 69 77 79 98 114
MIR_6_FF: 80 96 103 78 102 101 92 117
MIR_6_K: 85 62 67 42 76 53 75 82
MIR_6_KL: 42 41 54 55 50 59 56 47
MIR_6_R: 12 13 17 7 6 12 6 9
MIR_6_RB: 60 43 86 53 56 60 51 62
MIR_6_RBP: 80 109 136 134 152 110 110 121
ZERO_HALF_FF: 26 39 54 16 35 11 39 31
ZERO_HALF_K: 11 24 10 1 15 2 21 16
ZERO_HALF_KL: 7 10 12 4 4 2 15 12
ZERO_HALF_R: 516 574 547 451 520 374 567 645
ZERO_HALF_RB: 49 95 83 61 87 69 66 64
ZERO_HALF_RBP: 27 50 47 41 50 38 42 49
LNS stats Improv/Calls Closed Difficulty TimeLimit
'graph_arc_lns': 4/56 48% 3.46e-01 0.10
'graph_cst_lns': 3/54 50% 6.18e-01 0.10
'graph_dec_lns': 5/56 52% 8.15e-01 0.10
'graph_var_lns': 6/55 47% 4.75e-01 0.10
'lb_relax_lns': 6/16 50% 4.51e-01 0.50
'rins/rens': 37/53 47% 3.76e-01 0.10
'rnd_cst_lns': 7/55 49% 6.71e-01 0.10
'rnd_var_lns': 7/54 48% 6.56e-01 0.10
LS stats Batches Restarts/Perturbs LinMoves GenMoves CompoundMoves Bactracks WeightUpdates ScoreComputed
'ls_lin_restart': 12 9 125'855 0 0 0 17'965 4'682'428
'ls_lin_restart_compound': 8 6 0 96'726 10'399 43'139 525 2'734'879
'ls_lin_restart_compound_perturb': 9 7 0 103'941 9'196 47'362 624 2'998'954
'ls_lin_restart_decay': 8 6 98'785 0 0 0 1'633 2'317'466
'ls_lin_restart_decay_compound': 9 8 0 96'916 18'819 39'032 225 2'829'170
'ls_lin_restart_decay_compound_perturb': 13 10 0 138'811 25'292 56'720 348 4'441'985
'ls_lin_restart_decay_perturb': 14 7 172'372 0 0 0 2'830 3'940'456
'ls_lin_restart_perturb': 10 9 106'780 0 0 0 18'941 3'869'387
'ls_restart': 7 4 78'280 0 0 0 12'751 2'843'521
'ls_restart_compound': 16 12 0 180'828 17'989 81'395 973 4'901'678
'ls_restart_compound_perturb': 12 11 0 142'506 12'858 64'805 922 4'011'765
'ls_restart_decay': 16 13 193'339 0 0 0 3'131 4'664'670
'ls_restart_decay_compound': 10 5 0 103'807 21'177 41'289 207 3'131'052
'ls_restart_decay_compound_perturb': 6 6 0 56'940 9'960 23'480 202 2'072'594
'ls_restart_decay_perturb': 8 4 100'113 0 0 0 1'576 2'312'722
'ls_restart_perturb': 10 9 102'945 0 0 0 14'892 3'925'385
Solutions (16) Num Rank
'complete_hint': 1 [1,1]
'graph_arc_lns': 4 [4,12]
'graph_dec_lns': 1 [8,8]
'graph_var_lns': 2 [15,16]
'quick_restart_no_lp': 4 [2,7]
'reduced_costs': 1 [9,9]
'rnd_var_lns': 3 [11,14]
Objective bounds Num
'am1_presolve': 1
'default_lp': 1
'initial_domain': 1
'lb_tree_search': 5
'max_lp': 9
'reduced_costs': 24
Solution repositories Added Queried Synchro
'feasible solutions': 131 962 84
'fj solution hints': 0 0 0
'lp solutions': 49 25 37
'pump': 181 28
Improving bounds shared Num Sym
'default_lp': 12 0
'lb_tree_search': 40 0
'max_lp': 20 0
'objective_lb_search': 552 0
'probing': 2 0
'pseudo_costs': 6 0
'quick_restart': 24 0
'quick_restart_no_lp': 20 0
'reduced_costs': 281 0
Clauses shared Num
'core': 2
'no_lp': 3
'pseudo_costs': 40
'quick_restart_no_lp': 23
'reduced_costs': 1
[Scaling] scaled_objective_bound: 141892 corrected_bound: 141892 delta: 1.77117e-06
CpSolverResponse summary:
status: FEASIBLE
objective: 143300.1064689605
best_bound: 141892.4508663586
integers: 0
booleans: 0
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 0
restarts: 0
lp_iterations: 0
walltime: 40.2425
usertime: 40.2425
deterministic_time: 160.607
gap_integral: 1177.65
solution_fingerprint: 0x667eaa3ffcd9c64f
[9]:
SolutionInfo(runtime=40.2424905, bound=141892.45086635856, objective=143300.10646896047, relgap=0.009823130193603924, termination='FEASIBLE')
[10]:
S, G = solver.get_solution()
[11]:
svgplot(G)
[11]:
Balanced subtrees¶
[12]:
solver.set_problem(
P, A, S_ew.graph['capacity'],
ModelOptions(
topology='branched',
feeder_route='segmented',
feeder_limit='minimum',
balanced=True,
), warmstart=S_ew
)
[13]:
# 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.14.6206
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: 0x5be922034da5af60)
#Variables: 2'440 (#bools: 1'220 in floating point objective) (2'240 primary variables)
- 1'220 Booleans in [0,1]
- 920 in [0,6]
- 300 in [0,7]
#kAtMostOne: 784 (#literals: 2'340)
#kLinear1: 2'440 (#enforced: 2'440)
#kLinear2: 300
#kLinearN: 303 (#terms: 6'100)
Starting presolve at 0.01s
The solution hint is complete, but it is infeasible! we will try to repair it.
[Scaling] Floating point objective has 1220 terms with magnitude in [1119.02, 18596.1] average = 3976.33
[Scaling] Objective coefficient relative error: 2.09617e-10
[Scaling] Objective worst-case absolute error: 7.84164e-05
[Scaling] Objective scaling factor: 2.09715e+06
1.18e-03s 0.00e+00d [DetectDominanceRelations]
1.82e-02s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
4.69e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::ExtractEncodingFromLinear] #potential_supersets=884
1.16e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateColumns]
9.49e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints] #duplicates=300
[Symmetry] Graph for symmetry has 8'552 nodes and 16'365 arcs.
[Symmetry] Symmetry computation done. time: 0.0020795 dtime: 0.0015471
7.87e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
2.91e-02s 9.76e-03d [operations_research::sat::CpModelPresolver::Probe] #probed=3'640 #new_bounds=300
1.41e-03s 5.85e-04d [MaxClique] Merged 784(2'340 literals) into 417(1'606 literals) at_most_ones.
9.07e-04s 0.00e+00d [DetectDominanceRelations]
1.10e-02s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
1.22e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::ProcessAtMostOneAndLinear]
8.33e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
6.08e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
8.64e-04s 1.92e-05d [operations_research::sat::CpModelPresolver::DetectDominatedLinearConstraints] #relevant_constraints=203 #num_inclusions=101 #num_redundant=1
8.57e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDifferentVariables]
3.80e-04s 3.99e-04d [operations_research::sat::CpModelPresolver::ProcessSetPPC] #relevant_constraints=519 #num_inclusions=417
1.28e-04s 3.90e-07d [operations_research::sat::CpModelPresolver::FindAlmostIdenticalLinearConstraints] #num_tested_pairs=4
1.24e-02s 9.71e-03d [operations_research::sat::CpModelPresolver::FindBigAtMostOneAndLinearOverlap]
3.23e-03s 5.48e-03d [operations_research::sat::CpModelPresolver::FindBigVerticalLinearOverlap]
1.43e-03s 1.54e-03d [operations_research::sat::CpModelPresolver::FindBigHorizontalLinearOverlap] #linears=201
9.05e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::MergeClauses]
9.65e-04s 0.00e+00d [DetectDominanceRelations]
7.81e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
6.12e-04s 0.00e+00d [DetectDominanceRelations]
8.38e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
9.17e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateColumns]
7.37e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 7'818 nodes and 14'597 arcs.
[Symmetry] Symmetry computation done. time: 0.0015178 dtime: 0.001433
[SAT presolve] num removable Booleans: 0 / 1220
[SAT presolve] num trivial clauses: 0
[SAT presolve] [0s] clauses:93 literals:186 vars:186 one_side_vars:186 simple_definition:0 singleton_clauses:0
[SAT presolve] [0.0007453s] clauses:93 literals:186 vars:186 one_side_vars:186 simple_definition:0 singleton_clauses:0
[SAT presolve] [0.0010294s] clauses:93 literals:186 vars:186 one_side_vars:186 simple_definition:0 singleton_clauses:0
6.12e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
2.30e-02s 5.90e-03d [operations_research::sat::CpModelPresolver::Probe] #probed=2'440
2.05e-03s 5.00e-04d [MaxClique]
6.55e-04s 0.00e+00d [DetectDominanceRelations]
6.58e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
1.07e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::ProcessAtMostOneAndLinear]
6.11e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
5.36e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
7.01e-04s 1.77e-05d [operations_research::sat::CpModelPresolver::DetectDominatedLinearConstraints] #relevant_constraints=203 #num_inclusions=100
8.69e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDifferentVariables]
3.56e-04s 3.99e-04d [operations_research::sat::CpModelPresolver::ProcessSetPPC] #relevant_constraints=519 #num_inclusions=417
1.24e-04s 3.65e-07d [operations_research::sat::CpModelPresolver::FindAlmostIdenticalLinearConstraints] #num_tested_pairs=3
1.36e-02s 9.71e-03d [operations_research::sat::CpModelPresolver::FindBigAtMostOneAndLinearOverlap]
4.88e-03s 5.48e-03d [operations_research::sat::CpModelPresolver::FindBigVerticalLinearOverlap]
2.00e-03s 1.54e-03d [operations_research::sat::CpModelPresolver::FindBigHorizontalLinearOverlap] #linears=201
8.78e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::MergeClauses]
8.87e-04s 0.00e+00d [DetectDominanceRelations]
9.30e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
2.22e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::ExpandObjective] #entries=14'058 #tight_variables=1'220 #tight_constraints=100
Presolve summary:
- 0 affine relations were detected.
- rule 'TODO linear inclusion: superset is equality' was applied 200 times.
- rule 'at_most_one: transformed into max clique.' was applied 1 time.
- rule 'deductions: 2440 stored' was applied 1 time.
- rule 'duplicate: merged rhs of linear constraint' was applied 300 times.
- rule 'duplicate: removed constraint' was applied 300 times.
- rule 'exactly_one: simplified objective' was applied 100 times.
- rule 'linear inclusion: sparsify superset' was applied 1 time.
- rule 'linear2: contains a Boolean.' was applied 300 times.
- rule 'linear: positive equal one' was applied 100 times.
- rule 'objective: shifted cost with exactly ones' was applied 100 times.
- rule 'presolve: 0 unused variables removed.' was applied 1 time.
- rule 'presolve: iteration' was applied 2 times.
- rule 'variables: detect fully reified value encoding' was applied 1'220 times.
- rule 'variables: detect half reified value encoding' was applied 2'440 times.
Presolved optimization model '': (model_fingerprint: 0x940e0b1662fe51b9)
#Variables: 2'440 (#bools: 1'120 in objective) (2'239 primary variables)
- 1'220 Booleans in [0,1]
- 300 in [0][6,7]
- 920 in [0,6]
#kAtMostOne: 324 (#literals: 1'420)
#kBoolAnd: 93 (#enforced: 93) (#literals: 186)
#kExactlyOne: 100 (#literals: 1'220)
#kLinear1: 2'440 (#enforced: 2'440)
#kLinearN: 203 (#terms: 4'580)
[Symmetry] Graph for symmetry has 7'818 nodes and 14'597 arcs.
[Symmetry] Symmetry computation done. time: 0.0010778 dtime: 0.00142949
Preloading model.
#Bound 0.23s best:inf next:[115871.04,3301478.29] initial_domain
The solution hint is complete, but it is infeasible! we will try to repair it.
#Model 0.23s var:2440/2440 constraints:3160/3160
Starting search at 0.24s with 16 workers.
11 full problem subsolvers: [core, default_lp, lb_tree_search, max_lp, no_lp, objective_lb_search, probing, pseudo_costs, quick_restart, quick_restart_no_lp, reduced_costs]
5 first solution subsolvers: [fj(2), fs_random, fs_random_no_lp, fs_random_quick_restart_no_lp]
11 interleaved subsolvers: [feasibility_pump, graph_arc_lns, graph_cst_lns, graph_dec_lns, graph_var_lns, lb_relax_lns, ls, ls_lin, rins/rens, rnd_cst_lns, rnd_var_lns]
3 helper subsolvers: [neighborhood_helper, synchronization_agent, update_gap_integral]
#1 0.29s best:152649.356 next:[115871.04,152649.356] fj_restart_decay_compound_perturb_obj(batch:1 lin{mvs:0 evals:10'796} gen{mvs:494 evals:0} comp{mvs:40 btracks:227} #w_updates:2 #perturb:0)
#Bound 0.31s best:152649.356 next:[119116.745,152649.356] am1_presolve (num_literals=1120 num_am1=33 increase=6806735150 work_done=3885)
#Bound 0.35s best:152649.356 next:[124581.315,152649.356] objective_lb_search
#Bound 0.36s best:152649.356 next:[126580.195,152649.356] reduced_costs
#Bound 0.44s best:152649.356 next:[126582.05,152649.356] pseudo_costs
#Bound 0.44s best:152649.356 next:[128403.402,152649.356] reduced_costs
#Bound 0.47s best:152649.356 next:[139054.342,152649.356] lb_tree_search
#2 0.49s best:152648.841 next:[139054.342,152648.841] quick_restart_no_lp (fixed_bools=0/1220)
#Bound 0.66s best:152648.841 next:[139813.704,152648.841] lb_tree_search
#3 0.68s best:152648.788 next:[139813.704,152648.788] rnd_var_lns (d=7.07e-01 s=26 t=0.10 p=1.00 stall=1 h=base) (fixed_bools=0/1220)
#4 0.75s best:152648.273 next:[139813.704,152648.273] quick_restart_no_lp (fixed_bools=0/1220)
#5 0.90s best:152647.832 next:[139813.704,152647.832] quick_restart_no_lp (fixed_bools=0/1220)
#Bound 1.01s best:152647.832 next:[140262.391,152647.832] lb_tree_search
#6 1.09s best:151538.14 next:[140262.391,151538.14] graph_arc_lns (d=7.07e-01 s=29 t=0.10 p=1.00 stall=1 h=base) (fixed_bools=0/1220)
#Bound 1.30s best:151538.14 next:[140674.316,151538.14] lb_tree_search
#7 1.37s best:151158.481 next:[140674.316,151158.481] quick_restart_no_lp (fixed_bools=0/1220)
#8 1.47s best:151158.04 next:[140674.316,151158.04] quick_restart_no_lp (fixed_bools=0/1220)
#Bound 1.60s best:151158.04 next:[140805.213,151158.04] max_lp
#Bound 1.67s best:151158.04 next:[140877.333,151158.04] lb_tree_search
#Bound 2.25s best:151158.04 next:[141095.671,151158.04] max_lp
#9 2.55s best:150148.586 next:[141095.671,150148.586] lb_relax_lns_int (d=5.00e-01 s=23 t=0.50 p=0.00 stall=0 h=base) (fixed_bools=0/1220)
#10 2.97s best:150148.146 next:[141095.671,150148.146] quick_restart_no_lp (fixed_bools=0/1220)
#11 3.15s best:149860.312 next:[141095.671,149860.312] graph_arc_lns (d=6.92e-01 s=54 t=0.10 p=0.67 stall=1 h=base) (fixed_bools=0/1220)
#12 3.17s best:149859.871 next:[141095.671,149859.871] graph_arc_lns (d=6.92e-01 s=54 t=0.10 p=0.67 stall=1 h=base) [combined with: quick_restart_no_lp...] (fixed_bools=0/1220)
#13 3.20s best:149789.688 next:[141095.671,149789.688] graph_var_lns (d=7.21e-01 s=55 t=0.10 p=0.67 stall=0 h=base) (fixed_bools=0/1220)
#14 3.23s best:149501.413 next:[141095.671,149501.413] graph_var_lns (d=7.21e-01 s=55 t=0.10 p=0.67 stall=0 h=base) [combined with: graph_arc_lns (d=6.9...] (fixed_bools=0/1220)
#15 3.24s best:149439.539 next:[141095.671,149439.539] graph_cst_lns (d=6.92e-01 s=53 t=0.10 p=0.67 stall=1 h=base) (fixed_bools=0/1220)
#Bound 3.27s best:149439.539 next:[141251.92,149439.539] max_lp
#16 3.30s best:149362.735 next:[141251.92,149362.735] ls_lin_restart_decay_compound_perturb(batch:1 lin{mvs:0 evals:23'120} gen{mvs:736 evals:0} comp{mvs:20 btracks:358} #w_updates:4 #perturb:0) (fixed_bools=0/1220)
#Model 3.32s var:2416/2440 constraints:3136/3160
#17 3.46s best:148588.105 next:[141251.92,148588.105] quick_restart_no_lp (fixed_bools=12/1220)
#18 4.20s best:148588.104 next:[141251.92,148588.104] rnd_cst_lns (d=8.08e-01 s=63 t=0.10 p=0.75 stall=2 h=base) (fixed_bools=0/1220)
#19 4.30s best:147699.634 next:[141251.92,147699.634] graph_arc_lns (d=5.54e-01 s=69 t=0.10 p=0.50 stall=0 h=base) (fixed_bools=0/1220)
#Bound 4.90s best:147699.634 next:[141442.275,147699.634] max_lp
#20 5.32s best:147327.71 next:[141442.275,147327.71] graph_arc_lns (d=5.64e-01 s=86 t=0.10 p=0.50 stall=1 h=base) (fixed_bools=0/1220)
#Bound 5.37s best:147327.71 next:[141464.901,147327.71] lb_tree_search
#Bound 5.74s best:147327.71 next:[141560.698,147327.71] max_lp
#21 6.24s best:147219.449 next:[141560.698,147219.449] graph_arc_lns (d=5.55e-01 s=103 t=0.10 p=0.50 stall=1 h=base) (fixed_bools=0/1220)
#Bound 7.43s best:147219.449 next:[141745.93,147219.449] max_lp
#Bound 7.83s best:147219.449 next:[141802.772,147219.449] lb_tree_search
#Model 7.90s var:2146/2440 constraints:2862/3160
#Bound 9.23s best:147219.449 next:[141940.856,147219.449] lb_tree_search
#Model 9.35s var:2138/2440 constraints:2854/3160
#Bound 10.46s best:147219.449 next:[141970.823,147219.449] lb_tree_search
#Model 10.51s var:2136/2440 constraints:2852/3160
#22 11.28s best:146217.47 next:[141970.823,146217.47] lb_relax_lns_int (d=1.86e-01 s=179 t=0.50 p=0.00 stall=0 h=base) (fixed_bools=0/1220)
#Bound 11.62s best:146217.47 next:[142023.293,146217.47] lb_tree_search
#Model 11.66s var:2134/2440 constraints:2850/3160
#Bound 13.10s best:146217.47 next:[142093.051,146217.47] lb_tree_search
#Model 13.12s var:2082/2440 constraints:2798/3160
#23 14.58s best:146200.672 next:[142093.051,146200.672] lb_relax_lns_bool_h (d=4.03e-01 s=235 t=0.50 p=0.50 stall=1 h=base) (fixed_bools=0/1220)
#Bound 14.79s best:146200.672 next:[142204.048,146200.672] lb_tree_search
#Model 14.84s var:2072/2440 constraints:2788/3160
#24 15.40s best:146106.061 next:[142204.048,146106.061] ls_restart(batch:1 lin{mvs:4'891 evals:134'335} #w_updates:1'797 #perturb:0) (fixed_bools=0/1220)
#25 15.50s best:145747.366 next:[142204.048,145747.366] quick_restart_no_lp (fixed_bools=184/1327)
#26 15.56s best:145745.516 next:[142204.048,145745.516] quick_restart_no_lp (fixed_bools=184/1327)
#27 15.59s best:145743.66 next:[142204.048,145743.66] quick_restart_no_lp (fixed_bools=184/1327)
#28 15.64s best:145366.41 next:[142204.048,145366.41] quick_restart_no_lp (fixed_bools=184/1327)
#29 15.70s best:145012.646 next:[142204.048,145012.646] quick_restart_no_lp (fixed_bools=184/1327)
#30 16.01s best:145012.205 next:[142204.048,145012.205] quick_restart_no_lp (fixed_bools=184/1328)
#31 16.33s best:144992.38 next:[142204.048,144992.38] quick_restart_no_lp (fixed_bools=184/1331)
#Bound 16.69s best:144992.38 next:[142236.424,144992.38] lb_tree_search
#Bound 16.72s best:144992.38 next:[142236.467,144992.38] lb_tree_search
#Model 16.80s var:1918/2440 constraints:2625/3160
#32 18.08s best:144828.315 next:[142236.467,144828.315] graph_cst_lns (d=8.35e-01 s=282 t=0.10 p=0.58 stall=20 h=base) (fixed_bools=0/1220)
#Bound 18.65s best:144828.315 next:[142274.472,144828.315] lb_tree_search
#Model 18.70s var:1916/2440 constraints:2623/3160
#33 19.38s best:144078.784 next:[142274.472,144078.784] rins_pump_lns (d=5.93e-01 s=307 t=0.10 p=0.52 stall=0 h=base) (fixed_bools=0/1220)
#34 20.25s best:144078.352 next:[142274.472,144078.352] lb_relax_lns_int (d=4.12e-01 s=310 t=0.50 p=0.50 stall=1 h=base) (fixed_bools=0/1220)
#Bound 20.30s best:144078.352 next:[142298.959,144078.352] lb_tree_search
#Model 20.33s var:1874/2440 constraints:2575/3160
#Bound 21.34s best:144078.352 next:[142332.828,144078.352] reduced_costs
#Bound 21.99s best:144078.352 next:[142353.226,144078.352] lb_tree_search
#Model 22.01s var:1658/2440 constraints:2337/3160
#Bound 22.48s best:144078.352 next:[142391.291,144078.352] max_lp
#Bound 22.81s best:144078.352 next:[142416.601,144078.352] reduced_costs
#Bound 22.99s best:144078.352 next:[142426.423,144078.352] reduced_costs
#Bound 23.58s best:144078.352 next:[142437.367,144078.352] lb_tree_search
#Model 23.64s var:1632/2440 constraints:2311/3160
#Bound 24.32s best:144078.352 next:[142455.025,144078.352] max_lp
#Bound 25.25s best:144078.352 next:[142482.878,144078.352] lb_tree_search
#Model 25.30s var:1614/2440 constraints:2293/3160
#Bound 26.94s best:144078.352 next:[142559.116,144078.352] lb_tree_search
#Bound 26.96s best:144078.352 next:[142559.174,144078.352] lb_tree_search
#Model 26.98s var:1574/2440 constraints:2248/3160
#Bound 28.74s best:144078.352 next:[142608.04,144078.352] lb_tree_search
#Model 28.80s var:1556/2440 constraints:2226/3160
#Bound 30.34s best:144078.352 next:[142611.136,144078.352] lb_tree_search
#Model 30.35s var:1552/2440 constraints:2222/3160
#35 30.50s best:143698.733 next:[142611.136,143698.733] lb_relax_lns_int_h (d=6.64e-01 s=460 t=0.50 p=0.60 stall=3 h=base) (fixed_bools=0/1220)
#Bound 31.91s best:143698.733 next:[142619.962,143698.733] lb_tree_search
#Model 31.97s var:1546/2440 constraints:2215/3160
#Model 32.06s var:1512/2440 constraints:2174/3160
#Bound 33.39s best:143698.733 next:[142636.583,143698.733] objective_lb_search
#Model 33.46s var:1358/2440 constraints:2003/3160
#Bound 34.73s best:143698.733 next:[142638.545,143698.733] max_lp
#Model 34.83s var:1346/2440 constraints:1987/3160
#Bound 35.10s best:143698.733 next:[142653.569,143698.733] objective_lb_search
#Bound 35.12s best:143698.733 next:[142653.613,143698.733] objective_lb_search
#Bound 36.52s best:143698.733 next:[142666.24,143698.733] objective_lb_search
#Bound 36.59s best:143698.733 next:[142674.105,143698.733] lb_tree_search
#Model 36.60s var:1328/2440 constraints:1966/3160
#Bound 38.03s best:143698.733 next:[142688.513,143698.733] lb_tree_search
#Model 38.09s var:1309/2440 constraints:1939/3160
#Bound 38.13s best:143698.733 next:[142701.801,143698.733] objective_lb_search
#Bound 39.53s best:143698.733 next:[142710.981,143698.733] objective_lb_search
#Model 39.55s var:1303/2440 constraints:1933/3160
Task timing n [ min, max] avg dev time n [ min, max] avg dev dtime
'core': 1 [ 39.79s, 39.79s] 39.79s 0.00ns 39.79s 1 [ 27.30s, 27.30s] 27.30s 0.00ns 27.30s
'default_lp': 1 [ 39.79s, 39.79s] 39.79s 0.00ns 39.79s 1 [ 5.60s, 5.60s] 5.60s 0.00ns 5.60s
'feasibility_pump': 11 [ 29.71ms, 3.73s] 1.70s 1.07s 18.65s 10 [428.27ms, 2.12s] 1.00s 538.75ms 10.00s
'fj': 1 [ 34.84ms, 34.84ms] 34.84ms 0.00ns 34.84ms 1 [ 8.57ms, 8.57ms] 8.57ms 0.00ns 8.57ms
'fj': 1 [159.52ms, 159.52ms] 159.52ms 0.00ns 159.52ms 1 [100.05ms, 100.05ms] 100.05ms 0.00ns 100.05ms
'fs_random': 1 [ 65.89ms, 65.89ms] 65.89ms 0.00ns 65.89ms 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'fs_random_no_lp': 1 [ 69.09ms, 69.09ms] 69.09ms 0.00ns 69.09ms 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'fs_random_quick_restart_no_lp': 1 [ 65.58ms, 65.58ms] 65.58ms 0.00ns 65.58ms 0 [ 0.00ns, 0.00ns] 0.00ns 0.00ns 0.00ns
'graph_arc_lns': 58 [ 25.16ms, 1.39s] 303.49ms 297.62ms 17.60s 58 [ 4.46us, 100.42ms] 51.63ms 47.02ms 2.99s
'graph_cst_lns': 58 [ 16.46ms, 629.20ms] 309.82ms 203.37ms 17.97s 58 [ 10.00ns, 100.30ms] 57.09ms 45.65ms 3.31s
'graph_dec_lns': 56 [ 15.81ms, 878.00ms] 310.62ms 221.26ms 17.39s 56 [ 10.00ns, 100.40ms] 54.91ms 46.42ms 3.08s
'graph_var_lns': 48 [ 15.50ms, 1.20s] 364.44ms 245.70ms 17.49s 48 [ 10.00ns, 100.15ms] 57.42ms 44.05ms 2.76s
'lb_relax_lns': 15 [394.03ms, 2.33s] 1.28s 792.95ms 19.25s 15 [ 82.57ms, 615.41ms] 341.70ms 227.07ms 5.13s
'lb_tree_search': 1 [ 39.78s, 39.78s] 39.78s 0.00ns 39.78s 1 [ 1.93s, 1.93s] 1.93s 0.00ns 1.93s
'ls': 100 [130.40ms, 288.74ms] 175.11ms 31.49ms 17.51s 100 [ 63.39ms, 100.08ms] 99.41ms 4.37ms 9.94s
'ls_lin': 101 [ 56.40ms, 266.16ms] 172.27ms 29.58ms 17.40s 101 [ 29.34ms, 100.10ms] 98.85ms 8.43ms 9.98s
'max_lp': 1 [ 39.78s, 39.78s] 39.78s 0.00ns 39.78s 1 [816.50ms, 816.50ms] 816.50ms 0.00ns 816.50ms
'no_lp': 1 [ 39.76s, 39.76s] 39.76s 0.00ns 39.76s 1 [ 16.14s, 16.14s] 16.14s 0.00ns 16.14s
'objective_lb_search': 1 [ 39.79s, 39.79s] 39.79s 0.00ns 39.79s 1 [ 5.13s, 5.13s] 5.13s 0.00ns 5.13s
'probing': 1 [ 39.78s, 39.78s] 39.78s 0.00ns 39.78s 1 [ 2.92s, 2.92s] 2.92s 0.00ns 2.92s
'pseudo_costs': 1 [ 39.79s, 39.79s] 39.79s 0.00ns 39.79s 1 [ 3.64s, 3.64s] 3.64s 0.00ns 3.64s
'quick_restart': 1 [ 39.78s, 39.78s] 39.78s 0.00ns 39.78s 1 [ 4.48s, 4.48s] 4.48s 0.00ns 4.48s
'quick_restart_no_lp': 1 [ 39.76s, 39.76s] 39.76s 0.00ns 39.76s 1 [ 14.14s, 14.14s] 14.14s 0.00ns 14.14s
'reduced_costs': 1 [ 39.78s, 39.78s] 39.78s 0.00ns 39.78s 1 [ 3.35s, 3.35s] 3.35s 0.00ns 3.35s
'rins/rens': 70 [652.80us, 596.40ms] 265.44ms 204.07ms 18.58s 58 [ 1.27us, 100.18ms] 62.93ms 41.90ms 3.65s
'rnd_cst_lns': 58 [ 25.21ms, 676.82ms] 304.66ms 217.37ms 17.67s 56 [168.00ns, 100.24ms] 55.28ms 46.28ms 3.10s
'rnd_var_lns': 59 [ 19.56ms, 1.14s] 317.85ms 252.54ms 18.75s 59 [ 10.00ns, 100.46ms] 53.21ms 47.26ms 3.14s
Search stats Bools Conflicts Branches Restarts BoolPropag IntegerPropag
'core': 1'253 489'773 1'093'766 24'846 8'079'853 22'270'716
'default_lp': 1'220 121 12'130 6'687 60'600 391'600
'fs_random': 1'220 0 1'064 1'064 8'864 29'279
'fs_random_no_lp': 1'220 0 1'432 1'432 11'908 39'314
'fs_random_quick_restart_no_lp': 1'220 0 1'318 1'318 10'899 36'006
'lb_tree_search': 1'220 10 82'673 40'496 287'056 763'021
'max_lp': 1'220 14 2'558 2'441 19'598 69'105
'no_lp': 1'220 209'447 407'871 14'305 16'335'403 62'689'141
'objective_lb_search': 1'223 53 5'994 3'670 30'760 178'856
'probing': 1'221 11 3'002 2'445 19'671 72'505
'pseudo_costs': 1'220 106 12'769 6'817 58'927 389'456
'quick_restart': 1'220 20 3'018 2'442 21'844 81'358
'quick_restart_no_lp': 1'363 63'459 1'675'537 37'612 7'018'297 38'809'947
'reduced_costs': 1'220 50 8'358 4'671 38'755 232'840
SAT stats ClassicMinim LitRemoved LitLearned LitForgotten Subsumed MClauses MDecisions MLitTrue MSubsumed MLitRemoved MReused
'core': 470'297 5'823'545 35'716'304 34'112'413 3'705 4'163 35'203 0 152 2'119 388
'default_lp': 118 8'324 29'312 0 0 400 3'828 0 0 0 0
'fs_random': 0 0 0 0 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0 0 0 0 0
'lb_tree_search': 5 33 1'025 0 0 4'776 37'436 0 0 0 0
'max_lp': 14 705 2'416 0 0 0 0 0 0 0 0
'no_lp': 206'755 4'616'493 19'239'955 15'533'778 793 2'341 28'853 0 101 2'231 266
'objective_lb_search': 50 12'224 7'090 0 0 200 1'356 0 0 0 0
'probing': 9 454 3'200 0 0 0 0 0 0 0 0
'pseudo_costs': 98 5'043 29'657 0 0 400 3'938 0 0 0 0
'quick_restart': 18 1'129 2'967 0 0 0 0 0 0 0 0
'quick_restart_no_lp': 58'470 1'493'502 7'091'093 4'765'454 470 9'998 73'964 0 1'140 9'752 703
'reduced_costs': 42 1'551 17'572 0 0 200 2'010 0 0 0 0
Lp stats Component Iterations AddedCuts OPTIMAL DUAL_F. DUAL_U.
'default_lp': 1 40'582 6'153 876 0 12
'fs_random': 1 0 0 0 0 0
'lb_tree_search': 1 12'606 3'624 287 2 2
'max_lp': 1 13'595 3'730 164 3 0
'objective_lb_search': 1 28'293 6'247 493 0 0
'probing': 1 17'817 5'336 313 0 0
'pseudo_costs': 1 27'844 6'883 795 112 7
'quick_restart': 1 24'665 5'903 350 1 0
'reduced_costs': 1 21'161 5'598 421 96 16
Lp dimension Final dimension of first component
'default_lp': 2101 rows, 2440 columns, 48751 entries
'fs_random': 0 rows, 2440 columns, 0 entries
'lb_tree_search': 2205 rows, 2440 columns, 45109 entries
'max_lp': 4694 rows, 2440 columns, 87015 entries
'objective_lb_search': 2587 rows, 2440 columns, 61015 entries
'probing': 2915 rows, 2440 columns, 104830 entries
'pseudo_costs': 2082 rows, 2440 columns, 57161 entries
'quick_restart': 2438 rows, 2440 columns, 62251 entries
'reduced_costs': 2424 rows, 2440 columns, 68994 entries
Lp debug CutPropag CutEqPropag Adjust Overflow Bad BadScaling
'default_lp': 0 4 887 0 98'578 0
'fs_random': 0 0 0 0 0 0
'lb_tree_search': 0 30 291 0 115'524 0
'max_lp': 0 4 167 0 108'573 0
'objective_lb_search': 0 0 490 0 113'325 0
'probing': 0 8 310 0 94'840 0
'pseudo_costs': 0 3 908 0 98'975 0
'quick_restart': 0 18 350 0 103'392 0
'reduced_costs': 0 26 525 0 111'776 0
Lp pool Constraints Updates Simplif Merged Shortened Split Strenghtened Cuts/Call
'default_lp': 10'438 1'317 54'736 2 29'530 243 258 6'153/12'625
'fs_random': 4'287 0 0 0 0 0 0 0/0
'lb_tree_search': 8'004 2'171 46'838 0 23'785 382 470 3'624/6'300
'max_lp': 8'110 1'177 19'661 0 10'573 468 73 3'730/7'173
'objective_lb_search': 10'534 1'415 49'575 0 28'227 150 235 6'247/12'983
'probing': 9'623 649 4'163 0 2'952 238 39 5'336/10'965
'pseudo_costs': 11'263 981 49'027 0 30'728 548 157 6'883/15'051
'quick_restart': 10'190 1'126 36'437 0 21'091 218 207 5'903/12'725
'reduced_costs': 9'977 1'048 40'758 1 19'446 234 170 5'598/11'411
Lp Cut default_lp max_lp quick_restart reduced_costs pseudo_costs lb_tree_search probing objective_lb_search
CG_FF: 40 13 39 54 74 18 28 48
CG_K: 36 12 19 32 62 17 18 37
CG_KL: 4 1 6 10 13 1 4 12
CG_R: 93 26 69 68 145 40 42 93
CG_RB: 171 58 137 141 242 70 133 157
CG_RBP: 63 27 40 66 108 27 29 72
Clique: - - - - - 1 - -
IB: 1'281 2 1'122 1'215 1'390 142 1'129 1'158
MIR_1_FF: 313 260 301 290 238 415 337 298
MIR_1_K: 93 69 105 86 87 45 112 110
MIR_1_KL: 68 50 73 48 51 36 81 98
MIR_1_R: 8 16 6 10 10 18 6 15
MIR_1_RB: 88 59 96 80 115 64 83 85
MIR_1_RBP: 95 98 105 95 89 167 90 124
MIR_2_FF: 343 234 273 251 310 246 293 356
MIR_2_K: 124 73 124 91 98 50 97 128
MIR_2_KL: 81 42 72 49 54 25 59 103
MIR_2_R: 13 20 6 8 12 7 12 23
MIR_2_RB: 241 116 196 180 249 103 184 249
MIR_2_RBP: 104 105 124 95 94 72 113 122
MIR_3_FF: 268 192 242 213 293 234 230 241
MIR_3_K: 111 64 93 72 107 61 70 106
MIR_3_KL: 65 26 41 38 53 28 37 50
MIR_3_R: 29 15 22 16 46 15 27 39
MIR_3_RB: 175 119 160 160 224 127 157 205
MIR_3_RBP: 99 82 81 76 95 53 75 95
MIR_4_FF: 188 178 176 161 249 133 171 190
MIR_4_K: 87 72 81 71 94 58 64 91
MIR_4_KL: 41 28 30 28 47 26 28 35
MIR_4_R: 25 13 31 26 46 8 23 27
MIR_4_RB: 118 91 134 118 172 86 108 131
MIR_4_RBP: 70 59 76 76 86 57 60 70
MIR_5_FF: 131 116 109 108 115 113 85 91
MIR_5_K: 92 87 74 71 87 68 62 105
MIR_5_KL: 54 46 42 51 49 41 49 61
MIR_5_R: 26 14 9 15 33 6 5 16
MIR_5_RB: 67 68 74 76 118 56 76 86
MIR_5_RBP: 59 82 83 106 94 70 74 87
MIR_6_FF: 65 64 65 56 92 75 61 53
MIR_6_K: 76 90 75 65 88 65 59 80
MIR_6_KL: 59 54 61 47 81 46 62 54
MIR_6_R: 12 13 16 15 19 6 5 9
MIR_6_RB: 40 39 57 58 102 44 48 46
MIR_6_RBP: 95 133 124 110 107 83 103 119
ZERO_HALF_FF: 99 31 63 56 66 16 46 63
ZERO_HALF_K: 45 10 9 19 32 4 16 17
ZERO_HALF_KL: 19 13 9 18 9 7 15 16
ZERO_HALF_R: 565 532 764 655 699 400 577 632
ZERO_HALF_RB: 62 76 126 79 82 48 59 90
ZERO_HALF_RBP: 52 42 63 69 57 26 34 54
LNS stats Improv/Calls Closed Difficulty TimeLimit
'graph_arc_lns': 7/58 53% 7.32e-01 0.10
'graph_cst_lns': 4/58 50% 7.07e-01 0.10
'graph_dec_lns': 3/56 52% 7.98e-01 0.10
'graph_var_lns': 5/48 54% 8.63e-01 0.10
'lb_relax_lns': 7/15 53% 5.80e-01 0.50
'rins/rens': 46/66 52% 6.55e-01 0.10
'rnd_cst_lns': 7/56 52% 7.78e-01 0.10
'rnd_var_lns': 6/59 51% 7.44e-01 0.10
LS stats Batches Restarts/Perturbs LinMoves GenMoves CompoundMoves Bactracks WeightUpdates ScoreComputed
'fj_restart': 1 1 6'919 0 0 0 1'655 207'073
'fj_restart_decay_compound_perturb_obj': 1 1 0 494 40 227 2 16'228
'ls_lin_restart': 14 11 131'035 0 0 0 19'714 4'320'245
'ls_lin_restart_compound': 11 11 0 82'695 5'325 38'670 704 2'830'776
'ls_lin_restart_compound_perturb': 13 11 0 94'633 6'279 44'162 769 3'212'291
'ls_lin_restart_decay': 11 11 109'920 0 0 0 1'978 2'346'252
'ls_lin_restart_decay_compound': 12 11 0 77'472 12'960 32'234 256 2'720'845
'ls_lin_restart_decay_compound_perturb': 10 10 0 63'883 10'208 26'824 255 2'192'704
'ls_lin_restart_decay_perturb': 17 16 170'111 0 0 0 3'116 3'601'403
'ls_lin_restart_perturb': 13 12 118'073 0 0 0 18'685 3'803'196
'ls_restart': 15 15 132'260 0 0 0 18'341 4'301'253
'ls_restart_compound': 21 17 0 144'439 9'896 67'246 1'139 4'936'433
'ls_restart_compound_perturb': 6 5 0 47'116 3'482 21'806 361 1'760'432
'ls_restart_decay': 12 12 120'053 0 0 0 2'218 2'472'451
'ls_restart_decay_compound': 13 13 0 90'023 16'076 36'948 334 3'267'260
'ls_restart_decay_compound_perturb': 11 11 0 75'783 14'145 30'788 278 2'407'856
'ls_restart_decay_perturb': 9 8 89'964 0 0 0 1'621 1'929'036
'ls_restart_perturb': 13 11 122'713 0 0 0 13'965 3'995'460
Solutions (35) Num Rank
'fj_restart_decay_compound_perturb_obj': 1 [1,1]
'graph_arc_lns': 6 [6,21]
'graph_cst_lns': 2 [15,32]
'graph_var_lns': 2 [13,14]
'lb_relax_lns_bool_h': 1 [23,23]
'lb_relax_lns_int': 3 [9,34]
'lb_relax_lns_int_h': 1 [35,35]
'ls_lin_restart_decay_compound_perturb': 1 [16,16]
'ls_restart': 1 [24,24]
'quick_restart_no_lp': 14 [2,31]
'rins_pump_lns': 1 [33,33]
'rnd_cst_lns': 1 [18,18]
'rnd_var_lns': 1 [3,3]
Objective bounds Num
'am1_presolve': 1
'initial_domain': 1
'lb_tree_search': 26
'max_lp': 9
'objective_lb_search': 7
'pseudo_costs': 1
'reduced_costs': 5
Solution repositories Added Queried Synchro
'feasible solutions': 118 1'084 91
'fj solution hints': 0 0 0
'lp solutions': 42 32 31
'pump': 127 38
Improving bounds shared Num Sym
'default_lp': 6 0
'lb_tree_search': 1'113 0
'max_lp': 24 0
'objective_lb_search': 63 0
'quick_restart': 48 0
'quick_restart_no_lp': 13 0
Clauses shared Num
'lb_tree_search': 2
'probing': 6
'quick_restart_no_lp': 20
[Scaling] scaled_objective_bound: 142711 corrected_bound: 142711 delta: 1.78209e-06
CpSolverResponse summary:
status: FEASIBLE
objective: 143698.7327195847
best_bound: 142710.9814196886
integers: 2491
booleans: 1220
conflicts: 0
branches: 1064
propagations: 8864
integer_propagations: 29279
restarts: 1064
lp_iterations: 0
walltime: 40.2797
usertime: 40.2797
deterministic_time: 142.679
gap_integral: 1033.73
solution_fingerprint: 0xc2eb414c3936b6c3
[13]:
SolutionInfo(runtime=40.2796855, bound=142710.98141968856, objective=143698.73271958472, relgap=0.0068737648634916715, termination='FEASIBLE')
[14]:
S, G = solver.get_solution()
[15]:
svgplot(G)
[15]:
