Benchmark of Google's or-tools and a prototype cython interface

or_tools_SimpleMinCostFlow_cython_benchmark.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from ortools.graph.pywrapgraph import SimpleMinCostFlow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create graph\n",
    "# 1 start and 1 stop. All intercenected via some nodes\n",
    "\n",
    "seed = 1\n",
    "n_int = int(1e7) # N intconecting_nodes\n",
    "\n",
    "edges = np.concatenate([\n",
    "    np.stack([0*np.ones(n_int), np.arange(2, n_int+2)], axis=1),\n",
    "    np.stack([np.arange(2, n_int+2), 1*np.ones(n_int)], axis=1)\n",
    "]).astype('int32')\n",
    "\n",
    "costs = np.random.randint(low=0, high=100, size=len(edges)).astype('int32')\n",
    "capacities = np.random.randint(low=1, high=n_int, size=len(edges)).astype('int32')\n",
    "\n",
    "supplies = np.concatenate([[1, -1], np.zeros(n_int)]).astype('int32')\n",
    "\n",
    "N_edges = edges.shape[0]\n",
    "N_nodes = len(supplies)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Current interface"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [],
   "source": [
    "min_cost_flow = SimpleMinCostFlow()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1min 15s, sys: 2.72 s, total: 1min 18s\n",
      "Wall time: 1min 30s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "for i in range(0, N_edges):\n",
    "    min_cost_flow.AddArcWithCapacityAndUnitCost(int(edges[i, 0]), int(edges[i, 1]),\n",
    "                                                int(capacities[i]), int(costs[i]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 16.2 s, sys: 84 ms, total: 16.3 s\n",
      "Wall time: 18.2 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "for i in range(0, N_nodes):\n",
    "    min_cost_flow.SetNodeSupply(i, int(supplies[i]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 16.6 s, sys: 3.89 s, total: 20.5 s\n",
      "Wall time: 23.3 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "if min_cost_flow.Solve() != min_cost_flow.OPTIMAL:\n",
    "    raise Exception('There was an issue with the min cost flow input.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 19.7 s, sys: 504 ms, total: 20.2 s\n",
      "Wall time: 23.4 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "flow = np.array([min_cost_flow.Flow(i) for i in range(N_edges)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Cython interface"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [],
   "source": [
    "min_cost_flow_vec = SimpleMinCostFlowVectorized()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 11.3 s, sys: 664 ms, total: 12 s\n",
      "Wall time: 12.4 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "min_cost_flow_vec.AddArcWithCapacityAndUnitCostVectorized(edges[:,0], edges[:,1], capacities, costs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 3.37 s, sys: 12 ms, total: 3.38 s\n",
      "Wall time: 3.39 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "min_cost_flow_vec.SetNodeSupplyVectorized(np.arange(N_nodes, dtype='int32'), supplies)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 15.2 s, sys: 3.63 s, total: 18.9 s\n",
      "Wall time: 20 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "if min_cost_flow_vec.Solve() != min_cost_flow_vec.OPTIMAL:\n",
    "    raise Exception('There was an issue with the min cost flow input.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 8.31 s, sys: 296 ms, total: 8.61 s\n",
      "Wall time: 9.07 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "flow = min_cost_flow_vec.FlowVectorized(np.arange(N_edges, dtype='int32'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| Step          | Current interface | Cython interface |\n",
    "|---------------|-------------------|------------------|\n",
    "| AddArc        | 90 s              | 12.4 s           |\n",
    "| SetNodeSupply | 18.2 s            | 3.39 ms          |\n",
    "| Solve         | 23.3 s            | 20 s             |\n",
    "| Flow          | 23.4 s            | 9.07 s           |\n",
    "| **Total**         | **154.9 s**           | **41.1 s**          |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Time comparision"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Cython interface code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%cython\n",
    "import numpy as np\n",
    "cimport numpy as np\n",
    "cimport cython\n",
    "\n",
    "from ortools.graph._pywrapgraph import \\\n",
    "    SimpleMinCostFlow_AddArcWithCapacityAndUnitCost,\\\n",
    "    SimpleMinCostFlow_SetNodeSupply,\\\n",
    "    SimpleMinCostFlow_Flow\n",
    "\n",
    "DTYPE = np.int32\n",
    "ctypedef np.int32_t DTYPE_t\n",
    "\n",
    "\n",
    "@cython.boundscheck(False)\n",
    "@cython.wraparound(False)\n",
    "def SimpleMinCostFlow_AddArcWithCapacityAndUnitCostVectorized(\n",
    "        self,\n",
    "        np.ndarray[DTYPE_t, ndim=1] tail,\n",
    "        np.ndarray[DTYPE_t, ndim=1] head,\n",
    "        np.ndarray[DTYPE_t, ndim=1] capacity,\n",
    "        np.ndarray[DTYPE_t, ndim=1] unit_cost):\n",
    "\n",
    "    cdef int len = tail.shape[0]\n",
    "\n",
    "    assert tail.dtype == DTYPE\n",
    "    assert head.dtype == DTYPE\n",
    "    assert capacity.dtype == DTYPE\n",
    "    assert unit_cost.dtype == DTYPE\n",
    "    assert head.shape[0] == len\n",
    "    assert capacity.shape[0] == len\n",
    "    assert unit_cost.shape[0] == len\n",
    "\n",
    "    for i in range(len):\n",
    "        SimpleMinCostFlow_AddArcWithCapacityAndUnitCost(self, tail[i], head[i], capacity[i], unit_cost[i])\n",
    "\n",
    "\n",
    "@cython.boundscheck(False)\n",
    "@cython.wraparound(False)\n",
    "def SimpleMinCostFlow_SetNodeSupplyVectorized(self,\n",
    "                                              np.ndarray[DTYPE_t, ndim=1] node,\n",
    "                                              np.ndarray[DTYPE_t, ndim=1] supply):\n",
    "    cdef int len = node.shape[0]\n",
    "\n",
    "    assert node.dtype == DTYPE\n",
    "    assert supply.dtype == DTYPE\n",
    "    assert supply.shape[0] == len\n",
    "\n",
    "    for i in range(len):\n",
    "        SimpleMinCostFlow_SetNodeSupply(self, node[i], supply[i])\n",
    "\n",
    "\n",
    "@cython.boundscheck(False)\n",
    "@cython.wraparound(False)\n",
    "def SimpleMinCostFlow_FlowVectorized(self,\n",
    "                                     np.ndarray[DTYPE_t, ndim=1] arc):\n",
    "\n",
    "    cdef int len = arc.shape[0]\n",
    "\n",
    "    assert arc.dtype == DTYPE\n",
    "\n",
    "    cdef np.ndarray flow = np.zeros(len, dtype=DTYPE)\n",
    "\n",
    "    for i in range(len):\n",
    "        flow[i] = SimpleMinCostFlow_Flow(self, arc[i])\n",
    "\n",
    "    return flow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SimpleMinCostFlowVectorized(SimpleMinCostFlow):\n",
    "\n",
    "    def AddArcWithCapacityAndUnitCostVectorized(self, tail, head, capacity, unit_cost):\n",
    "        return SimpleMinCostFlow_AddArcWithCapacityAndUnitCostVectorized(self, tail, head, capacity, unit_cost)\n",
    "\n",
    "    def SetNodeSupplyVectorized(self, node, supply):\n",
    "        return SimpleMinCostFlow_SetNodeSupplyVectorized(self, node, supply)\n",
    "\n",
    "    def FlowVectorized(self, arc):\n",
    "        return SimpleMinCostFlow_FlowVectorized(self, arc)"
   ]
  }
 ],
 "metadata": {
  "creator": "josh",
  "kernelspec": {
   "display_name": "Python (env python3_dataiku)",
   "language": "python",
   "name": "py-dku-venv-python3_dataiku"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  },
  "tags": []
 },
 "nbformat": 4,
 "nbformat_minor": 1
}