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
[1]:
from optiwindnet.api import WindFarmNetwork, EWRouter, MILPRouter
[2]:
# Display figures as SVG in Jupyter notebooks
%config InlineBackend.figure_formats = ['svg']
create an instance of wfn using .from_pbf()
[3]:
wfn = WindFarmNetwork.from_pbf(filepath='data/DTU_letters.osm.pbf', cables=[(7, 2000.0)])
[4]:
wfn
[4]:
Optimize¶
Warmstart with EWRouter:
Note: In OptiWindNet,
MILPRouterautomatically uses any existing feasible network and checks whether it is eligible as a warm start for the MILP solver. If eligible, the MILP model will be warm-started from the existing network. Therefore, to warm-start a newly createdWindFarmNetwork, pre-run the optimization with a router (e.g.,EWRouterorHGSRouter) to obtain an initial solution; subsequent runs withMILPRouterwill pick it up automatically.
[5]:
res_warmstart= wfn.optimize(router=EWRouter())
[6]:
wfn.length()
[6]:
1647.108905210097
The syntax for defining a MILPRouter is:
router = MILPRouter(solver_name='ortools.cp_sat', time_limit=60, mip_gap=0.005, verbose=True)
The solver name could be chosen from among the following solvers:
solver_name = 'ortools.«backend»' # «backend» in (cp_sat, gscip, highs)
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.cp_sat’ 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)
[7]:
router = MILPRouter(solver_name='ortools.cp_sat', time_limit=60, mip_gap=0.005, verbose=True)
[8]:
res = wfn.optimize(router=router)
IntegerBoundsPreprocessor 1093 rows, 708 columns, 3962 entries with magnitude in [1.000000e+00, 7.000000e+00]
BoundPropagationPreprocessor 1093 rows, 708 columns, 3962 entries with magnitude in [1.000000e+00, 7.000000e+00]
ImpliedIntegerPreprocessor 1093 rows, 708 columns, 3962 entries with magnitude in [1.000000e+00, 7.000000e+00]
IntegerBoundsPreprocessor 1093 rows, 708 columns, 3962 entries with magnitude in [1.000000e+00, 7.000000e+00]
ReduceCostOverExclusiveOrConstraintPreprocessor 1093 rows, 708 columns, 3962 entries with magnitude in [1.000000e+00, 7.000000e+00]
Scaling to pure integer problem.
Num integers: 708/708 (implied: 0 in_inequalities: 0 max_scaling: 0) [IP]
Maximum constraint coefficient relative error: 0
Maximum constraint worst-case activity error: 0
Constraint scaling factor range: [1, 1]
Starting CP-SAT solver v9.15.6755
Parameters: max_time_in_seconds: 60 log_search_progress: true catch_sigint_signal: false relative_gap_limit: 0.005
Setting number of workers to 16
Initial optimization model 'optiwindnet': (model_fingerprint: 0x5ec2d01861d9914d)
#Variables: 708 (#bools: 314 in floating point objective) (628 primary variables)
- 354 Booleans in [0,1]
- 314 in [0,6]
- 40 in [0,7]
#kLinear2: 865
#kLinear3: 1
#kLinearN: 227 (#terms: 2'229)
Starting presolve at 0.00s
The solution hint is complete and is feasible.
[Scaling] Floating point objective has 314 terms with magnitude in [0.140862, 190.901] average = 35.1267
[Scaling] Objective coefficient relative error: 4.44741e-06
[Scaling] Objective worst-case absolute error: 8.26922e-05
[Scaling] Objective scaling factor: 524288
2.12e-04s 0.00e+00d [DetectDominanceRelations]
4.58e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
1.54e-05s 0.00e+00d [ExtractEncodingFromLinear] #potential_supersets=145
9.19e-05s 0.00e+00d [DetectDuplicateColumns]
7.36e-05s 0.00e+00d [DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 2'666 nodes and 4'984 arcs.
[Symmetry] Symmetry computation done. time: 0.000306732 dtime: 0.00047967
[SAT presolve] num removable Booleans: 0 / 354
[SAT presolve] num trivial clauses: 0
[SAT presolve] [0s] clauses:157 literals:314 vars:314 one_side_vars:314 simple_definition:0 singleton_clauses:0
[SAT presolve] [1.0112e-05s] clauses:157 literals:314 vars:314 one_side_vars:314 simple_definition:0 singleton_clauses:0
[SAT presolve] [1.6475e-05s] clauses:157 literals:314 vars:314 one_side_vars:314 simple_definition:0 singleton_clauses:0
2.48e-04s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
1.14e-02s 3.89e-03d [Probe] #probed=1'416 #new_binary_clauses=354
6.79e-04s 2.15e-04d [MaxClique] Merged 262 constraints with 776 literals into 142 constraints with 536 literals
2.57e-04s 0.00e+00d [DetectDominanceRelations]
3.12e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
8.21e-04s 0.00e+00d [ProcessAtMostOneAndLinear] #num_changes=354
1.06e-04s 0.00e+00d [DetectDuplicateConstraints]
9.30e-05s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
1.99e-04s 6.08e-06d [DetectDominatedLinearConstraints] #relevant_constraints=83 #num_inclusions=41
1.29e-05s 0.00e+00d [DetectDifferentVariables]
8.69e-04s 7.01e-05d [ProcessSetPPC] #relevant_constraints=184 #num_inclusions=182
1.10e-04s 0.00e+00d [TransformClausesToExactlyOne] #num_amos=142
2.93e-04s 0.00e+00d [DetectEncodedComplexDomains]
1.68e-05s 1.65e-07d [FindAlmostIdenticalLinearConstraints] #num_tested_pairs=3
1.25e-04s 9.42e-05d [FindBigAtMostOneAndLinearOverlap]
9.81e-05s 1.07e-04d [FindBigVerticalLinearOverlap]
1.36e-05s 5.27e-06d [FindBigHorizontalLinearOverlap] #linears=80
9.94e-06s 0.00e+00d [MergeClauses]
2.22e-04s 0.00e+00d [DetectDominanceRelations]
3.71e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
5.36e-04s 0.00e+00d [DetectDominanceRelations]
1.82e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
9.02e-05s 0.00e+00d [DetectDuplicateColumns]
1.28e-04s 0.00e+00d [DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 2'412 nodes and 4'137 arcs.
[Symmetry] Symmetry computation done. time: 0.000229899 dtime: 0.00043586
[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] [9.247e-06s] clauses:37 literals:74 vars:74 one_side_vars:74 simple_definition:0 singleton_clauses:0
[SAT presolve] [2.0816e-05s] clauses:37 literals:74 vars:74 one_side_vars:74 simple_definition:0 singleton_clauses:0
2.13e-04s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
4.56e-03s 1.27e-03d [Probe] #probed=708
4.84e-04s 1.45e-04d [MaxClique]
2.11e-04s 0.00e+00d [DetectDominanceRelations]
2.03e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
7.93e-05s 0.00e+00d [ProcessAtMostOneAndLinear]
7.49e-05s 0.00e+00d [DetectDuplicateConstraints]
5.99e-05s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
1.16e-04s 4.59e-06d [DetectDominatedLinearConstraints] #relevant_constraints=82 #num_inclusions=40
1.11e-05s 0.00e+00d [DetectDifferentVariables]
7.01e-05s 3.03e-06d [ProcessSetPPC] #relevant_constraints=183
8.37e-05s 0.00e+00d [TransformClausesToExactlyOne] #num_amos=142
2.64e-04s 0.00e+00d [DetectEncodedComplexDomains]
1.60e-05s 1.10e-07d [FindAlmostIdenticalLinearConstraints] #num_tested_pairs=2
1.23e-04s 9.14e-05d [FindBigAtMostOneAndLinearOverlap]
8.96e-05s 1.07e-04d [FindBigVerticalLinearOverlap]
1.17e-05s 5.27e-06d [FindBigHorizontalLinearOverlap] #linears=80
8.66e-06s 0.00e+00d [MergeClauses]
2.15e-04s 0.00e+00d [DetectDominanceRelations]
2.45e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
3.46e-06s 0.00e+00d [MergeNoOverlap]
3.57e-06s 0.00e+00d [MergeNoOverlap2D]
1.39e-04s 0.00e+00d [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 'TODO linear2: convert ax + by != cte to clauses for large domains' was applied 2'124 times.
- rule 'at_most_one: transformed into max clique' was applied 1 time.
- rule 'bool_or: implications' was applied 157 times.
- rule 'deductions: 708 stored' was applied 1 time.
- rule 'linear + amo: extracted enforcement literal' was applied 354 times.
- rule 'linear2: contains a boolean' was applied 354 times.
- rule 'linear2: convert ax + by != cte to clauses' was applied 157 times.
- rule 'linear: positive at most one' was applied 105 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 'optiwindnet': (model_fingerprint: 0xbceb3d0f5e9b4ebe)
#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.000251257 dtime: 0.00043646
Preloading model.
#Bound 0.04s best:inf next:[1364.00132,11449.6914] initial_domain
#1 0.04s best:1645.69852 next:[1364.00132,1645.69852] complete_hint
#Model 0.05s var:708/708 constraints:972/972
Starting search at 0.05s with 16 workers.
11 full problem subsolvers: [core, default_lp, lb_tree_search, max_lp, no_lp, objective_lb_search, probing, pseudo_costs, quick_restart, quick_restart_no_lp, reduced_costs]
5 first solution subsolvers: [fj(2), fs_random, fs_random_no_lp, fs_random_quick_restart_no_lp]
11 interleaved subsolvers: [feasibility_pump, graph_arc_lns, graph_cst_lns, graph_dec_lns, graph_var_lns, lb_relax_lns, ls, ls_lin, rins/rens, rnd_cst_lns, rnd_var_lns]
3 helper subsolvers: [neighborhood_helper, synchronization_agent, update_gap_integral]
#2 0.06s best:1629.22229 next:[1364.00132,1629.22229] no_lp [hint] (fixed_bools=0/354)
#Bound 0.06s best:1629.22229 next:[1377.09321,1629.22229] am1_presolve (num_literals=314 num_am1=11 increase=6863921 work_done=1181)
#Bound 0.06s best:1629.22229 next:[1402.64487,1629.22229] objective_lb_search
#Bound 0.06s best:1629.22229 next:[1409.52721,1629.22229] pseudo_costs
#Bound 0.07s best:1629.22229 next:[1409.68956,1629.22229] probing
#Bound 0.07s best:1629.22229 next:[1499.2973,1629.22229] lb_tree_search
#3 0.08s best:1628.56605 next:[1499.2973,1628.56605] quick_restart_no_lp (fixed_bools=0/366)
#4 0.09s best:1624.35452 next:[1499.2973,1624.35452] rnd_cst_lns (d=7.07e-01 s=22 t=0.10 p=1.00 stall=1 h=base)
#5 0.09s best:1620.81203 next:[1499.2973,1620.81203] graph_var_lns (d=7.07e-01 s=23 t=0.10 p=1.00 stall=1 h=base)
#6 0.10s best:1620.1558 next:[1499.2973,1620.1558] graph_var_lns (d=7.07e-01 s=23 t=0.10 p=1.00 stall=1 h=base) [combined with: quick_restart_no_lp...]
#7 0.10s best:1608.69336 next:[1499.2973,1608.69336] quick_restart_no_lp (fixed_bools=0/372)
#8 0.11s best:1608.24843 next:[1499.2973,1608.24843] quick_restart_no_lp (fixed_bools=0/375)
#Bound 0.12s best:1608.24843 next:[1508.6868,1608.24843] lb_tree_search
#Bound 0.13s best:1608.24843 next:[1510.86835,1608.24843] max_lp
#Bound 0.14s best:1608.24843 next:[1511.62243,1608.24843] max_lp
#Model 0.16s var:696/708 constraints:959/972
#9 0.16s best:1594.62232 next:[1511.62243,1594.62232] graph_arc_lns (d=7.07e-01 s=25 t=0.10 p=1.00 stall=0 h=base)
#10 0.17s best:1594.1774 next:[1511.62243,1594.17739] graph_arc_lns (d=7.07e-01 s=25 t=0.10 p=1.00 stall=0 h=base) [combined with: quick_restart_no_lp...]
#11 0.19s best:1593.08762 next:[1511.62243,1593.08762] quick_restart_no_lp (fixed_bools=6/386)
#Model 0.23s var:694/708 constraints:957/972
#Bound 0.27s best:1593.08762 next:[1512.29863,1593.08762] max_lp
#12 0.29s best:1588.29611 next:[1512.29863,1588.2961] quick_restart_no_lp (fixed_bools=7/388)
#Bound 0.29s best:1588.29611 next:[1512.70322,1588.2961] objective_lb_search
#Bound 0.33s best:1588.29611 next:[1523.53914,1588.2961] lb_tree_search
#Bound 0.34s best:1588.29611 next:[1524.9632,1588.2961] max_lp
#13 0.35s best:1582.27954 next:[1524.9632,1582.27954] quick_restart_no_lp (fixed_bools=19/390)
#Model 0.37s var:672/708 constraints:933/972
#Bound 0.38s best:1582.27954 next:[1525.07248,1582.27954] lb_tree_search (nodes=2/2 rc=0 decisions=9 @root=2 restarts=0 lp_iters=[0, 0, 116, 119])
#Bound 0.38s best:1582.27954 next:[1525.07852,1582.27954] lb_tree_search (nodes=2/2 rc=0 decisions=10 @root=2 restarts=0 lp_iters=[0, 0, 120, 119])
#Bound 0.40s best:1582.27954 next:[1526.46836,1582.27954] lb_tree_search (nodes=3/3 rc=0 decisions=15 @root=2 restarts=0 lp_iters=[0, 0, 173, 168])
#Bound 0.41s best:1582.27954 next:[1526.47914,1582.27954] lb_tree_search (nodes=3/3 rc=0 decisions=16 @root=2 restarts=0 lp_iters=[0, 0, 245, 168])
#Bound 0.42s best:1582.27954 next:[1526.62668,1582.27954] lb_tree_search (nodes=4/4 rc=0 decisions=21 @root=2 restarts=0 lp_iters=[0, 0, 298, 185])
#Bound 0.43s best:1582.27954 next:[1526.7599,1582.27954] lb_tree_search (nodes=5/5 rc=0 decisions=31 @root=2 restarts=0 lp_iters=[0, 0, 414, 192])
#Bound 0.45s best:1582.27954 next:[1526.81281,1582.27954] lb_tree_search (nodes=6/6 rc=0 decisions=34 @root=2 restarts=0 lp_iters=[0, 0, 516, 243])
#Bound 0.46s best:1582.27954 next:[1526.87021,1582.27954] lb_tree_search (nodes=6/6 rc=0 decisions=35 @root=2 restarts=0 lp_iters=[0, 0, 617, 243])
#14 0.48s best:1580.99387 next:[1526.88985,1580.99387] graph_var_lns (d=8.14e-01 s=33 t=0.10 p=1.00 stall=0 h=base) [combined with: quick_restart_no_lp...]
#Model 0.70s var:670/708 constraints:931/972
#Model 0.79s var:656/708 constraints:915/972
#Bound 1.00s best:1580.99387 next:[1532.12612,1580.99387] max_lp [skipped_logs=13]
#Model 1.06s var:624/708 constraints:881/972
#15 1.06s best:1575.35544 next:[1532.12612,1575.35543] graph_var_lns (d=8.76e-01 s=46 t=0.10 p=1.00 stall=0 h=base)
#Model 1.09s var:622/708 constraints:879/972
#Model 1.21s var:620/708 constraints:877/972
#Model 1.50s var:606/708 constraints:862/972
#Model 1.65s var:604/708 constraints:860/972
#Model 1.73s var:596/708 constraints:852/972
#Model 1.81s var:586/708 constraints:842/972
#Bound 1.99s best:1575.35544 next:[1538.67998,1575.35543] lb_tree_search (nodes=19/19 rc=7 decisions=150 @root=6 restarts=0 lp_iters=[0, 0, 4'560, 581]) [skipped_logs=22]
#Model 2.56s var:582/708 constraints:838/972
#Bound 3.00s best:1575.35544 next:[1541.86761,1575.35543] lb_tree_search (nodes=31/31 rc=11 decisions=312 @root=6 restarts=0 lp_iters=[0, 0, 10'105, 1'202]) [skipped_logs=21]
#Model 3.12s var:576/708 constraints:831/972
#Model 3.40s var:568/708 constraints:823/972
#Model 3.51s var:564/708 constraints:819/972
#Bound 3.85s best:1575.35544 next:[1543.37889,1575.35543] lb_tree_search (nodes=50/55 rc=25 decisions=512 @root=6 restarts=0 lp_iters=[0, 0, 15'906, 1'507]) [skipped_logs=23]
#Model 4.13s var:560/708 constraints:814/972
#Bound 5.02s best:1575.35544 next:[1545.15584,1575.35543] lb_tree_search (nodes=60/68 rc=28 decisions=730 @root=8 restarts=0 lp_iters=[0, 0, 22'669, 1'913]) [skipped_logs=25]
#Bound 5.98s best:1575.35544 next:[1545.769,1575.35543] lb_tree_search (nodes=77/89 rc=37 decisions=972 @root=8 restarts=0 lp_iters=[0, 0, 30'797, 2'447]) [skipped_logs=26]
#Model 6.67s var:556/708 constraints:810/972
#Bound 6.15s best:1575.35544 next:[1545.78961,1575.35543] lb_tree_search (nodes=79/91 rc=38 decisions=1011 @root=8 restarts=0 lp_iters=[0, 0, 31'846, 2'497]) [skipped_logs=2]
#Model 7.40s var:554/708 constraints:806/972
#Model 8.08s var:548/708 constraints:799/972
#Model 8.40s var:546/708 constraints:796/972
#Model 8.71s var:534/708 constraints:783/972
#Model 9.04s var:532/708 constraints:780/972
#Bound 10.06s best:1575.35544 next:[1545.84997,1575.35543] lb_tree_search (nodes=45/45 rc=40 decisions=1156 @root=17 restarts=1 lp_iters=[0, 0, 36'678, 4'390])
#Bound 10.12s best:1575.35544 next:[1545.8705,1575.35543] lb_tree_search (nodes=46/46 rc=40 decisions=1165 @root=17 restarts=1 lp_iters=[0, 0, 36'985, 4'431])
#Bound 10.20s best:1575.35544 next:[1545.89946,1575.35543] lb_tree_search (nodes=47/47 rc=40 decisions=1172 @root=17 restarts=1 lp_iters=[0, 0, 37'405, 4'513])
#Model 11.00s var:530/708 constraints:778/972
#Bound 11.01s best:1575.35544 next:[1546.46288,1575.35543] lb_tree_search (nodes=56/56 rc=43 decisions=1278 @root=17 restarts=1 lp_iters=[0, 0, 40'886, 4'887]) [skipped_logs=9]
#Model 11.31s var:528/708 constraints:776/972
#Model 11.35s var:526/708 constraints:774/972
#Model 11.77s var:524/708 constraints:772/972
#Model 11.86s var:522/708 constraints:770/972
#Bound 11.94s best:1575.35544 next:[1547.23899,1575.35543] lb_tree_search (nodes=66/68 rc=43 decisions=1445 @root=17 restarts=1 lp_iters=[0, 0, 47'075, 5'464]) [skipped_logs=22]
#Model 12.20s var:520/708 constraints:768/972
#Bound 12.99s best:1575.35544 next:[1548.42222,1575.35543] lb_tree_search (nodes=86/88 rc=45 decisions=1714 @root=17 restarts=1 lp_iters=[0, 0, 54'166, 5'983]) [skipped_logs=23]
#Model 13.69s var:518/708 constraints:766/972
#Model 13.92s var:516/708 constraints:763/972
#Bound 13.85s best:1575.35544 next:[1548.87363,1575.35543] lb_tree_search (nodes=95/97 rc=46 decisions=1829 @root=18 restarts=1 lp_iters=[0, 0, 58'624, 6'333]) [skipped_logs=12]
#Model 14.54s var:514/708 constraints:761/972
#Done 14.91s reduced_costs
#Done 14.92s pseudo_costs
#Bound 14.59s best:1575.35544 next:[1548.93973,1575.35543] lb_tree_search (nodes=95/97 rc=46 decisions=1842 @root=19 restarts=1 lp_iters=[0, 0, 59'056, 6'333]) [skipped_logs=0]
Task timing n [ min, max] avg dev time n [ min, max] avg dev dtime
'core': 1 [ 14.87s, 14.87s] 14.87s 0.00ns 14.87s 2 [ 1.31ms, 11.31s] 5.65s 5.65s 11.31s
'default_lp': 1 [ 14.87s, 14.87s] 14.87s 0.00ns 14.87s 2 [ 22.49ms, 6.91s] 3.47s 3.44s 6.93s
'feasibility_pump': 69 [835.19us, 25.64ms] 1.59ms 2.93ms 110.02ms 68 [145.21us, 14.25ms] 365.92us 1.70ms 24.88ms
'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': 39 [ 15.18ms, 443.40ms] 202.24ms 141.92ms 7.89s 39 [ 16.40us, 100.14ms] 49.63ms 40.39ms 1.94s
'graph_cst_lns': 40 [ 16.49ms, 416.40ms] 200.37ms 163.92ms 8.01s 40 [ 20.89us, 100.12ms] 50.30ms 46.32ms 2.01s
'graph_dec_lns': 39 [701.90us, 422.57ms] 178.95ms 156.21ms 6.98s 37 [ 10.00ns, 100.19ms] 50.72ms 46.80ms 1.88s
'graph_var_lns': 38 [887.02us, 426.35ms] 213.05ms 145.67ms 8.10s 37 [ 10.00ns, 100.14ms] 55.40ms 42.09ms 2.05s
'lb_relax_lns': 11 [ 86.60ms, 1.46s] 671.55ms 554.39ms 7.39s 11 [ 11.83ms, 514.23ms] 238.61ms 222.98ms 2.62s
'lb_tree_search': 1 [ 14.87s, 14.87s] 14.87s 0.00ns 14.87s 2 [ 57.26ms, 7.54s] 3.80s 3.74s 7.60s
'ls': 32 [188.28ms, 252.29ms] 218.08ms 16.83ms 6.98s 32 [100.00ms, 100.01ms] 100.01ms 3.01us 3.20s
'ls_lin': 32 [183.79ms, 269.72ms] 219.36ms 22.44ms 7.02s 32 [100.00ms, 100.01ms] 100.01ms 3.28us 3.20s
'max_lp': 1 [ 14.87s, 14.87s] 14.87s 0.00ns 14.87s 2 [ 65.57ms, 6.81s] 3.44s 3.37s 6.87s
'no_lp': 1 [ 14.87s, 14.87s] 14.87s 0.00ns 14.87s 2 [ 1.49ms, 8.89s] 4.44s 4.44s 8.89s
'objective_lb_search': 1 [ 14.87s, 14.87s] 14.87s 0.00ns 14.87s 2 [ 23.99ms, 8.08s] 4.05s 4.03s 8.10s
'probing': 1 [ 14.88s, 14.88s] 14.88s 0.00ns 14.88s 2 [ 29.18ms, 8.68s] 4.36s 4.33s 8.71s
'pseudo_costs': 1 [ 14.87s, 14.87s] 14.87s 0.00ns 14.87s 2 [ 7.71ms, 6.20s] 3.10s 3.09s 6.20s
'quick_restart': 1 [ 14.87s, 14.87s] 14.87s 0.00ns 14.87s 2 [ 20.93ms, 7.42s] 3.72s 3.70s 7.44s
'quick_restart_no_lp': 1 [ 14.90s, 14.90s] 14.90s 0.00ns 14.90s 2 [ 1.58ms, 10.76s] 5.38s 5.38s 10.76s
'reduced_costs': 1 [ 14.87s, 14.87s] 14.87s 0.00ns 14.87s 2 [ 8.27ms, 8.90s] 4.45s 4.45s 8.91s
'rins/rens': 33 [ 2.40ms, 448.36ms] 214.34ms 172.11ms 7.07s 30 [ 35.32us, 100.21ms] 60.30ms 46.11ms 1.81s
'rnd_cst_lns': 34 [ 5.54ms, 408.38ms] 208.63ms 154.99ms 7.09s 34 [ 10.00ns, 100.14ms] 54.41ms 46.30ms 1.85s
'rnd_var_lns': 39 [ 4.42ms, 393.11ms] 194.49ms 145.38ms 7.58s 39 [ 10.00ns, 100.22ms] 52.60ms 44.39ms 2.05s
Search stats Bools Conflicts Branches Restarts BacktrackToRoot Backtrack BoolPropag IntegerPropag
'core': 365 229'645 434'490 292 11'005 240'893 3'736'456 9'473'429
'default_lp': 407 1'771 39'808 15 11'957 18'647 297'498 1'278'673
'fs_random': 0 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0 0
'lb_tree_search': 354 65 28'656 0 10'101 13'473 166'350 877'958
'max_lp': 354 2'041 31'226 10 10'276 15'391 218'978 1'126'089
'no_lp': 354 140'345 243'042 471 12'669 152'644 6'352'508 21'896'584
'objective_lb_search': 397 1'222 37'766 13 12'537 18'143 260'895 1'215'367
'probing': 394 25 1'007 0 863 881 9'589 30'750
'pseudo_costs': 354 1'838 45'956 21 14'776 21'124 308'497 1'579'250
'quick_restart': 385 479 59'228 27 20'195 28'085 357'059 1'724'273
'quick_restart_no_lp': 551 76'574 629'338 6'644 30'830 113'075 5'613'404 16'907'357
'reduced_costs': 360 1'894 29'212 11 8'932 13'394 160'968 851'477
SAT formula Fixed Equiv Total VarLeft BinaryClauses PermanentClauses TemporaryClauses
'core': 97 0 365 268 618 1'411 11'920
'default_lp': 98 0 407 309 792 335 1'058
'fs_random': 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0
'lb_tree_search': 101 0 354 253 592 328 4
'max_lp': 96 0 354 258 596 295 1'210
'no_lp': 98 0 354 256 626 953 11'991
'objective_lb_search': 112 0 397 285 736 342 91
'probing': 29 0 394 365 4'568 40 14
'pseudo_costs': 97 0 354 257 612 327 1'071
'quick_restart': 98 0 385 287 746 345 217
'quick_restart_no_lp': 131 0 551 420 1'900 3'055 13'122
'reduced_costs': 113 0 360 247 654 283 1'277
SAT stats ClassicMinim LitRemoved LitRemovedBinary LitLearned LitForgotten Subsumed
'core': 205'153 3'129'017 1'136'233 10'999'787 6'747'716 71'794
'default_lp': 1'390 21'880 28'707 57'282 0 434
'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': 11 32 508 571 0 29
'max_lp': 1'818 48'335 34'615 94'210 0 567
'no_lp': 107'724 1'193'262 392'462 4'483'129 2'628'188 37'997
'objective_lb_search': 1'052 32'021 10'582 20'183 0 503
'probing': 14 68 265 2'177 0 4
'pseudo_costs': 1'494 25'100 28'716 71'174 0 410
'quick_restart': 310 4'277 5'949 11'958 0 137
'quick_restart_no_lp': 61'069 506'057 812'591 2'450'901 1'398'834 14'341
'reduced_costs': 1'535 22'422 17'490 106'895 0 314
Vivification Clauses Decisions LitTrue Subsumed LitRemoved DecisionReused Conflicts
'core': 9'991 89'717 0 1'316 17'263 10'134 119
'default_lp': 6'114 25'139 1 322 1'671 1'116 7
'fs_random': 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0
'lb_tree_search': 4'370 17'876 0 366 1'751 644 3
'max_lp': 4'890 18'472 1 377 1'889 813 7
'no_lp': 8'198 42'534 2 683 6'238 5'896 37
'objective_lb_search': 6'151 24'832 1 294 1'423 1'091 4
'probing': 0 0 0 0 0 0 0
'pseudo_costs': 7'541 30'196 1 403 2'036 1'238 14
'quick_restart': 9'090 38'683 1 328 1'573 1'471 10
'quick_restart_no_lp': 23'088 135'536 9 2'585 22'423 14'320 390
'reduced_costs': 3'209 14'530 0 164 910 496 1
Clause deletion at_true l_and_not(l) to_binary sub_conflict sub_extra sub_decisions sub_eager sub_vivify sub_probing sub_inpro blocked eliminated forgotten promoted conflicts
'core': 819 28 2 67'513 2'175 15 4'281 1'316 82 429 0 0 140'434 568'820 229'645
'default_lp': 125 9 4 402 1 7 32 322 183 121 0 0 0 3'837 1'771
'fs_random': 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
'lb_tree_search': 84 3 0 28 0 0 1 366 130 44 0 0 0 25 65
'max_lp': 89 0 3 530 6 11 37 377 90 173 0 0 0 5'207 2'041
'no_lp': 4'813 117 2 35'977 3'415 295 2'020 683 136 314 0 0 80'188 321'363 140'345
'objective_lb_search': 522 38 2 451 0 28 52 294 167 68 0 0 0 1'800 1'222
'probing': 0 0 0 4 0 0 0 0 0 0 0 0 0 34 25
'pseudo_costs': 218 11 3 382 3 5 28 403 152 111 0 0 0 4'029 1'838
'quick_restart': 97 0 3 127 0 8 10 328 157 65 0 0 0 727 479
'quick_restart_no_lp': 3'575 4 37 13'290 509 151 1'051 2'585 679 742 0 0 37'582 163'606 76'574
'reduced_costs': 185 13 3 300 1 24 14 164 91 104 0 0 0 7'310 1'894
Lp stats Component Iterations AddedCuts OPTIMAL DUAL_F. DUAL_U.
'default_lp': 1 115'068 2'225 5'313 1 237
'lb_tree_search': 1 72'845 1'536 1'919 603 3
'max_lp': 1 105'539 2'194 4'252 928 229
'objective_lb_search': 1 114'892 2'206 3'842 1 187
'probing': 1 29'482 2'371 345 0 2
'pseudo_costs': 1 96'531 2'105 4'172 837 228
'quick_restart': 1 61'622 2'411 1'857 0 37
'reduced_costs': 1 128'375 1'969 3'198 1'184 269
Lp dimension Final dimension of first component
'default_lp': 720 rows, 669 columns, 9388 entries
'lb_tree_search': 785 rows, 708 columns, 13000 entries
'max_lp': 618 rows, 708 columns, 6468 entries
'objective_lb_search': 823 rows, 669 columns, 11640 entries
'probing': 1809 rows, 669 columns, 59392 entries
'pseudo_costs': 721 rows, 708 columns, 10327 entries
'quick_restart': 953 rows, 669 columns, 18375 entries
'reduced_costs': 812 rows, 708 columns, 11093 entries
Lp debug CutPropag CutEqPropag Adjust Overflow Bad BadScaling
'default_lp': 0 0 5'537 0 15'698 0
'lb_tree_search': 0 0 2'524 0 35'145 0
'max_lp': 0 0 5'406 0 20'582 0
'objective_lb_search': 0 0 4'020 0 21'126 0
'probing': 0 0 344 0 53'765 0
'pseudo_costs': 0 0 5'215 0 31'208 0
'quick_restart': 0 8 1'886 0 38'248 0
'reduced_costs': 0 10 4'637 0 17'514 0
Lp pool Constraints Updates Simplif Merged Shortened Split Strengthened Cuts/Call
'default_lp': 3'397 235 8'743 0 4'258 135 166 2'225/4'670
'lb_tree_search': 2'862 728 10'600 0 5'571 284 144 1'536/2'608
'max_lp': 3'520 457 9'244 0 6'000 143 226 2'194/4'277
'objective_lb_search': 3'378 307 9'710 0 5'169 111 135 2'206/4'345
'probing': 3'543 556 4'986 0 2'046 812 44 2'371/4'036
'pseudo_costs': 3'431 583 10'482 0 4'617 355 190 2'105/4'154
'quick_restart': 3'583 490 14'982 0 7'571 372 131 2'411/4'288
'reduced_costs': 3'295 311 7'126 0 4'180 96 132 1'969/3'681
Lp Cut reduced_costs default_lp max_lp quick_restart pseudo_costs lb_tree_search objective_lb_search probing
CG_FF: 19 21 26 15 17 15 20 15
CG_K: 13 16 21 16 7 14 15 13
CG_KL: 1 3 3 3 3 6 1 2
CG_R: 41 40 38 20 40 18 29 20
CG_RB: 69 77 77 34 68 28 54 29
CG_RBP: 30 45 28 20 27 14 20 20
Clique: 3 - 7 - 7 4 - -
IB: 654 778 565 496 712 200 562 430
MIR_1_FF: 120 102 83 171 87 123 96 203
MIR_1_K: 8 17 12 34 7 13 34 44
MIR_1_KL: 10 13 14 30 9 20 17 40
MIR_1_R: 1 7 5 5 4 3 3 9
MIR_1_RB: 34 40 37 43 33 16 42 52
MIR_1_RBP: 18 42 21 62 22 50 37 33
MIR_2_FF: 91 85 86 117 92 104 84 143
MIR_2_K: 27 31 20 47 14 26 54 54
MIR_2_KL: 16 10 8 24 16 21 15 27
MIR_2_R: 5 5 13 5 11 2 3 2
MIR_2_RB: 75 54 84 60 66 37 69 46
MIR_2_RBP: 26 45 21 57 28 26 54 57
MIR_3_FF: 81 68 77 82 72 83 45 80
MIR_3_K: 15 36 21 53 20 15 32 48
MIR_3_KL: 9 12 11 16 11 5 7 8
MIR_3_R: 3 6 14 11 7 2 5 5
MIR_3_RB: 45 43 78 50 62 51 46 40
MIR_3_RBP: 19 39 24 50 18 21 49 43
MIR_4_FF: 66 45 78 52 67 54 38 57
MIR_4_K: 23 26 24 26 28 18 35 47
MIR_4_KL: 6 7 11 11 11 9 11 11
MIR_4_R: 4 4 6 8 7 3 10 7
MIR_4_RB: 32 37 64 37 39 30 36 26
MIR_4_RBP: 19 24 30 28 23 17 40 29
MIR_5_FF: 28 16 53 32 36 38 27 38
MIR_5_K: 20 27 25 28 11 15 21 28
MIR_5_KL: 4 13 12 14 4 5 9 5
MIR_5_R: 3 3 6 6 2 2 2 3
MIR_5_RB: 28 28 36 18 32 32 19 20
MIR_5_RBP: 19 22 36 40 19 14 31 14
MIR_6_FF: 29 12 35 22 21 31 19 16
MIR_6_K: 27 20 28 35 20 28 24 21
MIR_6_KL: 10 8 19 16 16 11 13 9
MIR_6_R: 4 2 5 3 3 2 2 3
MIR_6_RB: 23 18 27 13 19 17 19 8
MIR_6_RBP: 21 29 20 48 25 31 44 26
ZERO_HALF_FF: 9 16 18 7 15 5 24 15
ZERO_HALF_K: - 5 9 1 1 1 13 10
ZERO_HALF_KL: 1 4 3 2 9 - 5 1
ZERO_HALF_R: 132 199 197 379 192 212 297 377
ZERO_HALF_RB: 22 9 44 39 32 33 51 80
ZERO_HALF_RBP: 6 16 14 25 13 11 23 57
LNS stats Improv/Calls Closed Difficulty TimeLimit
'graph_arc_lns': 19/39 54% 8.60e-01 0.10
'graph_cst_lns': 19/40 60% 9.47e-01 0.10
'graph_dec_lns': 16/38 58% 9.36e-01 0.10
'graph_var_lns': 23/37 59% 9.38e-01 0.10
'lb_relax_lns': 7/11 64% 8.44e-01 0.50
'rins/rens': 29/33 48% 7.17e-01 0.10
'rnd_cst_lns': 8/34 50% 8.25e-01 0.10
'rnd_var_lns': 16/39 64% 9.67e-01 0.10
LS stats Batches Restarts/Perturbs LinMoves GenMoves CompoundMoves Bactracks WeightUpdates ScoreComputed
'ls_lin_restart': 3 3 58'028 0 0 0 39'817 1'604'828
'ls_lin_restart_compound': 6 6 0 155'148 12'158 71'479 1'045 2'949'634
'ls_lin_restart_compound_perturb': 4 4 0 100'124 8'452 45'832 728 1'912'682
'ls_lin_restart_decay': 1 1 23'098 0 0 0 972 401'284
'ls_lin_restart_decay_compound': 1 1 0 25'738 3'317 11'206 33 495'895
'ls_lin_restart_decay_compound_perturb': 7 5 0 179'185 23'917 77'598 227 3'524'424
'ls_lin_restart_decay_perturb': 1 1 24'812 0 0 0 1'266 409'378
'ls_lin_restart_perturb': 9 7 167'364 0 0 0 86'318 4'964'661
'ls_restart': 3 3 58'039 0 0 0 21'493 1'692'377
'ls_restart_compound': 7 5 0 180'648 12'950 83'832 905 3'286'511
'ls_restart_compound_perturb': 2 2 0 51'625 3'826 23'891 254 980'260
'ls_restart_decay': 4 3 94'380 0 0 0 4'404 1'644'070
'ls_restart_decay_compound': 3 3 0 71'706 11'582 30'053 170 1'528'644
'ls_restart_decay_compound_perturb': 8 6 0 200'032 29'541 85'231 320 4'184'650
'ls_restart_decay_perturb': 4 4 97'481 0 0 0 4'696 1'610'826
'ls_restart_perturb': 1 1 19'677 0 0 0 6'865 618'175
Solutions (15) Num Rank
'complete_hint': 2 [0,1]
'graph_arc_lns': 4 [8,10]
'graph_var_lns': 8 [4,15]
'no_lp': 2 [1,2]
'quick_restart_no_lp': 12 [2,13]
'rnd_cst_lns': 2 [3,4]
Objective bounds Num
'am1_presolve': 1
'initial_domain': 1
'lb_tree_search': 223
'max_lp': 5
'objective_lb_search': 2
'probing': 1
'pseudo_costs': 1
Solution repositories Added Queried Synchro
'alternative_path': 2 114 2
'best_solutions': 26 237 22
'fj solution hints': 0 0 0
'lp solutions': 140 33 109
'pump': 0 0
Improving bounds shared Num Sym
'default_lp': 2 0
'lb_tree_search': 74 0
'max_lp': 76 0
'no_lp': 4 0
'probing': 4 0
'pseudo_costs': 4 0
'quick_restart': 9 0
'quick_restart_no_lp': 39 0
'reduced_costs': 45 0
Clauses shared #Exported #Imported #BinaryRead #BinaryTotal
'core': 488 1'049 1'494 1'499
'default_lp': 149 1'074 1'498 1'499
'lb_tree_search': 27 1'136 1'499 1'499
'max_lp': 111 834 1'362 1'499
'no_lp': 824 656 1'499 1'499
'objective_lb_search': 79 1'076 1'493 1'499
'probing': 1'040 0 280 1'499
'pseudo_costs': 194 1'026 1'490 1'499
'quick_restart': 109 1'058 1'494 1'499
'quick_restart_no_lp': 1'017 764 1'493 1'499
'reduced_costs': 87 623 1'183 1'499
LRAT_status: NA
[Scaling] scaled_objective_bound: 1575.36 corrected_bound: 1575.36 delta: 1.00542e-06
CpSolverResponse summary:
status: OPTIMAL
objective: 1575.355435923973
best_bound: 1575.355435314589
integers: 0
booleans: 0
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 0
restarts: 0
lp_iterations: 0
walltime: 14.9516
usertime: 14.9516
deterministic_time: 114.369
gap_integral: 108.307
solution_fingerprint: 0x74f029e2c7dc518
[9]:
wfn.solution_info()
[9]:
{'router': 'MILPRouter',
'capacity': 7,
'solver_name': 'ortools.cp_sat',
'mip_gap': 0.005,
'time_limit': 60,
'topology': <Topology.BRANCHED: 'branched'>,
'feeder_route': <FeederRoute.SEGMENTED: 'segmented'>,
'feeder_limit': <FeederLimit.UNLIMITED: 'unlimited'>,
'balanced': False,
'runtime': 14.954764,
'bound': 1575.3554353145887,
'objective': 1575.3554359239731,
'relgap': 3.868234621506872e-10,
'termination': 'OPTIMAL'}
[10]:
wfn.length()
[10]:
1575.355435923973
[11]:
wfn
[11]:
MILPRouter has two optional arguments: ModelOptions (what kind of solution you want, e.g., topology='branched', 'radial', or 'ringed') and SolverOptions (how long/how hard the solver searches). For more details about ModelOptions and SolverOptions see ModelOptions vs SolverOptions.
[12]:
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.cp_sat', time_limit=60, mip_gap=0.01, model_options=model_options, verbose=True)
res = wfn.optimize(router=router)
IntegerBoundsPreprocessor 1133 rows, 708 columns, 4276 entries with magnitude in [1.000000e+00, 7.000000e+00]
BoundPropagationPreprocessor 1133 rows, 708 columns, 4276 entries with magnitude in [1.000000e+00, 7.000000e+00]
ImpliedIntegerPreprocessor 1133 rows, 708 columns, 4276 entries with magnitude in [1.000000e+00, 7.000000e+00]
IntegerBoundsPreprocessor 1133 rows, 708 columns, 4276 entries with magnitude in [1.000000e+00, 7.000000e+00]
ReduceCostOverExclusiveOrConstraintPreprocessor 1133 rows, 708 columns, 4276 entries with magnitude in [1.000000e+00, 7.000000e+00]
Scaling to pure integer problem.
Num integers: 708/708 (implied: 0 in_inequalities: 0 max_scaling: 0) [IP]
Maximum constraint coefficient relative error: 0
Maximum constraint worst-case activity error: 0
Constraint scaling factor range: [1, 1]
Starting CP-SAT solver v9.15.6755
Parameters: max_time_in_seconds: 60 log_search_progress: true catch_sigint_signal: false relative_gap_limit: 0.01
Setting number of workers to 16
Initial optimization model 'optiwindnet': (model_fingerprint: 0xf49e5e1dfb1a5131)
#Variables: 708 (#bools: 314 in floating point objective) (627 primary variables)
- 354 Booleans in [0,1]
- 314 in [0,6]
- 40 in [0,7]
#kLinear2: 865
#kLinear3: 2
#kLinearN: 266 (#terms: 2'540)
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 314 terms with magnitude in [0.140862, 190.901] average = 35.1267
[Scaling] Objective coefficient relative error: 4.44741e-06
[Scaling] Objective worst-case absolute error: 8.26922e-05
[Scaling] Objective scaling factor: 524288
4.92e-04s 0.00e+00d [DetectDominanceRelations]
5.27e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
1.56e-05s 0.00e+00d [ExtractEncodingFromLinear] #potential_supersets=185
2.00e-04s 0.00e+00d [DetectDuplicateColumns]
2.39e-04s 0.00e+00d [DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 2'706 nodes and 5'298 arcs.
[Symmetry] Symmetry computation done. time: 0.000256052 dtime: 0.00049148
[SAT presolve] num removable Booleans: 0 / 354
[SAT presolve] num trivial clauses: 0
[SAT presolve] [0s] clauses:157 literals:314 vars:314 one_side_vars:314 simple_definition:0 singleton_clauses:0
[SAT presolve] [1.0439e-05s] clauses:157 literals:314 vars:314 one_side_vars:314 simple_definition:0 singleton_clauses:0
[SAT presolve] [1.8061e-05s] clauses:157 literals:314 vars:314 one_side_vars:314 simple_definition:0 singleton_clauses:0
3.33e-04s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
8.11e-03s 4.41e-03d [Probe] #probed=1'416 #new_binary_clauses=354
3.25e-04s 4.55e-04d [MaxClique] Merged 302 constraints with 1'090 literals into 182 constraints with 850 literals
2.08e-04s 0.00e+00d [DetectDominanceRelations]
1.87e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
5.75e-04s 0.00e+00d [ProcessAtMostOneAndLinear] #num_changes=354
7.16e-05s 0.00e+00d [DetectDuplicateConstraints]
5.71e-05s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
1.04e-04s 5.73e-06d [DetectDominatedLinearConstraints] #relevant_constraints=83 #num_inclusions=41 #num_redundant=1
9.73e-06s 0.00e+00d [DetectDifferentVariables]
1.02e-04s 6.42e-05d [ProcessSetPPC] #relevant_constraints=224 #num_inclusions=182
8.38e-05s 0.00e+00d [TransformClausesToExactlyOne] #num_amos=182
2.50e-04s 0.00e+00d [DetectEncodedComplexDomains]
1.32e-05s 1.65e-07d [FindAlmostIdenticalLinearConstraints] #num_tested_pairs=3
6.74e-04s 1.09e-03d [FindBigAtMostOneAndLinearOverlap]
1.77e-04s 6.03e-04d [FindBigVerticalLinearOverlap]
6.96e-05s 1.32e-04d [FindBigHorizontalLinearOverlap] #linears=81
1.48e-05s 0.00e+00d [MergeClauses]
1.59e-04s 0.00e+00d [DetectDominanceRelations]
2.75e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
1.72e-04s 0.00e+00d [DetectDominanceRelations]
1.92e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
5.77e-05s 0.00e+00d [DetectDuplicateColumns]
7.45e-05s 0.00e+00d [DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 2'453 nodes and 4'765 arcs.
[Symmetry] Symmetry computation done. time: 0.000254105 dtime: 0.00045598
[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] [3.1561e-05s] clauses:37 literals:74 vars:74 one_side_vars:74 simple_definition:0 singleton_clauses:0
[SAT presolve] [8.6807e-05s] clauses:37 literals:74 vars:74 one_side_vars:74 simple_definition:0 singleton_clauses:0
6.66e-05s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
4.25e-03s 1.40e-03d [Probe] #probed=708
2.08e-04s 3.09e-04d [MaxClique]
1.75e-04s 0.00e+00d [DetectDominanceRelations]
1.35e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
1.21e-04s 0.00e+00d [ProcessAtMostOneAndLinear]
7.07e-05s 0.00e+00d [DetectDuplicateConstraints]
5.96e-05s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
1.07e-04s 5.53e-06d [DetectDominatedLinearConstraints] #relevant_constraints=83 #num_inclusions=40
1.31e-05s 0.00e+00d [DetectDifferentVariables]
1.90e-04s 6.42e-05d [ProcessSetPPC] #relevant_constraints=224 #num_inclusions=182
3.60e-04s 0.00e+00d [TransformClausesToExactlyOne] #num_amos=182
3.19e-04s 0.00e+00d [DetectEncodedComplexDomains]
2.54e-05s 0.00e+00d [FindAlmostIdenticalLinearConstraints]
5.16e-04s 1.09e-03d [FindBigAtMostOneAndLinearOverlap]
1.40e-04s 6.03e-04d [FindBigVerticalLinearOverlap]
5.29e-05s 1.32e-04d [FindBigHorizontalLinearOverlap] #linears=81
1.12e-05s 0.00e+00d [MergeClauses]
1.67e-04s 0.00e+00d [DetectDominanceRelations]
1.39e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
2.62e-06s 0.00e+00d [MergeNoOverlap]
2.65e-06s 0.00e+00d [MergeNoOverlap2D]
1.18e-04s 0.00e+00d [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 'TODO linear2: convert ax + by != cte to clauses for large domains' was applied 2'124 times.
- rule 'at_most_one: transformed into max clique' was applied 1 time.
- rule 'bool_or: implications' was applied 157 times.
- rule 'deductions: 708 stored' was applied 1 time.
- rule 'linear + amo: extracted enforcement literal' was applied 354 times.
- rule 'linear inclusion: sparsify superset' was applied 1 time.
- rule 'linear2: contains a boolean' was applied 354 times.
- rule 'linear2: convert ax + by != cte to clauses' was applied 157 times.
- rule 'linear: positive at most one' was applied 145 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 'optiwindnet': (model_fingerprint: 0x510fe2cea8f40f0f)
#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.00019885 dtime: 0.00045642
Preloading model.
#Bound 0.04s best:inf next:[1364.00132,11449.6914] initial_domain
The solution hint is complete, but it is infeasible! we will try to repair it.
#Model 0.04s var:708/708 constraints:1013/1013
Starting search at 0.04s 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.05s best:inf next:[1396.24224,11449.6914] am1_presolve (num_literals=314 num_am1=12 increase=16903530 work_done=1733)
#1 0.05s best:1631.93805 next:[1396.24224,1631.93805] no_lp [hint] (fixed_bools=0/354)
#Bound 0.06s best:1631.93805 next:[1427.81903,1631.93805] probing
#Bound 0.06s best:1631.93805 next:[1434.70137,1631.93805] reduced_costs
#Bound 0.06s best:1631.93805 next:[1518.98019,1631.93805] max_lp
#2 0.09s best:1629.24862 next:[1518.98019,1629.24862] reduced_costs [hint] (fixed_bools=0/354)
#Bound 0.14s best:1629.24862 next:[1525.53027,1629.24862] max_lp
#Bound 0.14s best:1629.24862 next:[1527.255,1629.24862] lb_tree_search
#Model 0.15s var:702/708 constraints:1006/1013
#3 0.18s best:1628.51262 next:[1527.255,1628.51262] quick_restart_no_lp (fixed_bools=3/354)
#Bound 0.25s best:1628.51262 next:[1527.25504,1628.51262] objective_lb_search
#Model 0.27s var:700/708 constraints:1004/1013
#Bound 0.28s best:1628.51262 next:[1527.81306,1628.51262] lb_tree_search
#4 0.31s best:1618.50518 next:[1527.81306,1618.50518] graph_arc_lns (d=7.07e-01 s=31 t=0.10 p=1.00 stall=1 h=base) (fixed_bools=0/354)
#5 0.32s best:1614.73248 next:[1527.81306,1614.73248] lb_relax_lns_bool (d=5.00e-01 s=23 t=0.50 p=0.00 stall=0 h=base) (fixed_bools=0/354)
#Bound 0.33s best:1614.73248 next:[1528.04658,1614.73248] probing
#Model 0.34s var:698/708 constraints:1002/1013
#Bound 0.34s best:1614.73248 next:[1530.15971,1614.73248] probing
#Bound 0.38s best:1614.73248 next:[1538.01985,1614.73248] max_lp
#6 0.39s best:1613.51861 next:[1538.01985,1613.51861] graph_arc_lns (d=8.14e-01 s=41 t=0.10 p=1.00 stall=0 h=base) (fixed_bools=0/354)
#Model 0.39s var:690/708 constraints:994/1013
#Bound 0.39s best:1613.51861 next:[1539.36691,1613.51861] lb_tree_search
#Model 0.41s var:688/708 constraints:992/1013
#Model 0.43s var:686/708 constraints:990/1013
#Model 0.61s var:680/708 constraints:983/1013
#Bound 0.61s best:1613.51861 next:[1543.53679,1613.51861] lb_tree_search
#Bound 0.63s best:1613.51861 next:[1543.55217,1613.51861] lb_tree_search (nodes=2/2 rc=0 decisions=7 @root=3 restarts=0 lp_iters=[0, 0, 92, 25])
#Model 0.65s var:674/708 constraints:976/1013
#Model 0.69s var:670/708 constraints:972/1013
#7 0.72s best:1613.50867 next:[1543.55217,1613.50867] lb_relax_lns_bool_h (d=7.07e-01 s=45 t=0.50 p=1.00 stall=0 h=base) (fixed_bools=0/354)
#8 0.72s best:1612.2948 next:[1543.55217,1612.2948] lb_relax_lns_bool_h (d=7.07e-01 s=45 t=0.50 p=1.00 stall=0 h=base) [combined with: graph_arc_lns (d=8.1...] (fixed_bools=0/354)
#Bound 0.78s best:1612.2948 next:[1545.81028,1612.2948] probing
#Bound 0.88s best:1612.2948 next:[1547.46896,1612.2948] probing
#Model 0.93s var:668/708 constraints:970/1013
#Bound 1.01s best:1612.2948 next:[1548.33436,1612.2948] lb_tree_search (nodes=8/8 rc=2 decisions=47 @root=6 restarts=0 lp_iters=[0, 0, 604, 135])
#Bound 1.04s best:1612.2948 next:[1548.33866,1612.2948] lb_tree_search (nodes=8/8 rc=2 decisions=53 @root=6 restarts=0 lp_iters=[0, 0, 804, 135])
#Model 1.05s var:666/708 constraints:968/1013
#Bound 1.05s best:1612.2948 next:[1548.36613,1612.2948] lb_tree_search (nodes=9/9 rc=2 decisions=57 @root=6 restarts=0 lp_iters=[0, 0, 859, 140])
#Bound 1.07s best:1612.2948 next:[1548.41571,1612.2948] lb_tree_search (nodes=10/10 rc=2 decisions=62 @root=6 restarts=0 lp_iters=[0, 0, 992, 141])
#Bound 1.11s best:1612.2948 next:[1549.11379,1612.2948] lb_tree_search (nodes=13/13 rc=3 decisions=71 @root=6 restarts=0 lp_iters=[0, 0, 1'251, 157])
#Model 1.47s var:664/708 constraints:965/1013
#Model 1.50s var:658/708 constraints:959/1013
#Bound 2.00s best:1612.2948 next:[1558.02415,1612.2948] lb_tree_search (nodes=36/37 rc=18 decisions=287 @root=6 restarts=0 lp_iters=[0, 0, 6'293, 1'059]) [skipped_logs=27]
#Model 2.59s var:656/708 constraints:957/1013
#Bound 2.78s best:1612.2948 next:[1559.6799,1612.2948] lb_tree_search (nodes=38/40 rc=22 decisions=328 @root=8 restarts=0 lp_iters=[0, 0, 7'347, 1'108]) [skipped_logs=3]
#Model 3.11s var:654/708 constraints:954/1013
#Model 3.37s var:652/708 constraints:952/1013
#Model 3.77s var:650/708 constraints:950/1013
#Bound 3.98s best:1612.2948 next:[1564.48997,1612.2948] lb_tree_search (nodes=40/42 rc=24 decisions=449 @root=12 restarts=0 lp_iters=[0, 0, 11'331, 1'170]) [skipped_logs=19]
#Model 4.27s var:648/708 constraints:948/1013
#Model 4.68s var:646/708 constraints:945/1013
#Model 4.84s var:644/708 constraints:943/1013
#Bound 4.78s best:1612.2948 next:[1564.54676,1612.2948] lb_tree_search (nodes=40/42 rc=25 decisions=462 @root=13 restarts=0 lp_iters=[0, 0, 11'541, 1'170]) [skipped_logs=0]
#Model 5.11s var:642/708 constraints:941/1013
#Model 5.55s var:640/708 constraints:939/1013
#Bound 6.03s best:1612.2948 next:[1566.04466,1612.2948] lb_tree_search (nodes=40/42 rc=26 decisions=552 @root=16 restarts=0 lp_iters=[0, 0, 14'150, 1'170]) [skipped_logs=9]
#Bound 6.99s best:1612.2948 next:[1567.17222,1612.2948] lb_tree_search (nodes=40/42 rc=27 decisions=625 @root=19 restarts=0 lp_iters=[0, 0, 16'386, 1'389]) [skipped_logs=8]
#Model 7.49s var:638/708 constraints:937/1013
#Bound 7.99s best:1612.2948 next:[1570.2041,1612.2948] lb_tree_search (nodes=52/54 rc=35 decisions=784 @root=19 restarts=0 lp_iters=[0, 0, 21'447, 1'687]) [skipped_logs=17]
#Bound 8.94s best:1612.2948 next:[1572.04738,1612.2948] lb_tree_search (nodes=67/70 rc=41 decisions=984 @root=19 restarts=0 lp_iters=[0, 0, 27'469, 2'613]) [skipped_logs=24]
#Model 9.19s var:636/708 constraints:935/1013
#Model 10.42s var:634/708 constraints:933/1013
#Model 11.57s var:632/708 constraints:931/1013
#Bound 13.22s best:1612.2948 next:[1572.04756,1612.2948] objective_lb_search
#Bound 13.86s best:1612.2948 next:[1572.04757,1612.2948] objective_lb_search
#Bound 14.55s best:1612.2948 next:[1572.0776,1612.2948] objective_lb_search
#Model 14.67s var:630/708 constraints:929/1013
#Model 15.17s var:628/708 constraints:927/1013
#Bound 15.32s best:1612.2948 next:[1572.50608,1612.2948] objective_lb_search
#Model 15.69s var:626/708 constraints:925/1013
#Model 16.18s var:624/708 constraints:923/1013
#Model 16.25s var:622/708 constraints:921/1013
#Bound 16.38s best:1612.2948 next:[1572.51292,1612.2948] lb_tree_search (nodes=114/114 rc=51 decisions=1464 @root=32 restarts=1 lp_iters=[0, 0, 42'284, 7'287])
#Model 16.83s var:620/708 constraints:918/1013
#Bound 16.87s best:1612.2948 next:[1572.59413,1612.2948] lb_tree_search (nodes=114/114 rc=52 decisions=1477 @root=33 restarts=1 lp_iters=[0, 0, 42'644, 7'287])
#Model 17.43s var:618/708 constraints:916/1013
#Bound 17.68s best:1612.2948 next:[1572.60924,1612.2948] lb_tree_search (nodes=114/114 rc=52 decisions=1484 @root=34 restarts=1 lp_iters=[0, 0, 42'960, 7'287])
#Model 17.69s var:614/708 constraints:912/1013
#Bound 17.71s best:1612.2948 next:[1572.65313,1612.2948] lb_tree_search (nodes=114/114 rc=52 decisions=1487 @root=35 restarts=1 lp_iters=[0, 0, 43'158, 7'287])
#Bound 17.77s best:1612.2948 next:[1572.71185,1612.2948] lb_tree_search (nodes=114/114 rc=52 decisions=1497 @root=35 restarts=1 lp_iters=[0, 0, 43'414, 7'287]) [skipped_logs=1]
#Model 18.68s var:612/708 constraints:909/1013
#Bound 18.87s best:1612.2948 next:[1572.93066,1612.2948] lb_tree_search (nodes=114/114 rc=53 decisions=1524 @root=37 restarts=1 lp_iters=[0, 0, 44'854, 7'287]) [skipped_logs=2]
#Model 19.29s var:610/708 constraints:907/1013
#Bound 19.41s best:1612.2948 next:[1572.93167,1612.2948] lb_tree_search (nodes=115/115 rc=53 decisions=1537 @root=38 restarts=1 lp_iters=[0, 0, 45'331, 7'310]) [skipped_logs=0]
#Model 20.37s var:608/708 constraints:905/1013
#Bound 20.88s best:1612.2948 next:[1573.09736,1612.2948] lb_tree_search (nodes=115/116 rc=55 decisions=1615 @root=40 restarts=1 lp_iters=[0, 0, 48'773, 7'513]) [skipped_logs=10]
#Bound 21.89s best:1612.2948 next:[1573.16654,1612.2948] lb_tree_search (nodes=115/116 rc=55 decisions=1684 @root=42 restarts=1 lp_iters=[0, 0, 52'066, 7'513]) [skipped_logs=7]
#Bound 22.97s best:1612.2948 next:[1573.47279,1612.2948] lb_tree_search (nodes=127/128 rc=56 decisions=1803 @root=42 restarts=1 lp_iters=[0, 0, 58'478, 7'838]) [skipped_logs=15]
#Model 23.86s var:606/708 constraints:903/1013
#Bound 23.97s best:1612.2948 next:[1573.87061,1612.2948] lb_tree_search (nodes=133/134 rc=60 decisions=1933 @root=42 restarts=1 lp_iters=[0, 0, 64'714, 8'171]) [skipped_logs=14]
#Model 24.55s var:604/708 constraints:901/1013
#Model 24.73s var:602/708 constraints:899/1013
#Bound 24.42s best:1612.2948 next:[1573.92493,1612.2948] lb_tree_search (nodes=137/138 rc=60 decisions=2003 @root=42 restarts=1 lp_iters=[0, 0, 68'102, 8'233]) [skipped_logs=6]
#Model 25.98s var:600/708 constraints:897/1013
#Model 26.12s var:598/708 constraints:895/1013
#Bound 26.91s best:1612.2948 next:[1574.07833,1612.2948] objective_lb_search
#Model 27.21s var:596/708 constraints:893/1013
#Model 28.03s var:594/708 constraints:891/1013
#Model 28.16s var:592/708 constraints:889/1013
#Bound 28.57s best:1612.2948 next:[1574.10337,1612.2948] objective_lb_search
#Bound 29.67s best:1612.2948 next:[1574.11185,1612.2948] lb_tree_search (nodes=164/165 rc=69 decisions=2502 @root=45 restarts=2 lp_iters=[0, 0, 84'302, 16'856])
#Model 30.18s var:590/708 constraints:886/1013
#Bound 30.67s best:1612.2948 next:[1574.1253,1612.2948] lb_tree_search (nodes=164/165 rc=70 decisions=2518 @root=46 restarts=2 lp_iters=[0, 0, 84'801, 16'856])
#Bound 31.89s best:1612.2948 next:[1574.16877,1612.2948] lb_tree_search (nodes=165/166 rc=71 decisions=2552 @root=48 restarts=2 lp_iters=[0, 0, 86'128, 16'895])
#Bound 32.46s best:1612.2948 next:[1574.17239,1612.2948] lb_tree_search (nodes=165/166 rc=71 decisions=2564 @root=49 restarts=2 lp_iters=[0, 0, 86'639, 16'895])
#Bound 32.51s best:1612.2948 next:[1574.19516,1612.2948] lb_tree_search (nodes=165/166 rc=71 decisions=2569 @root=50 restarts=2 lp_iters=[0, 0, 86'948, 16'895])
#Bound 32.58s best:1612.2948 next:[1574.20502,1612.2948] lb_tree_search (nodes=166/167 rc=71 decisions=2578 @root=50 restarts=2 lp_iters=[0, 0, 87'295, 16'935]) [skipped_logs=1]
#Model 33.54s var:588/708 constraints:884/1013
#Model 33.74s var:586/708 constraints:882/1013
#Model 33.94s var:584/708 constraints:880/1013
#Bound 33.62s best:1612.2948 next:[1574.25493,1612.2948] lb_tree_search (nodes=166/167 rc=71 decisions=2600 @root=52 restarts=2 lp_iters=[0, 0, 88'173, 16'935]) [skipped_logs=1]
#Bound 34.20s best:1612.2948 next:[1574.27411,1612.2948] lb_tree_search (nodes=166/167 rc=71 decisions=2607 @root=53 restarts=2 lp_iters=[0, 0, 88'581, 16'935]) [skipped_logs=0]
#Model 35.27s var:582/708 constraints:878/1013
#Bound 36.00s best:1612.2948 next:[1574.33359,1612.2948] lb_tree_search (nodes=167/168 rc=72 decisions=2660 @root=57 restarts=2 lp_iters=[0, 0, 91'316, 16'966]) [skipped_logs=5]
#Model 36.16s var:580/708 constraints:875/1013
#Bound 36.97s best:1612.2948 next:[1574.73579,1612.2948] lb_tree_search (nodes=171/172 rc=73 decisions=2764 @root=57 restarts=2 lp_iters=[0, 0, 96'832, 17'180]) [skipped_logs=12]
#Model 37.32s var:578/708 constraints:873/1013
#Model 37.42s var:576/708 constraints:871/1013
#Bound 37.63s best:1612.2948 next:[1574.9356,1612.2948] lb_tree_search (nodes=173/175 rc=73 decisions=2830 @root=57 restarts=2 lp_iters=[0, 0, 100'835, 17'343]) [skipped_logs=8]
#Model 38.80s var:572/708 constraints:867/1013
#Bound 38.08s best:1612.2948 next:[1574.9407,1612.2948] lb_tree_search (nodes=173/175 rc=73 decisions=2839 @root=58 restarts=2 lp_iters=[0, 0, 101'255, 17'343]) [skipped_logs=0]
#Model 39.12s var:570/708 constraints:865/1013
#Model 39.26s var:566/708 constraints:859/1013
#Bound 39.07s best:1612.2948 next:[1574.94224,1612.2948] lb_tree_search (nodes=173/175 rc=73 decisions=2846 @root=59 restarts=2 lp_iters=[0, 0, 101'676, 17'343]) [skipped_logs=0]
#Model 40.32s var:562/708 constraints:854/1013
#Bound 40.80s best:1612.2948 next:[1575.14883,1612.2948] lb_tree_search (nodes=174/176 rc=75 decisions=2903 @root=61 restarts=2 lp_iters=[0, 0, 104'323, 17'386]) [skipped_logs=7]
#Model 41.99s var:560/708 constraints:852/1013
#Bound 41.75s best:1612.2948 next:[1575.177,1612.2948] lb_tree_search (nodes=174/176 rc=75 decisions=2906 @root=62 restarts=2 lp_iters=[0, 0, 104'554, 17'386]) [skipped_logs=0]
#Model 42.22s var:558/708 constraints:850/1013
#Bound 42.79s best:1612.2948 next:[1575.24057,1612.2948] lb_tree_search (nodes=153/176 rc=75 decisions=2930 @root=65 restarts=2 lp_iters=[0, 0, 105'797, 17'386]) [skipped_logs=2]
#Model 43.64s var:552/708 constraints:844/1013
#Model 43.85s var:550/708 constraints:842/1013
#Model 43.96s var:548/708 constraints:838/1013
#Bound 44.06s best:1612.2948 next:[1575.27606,1612.2948] lb_tree_search (nodes=153/176 rc=75 decisions=2972 @root=67 restarts=2 lp_iters=[0, 0, 108'380, 17'386]) [skipped_logs=5]
#Model 44.83s var:546/708 constraints:835/1013
#Bound 44.87s best:1612.2948 next:[1575.42196,1612.2948] lb_tree_search (nodes=153/176 rc=75 decisions=3008 @root=68 restarts=2 lp_iters=[0, 0, 110'517, 17'386]) [skipped_logs=4]
#Model 45.96s var:544/708 constraints:832/1013
#Bound 45.79s best:1612.2948 next:[1575.43869,1612.2948] lb_tree_search (nodes=153/176 rc=75 decisions=3016 @root=69 restarts=2 lp_iters=[0, 0, 110'879, 17'386]) [skipped_logs=0]
#Model 46.66s var:542/708 constraints:829/1013
#Bound 46.39s best:1612.2948 next:[1575.43952,1612.2948] lb_tree_search (nodes=153/176 rc=75 decisions=3027 @root=70 restarts=2 lp_iters=[0, 0, 111'432, 17'386]) [skipped_logs=0]
#Model 47.51s var:540/708 constraints:827/1013
#Model 47.73s var:538/708 constraints:825/1013
#Bound 48.02s best:1612.2948 next:[1609.86694,1612.2948] reduced_costs [skipped_logs=1]
Relative gap limit of 0.01 reached.
#Model 48.00s var:488/708 constraints:769/1013 [skipped_logs=6]
Task timing n [ min, max] avg dev time n [ min, max] avg dev dtime
'core': 1 [ 47.99s, 47.99s] 47.99s 0.00ns 47.99s 2 [ 1.47ms, 1.04m] 31.23s 31.23s 1.04m
'default_lp': 1 [ 47.99s, 47.99s] 47.99s 0.00ns 47.99s 2 [ 32.29ms, 26.03s] 13.03s 13.00s 26.06s
'feasibility_pump': 236 [962.95us, 96.24ms] 2.06ms 7.57ms 486.13ms 235 [162.57us, 48.62ms] 641.72us 4.41ms 150.80ms
'fj': 1 [ 94.93ms, 94.93ms] 94.93ms 0.00ns 94.93ms 1 [ 59.80ms, 59.80ms] 59.80ms 0.00ns 59.80ms
'fj': 1 [157.61ms, 157.61ms] 157.61ms 0.00ns 157.61ms 1 [100.02ms, 100.02ms] 100.02ms 0.00ns 100.02ms
'fs_random': 1 [ 14.37ms, 14.37ms] 14.37ms 0.00ns 14.37ms 1 [ 1.47ms, 1.47ms] 1.47ms 0.00ns 1.47ms
'fs_random_no_lp': 1 [ 13.37ms, 13.37ms] 13.37ms 0.00ns 13.37ms 1 [ 1.58ms, 1.58ms] 1.58ms 0.00ns 1.58ms
'fs_random_quick_restart_no_lp': 1 [ 13.25ms, 13.25ms] 13.25ms 0.00ns 13.25ms 1 [ 1.47ms, 1.47ms] 1.47ms 0.00ns 1.47ms
'graph_arc_lns': 108 [ 8.51ms, 481.69ms] 219.90ms 124.17ms 23.75s 108 [ 2.85us, 102.22ms] 63.68ms 40.47ms 6.88s
'graph_cst_lns': 108 [ 5.46ms, 493.57ms] 223.86ms 132.72ms 24.18s 108 [230.00ns, 100.31ms] 62.49ms 41.72ms 6.75s
'graph_dec_lns': 113 [ 2.56ms, 448.32ms] 219.27ms 136.70ms 24.78s 113 [ 10.00ns, 100.21ms] 59.13ms 42.71ms 6.68s
'graph_var_lns': 105 [ 2.52ms, 477.74ms] 225.50ms 140.67ms 23.68s 105 [ 10.00ns, 100.26ms] 59.37ms 41.81ms 6.23s
'lb_relax_lns': 30 [118.75ms, 1.54s] 784.01ms 509.64ms 23.52s 30 [ 16.89ms, 516.98ms] 293.15ms 220.48ms 8.79s
'lb_tree_search': 1 [ 47.98s, 47.98s] 47.98s 0.00ns 47.98s 2 [ 54.69ms, 23.06s] 11.56s 11.50s 23.11s
'ls': 135 [ 18.99ms, 304.61ms] 174.34ms 23.49ms 23.54s 135 [ 10.04ms, 100.03ms] 99.34ms 7.71ms 13.41s
'ls_lin': 131 [136.90ms, 269.33ms] 179.79ms 19.80ms 23.55s 131 [100.00ms, 100.03ms] 100.01ms 5.49us 13.10s
'max_lp': 1 [ 47.98s, 47.98s] 47.98s 0.00ns 47.98s 2 [ 53.12ms, 26.72s] 13.39s 13.33s 26.77s
'no_lp': 1 [ 47.98s, 47.98s] 47.98s 0.00ns 47.98s 2 [ 1.61ms, 28.51s] 14.26s 14.25s 28.51s
'objective_lb_search': 1 [ 47.98s, 47.98s] 47.98s 0.00ns 47.98s 2 [ 33.38ms, 26.07s] 13.05s 13.02s 26.10s
'probing': 1 [ 47.99s, 47.99s] 47.99s 0.00ns 47.99s 2 [ 32.29ms, 22.73s] 11.38s 11.35s 22.76s
'pseudo_costs': 1 [ 47.98s, 47.98s] 47.98s 0.00ns 47.98s 2 [ 12.12ms, 24.30s] 12.16s 12.15s 24.32s
'quick_restart': 1 [ 47.98s, 47.98s] 47.98s 0.00ns 47.98s 2 [ 41.60ms, 19.96s] 10.00s 9.96s 20.00s
'quick_restart_no_lp': 1 [ 48.00s, 48.00s] 48.00s 0.00ns 48.00s 2 [ 1.61ms, 40.00s] 20.00s 20.00s 40.00s
'reduced_costs': 1 [ 47.98s, 47.98s] 47.98s 0.00ns 47.98s 2 [ 9.59ms, 30.42s] 15.22s 15.21s 30.43s
'rins/rens': 120 [ 3.17ms, 497.04ms] 196.79ms 139.41ms 23.61s 116 [ 6.57us, 100.19ms] 56.92ms 42.88ms 6.60s
'rnd_cst_lns': 114 [ 5.37ms, 610.81ms] 211.50ms 128.34ms 24.11s 114 [145.00ns, 100.30ms] 57.85ms 40.64ms 6.59s
'rnd_var_lns': 105 [ 5.02ms, 452.70ms] 228.98ms 133.87ms 24.04s 105 [ 63.00ns, 100.23ms] 62.92ms 41.25ms 6.61s
Search stats Bools Conflicts Branches Restarts BacktrackToRoot Backtrack BoolPropag IntegerPropag
'core': 1'092 315'871 940'477 1'436 12'127 339'499 37'724'420 17'930'479
'default_lp': 354 3'306 137'810 27 37'089 49'039 1'800'373 5'925'320
'fs_random': 354 0 708 0 708 708 6'758 17'253
'fs_random_no_lp': 354 6 812 0 708 714 7'067 18'290
'fs_random_quick_restart_no_lp': 354 0 708 0 708 708 6'758 17'254
'lb_tree_search': 354 327 167'024 0 50'019 63'629 2'213'052 7'327'464
'max_lp': 354 3'764 147'223 27 38'998 51'533 1'964'378 6'511'012
'no_lp': 354 431'285 754'080 788 24'507 458'336 22'000'802 69'509'625
'objective_lb_search': 394 1'688 150'919 18 44'638 57'384 2'003'684 6'643'546
'probing': 444 61 1'137 0 1'038 1'047 20'412 55'640
'pseudo_costs': 354 4'761 172'429 34 44'881 60'602 2'223'398 7'408'653
'quick_restart': 354 1'267 235'235 50 66'031 83'490 2'987'855 9'859'236
'quick_restart_no_lp': 615 210'234 1'507'905 18'342 66'285 285'240 20'375'201 47'001'975
'reduced_costs': 358 4'806 130'627 26 32'073 45'037 1'552'350 5'154'777
SAT formula Fixed Equiv Total VarLeft BinaryClauses PermanentClauses TemporaryClauses
'core': 90 24 1'092 978 6'314 35'199 7'857
'default_lp': 225 5 354 124 482 52 652
'fs_random': 0 0 354 354 80 40 0
'fs_random_no_lp': 0 0 354 354 80 40 6
'fs_random_quick_restart_no_lp': 0 0 354 354 80 40 0
'lb_tree_search': 82 0 354 272 2'882 604 19
'max_lp': 84 0 354 270 2'808 699 1'936
'no_lp': 83 0 354 271 3'142 8'151 12'634
'objective_lb_search': 159 0 394 235 1'846 298 57
'probing': 104 0 444 340 12'468 1'863 7
'pseudo_costs': 83 0 354 271 2'736 662 2'879
'quick_restart': 85 0 354 269 2'666 686 319
'quick_restart_no_lp': 164 1 615 450 2'862 3'770 4'822
'reduced_costs': 226 0 358 132 2'156 -'217 1'714
SAT stats ClassicMinim LitRemoved LitRemovedBinary LitLearned LitForgotten Subsumed
'core': 270'111 2'962'620 1'321'492 16'335'111 10'008'340 68'328
'default_lp': 2'688 47'593 66'130 152'092 0 859
'fs_random': 0 0 0 0 0 0
'fs_random_no_lp': 6 8 27 767 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0
'lb_tree_search': 72 161 2'516 2'478 0 197
'max_lp': 3'134 63'243 74'397 157'953 0 1'040
'no_lp': 391'045 4'529'650 4'116'157 15'109'221 10'743'026 96'974
'objective_lb_search': 1'236 49'176 15'353 20'784 0 789
'probing': 8 62 476 881 0 2
'pseudo_costs': 3'829 75'927 101'436 193'825 0 1'301
'quick_restart': 719 11'063 13'410 26'865 0 585
'quick_restart_no_lp': 179'214 2'018'970 3'193'147 6'836'841 5'112'090 33'432
'reduced_costs': 3'496 46'962 55'555 285'214 0 1'199
Vivification Clauses Decisions LitTrue Subsumed LitRemoved DecisionReused Conflicts
'core': 12'948 439'753 0 2'413 103'131 32'483 514
'default_lp': 28'622 114'311 2 1'726 8'371 4'918 27
'fs_random': 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0
'lb_tree_search': 36'260 136'731 2 1'696 7'855 4'512 21
'max_lp': 30'958 123'427 1 1'899 9'107 5'284 36
'no_lp': 23'319 198'092 9 4'810 66'481 22'480 763
'objective_lb_search': 32'065 124'615 10 1'656 7'939 5'239 22
'probing': 1 2 0 1 3 0 0
'pseudo_costs': 34'486 142'453 3 1'768 8'655 6'059 39
'quick_restart': 48'873 197'361 2 1'865 8'999 7'655 44
'quick_restart_no_lp': 46'964 368'715 4 8'067 89'075 36'646 1'034
'reduced_costs': 22'890 99'593 45 1'833 9'511 5'086 78
Clause deletion at_true l_and_not(l) to_binary sub_conflict sub_extra sub_decisions sub_eager sub_vivify sub_probing sub_inpro blocked eliminated forgotten promoted conflicts
'core': 4'677 79 106 66'261 3'626 154 2'067 2'413 1'238 10'517 0 0 183'992 672'754 315'871
'default_lp': 1'540 706 43 829 9 9 30 1'726 746 250 0 0 0 7'593 3'306
'fs_random': 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0 0 0 0 0 0 0 11 6
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
'lb_tree_search': 319 0 5 195 0 8 2 1'696 949 128 0 0 0 64 327
'max_lp': 426 1 7 1'002 3 19 38 1'899 972 510 0 0 0 7'768 3'764
'no_lp': 11'165 74 16 94'345 2'848 1'113 2'629 4'810 1'052 4'994 0 0 289'799 1'008'872 431'285
'objective_lb_search': 1'127 56 29 709 0 67 80 1'656 801 141 0 0 0 1'838 1'688
'probing': 0 0 0 2 0 0 0 1 0 0 0 0 0 15 61
'pseudo_costs': 414 0 16 1'247 16 9 54 1'768 739 279 0 0 0 10'153 4'761
'quick_restart': 359 0 10 569 3 15 16 1'865 938 127 0 0 0 1'493 1'267
'quick_restart_no_lp': 8'774 41 108 31'568 1'130 409 1'864 8'067 4'814 4'189 0 0 140'942 487'025 210'234
'reduced_costs': 748 37 20 1'148 10 98 51 1'833 1'085 835 0 0 0 38'877 4'806
Lp stats Component Iterations AddedCuts OPTIMAL DUAL_F. DUAL_U.
'default_lp': 1 315'761 3'393 8'759 8 465
'fs_random': 1 0 0 0 0 0
'lb_tree_search': 1 164'729 1'660 2'772 1'266 4
'max_lp': 1 309'796 2'425 7'306 2'722 439
'objective_lb_search': 1 233'812 2'033 4'127 1 116
'probing': 1 89'904 2'540 655 9 15
'pseudo_costs': 1 327'730 3'353 8'966 2'974 635
'quick_restart': 1 148'704 2'297 3'400 3 100
'reduced_costs': 1 375'687 3'219 6'300 3'246 610
Lp dimension Final dimension of first component
'default_lp': 791 rows, 708 columns, 11464 entries
'fs_random': 0 rows, 708 columns, 0 entries
'lb_tree_search': 875 rows, 708 columns, 20760 entries
'max_lp': 767 rows, 708 columns, 14517 entries
'objective_lb_search': 791 rows, 708 columns, 14899 entries
'probing': 1201 rows, 708 columns, 33251 entries
'pseudo_costs': 763 rows, 708 columns, 11020 entries
'quick_restart': 777 rows, 708 columns, 13372 entries
'reduced_costs': 921 rows, 708 columns, 18436 entries
Lp debug CutPropag CutEqPropag Adjust Overflow Bad BadScaling
'default_lp': 0 37 9'208 0 73'602 0
'fs_random': 0 0 0 0 0 0
'lb_tree_search': 0 0 4'041 0 133'647 0
'max_lp': 0 10 10'458 0 65'015 0
'objective_lb_search': 0 9 4'238 0 105'919 0
'probing': 0 1 669 0 216'489 0
'pseudo_costs': 0 10 12'528 0 65'957 0
'quick_restart': 0 3 3'498 0 122'636 0
'reduced_costs': 0 0 10'126 0 52'973 0
Lp pool Constraints Updates Simplif Merged Shortened Split Strengthened Cuts/Call
'default_lp': 4'723 760 16'744 0 10'233 316 335 3'393/7'720
'fs_random': 1'330 0 0 0 0 0 0 0/0
'lb_tree_search': 3'027 1'069 16'328 0 8'998 902 178 1'660/3'298
'max_lp': 3'792 519 16'347 0 10'157 407 286 2'425/5'665
'objective_lb_search': 3'363 729 16'071 0 9'270 684 308 2'033/3'641
'probing': 3'870 1'791 7'323 0 4'390 995 237 2'540/4'340
'pseudo_costs': 4'720 733 16'404 0 8'229 416 380 3'353/7'697
'quick_restart': 3'627 811 21'467 0 11'065 602 286 2'297/4'222
'reduced_costs': 4'586 748 13'218 0 7'382 481 389 3'219/6'776
Lp Cut max_lp quick_restart reduced_costs pseudo_costs lb_tree_search objective_lb_search default_lp probing
CG_FF: 22 10 32 34 7 16 45 16
CG_K: 8 6 23 30 1 10 28 11
CG_KL: 4 2 3 2 1 4 11 3
CG_R: 44 21 44 74 8 33 72 23
CG_RB: 51 54 64 108 26 40 98 37
CG_RBP: 23 15 35 63 7 28 62 18
Clique: 25 - 21 26 21 - - -
IB: 913 768 1'126 1'444 254 708 1'302 592
MIR_1_FF: 87 160 132 95 116 136 162 209
MIR_1_K: 26 20 57 20 9 21 32 16
MIR_1_KL: 7 26 18 22 7 25 28 19
MIR_1_R: 15 17 9 8 6 2 2 16
MIR_1_RB: 58 24 42 42 24 39 58 22
MIR_1_RBP: 29 64 33 28 58 52 61 170
MIR_2_FF: 96 89 97 94 89 57 123 95
MIR_2_K: 25 18 36 31 19 24 23 22
MIR_2_KL: 6 16 17 11 12 5 20 15
MIR_2_R: 16 3 25 20 5 2 11 6
MIR_2_RB: 95 61 95 79 52 49 102 55
MIR_2_RBP: 25 22 31 38 20 17 44 27
MIR_3_FF: 49 50 72 71 45 49 73 75
MIR_3_K: 15 7 32 12 10 37 15 14
MIR_3_KL: 3 8 6 7 4 10 8 10
MIR_3_R: 20 6 9 13 3 7 9 5
MIR_3_RB: 71 50 62 73 41 46 72 47
MIR_3_RBP: 26 15 17 31 10 16 41 16
MIR_4_FF: 38 49 67 47 41 45 47 74
MIR_4_K: 15 10 27 12 8 27 10 9
MIR_4_KL: 4 4 8 7 5 7 4 10
MIR_4_R: 6 9 12 16 3 4 7 -
MIR_4_RB: 42 35 41 58 28 39 53 28
MIR_4_RBP: 19 13 27 30 8 17 25 11
MIR_5_FF: 23 32 47 45 39 30 47 57
MIR_5_K: 19 19 23 16 13 18 16 23
MIR_5_KL: 3 4 14 12 2 9 10 10
MIR_5_R: 8 7 9 13 1 4 7 4
MIR_5_RB: 27 14 36 35 20 26 42 27
MIR_5_RBP: 25 18 21 30 15 14 26 32
MIR_6_FF: 25 10 29 27 30 26 27 52
MIR_6_K: 24 18 20 18 19 26 17 16
MIR_6_KL: 9 12 10 19 11 10 18 13
MIR_6_R: 8 3 12 9 2 5 11 -
MIR_6_RB: 21 10 38 28 10 19 32 21
MIR_6_RBP: 23 32 26 38 32 30 45 38
ZERO_HALF_FF: 30 17 55 26 1 17 23 30
ZERO_HALF_K: 1 2 24 6 - 3 9 1
ZERO_HALF_KL: - 5 11 6 - 7 5 10
ZERO_HALF_R: 242 328 407 331 438 182 313 455
ZERO_HALF_RB: 43 75 64 25 56 28 61 54
ZERO_HALF_RBP: 11 39 53 23 23 7 36 26
LNS stats Improv/Calls Closed Difficulty TimeLimit
'graph_arc_lns': 14/108 54% 9.39e-01 0.10
'graph_cst_lns': 6/108 51% 9.01e-01 0.10
'graph_dec_lns': 8/113 51% 9.11e-01 0.10
'graph_var_lns': 6/105 53% 9.54e-01 0.10
'lb_relax_lns': 4/30 53% 7.83e-01 0.50
'rins/rens': 118/120 56% 9.41e-01 0.10
'rnd_cst_lns': 12/114 52% 9.20e-01 0.10
'rnd_var_lns': 5/105 52% 9.34e-01 0.10
LS stats Batches Restarts/Perturbs LinMoves GenMoves CompoundMoves Bactracks WeightUpdates ScoreComputed
'fj_restart': 1 1 8'791 0 0 0 8'797 255'737
'fj_restart_decay_compound_perturb_obj': 1 1 0 12'932 2'200 5'365 27 347'114
'ls_lin_restart': 12 7 170'890 0 0 0 147'479 5'120'584
'ls_lin_restart_compound': 21 7 0 318'765 19'426 149'633 1'718 7'664'363
'ls_lin_restart_compound_perturb': 14 8 0 224'982 14'301 105'321 1'743 5'439'661
'ls_lin_restart_decay': 8 6 133'891 0 0 0 5'650 2'400'398
'ls_lin_restart_decay_compound': 36 16 0 580'916 82'658 249'024 802 14'703'978
'ls_lin_restart_decay_compound_perturb': 8 7 0 125'423 21'112 52'147 295 3'258'541
'ls_lin_restart_decay_perturb': 17 10 282'910 0 0 0 12'002 5'176'761
'ls_lin_restart_perturb': 15 9 220'983 0 0 0 151'029 7'191'986
'ls_restart': 12 6 176'693 0 0 0 100'185 5'722'677
'ls_restart_compound': 31 13 0 506'537 27'750 239'342 3'936 12'050'971
'ls_restart_compound_perturb': 13 9 0 195'433 12'859 91'268 1'798 4'680'184
'ls_restart_decay': 24 10 400'180 0 0 0 16'491 7'450'889
'ls_restart_decay_compound': 9 6 0 142'058 23'215 59'409 251 3'459'408
'ls_restart_decay_compound_perturb': 8 4 0 112'287 16'280 47'987 186 2'919'361
'ls_restart_decay_perturb': 28 15 464'097 0 0 0 19'258 8'547'790
'ls_restart_perturb': 10 9 145'106 0 0 0 114'128 4'373'120
Solutions (8) Num Rank
'graph_arc_lns': 4 [3,6]
'lb_relax_lns_bool': 2 [4,5]
'lb_relax_lns_bool_h': 4 [6,8]
'no_lp': 2 [0,1]
'quick_restart_no_lp': 2 [2,3]
'reduced_costs': 2 [1,2]
Objective bounds Num
'am1_presolve': 1
'initial_domain': 1
'lb_tree_search': 257
'max_lp': 3
'objective_lb_search': 8
'probing': 5
'reduced_costs': 2
Solution repositories Added Queried Synchro
'alternative_path': 53 459 53
'best_solutions': 164 567 113
'fj solution hints': 0 0 0
'lp solutions': 264 99 228
'pump': 83 21
Improving bounds shared Num Sym
'default_lp': 12 0
'lb_tree_search': 17 0
'max_lp': 22 0
'no_lp': 10 0
'objective_lb_search': 34 0
'probing': 87 0
'pseudo_costs': 20 0
'quick_restart': 26 0
'quick_restart_no_lp': 81 0
'reduced_costs': 257 0
Clauses shared #Exported #Imported #BinaryRead #BinaryTotal
'core': 1'483 4'236 3'783 4'143
'default_lp': 381 4'390 4'143 4'143
'fs_random': 0 0 0 4'143
'fs_random_no_lp': 0 0 0 4'143
'fs_random_quick_restart_no_lp': 0 0 0 4'143
'lb_tree_search': 223 4'305 3'724 4'143
'max_lp': 439 4'402 3'786 4'143
'no_lp': 2'663 2'976 3'785 4'143
'objective_lb_search': 394 4'371 4'101 4'143
'probing': 2'957 2'157 2'581 4'143
'pseudo_costs': 394 4'198 3'726 4'143
'quick_restart': 577 4'245 3'793 4'143
'quick_restart_no_lp': 4'522 2'469 3'964 4'143
'reduced_costs': 620 4'138 3'786 4'143
LRAT_status: NA
[Scaling] scaled_objective_bound: 1609.87 corrected_bound: 1609.87 delta: 1.46501e-06
[Scaling] Warning: OPTIMAL was reported, yet the objective gap (2.42787) is greater than requested absolute limit (0.0001).
CpSolverResponse summary:
status: OPTIMAL
objective: 1612.294803789032
best_bound: 1609.866938074606
integers: 727
booleans: 354
conflicts: 6
branches: 812
propagations: 7067
integer_propagations: 18290
restarts: 0
lp_iterations: 0
walltime: 48.0397
usertime: 48.0397
deterministic_time: 412.521
gap_integral: 713.208
solution_fingerprint: 0x5b832712c354a6b2
[13]:
wfn
[13]:
Ringed Topology with MILPRouter¶
We can also optimize for a ringed topology by setting topology='ringed' in ModelOptions:
[14]:
router_ring = MILPRouter(
solver_name='ortools.cp_sat',
time_limit=15,
mip_gap=0.01,
model_options=ModelOptions(topology='ringed', feeder_limit='minimum'),
verbose=True,
)
res_ring = wfn.optimize(router=router_ring)
wfn
IntegerBoundsPreprocessor 1132 rows, 748 columns, 3962 entries with magnitude in [1.000000e+00, 1.400000e+01]
BoundPropagationPreprocessor 1132 rows, 748 columns, 3962 entries with magnitude in [1.000000e+00, 1.400000e+01]
ImpliedIntegerPreprocessor 1132 rows, 748 columns, 3962 entries with magnitude in [1.000000e+00, 1.400000e+01]
IntegerBoundsPreprocessor 1132 rows, 748 columns, 3962 entries with magnitude in [1.000000e+00, 1.400000e+01]
ReduceCostOverExclusiveOrConstraintPreprocessor 1132 rows, 748 columns, 3962 entries with magnitude in [1.000000e+00, 1.400000e+01]
Scaling to pure integer problem.
Num integers: 748/748 (implied: 0 in_inequalities: 0 max_scaling: 0) [IP]
Maximum constraint coefficient relative error: 0
Maximum constraint worst-case activity error: 0
Constraint scaling factor range: [1, 1]
Starting CP-SAT solver v9.15.6755
Parameters: max_time_in_seconds: 15 log_search_progress: true catch_sigint_signal: false relative_gap_limit: 0.01
Setting number of workers to 16
Initial optimization model 'optiwindnet': (model_fingerprint: 0x192a0d00893e613d)
#Variables: 748 (#bools: 340 in floating point objective) (628 primary variables)
- 394 Booleans in [0,1]
- 314 in [0,13]
- 40 in [0,14]
#kLinear2: 865
#kLinear3: 1
#kLinearN: 266 (#terms: 2'229)
Starting presolve at 0.00s
The solution hint is complete and is feasible.
[Scaling] Floating point objective has 340 terms with magnitude in [0.100627, 223.305] average = 45.1849
[Scaling] Objective coefficient relative error: 6.6288e-06
[Scaling] Objective worst-case absolute error: 8.89826e-05
[Scaling] Objective scaling factor: 524288
2.09e-04s 0.00e+00d [DetectDominanceRelations]
3.79e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
1.18e-05s 0.00e+00d [ExtractEncodingFromLinear] #potential_supersets=185
6.49e-05s 0.00e+00d [DetectDuplicateColumns]
6.69e-05s 0.00e+00d [DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 2'745 nodes and 4'944 arcs.
[Symmetry] Symmetry computation done. time: 0.000232293 dtime: 0.00048967
[SAT presolve] num removable Booleans: 0 / 354
[SAT presolve] num trivial clauses: 0
[SAT presolve] [0s] clauses:157 literals:314 vars:314 one_side_vars:314 simple_definition:0 singleton_clauses:0
[SAT presolve] [1.312e-05s] clauses:157 literals:314 vars:314 one_side_vars:314 simple_definition:0 singleton_clauses:0
[SAT presolve] [1.9334e-05s] clauses:157 literals:314 vars:314 one_side_vars:314 simple_definition:0 singleton_clauses:0
8.10e-05s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
8.62e-03s 4.11e-03d [Probe] #probed=1'496 #new_binary_clauses=354
2.90e-04s 4.55e-04d [MaxClique] Merged 302 constraints with 1'090 literals into 182 constraints with 850 literals
1.87e-04s 0.00e+00d [DetectDominanceRelations]
2.49e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
5.49e-04s 0.00e+00d [ProcessAtMostOneAndLinear] #num_changes=354
7.41e-05s 0.00e+00d [DetectDuplicateConstraints]
5.87e-05s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
1.04e-04s 4.59e-06d [DetectDominatedLinearConstraints] #relevant_constraints=82 #num_inclusions=40
1.06e-05s 0.00e+00d [DetectDifferentVariables]
8.43e-05s 4.19e-06d [ProcessSetPPC] #relevant_constraints=223
1.12e-04s 0.00e+00d [TransformClausesToExactlyOne] #num_amos=182
2.81e-04s 0.00e+00d [DetectEncodedComplexDomains]
1.42e-05s 1.65e-07d [FindAlmostIdenticalLinearConstraints] #num_tested_pairs=3
1.21e-04s 1.02e-04d [FindBigAtMostOneAndLinearOverlap]
7.84e-05s 1.08e-04d [FindBigVerticalLinearOverlap]
1.44e-05s 5.27e-06d [FindBigHorizontalLinearOverlap] #linears=80
9.89e-06s 0.00e+00d [MergeClauses]
1.83e-04s 0.00e+00d [DetectDominanceRelations]
2.74e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1
1.53e-04s 0.00e+00d [DetectDominanceRelations]
1.24e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
4.13e-05s 0.00e+00d [DetectDuplicateColumns]
5.92e-05s 0.00e+00d [DetectDuplicateConstraints]
[Symmetry] Graph for symmetry has 2'492 nodes and 4'451 arcs.
[Symmetry] Symmetry computation done. time: 0.000399166 dtime: 0.0004571
[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] [7.392e-06s] clauses:37 literals:74 vars:74 one_side_vars:74 simple_definition:0 singleton_clauses:0
[SAT presolve] [1.944e-05s] clauses:37 literals:74 vars:74 one_side_vars:74 simple_definition:0 singleton_clauses:0
7.82e-05s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
4.06e-03s 1.27e-03d [Probe] #probed=788
2.51e-04s 3.09e-04d [MaxClique]
5.11e-04s 0.00e+00d [DetectDominanceRelations]
2.90e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
3.18e-04s 0.00e+00d [ProcessAtMostOneAndLinear]
6.56e-05s 0.00e+00d [DetectDuplicateConstraints]
6.43e-05s 0.00e+00d [DetectDuplicateConstraintsWithDifferentEnforcements]
8.59e-05s 4.59e-06d [DetectDominatedLinearConstraints] #relevant_constraints=82 #num_inclusions=40
9.47e-06s 0.00e+00d [DetectDifferentVariables]
7.61e-05s 4.19e-06d [ProcessSetPPC] #relevant_constraints=223
8.94e-05s 0.00e+00d [TransformClausesToExactlyOne] #num_amos=182
2.58e-04s 0.00e+00d [DetectEncodedComplexDomains]
1.55e-05s 0.00e+00d [FindAlmostIdenticalLinearConstraints]
1.43e-04s 1.01e-04d [FindBigAtMostOneAndLinearOverlap]
7.90e-05s 1.08e-04d [FindBigVerticalLinearOverlap]
1.28e-05s 5.27e-06d [FindBigHorizontalLinearOverlap] #linears=80
9.75e-06s 0.00e+00d [MergeClauses]
5.96e-04s 0.00e+00d [DetectDominanceRelations]
1.98e-03s 0.00e+00d [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1
2.79e-06s 0.00e+00d [MergeNoOverlap]
2.98e-06s 0.00e+00d [MergeNoOverlap2D]
1.29e-04s 0.00e+00d [ExpandObjective] #entries=2'948 #tight_variables=354 #tight_constraints=40 #expands=3
Presolve summary:
- 0 affine relations were detected.
- rule 'TODO linear inclusion: superset is equality' was applied 80 times.
- rule 'TODO linear2: convert ax + by != cte to clauses for large domains' was applied 2'124 times.
- rule 'at_most_one: transformed into max clique' was applied 1 time.
- rule 'bool_or: implications' was applied 157 times.
- rule 'deductions: 708 stored' was applied 1 time.
- rule 'exactly_one: removed literals' was applied 37 times.
- rule 'exactly_one: simplified objective' was applied 39 times.
- rule 'exactly_one: singleton' was applied 37 times.
- rule 'linear + amo: extracted enforcement literal' was applied 354 times.
- rule 'linear2: contains a boolean' was applied 354 times.
- rule 'linear2: convert ax + by != cte to clauses' was applied 157 times.
- rule 'linear: positive at most one' was applied 108 times.
- rule 'linear: positive equal one' was applied 77 times.
- rule 'linear: singleton column' was applied 3 times.
- rule 'objective: expanded via tight equality' was applied 3 times.
- rule 'objective: shifted cost with exactly ones' was applied 37 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 'optiwindnet': (model_fingerprint: 0x7ca70ffef2fe892e)
#Variables: 708 (#bools: 310 in objective) (627 primary variables)
- 354 Booleans in [0,1]
- 314 in [0,13]
- 40 in [0,14]
#kAtMostOne: 145 (#literals: 776)
#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'452 nodes and 4'451 arcs.
[Symmetry] Symmetry computation done. time: 0.000192819 dtime: 0.00045848
Preloading model.
#Bound 0.04s best:inf next:[613.705382,16769.934] initial_domain
#1 0.04s best:1810.44465 next:[613.705382,1810.44464] complete_hint
#Model 0.04s var:708/708 constraints:1012/1012
Starting search at 0.04s 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.05s best:1810.44465 next:[724.544545,1810.44464] am1_presolve (num_literals=310 num_am1=12 increase=58111643 work_done=1571)
#Bound 0.05s best:1810.44465 next:[873.433064,1810.44464] default_lp
#Bound 0.05s best:1810.44465 next:[878.097617,1810.44464] reduced_costs
#Bound 0.06s best:1810.44465 next:[911.501117,1810.44464] reduced_costs
#Bound 0.06s best:1810.44465 next:[950.825274,1810.44464] pseudo_costs
#Bound 0.07s best:1810.44465 next:[1044.06746,1810.44464] pseudo_costs
#Bound 0.07s best:1810.44465 next:[1076.35594,1810.44464] pseudo_costs
#Bound 0.07s best:1810.44465 next:[1079.20803,1810.44464] reduced_costs
#Bound 0.07s best:1810.44465 next:[1087.40569,1810.44464] reduced_costs
#Bound 0.07s best:1810.44465 next:[1649.7498,1810.44464] lb_tree_search
#2 0.09s best:1806.84452 next:[1649.7498,1806.84451] graph_var_lns (d=7.07e-01 s=23 t=0.10 p=1.00 stall=1 h=base)
#Bound 0.15s best:1806.84452 next:[1663.59864,1806.84451] max_lp
#Bound 0.16s best:1806.84452 next:[1663.9932,1806.84451] max_lp
#Bound 0.35s best:1806.84452 next:[1664.45162,1806.84451] max_lp
#Bound 0.45s best:1806.84452 next:[1664.69409,1806.84451] max_lp
#Bound 0.85s best:1806.84452 next:[1665.36123,1806.84451] max_lp
#Bound 1.00s best:1806.84452 next:[1665.59072,1806.84451] max_lp
#Bound 1.06s best:1806.84452 next:[1666.87721,1806.84451] lb_tree_search
#Bound 1.36s best:1806.84452 next:[1668.95933,1806.84451] lb_tree_search
#Bound 1.38s best:1806.84452 next:[1669.08086,1806.84451] lb_tree_search
#Bound 1.42s best:1806.84452 next:[1669.21245,1806.84451] lb_tree_search (nodes=6/6 rc=0 decisions=27 @root=8 restarts=0 lp_iters=[0, 0, 333, 202])
#Bound 1.77s best:1806.84452 next:[1669.68257,1806.84451] lb_tree_search
#Bound 1.97s best:1806.84452 next:[1670.68995,1806.84451] lb_tree_search (nodes=6/6 rc=0 decisions=44 @root=11 restarts=0 lp_iters=[0, 0, 1'110, 202]) [skipped_logs=7]
#Bound 2.76s best:1806.84452 next:[1673.56404,1806.84451] lb_tree_search (nodes=16/16 rc=2 decisions=95 @root=11 restarts=0 lp_iters=[0, 0, 4'229, 790]) [skipped_logs=15]
#Bound 3.95s best:1806.84452 next:[1674.2135,1806.84451] lb_tree_search (nodes=16/16 rc=3 decisions=128 @root=15 restarts=0 lp_iters=[0, 0, 5'769, 790]) [skipped_logs=5]
#Bound 5.00s best:1806.84452 next:[1675.14275,1806.84451] lb_tree_search (nodes=16/16 rc=3 decisions=145 @root=18 restarts=0 lp_iters=[0, 0, 6'622, 790]) [skipped_logs=3]
#Bound 5.87s best:1806.84452 next:[1676.64053,1806.84451] lb_tree_search (nodes=16/16 rc=3 decisions=166 @root=20 restarts=0 lp_iters=[0, 0, 8'349, 790]) [skipped_logs=7]
#Bound 6.93s best:1806.84452 next:[1676.72295,1806.84451] lb_tree_search (nodes=16/16 rc=3 decisions=174 @root=22 restarts=0 lp_iters=[0, 0, 8'768, 790]) [skipped_logs=1]
#3 7.47s best:1806.84451 next:[1677.64512,1806.84451] lb_relax_lns_int (d=3.59e-01 s=207 t=0.50 p=0.33 stall=3 h=base)
#Bound 7.20s best:1806.84452 next:[1677.64512,1806.84451] lb_tree_search (nodes=17/17 rc=3 decisions=185 @root=24 restarts=0 lp_iters=[0, 0, 9'241, 1'008]) [skipped_logs=1]
#Bound 8.79s best:1806.84451 next:[1678.60307,1806.84451] lb_tree_search (nodes=17/17 rc=3 decisions=212 @root=27 restarts=0 lp_iters=[0, 0, 10'841, 1'206]) [skipped_logs=4]
#Bound 9.98s best:1806.84451 next:[1679.62339,1806.84451] lb_tree_search (nodes=17/17 rc=3 decisions=221 @root=30 restarts=0 lp_iters=[0, 0, 11'406, 1'206]) [skipped_logs=2]
#Bound 10.51s best:1806.84451 next:[1679.90788,1806.84451] lb_tree_search (nodes=17/17 rc=3 decisions=223 @root=31 restarts=0 lp_iters=[0, 0, 11'589, 1'206]) [skipped_logs=0]
#Bound 11.66s best:1806.84451 next:[1680.03252,1806.84451] lb_tree_search (nodes=17/17 rc=3 decisions=239 @root=34 restarts=0 lp_iters=[0, 0, 12'793, 1'206]) [skipped_logs=4]
#Bound 12.27s best:1806.84451 next:[1680.03352,1806.84451] lb_tree_search (nodes=29/29 rc=8 decisions=282 @root=34 restarts=0 lp_iters=[0, 0, 13'749, 2'019]) [skipped_logs=0]
#Bound 13.85s best:1806.84451 next:[1680.12513,1806.84451] lb_tree_search (nodes=29/29 rc=8 decisions=291 @root=36 restarts=0 lp_iters=[0, 0, 14'295, 2'019]) [skipped_logs=1]
#Bound 14.78s best:1806.84451 next:[1680.17679,1806.84451] lb_tree_search (nodes=29/29 rc=8 decisions=297 @root=37 restarts=0 lp_iters=[0, 0, 14'556, 2'019]) [skipped_logs=0]
Task timing n [ min, max] avg dev time n [ min, max] avg dev dtime
'core': 1 [ 14.97s, 14.97s] 14.97s 0.00ns 14.97s 2 [ 1.33ms, 10.66s] 5.33s 5.33s 10.66s
'default_lp': 1 [ 14.96s, 14.96s] 14.96s 0.00ns 14.96s 2 [ 21.87ms, 5.69s] 2.86s 2.84s 5.72s
'feasibility_pump': 70 [ 41.01us, 19.07ms] 1.52ms 2.14ms 106.47ms 68 [146.90us, 8.53ms] 278.86us 1.01ms 18.96ms
'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': 42 [ 4.14ms, 414.85ms] 191.04ms 140.00ms 8.02s 42 [ 42.00ns, 100.31ms] 60.95ms 45.56ms 2.56s
'graph_cst_lns': 37 [ 9.87ms, 421.04ms] 216.09ms 139.88ms 8.00s 37 [ 64.21us, 100.50ms] 60.49ms 42.67ms 2.24s
'graph_dec_lns': 37 [ 2.69ms, 454.72ms] 210.36ms 149.69ms 7.78s 37 [ 10.00ns, 100.15ms] 58.00ms 45.47ms 2.15s
'graph_var_lns': 41 [ 3.69ms, 361.18ms] 181.40ms 133.39ms 7.44s 41 [ 10.00ns, 100.30ms] 58.27ms 45.80ms 2.39s
'lb_relax_lns': 9 [157.86ms, 1.72s] 786.50ms 683.67ms 7.08s 9 [ 29.98ms, 536.23ms] 254.79ms 244.99ms 2.29s
'lb_tree_search': 1 [ 14.96s, 14.96s] 14.96s 0.00ns 14.96s 2 [ 62.71ms, 8.50s] 4.28s 4.22s 8.56s
'ls': 33 [172.42ms, 249.69ms] 210.27ms 21.24ms 6.94s 33 [100.00ms, 100.02ms] 100.01ms 2.34us 3.30s
'ls_lin': 34 [177.75ms, 273.75ms] 206.32ms 19.56ms 7.01s 34 [100.00ms, 100.01ms] 100.01ms 2.38us 3.40s
'max_lp': 1 [ 14.97s, 14.97s] 14.97s 0.00ns 14.97s 2 [ 89.76ms, 7.27s] 3.68s 3.59s 7.36s
'no_lp': 1 [ 14.97s, 14.97s] 14.97s 0.00ns 14.97s 2 [ 1.58ms, 7.34s] 3.67s 3.67s 7.34s
'objective_lb_search': 1 [ 14.96s, 14.96s] 14.96s 0.00ns 14.96s 2 [ 21.75ms, 6.26s] 3.14s 3.12s 6.28s
'probing': 1 [ 14.97s, 14.97s] 14.97s 0.00ns 14.97s 2 [ 23.97ms, 9.68s] 4.85s 4.83s 9.70s
'pseudo_costs': 1 [ 14.96s, 14.96s] 14.96s 0.00ns 14.96s 2 [ 32.15ms, 7.05s] 3.54s 3.51s 7.09s
'quick_restart': 1 [ 14.97s, 14.97s] 14.97s 0.00ns 14.97s 2 [ 22.68ms, 7.73s] 3.88s 3.85s 7.75s
'quick_restart_no_lp': 1 [ 14.96s, 14.96s] 14.96s 0.00ns 14.96s 2 [ 1.58ms, 11.48s] 5.74s 5.74s 11.49s
'reduced_costs': 1 [ 14.97s, 14.97s] 14.97s 0.00ns 14.97s 2 [ 45.86ms, 9.63s] 4.84s 4.79s 9.67s
'rins/rens': 40 [ 1.79ms, 440.44ms] 203.93ms 171.05ms 8.16s 33 [ 74.16us, 100.11ms] 65.24ms 44.45ms 2.15s
'rnd_cst_lns': 39 [ 5.09ms, 424.11ms] 177.59ms 143.06ms 6.93s 39 [ 43.00ns, 100.21ms] 50.07ms 45.35ms 1.95s
'rnd_var_lns': 39 [ 3.81ms, 421.29ms] 186.36ms 146.25ms 7.27s 39 [ 10.00ns, 100.19ms] 51.78ms 45.00ms 2.02s
Search stats Bools Conflicts Branches Restarts BacktrackToRoot Backtrack BoolPropag IntegerPropag
'core': 564 162'610 601'331 230 11'698 176'246 5'372'233 12'209'439
'default_lp': 406 1'189 51'634 15 14'565 18'091 320'652 1'082'525
'fs_random': 0 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0 0
'lb_tree_search': 354 119 54'507 0 16'640 18'442 310'661 1'116'169
'max_lp': 354 1'118 48'620 11 11'551 13'760 285'675 1'089'124
'no_lp': 354 123'614 241'227 382 15'156 139'667 5'157'122 16'329'950
'objective_lb_search': 464 2'111 48'310 11 11'812 16'329 378'099 1'181'127
'probing': 395 10 999 0 873 883 9'392 23'652
'pseudo_costs': 354 1'803 38'097 7 8'733 11'301 260'913 992'643
'quick_restart': 374 343 53'175 18 16'062 18'353 300'246 1'067'962
'quick_restart_no_lp': 580 66'049 726'766 5'759 33'119 103'526 6'079'709 14'021'377
'reduced_costs': 354 915 48'917 14 13'302 15'591 290'754 1'093'400
SAT formula Fixed Equiv Total VarLeft BinaryClauses PermanentClauses TemporaryClauses
'core': 0 0 564 564 1'426 3'953 12'181
'default_lp': 0 0 406 406 204 315 856
'fs_random': 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0
'lb_tree_search': 0 0 354 354 94 356 3
'max_lp': 0 0 354 354 94 355 872
'no_lp': 0 0 354 354 94 537 11'316
'objective_lb_search': 9 0 464 455 296 312 200
'probing': 0 0 395 395 308 40 10
'pseudo_costs': 0 0 354 354 94 296 1'426
'quick_restart': 0 0 374 374 136 378 189
'quick_restart_no_lp': 6 0 580 574 694 2'466 8'591
'reduced_costs': 0 0 354 354 94 386 706
SAT stats ClassicMinim LitRemoved LitRemovedBinary LitLearned LitForgotten Subsumed
'core': 137'833 1'945'202 848'695 13'057'769 7'832'799 49'764
'default_lp': 846 11'805 31'108 68'832 0 285
'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': 45 379 356 1'609 0 91
'max_lp': 737 11'085 21'868 93'722 0 211
'no_lp': 106'848 797'746 1'583'929 7'417'875 5'561'618 15'754
'objective_lb_search': 1'787 20'824 34'691 99'624 0 416
'probing': 6 22 526 683 0 0
'pseudo_costs': 1'406 16'576 33'001 109'637 0 351
'quick_restart': 187 1'737 7'189 10'043 0 105
'quick_restart_no_lp': 49'823 486'974 1'333'119 3'162'107 2'116'443 11'055
'reduced_costs': 724 8'084 24'517 35'505 0 164
Vivification Clauses Decisions LitTrue Subsumed LitRemoved DecisionReused Conflicts
'core': 10'822 332'618 0 1'867 45'583 28'122 123
'default_lp': 4'781 36'004 0 307 2'375 1'271 11
'fs_random': 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0
'lb_tree_search': 5'635 41'340 0 373 2'937 1'506 7
'max_lp': 4'998 38'047 0 288 2'314 1'706 13
'no_lp': 6'544 59'666 0 1'027 9'313 3'061 26
'objective_lb_search': 4'505 34'149 0 352 2'686 1'286 6
'probing': 0 0 0 0 0 0 0
'pseudo_costs': 3'971 29'259 0 326 2'493 1'112 9
'quick_restart': 5'125 38'620 0 341 2'501 1'614 9
'quick_restart_no_lp': 23'165 168'906 3 2'117 21'843 12'862 189
'reduced_costs': 4'875 35'598 0 299 2'394 1'467 11
Clause deletion at_true l_and_not(l) to_binary sub_conflict sub_extra sub_decisions sub_eager sub_vivify sub_probing sub_inpro blocked eliminated forgotten promoted conflicts
'core': 0 0 0 48'310 1'904 34 1'454 1'867 35 168 0 0 93'398 390'940 162'610
'default_lp': 0 0 1 279 5 0 6 307 21 56 0 0 0 2'460 1'189
'fs_random': 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
'fs_random_no_lp': 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
'fs_random_quick_restart_no_lp': 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
'lb_tree_search': 0 0 0 91 0 3 0 373 26 91 0 0 0 22 119
'max_lp': 0 0 1 204 4 3 7 288 13 133 0 0 0 2'061 1'118
'no_lp': 0 0 0 15'404 574 3 350 1'027 38 29 0 0 95'058 296'612 123'614
'objective_lb_search': 1'419 0 0 409 9 10 7 352 18 33 0 0 0 3'991 2'111
'probing': 0 0 0 0 0 0 0 0 0 0 0 0 0 17 10
'pseudo_costs': 0 0 1 344 2 3 7 326 13 62 0 0 0 3'615 1'803
'quick_restart': 0 0 0 104 0 3 1 341 11 68 0 0 0 381 343
'quick_restart_no_lp': 21 0 6 10'382 576 72 673 2'117 127 252 0 0 40'808 143'532 66'049
'reduced_costs': 0 0 1 158 0 3 6 299 10 126 0 0 0 1'720 915
Lp stats Component Iterations AddedCuts OPTIMAL DUAL_F. DUAL_U.
'default_lp': 1 69'803 4'352 4'229 0 165
'lb_tree_search': 1 25'833 1'888 357 107 0
'max_lp': 1 102'611 2'214 3'009 789 122
'objective_lb_search': 1 122'699 3'390 6'838 0 95
'probing': 1 26'160 5'222 257 4 1
'pseudo_costs': 1 154'873 2'051 4'274 1'549 185
'quick_restart': 1 50'259 4'224 1'575 1 19
'reduced_costs': 1 106'902 2'028 1'677 783 85
Lp dimension Final dimension of first component
'default_lp': 1028 rows, 664 columns, 16991 entries
'lb_tree_search': 1746 rows, 708 columns, 67518 entries
'max_lp': 821 rows, 708 columns, 13492 entries
'objective_lb_search': 913 rows, 664 columns, 11357 entries
'probing': 2464 rows, 664 columns, 91477 entries
'pseudo_costs': 729 rows, 708 columns, 8356 entries
'quick_restart': 1341 rows, 664 columns, 27739 entries
'reduced_costs': 1016 rows, 708 columns, 19966 entries
Lp debug CutPropag CutEqPropag Adjust Overflow Bad BadScaling
'default_lp': 0 4 4'386 0 22'334 0
'lb_tree_search': 0 0 463 0 63'061 0
'max_lp': 0 0 3'917 0 25'197 0
'objective_lb_search': 0 0 6'927 0 13'974 0
'probing': 0 1 259 0 55'583 0
'pseudo_costs': 0 0 5'999 0 9'787 0
'quick_restart': 0 0 1'594 0 35'951 0
'reduced_costs': 0 0 2'544 0 31'958 0
Lp pool Constraints Updates Simplif Merged Shortened Split Strengthened Cuts/Call
'default_lp': 5'548 227 22 0 0 156 164 4'352/9'356
'lb_tree_search': 3'254 616 12 0 0 790 29 1'888/3'737
'max_lp': 3'580 254 12 0 0 167 20 2'214/4'153
'objective_lb_search': 4'586 94 32 0 0 49 181 3'390/7'610
'probing': 6'418 461 2 0 0 0 231 5'222/9'924
'pseudo_costs': 3'417 83 21 0 0 17 22 2'051/3'864
'quick_restart': 5'420 349 21 0 0 234 145 4'224/8'717
'reduced_costs': 3'394 353 18 0 0 268 19 2'028/3'408
Lp Cut lb_tree_search objective_lb_search default_lp pseudo_costs quick_restart reduced_costs probing max_lp
CG_FF: 5 35 61 16 27 13 38 15
CG_K: 2 29 52 6 27 6 32 8
CG_KL: 3 9 3 - 6 - 4 5
CG_R: 13 60 64 44 47 33 49 33
CG_RB: 28 86 97 82 43 70 60 52
CG_RBP: 14 67 64 11 36 16 36 35
Clique: 1 - - - - 2 - -
IB: 10 783 917 1'193 592 697 410 729
MIR_1_FF: 172 337 426 42 567 113 792 108
MIR_1_K: 7 99 114 13 104 10 125 18
MIR_1_KL: 3 48 37 2 44 6 57 3
MIR_1_R: 1 14 9 2 4 1 17 4
MIR_1_RB: 13 25 31 12 29 24 32 18
MIR_1_RBP: 47 57 86 1 54 8 118 18
MIR_2_FF: 72 199 225 57 198 62 279 73
MIR_2_K: 37 84 102 7 96 11 118 25
MIR_2_KL: 7 32 38 - 38 2 30 1
MIR_2_R: 6 14 17 8 12 1 23 2
MIR_2_RB: 33 52 68 34 42 26 41 33
MIR_2_RBP: 33 46 66 3 53 14 61 12
MIR_3_FF: 65 115 151 50 148 70 155 68
MIR_3_K: 56 63 101 15 126 48 145 37
MIR_3_KL: 4 9 17 - 18 3 19 1
MIR_3_R: 2 12 23 10 24 4 19 4
MIR_3_RB: 30 30 48 35 52 29 46 35
MIR_3_RBP: 43 40 69 7 61 27 87 21
MIR_4_FF: 64 79 110 38 129 64 131 58
MIR_4_K: 73 63 83 17 103 38 138 39
MIR_4_KL: 2 10 9 2 9 - 8 1
MIR_4_R: 9 16 15 6 24 4 16 13
MIR_4_RB: 35 31 29 26 35 46 29 45
MIR_4_RBP: 47 46 65 7 65 18 108 23
MIR_5_FF: 60 45 66 25 88 41 83 46
MIR_5_K: 97 45 80 12 103 52 113 56
MIR_5_KL: 2 3 7 - 6 2 9 -
MIR_5_R: 6 13 7 2 16 5 12 7
MIR_5_RB: 47 36 19 25 21 30 24 38
MIR_5_RBP: 48 34 58 9 67 31 112 42
MIR_6_FF: 50 40 46 24 75 31 52 49
MIR_6_K: 76 48 64 17 97 33 100 63
MIR_6_KL: 2 3 2 2 8 - 9 3
MIR_6_R: 8 10 5 4 17 7 5 2
MIR_6_RB: 40 30 19 20 29 28 20 37
MIR_6_RBP: 45 38 48 11 57 18 87 45
ZERO_HALF_FF: 4 57 91 20 60 9 57 13
ZERO_HALF_K: - 20 25 - 29 - 22 -
ZERO_HALF_KL: - 7 16 - 10 - 9 1
ZERO_HALF_R: 376 301 464 113 578 245 1'010 241
ZERO_HALF_RB: 71 41 94 16 96 22 179 26
ZERO_HALF_RBP: 19 29 44 5 54 8 96 8
LNS stats Improv/Calls Closed Difficulty TimeLimit
'graph_arc_lns': 2/42 45% 2.93e-01 0.10
'graph_cst_lns': 1/37 51% 8.10e-01 0.10
'graph_dec_lns': 2/37 49% 7.84e-01 0.10
'graph_var_lns': 4/41 49% 6.63e-01 0.10
'lb_relax_lns': 1/9 56% 6.48e-01 0.50
'rins/rens': 33/40 48% 5.34e-01 0.10
'rnd_cst_lns': 2/39 56% 8.98e-01 0.10
'rnd_var_lns': 2/39 49% 7.69e-01 0.10
LS stats Batches Restarts/Perturbs LinMoves GenMoves CompoundMoves Bactracks WeightUpdates ScoreComputed
'ls_lin_restart': 3 3 52'509 0 0 0 35'037 1'816'238
'ls_lin_restart_compound': 4 4 0 86'329 6'723 39'793 504 1'987'588
'ls_lin_restart_compound_perturb': 5 5 0 110'272 9'829 50'201 2'433 2'643'086
'ls_lin_restart_decay': 5 4 106'658 0 0 0 3'060 2'217'436
'ls_lin_restart_decay_compound': 2 2 0 38'453 5'645 16'402 77 956'380
'ls_lin_restart_decay_compound_perturb': 2 2 0 39'443 5'805 16'816 68 1'017'757
'ls_lin_restart_decay_perturb': 6 6 127'432 0 0 0 3'724 2'623'907
'ls_lin_restart_perturb': 7 7 118'887 0 0 0 71'520 4'138'484
'ls_restart': 4 4 68'775 0 0 0 37'324 2'471'789
'ls_restart_compound': 4 4 0 88'052 9'047 39'494 13'031 2'120'226
'ls_restart_compound_perturb': 4 4 0 87'074 7'238 39'911 640 2'054'686
'ls_restart_decay': 9 9 191'189 0 0 0 5'567 3'946'241
'ls_restart_decay_compound': 3 3 0 59'682 9'779 24'949 110 1'467'509
'ls_restart_decay_compound_perturb': 3 3 0 57'401 9'571 23'907 117 1'368'821
'ls_restart_decay_perturb': 1 1 21'337 0 0 0 626 440'149
'ls_restart_perturb': 5 5 84'941 0 0 0 24'199 2'900'130
Solutions (3) Num Rank
'complete_hint': 2 [0,1]
'graph_var_lns': 2 [1,2]
'lb_relax_lns_int': 2 [2,3]
Objective bounds Num
'am1_presolve': 1
'default_lp': 1
'initial_domain': 1
'lb_tree_search': 70
'max_lp': 6
'pseudo_costs': 3
'reduced_costs': 4
Solution repositories Added Queried Synchro
'alternative_path': 17 76 17
'best_solutions': 39 301 37
'fj solution hints': 0 0 0
'lp solutions': 91 40 76
'pump': 0 0
Improving bounds shared Num Sym
'quick_restart_no_lp': 6 0
Clauses shared #Exported #Imported #BinaryRead #BinaryTotal
'core': 288 463 7 7
'default_lp': 19 619 7 7
'lb_tree_search': 1 784 7 7
'max_lp': 25 767 7 7
'no_lp': 79 693 7 7
'objective_lb_search': 18 618 7 7
'probing': 0 0 0 7
'pseudo_costs': 17 637 7 7
'quick_restart': 33 758 7 7
'quick_restart_no_lp': 624 213 7 7
'reduced_costs': 37 759 7 7
LRAT_status: NA
[Scaling] scaled_objective_bound: 1680.18 corrected_bound: 1680.18 delta: 4.23091e-07
CpSolverResponse summary:
status: FEASIBLE
objective: 1806.844516916113
best_bound: 1680.176790785937
integers: 0
booleans: 0
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 0
restarts: 0
lp_iterations: 0
walltime: 15.0165
usertime: 15.0165
deterministic_time: 116.09
gap_integral: 563.723
solution_fingerprint: 0x1c5bf311b8641372
[14]:
