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