MILPRouter example¶
This notebook demonstrates how to use OptiWindNet to design collector system cable networks using the MILPRouter with OR-Tools Solver.
Load data¶
import required modules
[14]:
from optiwindnet.api import WindFarmNetwork, EWRouter, MILPRouter
[15]:
# Display figures as SVG in Jupyter notebooks
%config InlineBackend.figure_formats = ['svg']
create an instance of wfn using .from_pbf()
[16]:
wfn = WindFarmNetwork.from_pbf(filepath='data/DTU_letters.osm.pbf', cables=[(7, 2000.0)])
[17]:
wfn
[17]:
Optimize¶
Warmstart with EWRouter:
Note: In OptiWindNet,
MILPRouterautomatically uses any existing feasible network and check if it is eligible as a warm start for the MILP solver. If eligible, the MILP model will be warmstarted from the existing network. Therefore, to warm-start a newly createdWindFarmNetwork, pre-un the optimization with a router (e.g.,EWRouterorHGSRouter) to obtain an initial solution; subsequent runs withMILPRouterwill pick it up automatically.
[18]:
res_warmstart= wfn.optimize(router=EWRouter())
[19]:
wfn.length()
[19]:
1820.1681190424422
The syntax for defining a MILPRouter is:
router = MILPRouter(solver_name='ortools', time_limit=60, mip_gap=0.005, verbose=True)
The solver name could be choosen from among following solvers:
solver_name = 'ortools'
solver_name = 'gurobi'
solver_name = 'cbc'
solver_name = 'cplex'
solver_name = 'highs'
solver_name = 'scip'
Rest of arguments (time_limit, mip_gap, verbose) are the same for all solvers.
In this example we use ‘ortools’ which is an opensource tool. You can easily use other solvers (note that depending on your problem size, you might need license for some of the solvers, e.g. cplex, gurobi)
[20]:
router = MILPRouter(solver_name='ortools', time_limit=60, mip_gap=0.005, verbose=True)
[21]:
res = wfn.optimize(router=router)
Using warm start: the model is initialized with the provided solution S.
Starting CP-SAT solver v9.14.6206
Parameters: max_time_in_seconds: 60 log_search_progress: true relative_gap_limit: 0.005
Setting number of workers to 8
Initial optimization model '': (model_fingerprint: 0x8f9424826fd0fab8)
#Variables: 708 (#bools: 354 in floating point objective) (628 primary variables)
- 354 Booleans in [0,1]
- 314 in [0,6]
- 40 in [0,7]
#kAtMostOne: 262 (#literals: 776)
#kLinear1: 708 (#enforced: 708)
#kLinear3: 1
#kLinearN: 122 (#terms: 1'767)
Starting presolve at 0.00s
The solution hint is complete and is feasible.
[Scaling] Floating point objective has 354 terms with magnitude in [18.5198, 233.655] average = 64.9733
[Scaling] Objective coefficient relative error: 2.56462e-08
[Scaling] Objective worst-case absolute error: 8.53137e-05
[Scaling] Objective scaling factor: 524288
2.72e-04s 0.00e+00d [DetectDominanceRelations]
5.40e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
4.76e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::ExtractEncodingFromLinear] #potential_supersets=302
2.22e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateColumns]
2.18e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 2'653 nodes and 4'971 arcs.
[Symmetry] Symmetry computation done. time: 0.0010272 dtime: 0.00048184
4.58e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
8.80e-03s 1.38e-03d [operations_research::sat::CpModelPresolver::Probe] #probed=708
6.58e-04s 1.49e-04d [MaxClique] Merged 262(776 literals) into 142(536 literals) at_most_ones.
3.68e-04s 0.00e+00d [DetectDominanceRelations]
3.00e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
4.16e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::ProcessAtMostOneAndLinear]
2.48e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
2.40e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
3.55e-04s 5.98e-06d [operations_research::sat::CpModelPresolver::DetectDominatedLinearConstraints] #relevant_constraints=83 #num_inclusions=41
3.01e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDifferentVariables]
2.63e-03s 6.97e-05d [operations_research::sat::CpModelPresolver::ProcessSetPPC] #relevant_constraints=184 #num_inclusions=182
5.37e-05s 1.65e-07d [operations_research::sat::CpModelPresolver::FindAlmostIdenticalLinearConstraints] #num_tested_pairs=3
3.95e-04s 9.42e-05d [operations_research::sat::CpModelPresolver::FindBigAtMostOneAndLinearOverlap]
4.13e-04s 1.07e-04d [operations_research::sat::CpModelPresolver::FindBigVerticalLinearOverlap]
1.24e-04s 5.27e-06d [operations_research::sat::CpModelPresolver::FindBigHorizontalLinearOverlap] #linears=80
3.79e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::MergeClauses]
4.10e-04s 0.00e+00d [DetectDominanceRelations]
4.52e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
3.65e-04s 0.00e+00d [DetectDominanceRelations]
3.29e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
2.44e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateColumns]
2.62e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 2'412 nodes and 4'137 arcs.
[Symmetry] Symmetry computation done. time: 0.0005969 dtime: 0.00043606
[SAT presolve] num removable Booleans: 0 / 354
[SAT presolve] num trivial clauses: 0
[SAT presolve] [0s] clauses:37 literals:74 vars:74 one_side_vars:74 simple_definition:0 singleton_clauses:0
[SAT presolve] [0.0001201s] clauses:37 literals:74 vars:74 one_side_vars:74 simple_definition:0 singleton_clauses:0
[SAT presolve] [0.0001906s] clauses:37 literals:74 vars:74 one_side_vars:74 simple_definition:0 singleton_clauses:0
4.02e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
1.13e-02s 1.27e-03d [operations_research::sat::CpModelPresolver::Probe] #probed=708
6.40e-04s 1.45e-04d [MaxClique]
4.99e-04s 0.00e+00d [DetectDominanceRelations]
5.00e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
5.56e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::ProcessAtMostOneAndLinear]
3.68e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
3.28e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
4.44e-04s 4.48e-06d [operations_research::sat::CpModelPresolver::DetectDominatedLinearConstraints] #relevant_constraints=82 #num_inclusions=40
5.53e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDifferentVariables]
2.85e-04s 2.79e-06d [operations_research::sat::CpModelPresolver::ProcessSetPPC] #relevant_constraints=183
6.42e-05s 1.10e-07d [operations_research::sat::CpModelPresolver::FindAlmostIdenticalLinearConstraints] #num_tested_pairs=2
5.64e-04s 9.14e-05d [operations_research::sat::CpModelPresolver::FindBigAtMostOneAndLinearOverlap]
5.08e-04s 1.07e-04d [operations_research::sat::CpModelPresolver::FindBigVerticalLinearOverlap]
1.06e-04s 5.27e-06d [operations_research::sat::CpModelPresolver::FindBigHorizontalLinearOverlap] #linears=80
4.06e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::MergeClauses]
4.01e-04s 0.00e+00d [DetectDominanceRelations]
4.42e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
4.49e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::ExpandObjective] #entries=2'948 #tight_variables=354 #tight_constraints=40
Presolve summary:
- 0 affine relations were detected.
- rule 'TODO linear inclusion: superset is equality' was applied 81 times.
- rule 'at_most_one: transformed into max clique.' was applied 1 time.
- rule 'deductions: 708 stored' was applied 1 time.
- rule 'exactly_one: simplified objective' was applied 40 times.
- rule 'linear: positive equal one' was applied 40 times.
- rule 'objective: shifted cost with exactly ones' was applied 40 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 40 times.
- rule 'setppc: reduced linear coefficients' was applied 39 times.
- rule 'setppc: removed trivial linear constraint' was applied 1 time.
- rule 'variables: detect fully reified value encoding' was applied 354 times.
- rule 'variables: detect half reified value encoding' was applied 708 times.
Presolved optimization model '': (model_fingerprint: 0xe40a2cb85cae44c)
#Variables: 708 (#bools: 314 in objective) (628 primary variables)
- 354 Booleans in [0,1]
- 314 in [0,6]
- 40 in [0,7]
#kAtMostOne: 105 (#literals: 462)
#kBoolAnd: 37 (#enforced: 37) (#literals: 74)
#kExactlyOne: 40 (#literals: 354)
#kLinear1: 708 (#enforced: 708)
#kLinear3: 1
#kLinearN: 81 (#terms: 1'059)
[Symmetry] Graph for symmetry has 2'412 nodes and 4'137 arcs.
[Symmetry] Symmetry computation done. time: 0.0005383 dtime: 0.00043662
Preloading model.
#Bound 0.07s best:inf next:[1364.00132,11454.0017] initial_domain
#1 0.07s best:1636.55509 next:[1364.00132,1636.55508] complete_hint
#Model 0.08s var:708/708 constraints:972/972
Starting search at 0.08s with 8 workers.
6 full problem subsolvers: [core, default_lp, max_lp, no_lp, quick_restart, reduced_costs]
2 first solution subsolvers: [fj, fs_random_no_lp]
9 interleaved subsolvers: [feasibility_pump, graph_arc_lns, graph_cst_lns, graph_dec_lns, graph_var_lns, ls, rins/rens, rnd_cst_lns, rnd_var_lns]
3 helper subsolvers: [neighborhood_helper, synchronization_agent, update_gap_integral]
#Bound 0.10s best:1636.55509 next:[1377.09321,1636.55508] am1_presolve (num_literals=314 num_am1=11 increase=6863922 work_done=1181)
#Bound 0.11s best:1636.55509 next:[1402.64487,1636.55508] quick_restart
#Bound 0.11s best:1636.55509 next:[1409.52721,1636.55508] reduced_costs
#2 0.13s best:1635.89885 next:[1409.52721,1635.89885] graph_arc_lns (d=5.00e-01 s=9 t=0.10 p=0.00 stall=0 h=base)
#Bound 0.15s best:1635.89885 next:[1410.39689,1635.89885] reduced_costs
#Bound 0.15s best:1635.89885 next:[1499.2973,1635.89885] max_lp
#3 0.25s best:1622.04604 next:[1499.2973,1622.04604] graph_var_lns (d=7.07e-01 s=16 t=0.10 p=1.00 stall=1 h=base)
#Bound 0.26s best:1622.04604 next:[1508.14839,1622.04604] max_lp
#4 0.38s best:1610.79303 next:[1508.14839,1610.79303] graph_arc_lns (d=7.07e-01 s=17 t=0.10 p=1.00 stall=0 h=base)
#Bound 0.45s best:1610.79303 next:[1516.61699,1610.79303] max_lp
#Bound 0.70s best:1610.79303 next:[1522.14908,1610.79303] max_lp
#Model 0.76s var:700/708 constraints:963/972
#5 0.91s best:1607.33975 next:[1522.14908,1607.33975] no_lp (fixed_bools=4/354)
#6 0.91s best:1607.19889 next:[1522.14908,1607.19888] no_lp (fixed_bools=4/354)
#7 1.10s best:1579.793 next:[1522.14908,1579.793] graph_var_lns (d=8.14e-01 s=26 t=0.10 p=1.00 stall=0 h=base)
#Bound 1.10s best:1579.793 next:[1525.33886,1579.793] max_lp
#Model 1.12s var:692/708 constraints:955/972
#Model 1.25s var:690/708 constraints:953/972
#Bound 1.38s best:1579.793 next:[1529.09045,1579.793] max_lp
#Model 1.68s var:688/708 constraints:951/972
#Bound 1.73s best:1579.793 next:[1531.81901,1579.793] max_lp
#Model 1.79s var:686/708 constraints:948/972
#Bound 2.11s best:1579.793 next:[1532.93909,1579.793] max_lp
#Model 2.18s var:628/708 constraints:885/972
#Model 2.28s var:626/708 constraints:883/972
#Bound 2.44s best:1579.793 next:[1534.09309,1579.793] max_lp
#Model 2.52s var:624/708 constraints:881/972
#Bound 2.84s best:1579.793 next:[1535.22029,1579.793] max_lp
#Model 3.02s var:622/708 constraints:879/972
#Bound 3.25s best:1579.793 next:[1536.91718,1579.793] max_lp
#8 3.44s best:1575.35543 next:[1536.91718,1575.35543] default_lp (fixed_bools=43/361)
#Model 3.54s var:610/708 constraints:867/972
#Bound 3.69s best:1575.35543 next:[1537.92206,1575.35543] max_lp
#Model 3.78s var:608/708 constraints:865/972
#Bound 4.12s best:1575.35543 next:[1539.70465,1575.35543] max_lp
#Model 4.34s var:606/708 constraints:863/972
#Bound 4.54s best:1575.35543 next:[1540.12251,1575.35543] max_lp
#Bound 4.94s best:1575.35543 next:[1540.75889,1575.35543] max_lp
#Bound 5.43s best:1575.35543 next:[1541.41151,1575.35543] max_lp
#Bound 5.89s best:1575.35543 next:[1541.82218,1575.35543] max_lp
#Model 6.00s var:590/708 constraints:846/972
#Bound 6.77s best:1575.35543 next:[1541.82397,1575.35543] max_lp
#Bound 7.20s best:1575.35543 next:[1542.02515,1575.35543] max_lp
#Bound 7.68s best:1575.35543 next:[1542.16811,1575.35543] max_lp
#Model 7.76s var:588/708 constraints:844/972
#Model 8.04s var:582/708 constraints:837/972
#Bound 8.11s best:1575.35543 next:[1542.59612,1575.35543] max_lp
#Bound 8.12s best:1575.35543 next:[1542.66543,1575.35543] max_lp
#Model 8.49s var:580/708 constraints:835/972
#Bound 8.55s best:1575.35543 next:[1542.9165,1575.35543] max_lp
#Bound 9.04s best:1575.35543 next:[1543.28407,1575.35543] max_lp
#Model 9.12s var:540/708 constraints:788/972
#Bound 9.52s best:1575.35543 next:[1543.48265,1575.35543] max_lp
#Bound 10.15s best:1575.35543 next:[1543.76632,1575.35543] max_lp
#Model 10.15s var:538/708 constraints:785/972
#Bound 10.74s best:1575.35543 next:[1543.91623,1575.35543] max_lp [skipped_logs=0]
#Model 11.30s var:534/708 constraints:781/972
#Bound 11.84s best:1575.35543 next:[1544.21399,1575.35543] max_lp [skipped_logs=1]
#Model 12.23s var:532/708 constraints:779/972
#Model 14.21s var:528/708 constraints:775/972
#Bound 14.60s best:1575.35543 next:[1544.22576,1575.35543] max_lp
#Bound 15.18s best:1575.35543 next:[1544.49836,1575.35543] max_lp
#Bound 15.72s best:1575.35543 next:[1544.54856,1575.35543] max_lp
#Model 17.06s var:526/708 constraints:773/972
#Model 17.16s var:524/708 constraints:771/972
#Model 19.63s var:522/708 constraints:769/972
#Model 21.67s var:512/708 constraints:759/972
#Model 24.21s var:510/708 constraints:757/972
#Bound 26.43s best:1575.35543 next:[1544.55702,1575.35543] reduced_costs
#Bound 26.83s best:1575.35543 next:[1544.68377,1575.35543] reduced_costs
#Model 26.94s var:508/708 constraints:755/972
#Bound 27.27s best:1575.35543 next:[1545.39932,1575.35543] reduced_costs
#Bound 27.72s best:1575.35543 next:[1545.89885,1575.35543] reduced_costs
#Model 27.76s var:502/708 constraints:748/972
#Bound 28.60s best:1575.35543 next:[1546.70652,1575.35543] max_lp
#Bound 28.98s best:1575.35543 next:[1547.10258,1575.35543] max_lp
#Bound 29.42s best:1575.35543 next:[1547.57934,1575.35543] max_lp
#Model 29.65s var:500/708 constraints:746/972
#Bound 29.88s best:1575.35543 next:[1547.97706,1575.35543] max_lp
#Model 30.09s var:498/708 constraints:744/972
#Bound 30.37s best:1575.35543 next:[1548.15456,1575.35543] max_lp
#Model 30.47s var:482/708 constraints:725/972
#Model 30.78s var:480/708 constraints:723/972
#Bound 30.85s best:1575.35543 next:[1548.29967,1575.35543] max_lp
#Model 33.37s var:478/708 constraints:721/972
#Bound 33.57s best:1575.35543 next:[1548.34266,1575.35543] max_lp
#Model 33.90s var:476/708 constraints:719/972
#Bound 34.01s best:1575.35543 next:[1548.39998,1575.35543] max_lp
#Bound 34.45s best:1575.35543 next:[1548.72473,1575.35543] max_lp
#Model 34.86s var:472/708 constraints:713/972
#Bound 34.89s best:1575.35543 next:[1548.8983,1575.35543] max_lp
#Bound 35.37s best:1575.35543 next:[1549.07114,1575.35543] max_lp
#Model 35.43s var:464/708 constraints:702/972
#Model 36.39s var:462/708 constraints:700/972
#Bound 37.31s best:1575.35543 next:[1549.30109,1575.35543] reduced_costs
#Bound 37.39s best:1575.35543 next:[1549.47797,1575.35543] reduced_costs
#Model 37.40s var:458/708 constraints:695/972
#Bound 37.89s best:1575.35543 next:[1550.1541,1575.35543] reduced_costs
#Bound 38.42s best:1575.35543 next:[1550.53246,1575.35543] reduced_costs
#Model 38.47s var:456/708 constraints:692/972
#Bound 38.53s best:1575.35543 next:[1551.53673,1575.35543] max_lp
#Bound 38.90s best:1575.35543 next:[1551.90576,1575.35543] max_lp
#Bound 39.28s best:1575.35543 next:[1552.1022,1575.35543] max_lp
#Model 39.33s var:446/708 constraints:680/972
#Bound 39.65s best:1575.35543 next:[1552.51216,1575.35543] max_lp
#Bound 40.02s best:1575.35543 next:[1552.66935,1575.35543] max_lp
#Model 43.61s var:432/708 constraints:661/972
#Bound 44.18s best:1575.35543 next:[1554.18732,1575.35543] quick_restart
#Bound 44.50s best:1575.35543 next:[1564.38131,1575.35543] max_lp
#Done 44.57s default_lp
Task timing n [ min, max] avg dev time n [ min, max] avg dev dtime
'core': 1 [ 44.51s, 44.51s] 44.51s 0.00ns 44.51s 1 [ 35.20s, 35.20s] 35.20s 0.00ns 35.20s
'default_lp': 1 [ 44.50s, 44.50s] 44.50s 0.00ns 44.50s 1 [ 17.68s, 17.68s] 17.68s 0.00ns 17.68s
'feasibility_pump': 57 [ 11.51ms, 401.86ms] 169.44ms 58.39ms 9.66s 56 [ 34.15ms, 148.00ms] 54.32ms 20.98ms 3.04s
'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_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': 35 [ 6.39ms, 780.61ms] 283.28ms 191.56ms 9.91s 34 [145.30us, 100.23ms] 59.01ms 38.68ms 2.01s
'graph_cst_lns': 43 [ 7.00ms, 622.53ms] 234.55ms 165.83ms 10.09s 41 [ 49.93us, 100.22ms] 56.33ms 43.92ms 2.31s
'graph_dec_lns': 40 [ 4.52ms, 645.04ms] 243.09ms 159.59ms 9.72s 39 [ 10.00ns, 100.23ms] 58.00ms 41.74ms 2.26s
'graph_var_lns': 34 [ 5.02ms, 948.17ms] 289.86ms 203.82ms 9.86s 34 [ 10.00ns, 100.30ms] 60.24ms 39.80ms 2.05s
'ls': 39 [211.35ms, 385.91ms] 251.49ms 30.00ms 9.81s 39 [ 68.41ms, 100.02ms] 99.20ms 4.99ms 3.87s
'max_lp': 1 [ 44.55s, 44.55s] 44.55s 0.00ns 44.55s 1 [ 17.83s, 17.83s] 17.83s 0.00ns 17.83s
'no_lp': 1 [ 44.58s, 44.58s] 44.58s 0.00ns 44.58s 1 [ 24.08s, 24.08s] 24.08s 0.00ns 24.08s
'quick_restart': 1 [ 44.51s, 44.51s] 44.51s 0.00ns 44.51s 1 [ 14.61s, 14.61s] 14.61s 0.00ns 14.61s
'reduced_costs': 1 [ 44.51s, 44.51s] 44.51s 0.00ns 44.51s 1 [ 18.79s, 18.79s] 18.79s 0.00ns 18.79s
'rins/rens': 43 [ 6.87ms, 498.95ms] 226.02ms 143.30ms 9.72s 41 [ 5.53us, 100.28ms] 53.34ms 38.92ms 2.19s
'rnd_cst_lns': 35 [ 23.87ms, 691.60ms] 290.34ms 213.11ms 10.16s 35 [ 13.10us, 100.22ms] 54.96ms 43.85ms 1.92s
'rnd_var_lns': 43 [ 9.13ms, 607.34ms] 230.54ms 183.89ms 9.91s 43 [ 10.00ns, 100.22ms] 51.26ms 45.39ms 2.20s
Search stats Bools Conflicts Branches Restarts BoolPropag IntegerPropag
'core': 867 343'495 1'034'386 24'716 17'686'628 15'453'336
'default_lp': 411 2'770 31'310 9'226 162'939 874'984
'fs_random_no_lp': 0 0 0 0 0 0
'max_lp': 354 732 7'517 2'929 31'545 212'283
'no_lp': 354 336'477 571'132 20'592 11'757'162 44'502'074
'quick_restart': 383 385 40'886 14'200 123'919 868'477
'reduced_costs': 357 1'121 23'552 7'980 78'895 559'759
SAT stats ClassicMinim LitRemoved LitLearned LitForgotten Subsumed MClauses MDecisions MLitTrue MSubsumed MLitRemoved MReused
'core': 319'679 3'201'312 15'992'059 13'471'680 4'204 20'570 465'201 0 6'585 180'811 11'819
'default_lp': 2'600 67'943 95'375 0 9 2'358 13'636 0 10 71 94
'fs_random_no_lp': 0 0 0 0 0 0 0 0 0 0 0
'max_lp': 695 16'260 20'666 0 3 505 2'598 0 8 48 1
'no_lp': 280'954 4'207'142 11'873'435 10'780'327 8'242 14'505 87'330 0 2'984 26'180 3'061
'quick_restart': 323 5'282 13'084 0 0 3'523 20'701 0 26 194 275
'reduced_costs': 982 19'208 56'198 0 5 1'749 9'313 0 9 51 68
Lp stats Component Iterations AddedCuts OPTIMAL DUAL_F. DUAL_U.
'default_lp': 1 252'778 3'241 8'478 2 409
'max_lp': 1 117'195 2'966 1'596 810 72
'quick_restart': 1 88'249 3'366 2'427 4 56
'reduced_costs': 1 121'795 4'159 2'121 906 177
Lp dimension Final dimension of first component
'default_lp': 742 rows, 669 columns, 8831 entries
'max_lp': 937 rows, 708 columns, 13842 entries
'quick_restart': 946 rows, 669 columns, 17872 entries
'reduced_costs': 1195 rows, 708 columns, 39225 entries
Lp debug CutPropag CutEqPropag Adjust Overflow Bad BadScaling
'default_lp': 0 12 8'862 0 34'652 0
'max_lp': 0 0 2'474 0 114'381 0
'quick_restart': 0 1 2'477 0 96'558 0
'reduced_costs': 0 2 3'185 0 106'745 0
Lp pool Constraints Updates Simplif Merged Shortened Split Strenghtened Cuts/Call
'default_lp': 4'413 856 15'923 0 10'754 279 144 3'241/7'111
'max_lp': 4'292 2'110 31'504 0 19'196 1'749 159 2'966/4'923
'quick_restart': 4'538 1'888 27'937 0 18'502 502 201 3'366/6'393
'reduced_costs': 5'485 2'029 28'548 0 19'059 756 209 4'159/7'597
Lp Cut default_lp quick_restart reduced_costs max_lp
CG_FF: 49 14 42 27
CG_K: 31 14 33 16
CG_KL: 6 2 13 -
CG_R: 58 25 55 30
CG_RB: 127 42 95 45
CG_RBP: 75 23 34 12
Clique: - - 8 9
IB: 810 536 582 207
MIR_1_FF: 174 229 214 152
MIR_1_K: 39 48 17 32
MIR_1_KL: 25 36 23 23
MIR_1_R: 3 2 3 8
MIR_1_RB: 66 46 48 21
MIR_1_RBP: 57 58 48 35
MIR_2_FF: 125 186 208 196
MIR_2_K: 51 54 27 75
MIR_2_KL: 12 20 27 25
MIR_2_R: 3 7 8 14
MIR_2_RB: 95 86 114 101
MIR_2_RBP: 60 66 49 60
MIR_3_FF: 120 102 167 160
MIR_3_K: 45 54 43 62
MIR_3_KL: 9 9 18 20
MIR_3_R: 12 8 19 14
MIR_3_RB: 79 60 105 103
MIR_3_RBP: 42 50 55 53
MIR_4_FF: 58 80 115 127
MIR_4_K: 41 56 54 71
MIR_4_KL: 6 12 22 17
MIR_4_R: 15 6 8 5
MIR_4_RB: 44 35 74 63
MIR_4_RBP: 33 52 55 52
MIR_5_FF: 46 46 76 114
MIR_5_K: 45 43 42 75
MIR_5_KL: 7 19 20 17
MIR_5_R: 5 7 5 8
MIR_5_RB: 32 33 49 53
MIR_5_RBP: 37 60 62 57
MIR_6_FF: 40 32 37 65
MIR_6_K: 30 40 65 44
MIR_6_KL: 10 22 17 24
MIR_6_R: 6 2 1 10
MIR_6_RB: 22 27 44 31
MIR_6_RBP: 27 70 83 48
ZERO_HALF_FF: 23 8 26 5
ZERO_HALF_K: 6 1 11 1
ZERO_HALF_KL: 7 1 10 1
ZERO_HALF_R: 431 737 948 449
ZERO_HALF_RB: 78 106 160 67
ZERO_HALF_RBP: 19 94 120 62
LNS stats Improv/Calls Closed Difficulty TimeLimit
'graph_arc_lns': 9/35 60% 9.24e-01 0.10
'graph_cst_lns': 14/43 58% 9.28e-01 0.10
'graph_dec_lns': 10/40 57% 9.39e-01 0.10
'graph_var_lns': 7/34 59% 9.13e-01 0.10
'rins/rens': 36/43 70% 9.87e-01 0.10
'rnd_cst_lns': 0/35 54% 8.95e-01 0.10
'rnd_var_lns': 9/43 56% 9.21e-01 0.10
LS stats Batches Restarts/Perturbs LinMoves GenMoves CompoundMoves Bactracks WeightUpdates ScoreComputed
'ls_restart': 3 3 56'605 0 0 0 23'530 1'707'214
'ls_restart_compound': 8 6 0 220'923 15'134 102'878 1'292 3'773'458
'ls_restart_compound_perturb': 8 6 0 209'960 13'764 98'083 1'233 3'518'835
'ls_restart_decay': 8 6 190'343 0 0 0 8'330 3'053'575
'ls_restart_decay_compound': 3 2 0 75'377 10'336 32'511 111 1'486'916
'ls_restart_decay_compound_perturb': 3 3 0 71'690 11'211 30'235 158 1'440'919
'ls_restart_decay_perturb': 2 2 49'577 0 0 0 2'324 714'591
'ls_restart_perturb': 4 3 78'840 0 0 0 22'346 2'403'625
Solutions (8) Num Rank
'complete_hint': 1 [1,1]
'default_lp': 1 [8,8]
'graph_arc_lns': 2 [2,4]
'graph_var_lns': 2 [3,7]
'no_lp': 2 [5,6]
Objective bounds Num
'am1_presolve': 1
'initial_domain': 1
'max_lp': 49
'quick_restart': 2
'reduced_costs': 10
Solution repositories Added Queried Synchro
'feasible solutions': 52 606 39
'fj solution hints': 0 0 0
'lp solutions': 57 22 54
'pump': 901 21
Improving bounds shared Num Sym
'default_lp': 16 0
'max_lp': 211 0
'no_lp': 15 0
'quick_restart': 23 0
'reduced_costs': 82 0
Clauses shared Num
'core': 8
'default_lp': 20
'max_lp': 3
'no_lp': 435
'quick_restart': 2
'reduced_costs': 30
[Scaling] scaled_objective_bound: 1575.36 corrected_bound: 1575.36 delta: -1.02945e-06
CpSolverResponse summary:
status: OPTIMAL
objective: 1575.355435924007
best_bound: 1575.355435447172
integers: 0
booleans: 0
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 0
restarts: 0
lp_iterations: 0
walltime: 44.672
usertime: 44.672
deterministic_time: 150.043
gap_integral: 129.764
solution_fingerprint: 0x74f029e2c7dc518
[22]:
wfn.solution_info()
[22]:
{'runtime': 44.672037,
'bound': 1575.3554354471723,
'objective': 1575.3554359240065,
'relgap': 3.0268354489493277e-10,
'termination': 'OPTIMAL'}
[23]:
wfn.length()
[23]:
1575.355435924007
[24]:
wfn
[24]:
MILPRouter has two optional arguments: ModelOptions (what kind of solution you want) and SolverOptions (how long/how hard the solver searches). For more detail about ModelOptions and SolverOptions see ModelOptions vs SolverOptions
[25]:
from optiwindnet.api import ModelOptions
model_options = ModelOptions(
topology='radial',
feeder_limit='minimum',
feeder_route='segmented',
)
solver_options=dict(
num_workers = 5,
)
router= MILPRouter(solver_name='ortools', time_limit=60, mip_gap=0.01, model_options=model_options, verbose=True)
res = wfn.optimize(router=router)
Warning: No warmstarting (even though a solution is available) due to the following reason(s):
- branched structure not allowed under "radial" topology
Starting CP-SAT solver v9.14.6206
Parameters: max_time_in_seconds: 60 log_search_progress: true relative_gap_limit: 0.01
Setting number of workers to 8
Initial optimization model '': (model_fingerprint: 0x16f14efd313c6050)
#Variables: 708 (#bools: 354 in floating point objective) (627 primary variables)
- 354 Booleans in [0,1]
- 314 in [0,6]
- 40 in [0,7]
#kAtMostOne: 262 (#literals: 776)
#kLinear1: 708 (#enforced: 708)
#kLinear3: 2
#kLinearN: 161 (#terms: 2'078)
Starting presolve at 0.00s
The solution hint is complete, but it is infeasible! we will try to repair it.
[Scaling] Floating point objective has 354 terms with magnitude in [18.5198, 233.655] average = 64.9733
[Scaling] Objective coefficient relative error: 2.56462e-08
[Scaling] Objective worst-case absolute error: 8.53137e-05
[Scaling] Objective scaling factor: 524288
4.00e-04s 0.00e+00d [DetectDominanceRelations]
9.06e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
1.02e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::ExtractEncodingFromLinear] #potential_supersets=342
5.70e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateColumns]
3.96e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 2'693 nodes and 5'285 arcs.
[Symmetry] Symmetry computation done. time: 0.0011188 dtime: 0.00049342
4.51e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
4.56e-02s 1.42e-03d [operations_research::sat::CpModelPresolver::Probe] #probed=708
1.16e-03s 3.14e-04d [MaxClique] Merged 302(1'090 literals) into 182(850 literals) at_most_ones.
5.48e-04s 0.00e+00d [DetectDominanceRelations]
5.27e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
7.58e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::ProcessAtMostOneAndLinear]
3.99e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
3.57e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
5.30e-04s 5.62e-06d [operations_research::sat::CpModelPresolver::DetectDominatedLinearConstraints] #relevant_constraints=83 #num_inclusions=41 #num_redundant=1
4.50e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDifferentVariables]
3.91e-04s 6.36e-05d [operations_research::sat::CpModelPresolver::ProcessSetPPC] #relevant_constraints=224 #num_inclusions=182
6.49e-05s 1.65e-07d [operations_research::sat::CpModelPresolver::FindAlmostIdenticalLinearConstraints] #num_tested_pairs=3
3.51e-03s 1.09e-03d [operations_research::sat::CpModelPresolver::FindBigAtMostOneAndLinearOverlap]
9.18e-04s 6.03e-04d [operations_research::sat::CpModelPresolver::FindBigVerticalLinearOverlap]
3.45e-04s 1.32e-04d [operations_research::sat::CpModelPresolver::FindBigHorizontalLinearOverlap] #linears=81
3.72e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::MergeClauses]
5.29e-04s 0.00e+00d [DetectDominanceRelations]
5.10e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
9.08e-04s 0.00e+00d [DetectDominanceRelations]
1.85e-02s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
5.84e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateColumns]
4.25e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 2'453 nodes and 4'765 arcs.
[Symmetry] Symmetry computation done. time: 0.0008052 dtime: 0.00045614
[SAT presolve] num removable Booleans: 0 / 354
[SAT presolve] num trivial clauses: 0
[SAT presolve] [0s] clauses:37 literals:74 vars:74 one_side_vars:74 simple_definition:0 singleton_clauses:0
[SAT presolve] [0.0001032s] clauses:37 literals:74 vars:74 one_side_vars:74 simple_definition:0 singleton_clauses:0
[SAT presolve] [0.0002179s] clauses:37 literals:74 vars:74 one_side_vars:74 simple_definition:0 singleton_clauses:0
4.60e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
9.98e-03s 1.41e-03d [operations_research::sat::CpModelPresolver::Probe] #probed=708
1.03e-03s 3.09e-04d [MaxClique]
5.81e-04s 0.00e+00d [DetectDominanceRelations]
1.63e-02s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
1.03e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::ProcessAtMostOneAndLinear]
4.56e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraints]
4.05e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDuplicateConstraintsWithDifferentEnforcements]
4.41e-04s 5.42e-06d [operations_research::sat::CpModelPresolver::DetectDominatedLinearConstraints] #relevant_constraints=83 #num_inclusions=40
5.27e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::DetectDifferentVariables]
3.64e-04s 6.36e-05d [operations_research::sat::CpModelPresolver::ProcessSetPPC] #relevant_constraints=224 #num_inclusions=182
6.32e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::FindAlmostIdenticalLinearConstraints]
2.96e-03s 1.09e-03d [operations_research::sat::CpModelPresolver::FindBigAtMostOneAndLinearOverlap]
6.46e-04s 6.03e-04d [operations_research::sat::CpModelPresolver::FindBigVerticalLinearOverlap]
2.89e-04s 1.32e-04d [operations_research::sat::CpModelPresolver::FindBigHorizontalLinearOverlap] #linears=81
3.81e-05s 0.00e+00d [operations_research::sat::CpModelPresolver::MergeClauses]
4.97e-04s 0.00e+00d [DetectDominanceRelations]
5.29e-03s 0.00e+00d [operations_research::sat::CpModelPresolver::PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
6.82e-04s 0.00e+00d [operations_research::sat::CpModelPresolver::ExpandObjective] #entries=2'948 #tight_variables=354 #tight_constraints=40
Presolve summary:
- 0 affine relations were detected.
- rule 'TODO linear inclusion: superset is equality' was applied 80 times.
- rule 'at_most_one: transformed into max clique.' was applied 1 time.
- rule 'deductions: 708 stored' was applied 1 time.
- rule 'exactly_one: simplified objective' was applied 40 times.
- rule 'linear inclusion: sparsify superset' was applied 1 time.
- rule 'linear: positive at most one' was applied 40 times.
- rule 'linear: positive equal one' was applied 40 times.
- rule 'objective: shifted cost with exactly ones' was applied 40 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 354 times.
- rule 'variables: detect half reified value encoding' was applied 708 times.
Presolved optimization model '': (model_fingerprint: 0x3f18bc4957acde62)
#Variables: 708 (#bools: 314 in objective) (627 primary variables)
- 354 Booleans in [0,1]
- 314 in [0,6]
- 40 in [0,7]
#kAtMostOne: 145 (#literals: 776)
#kBoolAnd: 37 (#enforced: 37) (#literals: 74)
#kExactlyOne: 40 (#literals: 354)
#kLinear1: 708 (#enforced: 708)
#kLinear3: 1
#kLinearN: 82 (#terms: 1'373)
[Symmetry] Graph for symmetry has 2'453 nodes and 4'765 arcs.
[Symmetry] Symmetry computation done. time: 0.0006826 dtime: 0.00045658
Preloading model.
#Bound 0.16s best:inf next:[1364.00132,11454.0017] initial_domain
The solution hint is complete, but it is infeasible! we will try to repair it.
#Model 0.16s var:708/708 constraints:1013/1013
Starting search at 0.16s with 8 workers.
6 full problem subsolvers: [core, default_lp, max_lp, no_lp, quick_restart, reduced_costs]
2 first solution subsolvers: [fj, fs_random_no_lp]
9 interleaved subsolvers: [feasibility_pump, graph_arc_lns, graph_cst_lns, graph_dec_lns, graph_var_lns, ls, rins/rens, rnd_cst_lns, rnd_var_lns]
3 helper subsolvers: [neighborhood_helper, synchronization_agent, update_gap_integral]
#Bound 0.18s best:inf next:[1396.24224,11454.0017] am1_presolve (num_literals=314 num_am1=12 increase=16903528 work_done=1733)
#1 0.18s best:3035.44867 next:[1396.24224,3035.44866] fs_random_no_lp (fixed_bools=0/354)
#Bound 0.19s best:3035.44867 next:[1427.81903,3035.44866] default_lp
#Bound 0.20s best:3035.44867 next:[1434.70137,3035.44866] reduced_costs
#2 0.20s best:2988.21918 next:[1434.70137,2988.21917] core (fixed_bools=0/366)
#Bound 0.20s best:2988.21918 next:[1518.98019,2988.21917] max_lp
#3 0.21s best:2163.4381 next:[1518.98019,2163.43809] no_lp (fixed_bools=0/354)
#4 0.22s best:1762.92972 next:[1518.98019,1762.92972] fj_restart(batch:1 lin{mvs:4'135 evals:83'036} #w_updates:2'617 #perturb:0) (fixed_bools=0/354)
#5 0.25s best:1753.27412 next:[1518.98019,1753.27411] graph_cst_lns (d=5.00e-01 s=13 t=0.10 p=0.00 stall=0 h=base) (fixed_bools=0/354)
#Bound 0.30s best:1753.27412 next:[1525.81064,1753.27411] max_lp
#6 0.35s best:1679.37489 next:[1525.81064,1679.37489] reduced_costs [hint] (fixed_bools=0/354)
#Bound 0.44s best:1679.37489 next:[1541.63598,1679.37489] max_lp
#7 0.47s best:1677.00272 next:[1541.63598,1677.00272] rnd_var_lns (d=8.14e-01 s=23 t=0.10 p=1.00 stall=2 h=base) (fixed_bools=0/354)
#8 0.61s best:1665.8485 next:[1541.63598,1665.8485] graph_arc_lns (d=8.14e-01 s=26 t=0.10 p=1.00 stall=2 h=base) (fixed_bools=0/354)
#Bound 0.66s best:1665.8485 next:[1546.76229,1665.8485] max_lp
#9 0.89s best:1613.50867 next:[1546.76229,1613.50867] rnd_cst_lns (d=8.76e-01 s=35 t=0.10 p=1.00 stall=3 h=base) (fixed_bools=0/354)
#Model 0.95s var:706/708 constraints:1010/1013
#Bound 1.04s best:1613.50867 next:[1550.4219,1613.50867] max_lp
#Bound 1.45s best:1613.50867 next:[1551.35304,1613.50867] max_lp
#Bound 1.90s best:1613.50867 next:[1552.26978,1613.50867] max_lp
#Model 2.14s var:676/708 constraints:979/1013
#Bound 2.37s best:1613.50867 next:[1552.93216,1613.50867] max_lp
#Model 2.50s var:666/708 constraints:968/1013
#Bound 2.84s best:1613.50867 next:[1553.45539,1613.50867] max_lp
#Model 2.92s var:656/708 constraints:957/1013
#Bound 3.31s best:1613.50867 next:[1553.98742,1613.50867] max_lp
#Bound 3.83s best:1613.50867 next:[1554.73213,1613.50867] max_lp
#Bound 3.86s best:1613.50867 next:[1555.59202,1613.50867] default_lp
#10 4.39s best:1612.2948 next:[1555.59202,1612.2948] graph_dec_lns (d=9.14e-01 s=61 t=0.10 p=1.00 stall=4 h=base) (fixed_bools=0/354)
#Model 4.48s var:654/708 constraints:955/1013
#Bound 5.23s best:1612.2948 next:[1556.00294,1612.2948] max_lp
#Bound 5.39s best:1612.2948 next:[1556.73864,1612.2948] quick_restart
#Model 5.40s var:652/708 constraints:953/1013
#Bound 5.92s best:1612.2948 next:[1557.78244,1612.2948] quick_restart
#Model 6.02s var:650/708 constraints:951/1013
#Bound 6.47s best:1612.2948 next:[1557.8018,1612.2948] quick_restart
#Bound 7.00s best:1612.2948 next:[1558.73585,1612.2948] quick_restart
#Bound 7.52s best:1612.2948 next:[1560.80928,1612.2948] quick_restart
#Model 7.56s var:648/708 constraints:949/1013
#Bound 8.05s best:1612.2948 next:[1562.37551,1612.2948] quick_restart
#Bound 8.69s best:1612.2948 next:[1563.20248,1612.2948] quick_restart
#Model 8.73s var:644/708 constraints:945/1013
#Model 10.86s var:640/708 constraints:940/1013
#Model 11.85s var:638/708 constraints:938/1013
#Bound 11.93s best:1612.2948 next:[1564.21304,1612.2948] quick_restart
#Bound 12.88s best:1612.2948 next:[1564.29035,1612.2948] quick_restart
#Bound 13.61s best:1612.2948 next:[1564.57567,1612.2948] quick_restart
#Model 14.26s var:636/708 constraints:936/1013
#Model 14.88s var:632/708 constraints:932/1013
#Bound 15.29s best:1612.2948 next:[1564.92845,1612.2948] quick_restart
#Bound 15.99s best:1612.2948 next:[1565.49838,1612.2948] quick_restart
#Model 16.00s var:628/708 constraints:928/1013
#Bound 16.64s best:1612.2948 next:[1565.64219,1612.2948] quick_restart
#Bound 18.00s best:1612.2948 next:[1565.8222,1612.2948] quick_restart
#Model 18.47s var:626/708 constraints:926/1013
#Bound 18.63s best:1612.2948 next:[1566.03236,1612.2948] quick_restart
#Bound 20.20s best:1612.2948 next:[1566.5582,1612.2948] quick_restart
#Model 20.22s var:624/708 constraints:924/1013
#Bound 20.93s best:1612.2948 next:[1566.73077,1612.2948] quick_restart
#Bound 30.11s best:1612.2948 next:[1566.85661,1612.2948] quick_restart
#Model 30.22s var:622/708 constraints:922/1013
#Bound 30.82s best:1612.2948 next:[1566.93204,1612.2948] quick_restart
#Model 30.89s var:620/708 constraints:920/1013
#Model 31.07s var:618/708 constraints:918/1013
#Bound 32.02s best:1612.2948 next:[1567.01157,1612.2948] quick_restart
#Model 32.38s var:614/708 constraints:914/1013
#Bound 33.40s best:1612.2948 next:[1567.51543,1612.2948] quick_restart
#Model 33.42s var:612/708 constraints:912/1013
#Bound 34.70s best:1612.2948 next:[1567.92698,1612.2948] quick_restart
#Bound 40.63s best:1612.2948 next:[1567.93453,1612.2948] quick_restart
#Bound 41.30s best:1612.2948 next:[1568.04483,1612.2948] quick_restart
#Model 41.32s var:610/708 constraints:910/1013
#Bound 41.40s best:1612.2948 next:[1568.97197,1612.2948] quick_restart
#Model 50.02s var:608/708 constraints:907/1013
#Bound 52.78s best:1612.2948 next:[1569.00591,1612.2948] quick_restart
#Bound 58.66s best:1612.2948 next:[1569.16939,1612.2948] quick_restart
#Bound 59.44s best:1612.2948 next:[1569.35415,1612.2948] quick_restart
Task timing n [ min, max] avg dev time n [ min, max] avg dev dtime
'core': 1 [ 59.85s, 59.85s] 59.85s 0.00ns 59.85s 1 [ 44.52s, 44.52s] 44.52s 0.00ns 44.52s
'default_lp': 1 [ 59.85s, 59.85s] 59.85s 0.00ns 59.85s 1 [ 24.80s, 24.80s] 24.80s 0.00ns 24.80s
'feasibility_pump': 129 [ 30.90us, 911.70ms] 96.42ms 228.67ms 12.44s 24 [ 81.07ms, 333.04ms] 191.80ms 96.63ms 4.60s
'fj': 1 [ 54.95ms, 54.95ms] 54.95ms 0.00ns 54.95ms 1 [ 28.95ms, 28.95ms] 28.95ms 0.00ns 28.95ms
'fs_random_no_lp': 1 [ 26.98ms, 26.98ms] 26.98ms 0.00ns 26.98ms 1 [140.09us, 140.09us] 140.09us 0.00ns 140.09us
'graph_arc_lns': 33 [ 17.86ms, 1.98s] 458.19ms 497.19ms 15.12s 33 [ 25.51us, 100.33ms] 63.51ms 40.02ms 2.10s
'graph_cst_lns': 42 [ 23.84ms, 1.72s] 327.57ms 308.61ms 13.76s 42 [ 28.66us, 100.36ms] 58.95ms 43.01ms 2.48s
'graph_dec_lns': 36 [ 1.16ms, 1.87s] 364.54ms 405.95ms 13.12s 33 [ 10.00ns, 101.00ms] 59.69ms 43.22ms 1.97s
'graph_var_lns': 34 [ 5.47ms, 955.58ms] 380.49ms 263.12ms 12.94s 34 [ 10.00ns, 100.30ms] 63.29ms 38.60ms 2.15s
'ls': 58 [189.09ms, 271.23ms] 224.13ms 18.24ms 13.00s 58 [100.00ms, 100.05ms] 100.01ms 8.19us 5.80s
'max_lp': 1 [ 59.85s, 59.85s] 59.85s 0.00ns 59.85s 1 [ 19.45s, 19.45s] 19.45s 0.00ns 19.45s
'no_lp': 1 [ 59.84s, 59.84s] 59.84s 0.00ns 59.84s 1 [ 26.34s, 26.34s] 26.34s 0.00ns 26.34s
'quick_restart': 1 [ 59.85s, 59.85s] 59.85s 0.00ns 59.85s 1 [ 21.87s, 21.87s] 21.87s 0.00ns 21.87s
'reduced_costs': 1 [ 59.85s, 59.85s] 59.85s 0.00ns 59.85s 1 [ 25.69s, 25.69s] 25.69s 0.00ns 25.69s
'rins/rens': 52 [ 10.56ms, 520.01ms] 248.81ms 166.65ms 12.94s 50 [ 11.05us, 100.10ms] 59.29ms 43.68ms 2.96s
'rnd_cst_lns': 47 [ 8.66ms, 793.88ms] 282.68ms 179.93ms 13.29s 47 [ 10.00ns, 100.25ms] 58.58ms 41.92ms 2.75s
'rnd_var_lns': 44 [ 7.66ms, 1.16s] 292.39ms 268.96ms 12.87s 44 [ 10.00ns, 100.30ms] 51.49ms 45.20ms 2.27s
Search stats Bools Conflicts Branches Restarts BoolPropag IntegerPropag
'core': 1'164 270'146 814'034 16'813 29'491'139 15'382'674
'default_lp': 354 2'126 20'285 7'562 149'227 739'778
'fs_random_no_lp': 354 18 849 710 7'630 19'564
'max_lp': 354 1'774 27'014 10'885 179'325 907'838
'no_lp': 354 376'387 649'406 21'151 17'210'068 60'745'976
'quick_restart': 354 661 116'369 36'242 551'687 2'890'518
'reduced_costs': 357 2'035 43'557 14'904 248'419 1'269'381
SAT stats ClassicMinim LitRemoved LitLearned LitForgotten Subsumed MClauses MDecisions MLitTrue MSubsumed MLitRemoved MReused
'core': 241'826 2'941'378 15'232'817 12'133'636 2'467 10'952 362'224 0 3'306 138'611 5'624
'default_lp': 1'961 44'233 109'291 0 13 1'116 8'068 0 14 124 28
'fs_random_no_lp': 6 48 867 0 0 0 0 0 0 0 0
'max_lp': 1'680 58'687 98'361 0 2 1'677 11'050 0 5 26 2
'no_lp': 352'910 5'846'731 13'841'473 12'343'819 2'652 14'414 111'233 0 3'774 39'867 2'962
'quick_restart': 577 20'432 30'071 0 5 8'719 74'284 0 40 457 2'430
'reduced_costs': 1'855 35'799 149'711 0 3 2'695 18'440 0 14 93 116
Lp stats Component Iterations AddedCuts OPTIMAL DUAL_F. DUAL_U.
'default_lp': 1 268'749 3'749 6'295 5 460
'max_lp': 1 187'649 2'047 3'893 1'525 260
'quick_restart': 1 160'118 2'630 3'821 22 101
'reduced_costs': 1 251'965 3'008 3'268 2'044 320
Lp dimension Final dimension of first component
'default_lp': 807 rows, 708 columns, 12446 entries
'max_lp': 849 rows, 708 columns, 16171 entries
'quick_restart': 923 rows, 708 columns, 18608 entries
'reduced_costs': 848 rows, 708 columns, 13329 entries
Lp debug CutPropag CutEqPropag Adjust Overflow Bad BadScaling
'default_lp': 0 0 6'744 0 45'291 0
'max_lp': 0 2 5'673 0 86'942 0
'quick_restart': 0 0 3'937 0 71'135 0
'reduced_costs': 0 9 5'623 0 69'852 0
Lp pool Constraints Updates Simplif Merged Shortened Split Strenghtened Cuts/Call
'default_lp': 5'079 685 9'590 0 7'787 289 183 3'749/7'435
'max_lp': 3'414 977 6'909 0 4'558 755 38 2'047/4'034
'quick_restart': 3'960 807 10'745 0 7'222 557 85 2'630/4'940
'reduced_costs': 4'375 967 7'889 0 5'969 399 114 3'008/6'059
Lp Cut default_lp max_lp quick_restart reduced_costs
CG_FF: 53 23 20 25
CG_K: 39 13 13 16
CG_KL: 10 - 3 11
CG_R: 71 37 23 61
CG_RB: 76 49 71 138
CG_RBP: 56 27 25 25
Clique: - 18 - 16
IB: 1'105 549 762 798
MIR_1_FF: 165 91 143 161
MIR_1_K: 68 14 36 20
MIR_1_KL: 28 6 20 14
MIR_1_R: 16 7 7 10
MIR_1_RB: 45 21 34 50
MIR_1_RBP: 41 90 76 62
MIR_2_FF: 142 67 110 122
MIR_2_K: 62 14 39 19
MIR_2_KL: 18 12 18 12
MIR_2_R: 51 3 21 13
MIR_2_RB: 112 51 78 82
MIR_2_RBP: 54 20 45 26
MIR_3_FF: 100 57 88 105
MIR_3_K: 53 19 24 19
MIR_3_KL: 12 7 5 8
MIR_3_R: 25 2 6 13
MIR_3_RB: 87 37 53 59
MIR_3_RBP: 39 24 20 25
MIR_4_FF: 69 51 59 74
MIR_4_K: 28 10 18 20
MIR_4_KL: 10 3 5 8
MIR_4_R: 22 1 4 9
MIR_4_RB: 57 31 41 56
MIR_4_RBP: 20 24 18 34
MIR_5_FF: 66 31 42 42
MIR_5_K: 28 15 25 34
MIR_5_KL: 7 6 10 7
MIR_5_R: 18 6 5 6
MIR_5_RB: 43 19 27 31
MIR_5_RBP: 17 22 22 28
MIR_6_FF: 49 18 46 42
MIR_6_K: 30 28 22 25
MIR_6_KL: 8 9 14 12
MIR_6_R: 18 3 2 14
MIR_6_RB: 29 16 28 24
MIR_6_RBP: 31 32 34 45
ZERO_HALF_FF: 67 22 15 35
ZERO_HALF_K: 32 1 1 15
ZERO_HALF_KL: 24 6 6 11
ZERO_HALF_R: 426 390 358 437
ZERO_HALF_RB: 62 18 37 56
ZERO_HALF_RBP: 60 27 51 33
LNS stats Improv/Calls Closed Difficulty TimeLimit
'graph_arc_lns': 6/33 55% 9.00e-01 0.10
'graph_cst_lns': 7/42 52% 8.93e-01 0.10
'graph_dec_lns': 3/33 55% 9.01e-01 0.10
'graph_var_lns': 4/34 59% 9.55e-01 0.10
'rins/rens': 51/52 54% 8.92e-01 0.10
'rnd_cst_lns': 7/47 55% 9.23e-01 0.10
'rnd_var_lns': 2/44 57% 9.28e-01 0.10
LS stats Batches Restarts/Perturbs LinMoves GenMoves CompoundMoves Bactracks WeightUpdates ScoreComputed
'fj_restart': 1 1 4'135 0 0 0 2'617 102'737
'ls_restart': 5 2 69'750 0 0 0 33'639 2'453'272
'ls_restart_compound': 5 4 0 73'537 5'643 33'943 722 1'939'596
'ls_restart_compound_perturb': 11 8 0 177'036 11'305 82'854 1'613 4'334'263
'ls_restart_decay': 12 9 197'600 0 0 0 7'952 3'780'346
'ls_restart_decay_compound': 8 5 0 125'134 20'410 52'349 242 3'343'160
'ls_restart_decay_compound_perturb': 5 4 0 74'942 12'775 31'065 150 1'874'221
'ls_restart_decay_perturb': 4 3 66'009 0 0 0 2'719 1'232'548
'ls_restart_perturb': 8 6 113'364 0 0 0 94'072 3'500'824
Solutions (10) Num Rank
'core': 1 [2,2]
'fj_restart': 1 [4,4]
'fs_random_no_lp': 1 [1,1]
'graph_arc_lns': 1 [8,8]
'graph_cst_lns': 1 [5,5]
'graph_dec_lns': 1 [10,10]
'no_lp': 1 [3,3]
'reduced_costs': 1 [6,6]
'rnd_cst_lns': 1 [9,9]
'rnd_var_lns': 1 [7,7]
Objective bounds Num
'am1_presolve': 1
'default_lp': 2
'initial_domain': 1
'max_lp': 12
'quick_restart': 28
'reduced_costs': 1
Solution repositories Added Queried Synchro
'feasible solutions': 72 653 47
'fj solution hints': 0 0 0
'lp solutions': 121 25 115
'pump': 239 27
Improving bounds shared Num Sym
'default_lp': 10 0
'max_lp': 20 0
'no_lp': 4 0
'quick_restart': 46 0
'reduced_costs': 22 0
Clauses shared Num
'core': 20
'default_lp': 6
'max_lp': 1
'no_lp': 261
'quick_restart': 12
'reduced_costs': 3
[Scaling] scaled_objective_bound: 1569.35 corrected_bound: 1569.35 delta: -1.03152e-06
CpSolverResponse summary:
status: FEASIBLE
objective: 1612.294803789018
best_bound: 1569.354147988913
integers: 727
booleans: 354
conflicts: 18
branches: 849
propagations: 7630
integer_propagations: 19564
restarts: 710
lp_iterations: 0
walltime: 60.0906
usertime: 60.0906
deterministic_time: 189.768
gap_integral: 720.381
solution_fingerprint: 0x5b832712c354a6b2
[26]:
wfn
[26]:
