coding-hometask-4-1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Задача 4-1. Линейное программирование: формулирование задачи.\n",
    "\n",
    "В этой задаче Вам предлагается закодировать задачу TSP для заданного графа в виде задачи ЦЛП с помощью условий MTZ (Миллера—Таккера—Землина) и поработать с библиотекой [PuLP](https://pypi.python.org/pypi/PuLP/1.6.5). Если Вы используете дистрибутив Anaconda, то эта библиотека не находится утилитой conda, зато совершенно нормально устанавливается с помощью pip:\n",
    "\n",
    "`pip install pulp`\n",
    "\n",
    "Вам дана функция `dist15`, которая по двум номерам вершин возвращает вес ребра между ними. Номера от 1 до 15, пример взят [отсюда](https://people.sc.fsu.edu/~jburkardt/datasets/tsp/tsp.html).\n",
    "Нужно построить соответствующую задачу ЦЛП и решить её средствами PuLP, чтобы найти оптимальный гамильтонов цикл в графе. Сделать это следует в функции `solve_tsp_with_lp`, которая получает на вход размерность задачи и весовую функцию, а на выходе даёт перестановку номеров вершин графа (нумеруемых с единицы), соответствующую оптимальному гамильтонову циклу."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def dist15(i: int, j: int) -> int:\n",
    "    return (\n",
    "        list(\n",
    "            map(\n",
    "                int, \n",
    "                filter(\n",
    "                    lambda s: len(s.strip()) > 0, '''\n",
    "                    0 29 82 46 68 52 72 42 51 55 29 74 23 72 46 \n",
    "                    29  0 55 46 42 43 43 23 23 31 41 51 11 52 21 \n",
    "                    82 55  0 68 46 55 23 43 41 29 79 21 64 31 51 \n",
    "                    46 46 68  0 82 15 72 31 62 42 21 51 51 43 64 \n",
    "                    68 42 46 82  0 74 23 52 21 46 82 58 46 65 23 \n",
    "                    52 43 55 15 74  0 61 23 55 31 33 37 51 29 59 \n",
    "                    72 43 23 72 23 61  0 42 23 31 77 37 51 46 33 \n",
    "                    42 23 43 31 52 23 42  0 33 15 37 33 33 31 37 \n",
    "                    51 23 41 62 21 55 23 33  0 29 62 46 29 51 11 \n",
    "                    55 31 29 42 46 31 31 15 29  0 51 21 41 23 37 \n",
    "                    29 41 79 21 82 33 77 37 62 51  0 65 42 59 61 \n",
    "                    74 51 21 51 58 37 37 33 46 21 65  0 61 11 55 \n",
    "                    23 11 64 51 46 51 51 33 29 41 42 61  0 62 23 \n",
    "                    72 52 31 43 65 29 46 31 51 23 59 11 62  0 59 \n",
    "                    46 21 51 64 23 59 33 37 11 37 61 55 23 59  0\n",
    "                    '''.split()\n",
    "                )\n",
    "            )\n",
    "        )[(i-1) * 15 + (j-1)]\n",
    "    )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "291.0\n",
      "1 ⟶ 13 ⟶ 2 ⟶ 15 ⟶ 9 ⟶ 5 ⟶ 7 ⟶ 3 ⟶ 12 ⟶ 14 ⟶ 10 ⟶ 8 ⟶ 6 ⟶ 4 ⟶ 11\n"
     ]
    }
   ],
   "source": [
    "import itertools\n",
    "from typing import List, Callable\n",
    "from pulp import LpVariable, LpProblem, LpConstraint, LpMinimize, LpAffineExpression\n",
    "\n",
    "def solve_tsp_with_lp(num_vertices: int, distance_function: Callable[[int, int], int]) -> List[int]:\n",
    "    lp = LpProblem(name='TSP using MTZ', sense=LpMinimize)\n",
    "\n",
    "    # Строим n^2 переменных x_{ij}; x_{ii} не нужны, но оставим их,\n",
    "    # чтобы избежать сложностей с индексами.\n",
    "    edge_vars = [[LpVariable(name='x_{}_{}'.format(i, j),\n",
    "                             lowBound=0, upBound=1, cat='Integer')\n",
    "                  for j in range(num_vertices)]\n",
    "                 for i in range(num_vertices)]\n",
    "\n",
    "    # Вводим дополнительные переменные u_{i} из условий Миллера-Таккера-Землина.\n",
    "    constr_vars = [LpVariable(name='u_{}'.format(i),\n",
    "                              lowBound=1, upBound=num_vertices, cat='Integer')\n",
    "                   for i in range(num_vertices)]\n",
    "    \n",
    "    # Добавляем условие минимизации: sum_{i, j} c_{ij} x_{ij} -> min.\n",
    "    flatten = lambda l: list(itertools.chain.from_iterable(l))    \n",
    "    lp.objective = LpAffineExpression(\n",
    "        flatten([[(edge_vars[i][j], distance_function(i + 1, j + 1))\n",
    "                  for j in range(num_vertices) if i != j]\n",
    "                 for i in range(num_vertices)]))\n",
    "    \n",
    "    # Ограничение - в каждую вершину входит только одно ребро: sum_{i} x_{ij} = 1.\n",
    "    for j in range(num_vertices):\n",
    "        lp += (LpAffineExpression([(edge_vars[i][j], 1)\n",
    "                                  for i in range(num_vertices) if i != j]) == 1)\n",
    "        \n",
    "    # Ограничение - из каждой вершины выходит только одно ребро: sum_{j} x_{ij} = 1.\n",
    "    for i in range(num_vertices):\n",
    "        lp += (LpAffineExpression([(edge_vars[i][j], 1)\n",
    "                                  for j in range(num_vertices) if i != j]) == 1)\n",
    "    \n",
    "    # Ограничения MTZ: u_{i} - u_{j} + nx_{ij} <= n - 1 для i =/= j от 2 до n.\n",
    "    for i in range(num_vertices):\n",
    "        for j in range(1, num_vertices):\n",
    "            if i != j:\n",
    "                lp += (constr_vars[i] - constr_vars[j] + \\\n",
    "                       num_vertices * edge_vars[i][j] <= num_vertices - 1)\n",
    "\n",
    "    lp_status = lp.solve()\n",
    "    print(lp.objective.value())\n",
    "\n",
    "    result = []\n",
    "    i, j = 0, 1\n",
    "    \n",
    "    while True:\n",
    "        result.append(i + 1)\n",
    "        for j in range(num_vertices):\n",
    "            if i != j and edge_vars[i][j].value() == 1:\n",
    "                i = j\n",
    "                break\n",
    "        if i == 0:\n",
    "            break\n",
    "        \n",
    "    # return list(range(1, num_vertices + 1))\n",
    "    return result\n",
    "    \n",
    "print(' ⟶ '.join(map(str, solve_tsp_with_lp(15, dist15))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Как использовать библиотеку PuLP\n",
    "\n",
    "Допустим, Вам нужно решить задачу СЦЛП: \\begin{array}{lll}\n",
    "2x+4y+3z & \\to & \\max,\\\\\n",
    "x,y,z &\\ge& 0,\\\\\n",
    "x,y&\\in& \\mathbb{Z},\\\\\n",
    "5x+2y&\\le& 10,\\\\\n",
    "7x+y &\\le& 9,\\\\\n",
    "3x+8z &\\le& 11.\n",
    "\\end{array}\n",
    "\n",
    "Ниже приведён достаточно само-описательный код программы, которая решает задачу с помощью библиотеки PuLP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "0.0 5.0 1.375\n"
     ]
    }
   ],
   "source": [
    "from pulp import LpVariable, LpProblem, LpConstraint, LpMaximize\n",
    "\n",
    "lp = LpProblem(name='My first linear program in PuLP', sense=LpMaximize)\n",
    "\n",
    "x = LpVariable(name='x', lowBound=0, upBound=None, cat='Integer')\n",
    "y = LpVariable(name='y', lowBound=0, upBound=None, cat='Integer')\n",
    "z = LpVariable(name='z', lowBound=0, upBound=None, cat='Continuous')\n",
    "\n",
    "lp.objective = 2*x + 4*y + 3*z\n",
    "\n",
    "lp += (5*x + 2*y <= 10)\n",
    "lp += (7*x + y <= 9)\n",
    "lp += (3*x + 8*z <= 11)\n",
    "\n",
    "lp_status = lp.solve()\n",
    "\n",
    "print(str(lp_status))\n",
    "print(\n",
    "    x.value(), \n",
    "    y.value(), \n",
    "    z.value()\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}