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