Optimize.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Google Hash Code 2018 using ILP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Import data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### import modules"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "import glob\n",
    "import numpy as np\n",
    "from gurobipy import *\n",
    "from itertools import product"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### get file list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['data/a_example.in',\n",
       " 'data/b_should_be_easy.in',\n",
       " 'data/c_no_hurry.in',\n",
       " 'data/d_metropolis.in',\n",
       " 'data/e_high_bonus.in']"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "files = glob.glob(\"data/*\")\n",
    "files = sorted(files)\n",
    "files"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### select file to pick"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "FILE_N = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(files[FILE_N]) as file:\n",
    "    file_iter = iter(list(file))\n",
    "    \n",
    "header = next(file_iter)\n",
    "header_elem = iter(header.split(\" \"))\n",
    "\n",
    "n_row = int(next(header_elem))\n",
    "n_col = int(next(header_elem))\n",
    "n_vehic = int(next(header_elem))\n",
    "n_rides = int(next(header_elem))\n",
    "bonus_point = int(next(header_elem))\n",
    "n_turns = int(next(header_elem))\n",
    "\n",
    "start_pos = np.zeros((n_rides,2), dtype=int)\n",
    "end_pos = np.zeros((n_rides,2), dtype=int)\n",
    "early_start_turn = np.zeros(n_rides, dtype=int)\n",
    "late_end_turn = np.zeros(n_rides, dtype=int)\n",
    "\n",
    "for i,e in enumerate(file_iter):\n",
    "    elements = iter(e.split(\" \"))\n",
    "    start_pos[i,0] = int(next(elements))\n",
    "    start_pos[i,1] = int(next(elements))\n",
    "    end_pos[i,0] = int(next(elements))\n",
    "    end_pos[i,1] = int(next(elements))\n",
    "    early_start_turn[i] = int(next(elements))\n",
    "    late_end_turn[i] = int(next(elements))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Preprocessing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### compute the length of rides"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "length_trip = np.sum(np.abs(start_pos - end_pos),axis=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### compute the latest a ride can start and the earliest a ride can finish"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "late_start_turn = late_end_turn - length_trip\n",
    "early_end_turn = early_start_turn + length_trip\n",
    "max_delay = late_start_turn - early_start_turn"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### compute distance from ride to ride"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "start_distance = np.sum(start_pos,axis=1)\n",
    "valid_transition = np.zeros((n_rides,n_rides),dtype=bool)\n",
    "distance = np.zeros((n_rides,n_rides),dtype=int)\n",
    "\n",
    "for i,j in product(range(n_rides),range(n_rides)):\n",
    "    \n",
    "    distance[i,j] = np.sum(np.abs(end_pos[i] - start_pos[j]))\n",
    "    \n",
    "    if early_end_turn[i] + distance[i,j] <= late_start_turn[j] and i != j:\n",
    "        valid_transition[i,j] = True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Create ILP model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = Model()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Initialize variables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "start_transition = np.empty((n_rides,),dtype=np.object)\n",
    "end_transition = np.empty((n_rides,),dtype=np.object)\n",
    "delay = np.empty((n_rides,),dtype=np.object)\n",
    "bonus = np.empty((n_rides,),dtype=np.object)\n",
    "\n",
    "for i in range(n_rides):\n",
    "    start_transition[i] = m.addVar(vtype=GRB.BINARY, name=\"t_S_\"+str(i))\n",
    "    end_transition[i] = m.addVar(vtype=GRB.BINARY, name=\"t_\"+str(i)+\"_E\")\n",
    "    delay[i] = m.addVar(lb=0,ub=max_delay[i],vtype=GRB.INTEGER, name=\"d_\"+str(i))\n",
    "    bonus[i] = m.addVar(vtype=GRB.BINARY, name=\"bonus_\"+str(i))\n",
    "\n",
    "transition = np.empty((n_rides,n_rides),dtype=np.object)\n",
    "\n",
    "for i,j in product(range(n_rides),range(n_rides)):\n",
    "    if valid_transition[i,j]:\n",
    "        transition[i,j] = m.addVar(vtype=GRB.BINARY, name=\"t_\"+str(i)+\"_\"+str(j))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Add constrins"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "m.addConstr(sum(start_transition) <= n_vehic,\"start_constrain\")\n",
    "\n",
    "for i in range(n_rides):\n",
    "    incoming_transitions = start_transition[i] + sum(transition[valid_transition[:,i],i])\n",
    "    outgoing_transitions = sum(transition[i,valid_transition[i,:]]) + end_transition[i]\n",
    "    \n",
    "    m.addConstr(incoming_transitions <= 1,name=\"at_most_one_\"+str(i))\n",
    "    m.addConstr(incoming_transitions == outgoing_transitions, name=\"io_euqal_\"+str(i))\n",
    "    m.addConstr(incoming_transitions >= bonus[i],name=\"bonus_if_ride_taken_\"+str(i))\n",
    "    \n",
    "    m.addConstr((1 - bonus[i])*max_delay[i] >= delay[i],\"bonus_apply_\"+str(i))\n",
    "    \n",
    "    m.addConstr(early_start_turn[i] + delay[i] + (1-start_transition[i])*(start_distance[i]-early_start_turn[i]-max_delay[i]) >= start_distance[i] , name=\"delay_S_\"+str(i))\n",
    "    \n",
    "for i,j in product(range(n_rides),range(n_rides)):\n",
    "    if valid_transition[i,j]:\n",
    "        m.addConstr(early_end_turn[i] + delay[i] + distance[i,j] <= early_start_turn[j] + delay[j] + (1-transition[i,j])*(max_delay[i]+distance[i,j]+early_end_turn[i]-early_start_turn[j]), name=\"delay_\"+str(i)+\"_\"+str(j))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Objective fuction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimize a model with 44607 rows, 44306 columns and 304737 nonzeros\n",
      "Variable types: 0 continuous, 44306 integer (44006 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 2e+04]\n",
      "  Objective range  [2e+01, 1e+03]\n",
      "  Bounds range     [1e+00, 2e+03]\n",
      "  RHS range        [1e+00, 2e+03]\n",
      "Found heuristic solution: objective 60585.000000\n",
      "Presolve removed 38534 rows and 1808 columns\n",
      "Presolve time: 1.11s\n",
      "Presolved: 6073 rows, 42498 columns, 100031 nonzeros\n",
      "Variable types: 0 continuous, 42498 integer (42216 binary)\n",
      "\n",
      "Root relaxation: objective 1.720770e+05, 2488 iterations, 0.40 seconds\n",
      "\n",
      "    Nodes    |    Current Node    |     Objective Bounds      |     Work\n",
      " Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time\n",
      "\n",
      "H    0     0                    172077.00000 2.3909e+07      -     -    1s\n",
      "     0     0          -    0      172077.000 172077.000  0.00%     -    2s\n",
      "\n",
      "Explored 0 nodes (9425 simplex iterations) in 2.07 seconds\n",
      "Thread count was 4 (of 4 available processors)\n",
      "\n",
      "Solution count 2: 172077 60585 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 1.720770000000e+05, best bound 1.720770000000e+05, gap 0.0000%\n"
     ]
    }
   ],
   "source": [
    "m.setObjective(bonus_point*sum(bonus) + \n",
    "               sum(length_trip[j]*transition[i,j] for i,j in product(range(n_rides),range(n_rides)) if valid_transition[i,j]) +\n",
    "               sum(start_transition[i]*length_trip[i] for i in range(n_rides)),\n",
    "               GRB.MAXIMIZE)\n",
    "\n",
    "m.write(\"model.lp\")\n",
    "m.optimize()\n",
    "m.write(\"model.sol\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Parse solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "vfunc = np.vectorize(lambda v: np.int(v.x) if v is not None else 0)\n",
    "start_transition = vfunc(start_transition)\n",
    "transition = vfunc(transition)\n",
    "bonus = vfunc(bonus)\n",
    "delay = vfunc(delay)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "vehicle_path = [[] for _ in range(n_vehic)]\n",
    "\n",
    "for i,node in enumerate(np.argwhere(start_transition).flatten()):\n",
    "    while node != -1:\n",
    "        vehicle_path[i].append(node)\n",
    "        nodes = np.argwhere(transition[node,:]).flatten()\n",
    "        if len(nodes) < 1:\n",
    "            node = -1\n",
    "        else:\n",
    "            node = nodes[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "out_dir = \"out\"\n",
    "if not os.path.exists(out_dir):\n",
    "    os.makedirs(out_dir)\n",
    "    \n",
    "out_file = os.path.join(out_dir,os.path.splitext(os.path.basename(files[FILE_N]))[0] + \".out\")\n",
    "\n",
    "with open(out_file,\"w\") as out:\n",
    "    for vp in vehicle_path:\n",
    "        out.write(str(len(vp)))\n",
    "        for e in vp:\n",
    "            out.write(\" \"+str(e))\n",
    "        out.write(\"\\n\")"
   ]
  }
 ],
 "metadata": {
  "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}