{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "*Combinatorial Optimization course, FEE CTU in Prague*. Created by [Industrial Informatics Department](https://iid.ciirc.cvut.cz/)."
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "%pip install -i https://pypi.gurobi.com gurobipy\n",
    "import gurobipy as g\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import networkx as nx"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Automatized model tuning\n",
    "As an example, we will revisit the model for Game of Fiver which for larger board sizes took considerable time to solve:"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "def game_of_fivers(n, params=None):\n",
    "  m = g.Model()\n",
    "\n",
    "  x = m.addVars(n+2, n+2, vtype=g.GRB.BINARY, obj=1)\n",
    "  k = m.addVars(range(1,n+1), range(1,n+1), vtype=g.GRB.INTEGER)\n",
    "\n",
    "  for i in range(1,n+1):\n",
    "      for j in range(1,n+1):\n",
    "          m.addConstr(x[i,j] + x[i+1, j] + x[i-1,j] + x[i,j+1] + x[i,j-1] == 2*k[i,j] + 1)\n",
    "          \n",
    "  m.addConstr(x.sum(0,\"*\") + x.sum(n+1,\"*\") + x.sum(\"*\",0) + x.sum(\"*\",n+1) == 0)\n",
    "\n",
    "  m.write('fivers_n{}.lp'.format(n))\n",
    "\n",
    "  if params is not None:\n",
    "    m.params.CutPasses = 10\n",
    "    m.params.PreDual = 1\n",
    "    m.params.outputflag = 0\n",
    "\n",
    "  m.optimize()\n",
    "\n",
    "  X = [[int(round(x[i,j].X)) for j in range(1,n+1)] for i in range(1,n+1)]\n",
    "  return m.runtime"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "# run with default parameters\n",
    "def_time = game_of_fivers(21)\n",
    "print('Time with default settings: {}s'.format(def_time))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "# lets try to tune some of the params\n",
    "model = g.read('fivers_n21.lp')\n",
    "\n",
    "model.params.tuneResults = 1\n",
    "model.params.TuneTimeLimit = 30   # how much time to invest into the tuning\n",
    "\n",
    "model.tune()\n",
    "if model.tuneResultCount > 0:\n",
    "    model.getTuneResult(0)\n",
    "    model.write('fivers_tuned_params.prm')"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "print('Time before tuning: {}s'.format(def_time))\n",
    "print('Time after tuning: {}s'.format(game_of_fivers(21, {'CutPasses': 10, 'PreDual':1})))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Nonlinear constrains"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "n = 200\n",
    "t = np.linspace(0, 20, n)\n",
    "y = 3*np.sin(t)+np.cos(6*t)+0.5*t+3\n",
    "\n",
    "plt.plot(t, y)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "m = g.Model()\n",
    "\n",
    "u = m.addVar(vtype=g.GRB.CONTINUOUS)\n",
    "v = m.addVar(vtype=g.GRB.CONTINUOUS)\n",
    "m.addGenConstrPWL(u, v, t, y)\n",
    "\n",
    "m.setObjective(v)\n",
    "\n",
    "m.optimize()\n",
    "\n",
    "\n",
    "plt.plot(t, y)\n",
    "plt.plot(u.x, v.x, marker='o', markersize=8, color=\"red\")"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Solution pool"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "dg = nx.DiGraph()\n",
    "dg = nx.random_k_out_graph(40, 5, 0.4, seed=22)\n",
    "pos = nx.spring_layout(dg)\n",
    "nx.draw(dg, pos, node_color='k', node_size=3, edge_color='grey', with_labels=True)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "s = 28\n",
    "t = 4\n",
    "E = dg.edges()\n",
    "E = dict.fromkeys(E)\n",
    "V = dg.nodes()\n",
    "np.random.seed(69)\n",
    "w = np.random.randint(0, 50, len(E))\n",
    "\n",
    "m = g.Model()\n",
    "x = m.addVars(E.keys(), vtype=g.GRB.BINARY, ub=1, obj=w)\n",
    "\n",
    "m.addConstr(g.quicksum([x[s, j] for k, j in E if k == s]) == 1)\n",
    "m.addConstr(g.quicksum([x[i, t] for i, k in E if k == t]) == 1)\n",
    "\n",
    "for i in V:\n",
    "  if i not in [s, t]:\n",
    "    m.addConstr(g.quicksum([x[i, j] for k, j in E if k == i]) == g.quicksum([x[j, i] for j, k in E if k == i]))\n",
    "\n",
    "m.setParam(g.GRB.Param.PoolSolutions, 3)\n",
    "m.setParam(g.GRB.Param.PoolSearchMode, 2)   # k-best solutions\n",
    "m.optimize()\n",
    "\n",
    "sols = [0]*m.solcount\n",
    "colorlist = ['r', 'g', 'b']\n",
    "\n",
    "print('Found {} solutions.'.format(m.solcount))\n",
    "for sol_idx in range(m.solcount):\n",
    "  print('Sol no. {}'.format(sol_idx+1))\n",
    "  sols[sol_idx] = []\n",
    "  m.setParam(g.GRB.Param.SolutionNumber, sol_idx)\n",
    "  for i, j in E:\n",
    "    if x[i, j].xn > 0.5:\n",
    "      print(i, j)\n",
    "      sols[sol_idx] += [(i, j)]\n",
    "\n",
    "nx.draw(dg, pos, node_color='k', node_size=3, edge_color='grey')\n",
    "\n",
    "for k in range(m.solcount):\n",
    "  nx.draw_networkx_edges(dg, pos, edgelist=sols[k], edge_color=colorlist[k], width=3)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Bratley revisited: CP model"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Visualization\n",
    "import matplotlib.pyplot as plt \n",
    "\n",
    "def plot_solution(s, p):\n",
    "    \"\"\"\n",
    "    s: solution vector\n",
    "    p: processing times\n",
    "    \"\"\"\n",
    "    fig = plt.figure(figsize=(10,2))\n",
    "    ax = plt.gca()\n",
    "    ax.set_xlabel('time')     \n",
    "    ax.grid(True) \n",
    "    ax.set_yticks([2.5])\n",
    "    ax.set_yticklabels([\"oven\"]) \n",
    "    eps = 0.25  # just to show spaces between the dishes\n",
    "    ax.broken_barh([(s[i], p[i]-eps) for i in range(len(s))], (0, 5), \n",
    "                   facecolors=('tab:orange', 'tab:green', 'tab:red', 'tab:blue', 'tab:gray'))\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Load data\n",
    "path = \"./bratley_data/instances/public_3.txt\"\n",
    "\n",
    "with open(path, \"r\") as f_in:\n",
    "    lines = f_in.readlines()\n",
    "        \n",
    "    n = int(lines[0].strip())\n",
    "    r,d,p = [],[],[]\n",
    "    \n",
    "    for i in range(n):\n",
    "        (pi, ri, di) = list(map(int, lines[1+i].split()))\n",
    "        r.append(ri)\n",
    "        p.append(pi)\n",
    "        d.append(di)\n",
    "        \n",
    "print(\"r\", r, \"d\", d, \"p\", p, sep=\"\\n\")"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Generate data \n",
    "from numpy import random as rnd\n",
    "import numpy as np\n",
    "rnd.seed(15)\n",
    "\n",
    "n = 200\n",
    "p = [rnd.randint(1,100) for i in range(n)]\n",
    "\n",
    "r = [0 for i in range(n)]\n",
    "for i in range(1,n):\n",
    "    r[i] = int(round(r[i-1] + rnd.exponential(0.5* sum(p)/len(p))))\n",
    "\n",
    "d = [ int(round(r[i] + p[i] + rnd.exponential(100*sum(p)/len(p)) )) for i in range(n)]\n",
    "print(\"r\", r, \"d\", d, \"p\", p, sep=\"\\n\")"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## CP model"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "from docplex.cp.model import CpoModel\n",
    "from docplex.cp.config import context\n",
    "import sys\n",
    "\n",
    "# Create model\n",
    "m = CpoModel()\n",
    "\n",
    "# - add variables\n",
    "tasks = [m.interval_var(name=\"task{:d}\".format(i), optional=False, size=p[i]) for i in range(n)]\n",
    "seq = m.sequence_var(tasks, name='seq')\n",
    "\n",
    "# - set objective\n",
    "m.add(m.minimize(m.max([m.end_of(tasks[i]) for i in range(n)]) ) )  # minimize C_max\n",
    "\n",
    "# - add constraints\n",
    "for i in range(n):\n",
    "    m.add(m.start_of(tasks[i]) >= r[i])  # release time\n",
    "    m.add(m.end_of(tasks[i]) <= d[i])    # deadline\n",
    "\n",
    "m.add(m.no_overlap(seq))  # one task executed at one time\n",
    "\n",
    "# Solve the model\n",
    "msol = m.solve(TimeLimit=10, LogVerbosity=\"Normal\", LogPeriod=1, Workers=1)\n",
    "\n",
    "\n",
    "# Print the solution\n",
    "print()\n",
    "if msol.is_solution():\n",
    "    starts = [msol.get_value(tasks[i])[0] for i in range(n)]\n",
    "    print(*starts, sep=\"\\n\")\n",
    "else:\n",
    "    print(\"No solution found.\")\n",
    "    \n",
    "print(\"Done\")"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "plot_solution(starts, p)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## ILP model"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "import gurobipy as g\n",
    "m = g.Model()\n",
    "\n",
    "# - add variables\n",
    "s = m.addVars(n, vtype=g.GRB.CONTINUOUS, lb=0)\n",
    "x = {}\n",
    "for i in range(n):\n",
    "    for j in range(i + 1, n):\n",
    "        x[i, j] = m.addVar(vtype=g.GRB.BINARY)\n",
    "\n",
    "Cmax = m.addVar(vtype=g.GRB.CONTINUOUS, obj=1)\n",
    "\n",
    "# - add constraints\n",
    "for i in range(n):\n",
    "    m.addConstr(s[i] + p[i] <= Cmax)\n",
    "    m.addConstr(s[i] >= r[i])\n",
    "    m.addConstr(s[i] + p[i] <= d[i])\n",
    "\n",
    "M = max(d)\n",
    "for i in range(n):\n",
    "    for j in range(i + 1, n):\n",
    "        m.addConstr(s[i] + p[i] <= s[j] + M*(1-x[i, j]))\n",
    "        m.addConstr(s[j] + p[j] <= s[i] + M*x[i, j])\n",
    "\n",
    "# call the solver -----------------------------------------------\n",
    "m.optimize()\n",
    "\n",
    "print()\n",
    "if m.SolCount > 0:\n",
    "    starts = [s[i].X for i in range(n)]\n",
    "else:\n",
    "    print(\"No solution was found.\")\n",
    "    \n",
    "print(\"Done\")"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "plot_solution(starts, p)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "# TSP"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "import math\n",
    "from collections import namedtuple\n",
    "import gurobipy as g\n",
    "\n",
    "Point = namedtuple(\"Point\", ['x', 'y'])\n",
    "\n",
    "def length(point1, point2):\n",
    "    return int(round(math.sqrt((point1.x - point2.x)**2 + (point1.y - point2.y)**2)))  # CP works with int only\n",
    "\n",
    "class TSP:\n",
    "    def __init__(self):\n",
    "        D = None  # distance matrix\n",
    "        points = None  # vertices        \n",
    "        \n",
    "    def load_instance(self, path):        \n",
    "        input_data_file = open(path, 'r')\n",
    "        input_data = ''.join(input_data_file.readlines())\n",
    "\n",
    "        # parse the input\n",
    "        lines = input_data.split('\\n')\n",
    "        nodeCount = int(lines[0])\n",
    "\n",
    "        points = []\n",
    "        for i in range(1, nodeCount+1):            \n",
    "            parts = lines[i].split()\n",
    "            points.append(Point(float(parts[0]), float(parts[1])))\n",
    "\n",
    "        # distance matrix\n",
    "        D = [[0 for _ in range(nodeCount+1)] for _ in range(nodeCount+1)]  # Add dummy vertex last\n",
    "        for i in range(nodeCount):\n",
    "            for j in range(nodeCount):\n",
    "                D[i][j] = length(points[i], points[j])\n",
    "                \n",
    "        # the last vertex is the same as the first one\n",
    "        for i in range(nodeCount):\n",
    "            D[i][-1] = D[i][0]\n",
    "            D[-1][i] = D[0][i]\n",
    "            \n",
    "                \n",
    "        self.D = D\n",
    "        self.points = points\n",
    "        \n",
    "        return self"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "instances = [\n",
    "        {\"inst\": TSP().load_instance(\"./tsp_data/tsp_5_1\"),\n",
    "         \"init\": [0, 1, 2, 4, 3]},\n",
    "        {\"inst\": TSP().load_instance(\"./tsp_data/tsp_51_1\"),\n",
    "         \"init\": [0, 5, 2, 28, 10, 9, 45, 3, 46, 8, 4, 35, 13, 7, 19, 40, 18, 11, 42, 37, 20, 25, 1, 31, 22, 48, 32, 17, 49, 39, 50, 38, 15, 44, 14, 16, 29, 43, 21, 30, 12, 23, 34, 24, 41, 27, 36, 6, 26, 47, 33]},\n",
    "        {\"inst\": TSP().load_instance(\"./tsp_data/tsp_70_1\"),\n",
    "         \"init\": [0, 35, 50, 11, 57, 2, 56, 27, 21, 49, 58, 53, 41, 36, 38, 52, 6, 5, 7, 51, 55, 68, 46, 67, 24, 16, 44, 39, 22, 1, 14, 15, 20, 29, 28, 45, 12, 31, 18, 26, 3, 59, 9, 25, 4, 10, 61, 43, 32, 8, 64, 54, 48, 62, 13, 19, 60, 42, 37, 66, 40, 17, 30, 23, 69, 33, 65, 34, 47, 63]},\n",
    "        {\"inst\": TSP().load_instance(\"./tsp_data/tsp_100_1\"),\n",
    "         \"init\": [0, 6, 69, 61, 76, 35, 84, 11, 9, 26, 72, 47, 40, 94, 81, 60, 64, 66, 8, 23, 70, 59, 33, 67, 43, 37, 65, 71, 19, 15, 75, 14, 53, 46, 5, 29, 80, 38, 91, 57, 41, 50, 12, 55, 98, 39, 24, 68, 2, 28, 73, 87, 48, 85, 21, 96, 42, 77, 16, 7, 10, 74, 30, 18, 17, 34, 22, 99, 93, 51, 3, 89, 13, 31, 44, 62, 25, 82, 86, 54, 1, 27, 45, 88, 79, 97, 49, 90, 20, 63, 52, 92, 95, 78, 83, 32, 4, 56, 58, 36]},\n",
    "        {\"inst\": TSP().load_instance(\"./tsp_data/tsp_200_1\"),\n",
    "         \"init\": [0, 103, 62, 192, 5, 48, 89, 148, 117, 9, 128, 83, 136, 23, 37, 108, 177, 181, 98, 106, 35, 160, 125, 131, 123, 58, 73, 20, 145, 71, 111, 46, 97, 22, 114, 112, 178, 59, 61, 163, 119, 154, 141, 34, 85, 26, 11, 19, 146, 130, 166, 76, 164, 179, 60, 24, 80, 101, 134, 68, 167, 129, 188, 158, 102, 172, 88, 168, 41, 30, 79, 55, 199, 132, 144, 96, 180, 196, 3, 64, 65, 195, 25, 186, 151, 110, 183, 147, 69, 21, 15, 87, 143, 162, 93, 150, 115, 17, 78, 52, 165, 18, 191, 198, 118, 109, 74, 135, 156, 173, 7, 113, 91, 159, 57, 176, 50, 86, 56, 6, 8, 105, 153, 174, 82, 54, 107, 121, 33, 28, 45, 116, 124, 133, 189, 42, 2, 13, 197, 157, 40, 70, 99, 187, 47, 127, 138, 137, 170, 29, 171, 182, 161, 84, 67, 72, 122, 49, 43, 169, 175, 190, 193, 194, 149, 38, 185, 95, 155, 51, 77, 104, 4, 142, 36, 32, 75, 12, 94, 81, 1, 63, 39, 120, 53, 140, 66, 27, 92, 126, 90, 44, 184, 31, 100, 152, 14, 16, 10, 139]}\n",
    "]"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "inst_id = 4\n",
    "inst = instances[inst_id][\"inst\"]\n",
    "init_order = instances[inst_id][\"init\"]"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "INITIALIZE = False"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## ILP"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "nodeCount = len(inst.points)\n",
    "points = inst.points\n",
    "\n",
    "# Create model\n",
    "m = g.Model(\"tsp\")\n",
    "\n",
    "# - add variables\n",
    "x = m.addVars(nodeCount,nodeCount, vtype=g.GRB.BINARY, name=\"x\")        \n",
    "u = m.addVars(nodeCount, vtype=g.GRB.INTEGER, lb=0, name=\"u\")\n",
    "\n",
    "# - set objective\n",
    "obj = g.quicksum(g.quicksum(inst.D[i][j]*x[i,j] for j in range(nodeCount)) for i in range(nodeCount))\n",
    "m.setObjective(obj, g.GRB.MINIMIZE)\n",
    "\n",
    "# - add constraints\n",
    "m.addConstrs((1 == g.quicksum(x[i,j] for j in range(nodeCount)) for i in range(nodeCount)))\n",
    "m.addConstrs((1 == g.quicksum(x[j,i] for j in range(nodeCount)) for i in range(nodeCount)))\n",
    "\n",
    "for i in range(1, nodeCount):\n",
    "    for j in range(1, nodeCount):\n",
    "        m.addConstr(u[i]-u[j]+1 <= nodeCount*(1-x[i,j]))\n",
    "\n",
    "# Initialization\n",
    "if INITIALIZE:\n",
    "    for i, order in enumerate(init_order):                \n",
    "        u[order].start = i        \n",
    "        \n",
    "m.Params.TimeLimit = 10\n",
    "m.optimize()\n",
    "\n",
    "\n",
    "# Print the solution\n",
    "print()\n",
    "if m.SolCount > 0:\n",
    "    obj = m.objVal\n",
    "    print(\"Objective {}\".format(obj))\n",
    "\n",
    "    order = [u[i].X for i in range(nodeCount)]\n",
    "    indices = range(nodeCount)\n",
    "    s = sorted(zip(order,indices), key=lambda x: x[0])\n",
    "    print([x[1] for x in s])    \n",
    "else:\n",
    "    print(\"No solution was found.\")\n",
    "    \n",
    "print(\"Done\")"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## CP"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "from docplex.cp.model import CpoModel\n",
    "from docplex.cp.config import context\n",
    "import sys\n",
    "\n",
    "node_count = len(inst.points)\n",
    "points = inst.points\n",
    "\n",
    "# Create model\n",
    "m = CpoModel()\n",
    "\n",
    "# - add variables\n",
    "cities = [m.interval_var(name=\"city{:d}\".format(i), optional=False, size=1) for i in range(node_count+1)]\n",
    "seq = m.sequence_var(cities, name='seq', types=([i for i in range(node_count)] + [0]))\n",
    "\n",
    "# - set objective\n",
    "m.add(m.minimize(m.max([m.end_of(cities[i]) for i in range(len(cities))]) - len(cities)))\n",
    "\n",
    "# - add constraints\n",
    "m.add(m.first(seq, cities[0]))  # start from city 0\n",
    "m.add(m.last(seq, cities[-1]))  # repeat the same city last\n",
    "m.add(m.no_overlap(seq, inst.D, True))\n",
    "\n",
    "# Solve the model\n",
    "msol = m.solve(TimeLimit=10, LogVerbosity=\"Verbose\", LogPeriod=1, Workers=1)\n",
    "\n",
    "# Print the solution\n",
    "print()\n",
    "if msol.is_solution():\n",
    "    \n",
    "    ovals = msol.get_objective_values()\n",
    "    print(\"Objective {}\".format(ovals[0]))\n",
    "    \n",
    "    starts = [msol.get_value(cities[i])[0] for i in range(len(cities)-1)]\n",
    "    indices = range(len(cities)-1)\n",
    "    s = sorted(zip(starts,indices), key=lambda x: x[0])\n",
    "    \n",
    "    print([x[1] for x in s])    \n",
    "else:\n",
    "    print(\"No solution found.\")\n",
    "    \n",
    "print(\"Done\")"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Comparison\n",
    "\n",
    "Best objective found by ILP and CP model under 10s timelimit. (without initialization)\n",
    "\n",
    "| instance | ILP | CP    |\n",
    "|----------|-----|-------|\n",
    "| 5        | 3   | 3     |\n",
    "| 50       | 496 | 441   |\n",
    "| 70       | 994 | 710   |\n",
    "| 100      | -   | 22247 |\n",
    "| 200      | -   | 31962 |"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "Masterclass.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.7.4"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}