{
"cells": [
{
"cell_type": "markdown",
"id": "3d21f91a-a0b6-47d8-8096-408733598cc2",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"# 3.1 Sparsified vs. complete graphs as search space"
]
},
{
"cell_type": "markdown",
"id": "833ef04c-0db6-4592-bcd1-c05ee0290184",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"This is used in the paper **Flexible cable routing framework for wind farm collection system optimization**."
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "d1034bcc-96af-41fa-a3d2-ead116bdafe1",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"import fnmatch\n",
"from itertools import chain, pairwise, accumulate\n",
"from pathlib import Path\n",
"import urllib.request\n",
"import networkx as nx\n",
"import numpy as np"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "8d9d606d-ac9b-4352-84a4-f046c8c7b2c5",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"from optiwindnet.svg import svgplot\n",
"from optiwindnet.interarraylib import G_from_S, L_from_site\n",
"from optiwindnet.mesh import make_planar_embedding"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "4caf3f04-bcca-43a1-8803-8fba37473e25",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"# Additional python packages needed\n",
"import py7zr\n",
"import vrplib"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "b8a31ffc-8537-4592-a5a0-40d3567dcc0a",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"import matplotlib.pyplot as plt\n",
"\n",
"%config InlineBackend.figure_formats = ['svg']\n",
"plt.rcParams['svg.fonttype'] = 'none'\n",
"\n",
"style = Path('mplstyles/jupyter_dark.mplstyle')\n",
"style.is_file() and plt.style.use(style)"
]
},
{
"cell_type": "markdown",
"id": "6de2a586-04d9-42cf-b2d3-f178b36045b8",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"## Data download"
]
},
{
"cell_type": "markdown",
"id": "c783317b-0eae-45eb-a6e6-6900c401872a",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Queiroga, E., Sadykov, R., Uchoa, E., & Vidal, T. (2021, November 24). 10,000 optimal CVRP solutions for testing machine learning based heuristics. AAAI-22 Workshop on Machine Learning for Operations Research (ML4OR). https://openreview.net/forum?id=yHiMXKN6nTl"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "bde1396d-78f5-4a5c-a66a-77605d00d9e4",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"# previously at: http://vrp.galgos.inf.puc-rio.br/media/com_vrp/instances/Vrp-Set-XML100.zip'\n",
"file_name = 'XML.7z'\n",
"# repository URL\n",
"url = 'https://galgos.inf.puc-rio.br/cvrplib/uploads/files/xml100/' + file_name"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "389ad434-e702-4aaa-8f34-97aa82c211c8",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"dir_instances = Path('XML/instances/')\n",
"dir_solutions = Path('XML/solutions/')"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "5a2e1dbe-d952-4e91-9e63-e330ce25e0c7",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"if dir_instances.is_dir() and dir_solutions.is_dir():\n",
" # Already extracted\n",
" instances = sorted(p.name for p in dir_instances.iterdir())\n",
" solutions = [\n",
" instance.replace('.vrp', '.sol')\n",
" for instance in instances\n",
" ]\n",
"else:\n",
" if Path(file_name).is_file():\n",
" # Already downloaded\n",
" filehandle = open(file_name, 'rb')\n",
" else:\n",
" # Download from repository\n",
" filehandle, _ = urllib.request.urlretrieve(url)\n",
" with py7zr.SevenZipFile(filehandle, mode=\"r\") as archive:\n",
" # Extract only the unitary-demand cases\n",
" archive_names = archive.getnames()\n",
" instances = fnmatch.filter(\n",
" archive_names,\n",
" dir_instances / \"XML100_?11?_??.vrp\",\n",
" )\n",
" solutions = fnmatch.filter(\n",
" archive_names,\n",
" dir_solutions / 'XML100_?11?_??.sol',\n",
" )\n",
" archive.extract(path='.', targets=instances + solutions)\n",
" instances = sorted(path.split('/')[-1] for path in instances)\n",
" solutions = [\n",
" instance.replace('.vrp', '.sol')\n",
" for instance in instances\n",
" ]"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "fd43603a-6392-42f7-abde-fde4f10ffadc",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [
{
"data": {
"text/plain": [
"(480, 480)"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(instances), len(solutions)"
]
},
{
"cell_type": "markdown",
"id": "205f5b2d-bbe3-464b-b5d3-ff8fe9168e5b",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"## Definitions"
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "3b1621e6-b4e6-40ac-99a1-4a2b1654de5d",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"def check_rogues(solution, A):\n",
" rogues = []\n",
" branches = ([n - 1 for n in branch] for branch in solution['routes'])\n",
" for branch in branches:\n",
" for edge in pairwise(branch):\n",
" if edge not in A.edges:\n",
" rogues.append(edge)\n",
" return rogues"
]
},