mkp_random_data.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyNcc7KhyDZH/lBGODopdTPa"
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    },
    "widgets": {
      "application/vnd.jupyter.widget-state+json": {
        "ae684b3d617e49d889352459f8c99859": {
          "model_module": "algorithmx-jupyter",
          "model_name": "AlgorithmXModel",
          "model_module_version": "^3.0.0",
          "state": {
            "_dom_classes": [],
            "_model_module": "algorithmx-jupyter",
            "_model_module_version": "^3.0.0",
            "_model_name": "AlgorithmXModel",
            "_view_count": null,
            "_view_module": "algorithmx-jupyter",
            "_view_module_version": "^3.0.0",
            "_view_name": "AlgorithmXView",
            "events": [
              "{\"attrs\": {\"size\": [500, 400]}}",
              "{\"attrs\": {\"nodes\": {\"0\": {}, \"1\": {}, \"2\": {}, \"3\": {}}}}",
              "{\"attrs\": {\"edges\": {\"0-1\": {\"source\": \"0\", \"target\": \"1\", \"labels\": {\"0\": {\"text\": 2565}}}, \"0-2\": {\"source\": \"0\", \"target\": \"2\", \"labels\": {\"0\": {\"text\": 2968}}}, \"0-3\": {\"source\": \"0\", \"target\": \"3\", \"labels\": {\"0\": {\"text\": 4189}}}, \"1-2\": {\"source\": \"1\", \"target\": \"2\", \"labels\": {\"0\": {\"text\": 2631}}}, \"1-3\": {\"source\": \"1\", \"target\": \"3\", \"labels\": {\"0\": {\"text\": 1939}}}, \"2-3\": {\"source\": \"2\", \"target\": \"3\", \"labels\": {\"0\": {\"text\": 1734}}}}}}",
              "{\"queues\": {\"0\": {\"pause\": 1}}, \"withQ\": 0}",
              "{\"attrs\": {\"nodes\": {\"0\": {\"color\": \"green\"}}}}",
              "{\"attrs\": {\"nodes\": {\"0\": {\"size\": \"1.25x\"}}}, \"animation\": {\"highlight\": true}}",
              "{\"attrs\": {\"nodes\": {\"2\": {\"color\": \"red\"}}}}",
              "{\"attrs\": {\"nodes\": {\"2\": {\"size\": \"1.25x\"}}}, \"animation\": {\"highlight\": true}}",
              "{\"queues\": {\"0\": {\"pause\": 1.5}}, \"withQ\": 0}"
            ],
            "layout": "IPY_MODEL_6252cd42ebca4e6ca2a715f62a1c1334",
            "show_buttons": true
          }
        },
        "6252cd42ebca4e6ca2a715f62a1c1334": {
          "model_module": "@jupyter-widgets/base",
          "model_name": "LayoutModel",
          "model_module_version": "1.2.0",
          "state": {
            "_model_module": "@jupyter-widgets/base",
            "_model_module_version": "1.2.0",
            "_model_name": "LayoutModel",
            "_view_count": null,
            "_view_module": "@jupyter-widgets/base",
            "_view_module_version": "1.2.0",
            "_view_name": "LayoutView",
            "align_content": null,
            "align_items": null,
            "align_self": null,
            "border": null,
            "bottom": null,
            "display": null,
            "flex": null,
            "flex_flow": null,
            "grid_area": null,
            "grid_auto_columns": null,
            "grid_auto_flow": null,
            "grid_auto_rows": null,
            "grid_column": null,
            "grid_gap": null,
            "grid_row": null,
            "grid_template_areas": null,
            "grid_template_columns": null,
            "grid_template_rows": null,
            "height": null,
            "justify_content": null,
            "justify_items": null,
            "left": null,
            "margin": null,
            "max_height": null,
            "max_width": null,
            "min_height": null,
            "min_width": null,
            "object_fit": null,
            "object_position": null,
            "order": null,
            "overflow": null,
            "overflow_x": null,
            "overflow_y": null,
            "padding": null,
            "right": null,
            "top": null,
            "visibility": null,
            "width": null
          }
        }
      }
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "**Graph network preparation with random data for Multi_knapsack**\n",
        "\n",
        "INSTRUCTIONS:  For simulation, firt change the graph nodes you want to generate at G = nx.complete_graph(4).  \n",
        "Then change the random data you want to generate for demands at the end of  5th tab # here: \n",
        "bw_dem = dem(10) \n",
        "revenue = reven(10) \n",
        "classes = clas(10) \n",
        "Note: The number (i.e, 10) should be same"
      ],
      "metadata": {
        "id": "j7W3bReK1oju"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "!pip install algorithmx"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "1ukK3beh1pMF",
        "outputId": "7845dbac-784c-47c9-f22f-3418f0a65698"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n",
            "Requirement already satisfied: algorithmx in /usr/local/lib/python3.7/dist-packages (2.0.3)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# Import all required liberaries\n",
        "from algorithmx import jupyter_canvas\n",
        "from random import randint\n",
        "import networkx as nx\n",
        "from algorithmx import jupyter_canvas\n",
        "from random import randint\n",
        "import networkx as nx\n",
        "from google.colab import output\n",
        "output.enable_custom_widget_manager()\n",
        "import random"
      ],
      "metadata": {
        "id": "hBgDiRHc1pOY"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Create graph with NetworkX\n",
        "\n",
        "random.seed(436)\n",
        "\n",
        "canvas = jupyter_canvas(buttons=True)\n",
        "canvas.size((500, 400))\n",
        "\n",
        "# Generate a random graph with random edge weights\n",
        "# G = nx.newman_watts_strogatz_graph(16, 2, 0.4, seed=537)\n",
        "G = nx.complete_graph(4)\n",
        "\n",
        "nx.set_edge_attributes(G, {e: randint(1000, 5000) for e in G.edges}, 'weight')\n",
        "\n",
        "# Add nodes and edges with weight labels\n",
        "canvas.nodes(G.nodes).add()\n",
        "canvas.edges(G.edges).add(\n",
        "    labels=lambda e: {0: {'text': G.edges[e]['weight']}}\n",
        ")\n",
        "canvas.pause(1)\n",
        "\n",
        "# Select the source and target\n",
        "source = 0\n",
        "target = 2\n",
        "canvas.node(source).color('green').highlight().size('1.25x')\n",
        "canvas.node(target).color('red').highlight().size('1.25x')\n",
        "canvas.pause(1.5)\n",
        "\n",
        "canvas"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 461,
          "referenced_widgets": [
            "ae684b3d617e49d889352459f8c99859",
            "6252cd42ebca4e6ca2a715f62a1c1334"
          ]
        },
        "id": "OaWGvYxG1pQu",
        "outputId": "0c1821b4-a7c4-4ab3-a26a-dc9c55a728b0"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "JupyterWidget(events=['{\"attrs\": {\"size\": [500, 400]}}', '{\"attrs\": {\"nodes\": {\"0\": {}, \"1\": {}, \"2\": {}, \"3\":…"
            ],
            "application/vnd.jupyter.widget-view+json": {
              "version_major": 2,
              "version_minor": 0,
              "model_id": "ae684b3d617e49d889352459f8c99859"
            }
          },
          "metadata": {
            "application/vnd.jupyter.widget-view+json": {
              "colab": {
                "custom_widget_manager": {
                  "url": "https://ssl.gstatic.com/colaboratory-static/widgets/colab-cdn-widget-manager/d2e234f7cc04bf79/manager.min.js"
                }
              }
            }
          }
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# Find al possible paths between S and D and save it into paths list\n",
        "\n",
        "paths = []\n",
        "\n",
        "for i in nx.all_simple_paths(G, source=0, target=2):\n",
        "  print(i)\n",
        "#paths"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "XnCLd_w11z1i",
        "outputId": "167b870b-13da-452e-f013-14f6f2cf3ec6"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[0, 1, 2]\n",
            "[0, 1, 3, 2]\n",
            "[0, 2]\n",
            "[0, 3, 1, 2]\n",
            "[0, 3, 2]\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[]"
            ]
          },
          "metadata": {},
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# Required lists and dictionaries for data\n",
        "\n",
        "# DICTIONARIES\n",
        "# 1. Bandwidth demands (weights) : keep the end user demands\n",
        "# 2. Revenue (profit) : keep the profit each demand making\n",
        "# 3. Capacities of paths (knapsacks) : keep the edge value with minimum capacity in path\n",
        "# LISTS\n",
        "# 4. Classes: keep the same IDs of bandwidth and revenue dictionaries for applying in constraints\n",
        "# 4. Classes: keep the same IDs of path (knapsack) dictionary for applying in constraints\n",
        "\n",
        "# EXAMPELES\n",
        "# revenue = {'item_1': 50, 'item_2': 10, 'item_3': 30, 'item_4': 40, 'item_5': 50} \n",
        "# bw_dem = {'item_1': 1000, 'item_2': 2000, 'item_3': 3000, 'item_4': 4000, 'item_5': 5000} \n",
        "# capacities = {'path_1': 1000, 'path_2': 6000, 'path_3': 8000}. # Knapsack capacities\n",
        "\n",
        "# classes = ['item_1', 'item_2', 'item_3', 'item_4', 'item_5']\n",
        "# paths = ['path_1', 'path_2', 'path_3']"
      ],
      "metadata": {
        "id": "pFHBvwSM1z4J"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Generate random data for demand and revenue, also the class ids\n",
        "\n",
        "import random\n",
        "from random import randrange\n",
        "\n",
        "def dem(n):\n",
        "   mydict = {}\n",
        "   for i in range(n):\n",
        "     mydict['item_'+str(i)] = randrange(1000,5000)\n",
        "   return mydict\n",
        "\n",
        "def reven(n):\n",
        "   mydict = {}\n",
        "   for i in range(n):\n",
        "     mydict['item_'+str(i)] = randrange(10,100)\n",
        "   return mydict\n",
        "\n",
        "def clas(n):\n",
        "   mydict = []\n",
        "   for i in range(n):\n",
        "        mydict.append('item_'+str(i))\n",
        "     #mydict['item'+str(i)] = randrange(1000,5000)\n",
        "   return mydict\n",
        "\n",
        "\n",
        "# Generate dictionaries\n",
        "bw_dem = dem(10) \n",
        "revenue = reven(10)\n",
        "\n",
        "# Generate classes ids\n",
        "classes = clas(10)\n",
        "\n",
        "# print(\"Demands: \", bw_dem)\n",
        "# print(\"Revenues: \", revenue)\n",
        "# print(\"Classes: \", classes)"
      ],
      "metadata": {
        "id": "wlApal0F1z6w"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Generate paths (knapsacks) between S and D\n",
        "\n",
        "# Find min cut for every path\n",
        "\n",
        "import random\n",
        "from random import randrange\n",
        "paths = []\n",
        "\n",
        "def find_cut(path):                        # a function to get the edge with minimum capacity in each path\n",
        "  min = 1000000                            # a random value to maintain minimum capacity record in each path\n",
        "  i = 0                                    # index for keeping path number\n",
        "  x = 0                                    # u node of an edge\n",
        "  y = 1                                    # v node of an edge\n",
        "                                           # print(\"Path id: \", i )\n",
        "  for i in range(len(path) - 1):           # to get u and v nodes of every edge\n",
        "                                           # print(path[x], path[y])\n",
        "    d = G.get_edge_data(path[x], path[y])  # get edge record from dictionary\n",
        "    val = d['weight']                      # get the capacity value of edge\n",
        "    if val < min:                          # compare the capacity value of edge to see if it is minimum until now\n",
        "      min = val                            # keep the minimum value\n",
        "    x = x + 1\n",
        "    y = y + 1\n",
        "    i = i + 1\n",
        "                                          # print(\"Min cut is\", min, \" for path : \", path)\n",
        "  return min\n",
        "\n",
        "def path_d():                             # a fucntion to keep dicitonary of paths (knapsacks)           \n",
        "   z = 0                                  # index for maintaining path id\n",
        "   mydic = {}\n",
        "   path_id = []                           # list to only keep the path id\n",
        "   for path in nx.all_simple_paths(G, source=0, target=2):               # a built-in function of networkx for finding paths\n",
        "     path_id.append('path_'+str(z))\n",
        "                                          #print(\"Path id: \", path_id[z])\n",
        "     # paths.append(path)                 # already defined above\n",
        "     #print(\"Path nodes:\", path)\n",
        "\n",
        "     min_cut = find_cut(path)             # cal the function to get minimum capacity edge of every path\n",
        "     #print(\"Path id: \", path_id[z], \"Path: \", path , \"Min cut: \", min_cut)\n",
        "     mydic['path_'+str(z)] = randrange(1000,5000) # was used to assign random min edge capacity to each path\n",
        "     mydic['path_'+str(z)] = min_cut     # assign minimum cut value here to each path\n",
        "     z = z + 1\n",
        "   return mydic                          # the output is path ids with minimum edge capacities\n",
        "\n",
        "\n",
        "def path_l():                            # function for keeping the path ids that will be used if defining contraint\n",
        "   z = 0       \n",
        "   mylist = []\n",
        "   for i in nx.all_simple_paths(G, source=0, target=2):\n",
        "     mylist.append('path_'+str(z))\n",
        "     z = z + 1\n",
        "   return mylist                         # the output is path ids\n",
        "\n",
        "path_dic = path_d()\n",
        "path_list = path_l()\n",
        "# print(\"Path dic: \", path_dic)\n",
        "# print(\"Path list: \", path_list)"
      ],
      "metadata": {
        "id": "F0Y9mVzI2FYc"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Our data are listed belows, ready for apply multi-knapsack optimization to find the optimal placements\n",
        "\n",
        "print(\"Demands: \", bw_dem)\n",
        "print(\"Revenues: \", revenue)\n",
        "print(\"Classes: \", classes)\n",
        "\n",
        "print(\"Path dic: \", path_dic)\n",
        "print(\"Path list: \", path_list)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "vW93PFGt2Fa7",
        "outputId": "e731175d-a76a-474d-b135-afd9287272a7"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Demands:  {'item_0': 4380, 'item_1': 2515, 'item_2': 1989, 'item_3': 3265, 'item_4': 3656, 'item_5': 1401, 'item_6': 2460, 'item_7': 3900, 'item_8': 3314, 'item_9': 1446}\n",
            "Revenues:  {'item_0': 16, 'item_1': 90, 'item_2': 67, 'item_3': 87, 'item_4': 14, 'item_5': 16, 'item_6': 77, 'item_7': 10, 'item_8': 74, 'item_9': 66}\n",
            "Classes:  ['item_0', 'item_1', 'item_2', 'item_3', 'item_4', 'item_5', 'item_6', 'item_7', 'item_8', 'item_9']\n",
            "Path dic:  {'path_0': 2979, 'path_1': 2566, 'path_2': 3083, 'path_3': 3395, 'path_4': 1769}\n",
            "Path list:  ['path_0', 'path_1', 'path_2', 'path_3', 'path_4']\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Apply Gurobi Optimizer to find the optimal assignment of traffic demands to network paths between S and D"
      ],
      "metadata": {
        "id": "HSDSZhGF69Dh"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Apply optimization here\n",
        "\n",
        "import numpy as np\n",
        "import pandas as pd\n",
        "import gurobipy as gp\n",
        "from gurobipy import GRB\n",
        "\n",
        "# This value above are just exemples\n",
        "m = gp.Model('ks')\n",
        "\n",
        "# Insert the decision variables\n",
        "x = m.addVars(classes, path_list, vtype = gp.GRB.BINARY)\n",
        "\n",
        "# Define the objective function\n",
        "m.setObjective(gp.quicksum(x[i, j] * revenue[i] for i in classes for j in path_list), sense=gp.GRB.MAXIMIZE)\n",
        "\n",
        "# Constraint 1: satisfy the demand once, assign demand to only one knapsack at most\n",
        "c1 = m.addConstrs(gp.quicksum(x[i,j] for j in path_list) <= 1 for i in classes)\n",
        "\n",
        "# Constraint 2: respect the path capacity\n",
        "c2 = m.addConstrs(gp.quicksum(x[i,j] * bw_dem[i] for i in classes) <= path_dic[j] for j in path_list)\n",
        "\n",
        "# Run the model\n",
        "m.optimize()\n",
        "m.setParam(GRB.Param.OutputFlag, 0)\n",
        "\n",
        "# Status checking\n",
        "status = m.Status\n",
        "if status in (GRB.INF_OR_UNBD, GRB.INFEASIBLE, GRB.UNBOUNDED):\n",
        "    print('The model cannot be solved because it is infeasible or '\n",
        "            'unbounded')\n",
        "    sys.exit(1)\n",
        "\n",
        "if status != GRB.OPTIMAL:\n",
        "    print('Optimization was stopped with status ' + str(status))\n",
        "    sys.exit(1)"
      ],
      "metadata": {
        "id": "oHGgAFSh2FdP"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Display optimal values of decision variables\n",
        "for v in m.getVars():\n",
        "    if v.x > 1e-6:\n",
        "        print(v.varName, v.x)\n",
        "\n",
        "# Display optimal total matching score\n",
        "print('Total matching score: ', m.objVal)"
      ],
      "metadata": {
        "id": "a-xZsXwH2Ffz"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "x # to see all the combinations"
      ],
      "metadata": {
        "id": "lESySQUa7LuE"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}