
{
"cell_type": "code",
"execution_count": 10,
"id": "dc8c242e-e87a-48a1-95f0-ecd2bbb884cf",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"def S_from_vrplib(solution, Sʹ):\n",
" '''\n",
" Beware: assumes a single depot!\n",
" '''\n",
" # create a topology graph S from the solution\n",
" S = nx.Graph(\n",
" T=Sʹ.graph['T'], R=Sʹ.graph['R'],\n",
" capacity=Sʹ.graph['capacity'],\n",
" has_loads=True,\n",
" objective=solution['cost'],\n",
" creator='vrplib',\n",
" )\n",
"\n",
" branches = ([n - 1 for n in branch] for branch in solution['routes'])\n",
" for subtree_id, branch in enumerate(branches):\n",
" loads = range(len(branch), 0, -1)\n",
" S.add_nodes_from(((n, {'load': load})\n",
" for n, load in zip(branch, loads)),\n",
" subtree=subtree_id)\n",
" branch_roll = [-1] + branch[:-1]\n",
" reverses = tuple(u < v for u, v in zip(branch, branch_roll))\n",
" edgeD = ({'load': load, 'reverse': reverse}\n",
" for load, reverse in zip(loads, reverses))\n",
" S.add_edges_from(zip(branch_roll, branch, edgeD))\n",
" root_load = sum(S.nodes[n]['load'] for n in S.neighbors(-1))\n",
" S.nodes[-1]['load'] = root_load\n",
" return S"
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "6b591101-512d-417f-8cc2-e0aa96157691",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"def L_from_vrplib(instance):\n",
" R = len(instance['depot'])\n",
" T = instance['dimension'] - R\n",
" # make sure depots are numbered 0..M-1\n",
" assert all(depot == i for i, depot in enumerate(instance['depot']))\n",
" L = L_from_site(\n",
" B=4, border=np.arange(T, T + 4),\n",
" R=R, T=T, name=instance['name'],\n",
" VertexC=np.vstack((instance['node_coord'][R:],\n",
" [[0,0], [1000, 0], [1000, 1000], [0, 1000]],\n",
" instance['node_coord'][:R])),\n",
" )\n",
" L.graph['capacity'] = instance['capacity']\n",
" return L"
]
},
{
"cell_type": "markdown",
"id": "a5b1bdb1-6157-433c-b1f2-f2a9dc6168a6",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"## Examine XML100 \\_11\\_\n",
"\n",
"(i.e. random client positions, 1-demand)"
]
},
{
"cell_type": "code",
"execution_count": 12,
"id": "7cf8bd99-e3cd-4c0b-96f3-7b2953f5b4cc",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"inst_id = '2115_07'\n",
"instance = vrplib.read_instance(dir_instances / f'XML100_{inst_id}.vrp')\n",
"solution = vrplib.read_solution(dir_solutions / f'XML100_{inst_id}.sol')"
]
},
{
"cell_type": "code",
"execution_count": 13,
"id": "03ebcb82-bcf7-4a9e-861b-868463bc6ac5",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [
{
"data": {
"text/plain": [
"dict_keys(['name', 'comment', 'type', 'dimension', 'edge_weight_type', 'capacity', 'node_coord', 'demand', 'depot', 'edge_weight'])"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"instance.keys()"
]
},
{
"cell_type": "code",
"execution_count": 14,
"id": "093488d6-9484-4af6-83ee-673e4876843a",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [
{
"data": {
"text/plain": [
"dict_keys(['routes', 'cost'])"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"solution.keys()"
]
},
{
"cell_type": "code",
"execution_count": 15,
"id": "9454307a-5a0a-4525-8ef6-c2d99b3e1682",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"L = L_from_vrplib(instance)"
]
},
{
"cell_type": "code",
"execution_count": 16,
"id": "bb0abae0-fde3-4506-aa9b-5ef312249084",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"svgplot(L)"
]
},
{
"cell_type": "code",
"execution_count": 17,
"id": "7b74b839-2ec5-4243-a16b-df2edccf1f72",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"P, A = make_planar_embedding(L)"
]
},
{
"cell_type": "code",
"execution_count": 18,
"id": "cbf57590-b17a-4f61-b738-f1f695a4d962",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"