optimisation-comp30390/notebooks/a2-comp30930-18202817.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "54fcb516",
   "metadata": {},
   "source": [
    "# Assignment 2: Integer Linear Programming\n",
    "\n",
    "**Module**: COMP30930 Optimisation, Autumn 2021<br/>\n",
    "**Student**: Rajit Banerjee, 18202817"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "02f6ec89",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "┌ Info: Xpress: Found license file /Applications/FICO Xpress/xpressmp/bin/xpauth.xpr\n",
      "└ @ Xpress /Users/rajitbanerjee/.julia/packages/Xpress/eJoYN/src/license.jl:44\n",
      "┌ Info: Xpress: Development license detected.\n",
      "└ @ Xpress /Users/rajitbanerjee/.julia/packages/Xpress/eJoYN/src/license.jl:89\n"
     ]
    }
   ],
   "source": [
    "using JuMP\n",
    "using Xpress"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be39a36d",
   "metadata": {},
   "source": [
    "## Question 1: Modified Knapsack Problem\n",
    "\n",
    "- Classical knapsack problem: fill your knapsack with one or more of the six items below, while maximising the utility and allowing a weight of 15 Kg. \n",
    "- Additional constraint: at least 3 items must be picked.\n",
    "\n",
    "|  | C1 | C2 | C3 | C4 | C5 | C6 |\n",
    "| --- | --- | --- | --- | --- | --- | --- |\n",
    "| Utility | 4 | 2 | 1 | 7 | 3 | 6 |\n",
    "| Weight (Kg) | 5 | 8 | 8 | 6 | 1 | 5 |\n",
    "\n",
    "Let the $i^{th}$ item have a utility $u_i$ units and weight $w_i$ Kg. The objective is to select a subset with maximum utility, such that the summation of the weights of the selected items is less than or equal to 15 Kg. Moreover, the summation of indicator variables $x_i$ essentially counts the number of items in the backpack, which must be at least 3.\n",
    " \n",
    "Considering a set of binary decision variables $x_i$ that receive value 1 if the $i^{th}$ item is selected, and 0 if it is not selected, the resulting mathematical programming formulation (Integer Linear Program or ILP) is:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "Max.&\\; \\sum_{i \\in I}u_i.x_i \\\\\n",
    "s.t.&\\; \\sum_{i \\in I}w_i.x_i \\le 15 \\\\\n",
    "&\\sum_{i \\in I}x_i \\ge 3 \\\\\n",
    "x_i&\\in\\{0,1\\}\\;\\; \\forall i\\in I\n",
    "\\end{align}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "ed7a19f3",
   "metadata": {},
   "outputs": [],
   "source": [
    "utility = [4, 2, 1, 7, 3, 6]\n",
    "weight = [5, 8, 8, 6, 1, 5]\n",
    "N = 6\n",
    "W = 15\n",
    "min_items = 3;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "9e48315e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# helper to optimise any given model and show results\n",
    "function solve(model, x)\n",
    "    optimize!(model)\n",
    "    if termination_status(model) == MOI.OPTIMAL\n",
    "        @show value.(x)\n",
    "        @show objective_value(model)\n",
    "    elseif termination_status(model) == MOI.INFEASIBLE\n",
    "        println(\"The model is infeasible!\")\n",
    "    else\n",
    "        println(\"The model didn't solve properly for some other reason.\")\n",
    "    end\n",
    "end;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "b949cc0d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "value.(x) = [0.0, -0.0, -0.0, 1.0, 1.0, 1.0]\n",
      "objective_value(model) = 16.0\n"
     ]
    }
   ],
   "source": [
    "model = Model(Xpress.Optimizer)\n",
    "\n",
    "# Decision variables: x[i] = 1 if item i is included, else 0\n",
    "@variable(model, x[1:N], Bin)\n",
    "\n",
    "# Constraints\n",
    "@constraint(model, weight' * x ≤ W)\n",
    "@constraint(model, sum(x) ≥ min_items)\n",
    "\n",
    "# Maximise utility\n",
    "@objective(model, Max, utility' * x)\n",
    "solve(model, x);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9017206c",
   "metadata": {},
   "source": [
    "The solution suggests that items $C_4, C_5, C_6$ should be selected to obtain the maximum utility."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69179971",
   "metadata": {},
   "source": [
    "## Question 2: Branch-and-Bound\n",
    "\n",
    "Original binary integer problem:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "Max.&\\; 12x_1 + x_2 + 10x_3 + 2x_4 \\\\\n",
    "s.t.&\\; 16x_1 + 2x_2 + 10x_3 + 8x_4 \\le 18 \\\\\n",
    "x_i &\\in \\{0, 1\\} \\;for\\; i = 1, ..., 4 \\\\\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "The above ILP can be solved using the branch-and-bound algorithm by systematically fixing values of $x_1, x_2, x_3, x_4$, to partition the entire set of feasible solutions into smaller and smaller subsets. The subproblems thus obtained can be solved using LP (Linear Program) relaxations, and fathoming steps can be applied to prune branches until we find an optimal integer-valued solution, if it exists."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "504f24d9",
   "metadata": {},
   "source": [
    "**Subproblem 0: Fixing $x_1 = 0$**\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "Max.&\\; 12x_1 + x_2 + 10x_3 + 2x_4 \\\\\n",
    "s.t.&\\; 16x_1 + 2x_2 + 10x_3 + 8x_4 \\le 18 \\\\\n",
    "0 &\\le x_i \\le 1 \\;for\\; i = 2, 3, 4 \\\\\n",
    "x_1 &= 0\n",
    "\\end{align}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "3c6e58b7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "value.(x) = [0.0, 1.0, 1.0, 0.75]\n",
      "objective_value(model) = 12.5\n"
     ]
    }
   ],
   "source": [
    "# Subproblem 0\n",
    "model = Model(Xpress.Optimizer)\n",
    "@variable(model, 0 ≤ x[1:4] ≤ 1)\n",
    "@objective(model, Max, 12x[1] + x[2] + 10x[3] + 2x[4])\n",
    "\n",
    "@constraint(model, 16x[1] + 2x[2] + 10x[3] + 8x[4] ≤ 18)\n",
    "@constraint(model, x[1] == 0)\n",
    "\n",
    "solve(model, x);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bc464a91",
   "metadata": {},
   "source": [
    "Since this a maximisation problem, we have achieved an upper bound = 12.5. We will keep this branch open for further exploration later."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f7ab3fc",
   "metadata": {},
   "source": [
    "**Subproblem 1: Fixing $x_1 = 1$**\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "Max.&\\; 12x_1 + x_2 + 10x_3 + 2x_4 \\\\\n",
    "s.t.&\\; 16x_1 + 2x_2 + 10x_3 + 8x_4 \\le 18 \\\\\n",
    "0 &\\le x_i \\le 1 \\;for\\; i = 2, 3, 4 \\\\\n",
    "x_1 &= 1\n",
    "\\end{align}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "f73d79f2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "value.(x) = [1.0, 0.0, 0.2, 0.0]\n",
      "objective_value(model) = 14.0\n"
     ]
    }
   ],
   "source": [
    "# Subproblem 1\n",
    "model = Model(Xpress.Optimizer)\n",
    "@variable(model, 0 ≤ x[1:4] ≤ 1)\n",
    "@objective(model, Max, 12x[1] + x[2] + 10x[3] + 2x[4])\n",
    "\n",
    "@constraint(model, 16x[1] + 2x[2] + 10x[3] + 8x[4] ≤ 18)\n",
    "@constraint(model, x[1] == 1)\n",
    "\n",
    "solve(model, x);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8eae078f",
   "metadata": {},
   "source": [
    "Subproblem 1 gives a better upper bound = 14, hence we can explore this branch further."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a19a13e0",
   "metadata": {},
   "source": [
    "**Subproblem 1-0: Fixing $x_1 = 1, x_2 = 0$**\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "Max.&\\; 12x_1 + x_2 + 10x_3 + 2x_4 \\\\\n",
    "s.t.&\\; 16x_1 + 2x_2 + 10x_3 + 8x_4 \\le 18 \\\\\n",
    "0 &\\le x_i \\le 1 \\;for\\; i = 3, 4 \\\\\n",
    "x_1 &= 1, x_2 = 0\n",
    "\\end{align}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "623084d2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "value.(x) = [1.0, 0.0, 0.2, 0.0]\n",
      "objective_value(model) = 14.0\n"
     ]
    }
   ],
   "source": [
    "# Subproblem 1-0\n",
    "model = Model(Xpress.Optimizer)\n",
    "@variable(model, 0 ≤ x[1:4] ≤ 1)\n",
    "@objective(model, Max, 12x[1] + x[2] + 10x[3] + 2x[4])\n",
    "\n",
    "@constraint(model, 16x[1] + 2x[2] + 10x[3] + 8x[4] ≤ 18)\n",
    "@constraint(model, x[1] == 1)\n",
    "@constraint(model, x[2] == 0)\n",
    "\n",
    "solve(model, x);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "defee65f",
   "metadata": {},
   "source": [
    "Best upper bound stays at 14."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c07f7da7",
   "metadata": {},
   "source": [
    "**Subproblem 1-1: Fixing $x_1 = 1, x_2 = 1$**\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "Max.&\\; 12x_1 + x_2 + 10x_3 + 2x_4 \\\\\n",
    "s.t.&\\; 16x_1 + 2x_2 + 10x_3 + 8x_4 \\le 18 \\\\\n",
    "0 &\\le x_i \\le 1 \\;for\\; i = 3, 4 \\\\\n",
    "x_1 &= 1, x_2 = 1\n",
    "\\end{align}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "11fda0b7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "value.(x) = [1.0, 1.0, 0.0, 0.0]\n",
      "objective_value(model) = 13.0\n"
     ]
    }
   ],
   "source": [
    "# Subproblem 1-1\n",
    "model = Model(Xpress.Optimizer)\n",
    "@variable(model, 0 ≤ x[1:4] ≤ 1)\n",
    "@objective(model, Max, 12x[1] + x[2] + 10x[3] + 2x[4])\n",
    "\n",
    "@constraint(model, 16x[1] + 2x[2] + 10x[3] + 8x[4] ≤ 18)\n",
    "@constraint(model, x[1] == 1)\n",
    "@constraint(model, x[2] == 1)\n",
    "\n",
    "solve(model, x);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a391a39",
   "metadata": {},
   "source": [
    "We have obtained an integer-valued solution with z* = 13, allowing us to fathom the current branch with $x_1 = 1, x_2 = 1$. Moreover, the branch with $x_1 = 0$ (objective value = 12.5) can also be fathomed, since 12.5 < z*.\n",
    "\n",
    "The only branch still open for exploration starts with $x_1 = 1, x_2 = 0$, with an upper bound of 14."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c765eae0",
   "metadata": {},
   "source": [
    "**Subproblem 1-0-0: Fixing $x_1 = 1, x_2 = 0, x_3 = 0$**\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "Max.&\\; 12x_1 + x_2 + 10x_3 + 2x_4 \\\\\n",
    "s.t.&\\; 16x_1 + 2x_2 + 10x_3 + 8x_4 \\le 18 \\\\\n",
    "0 &\\le x_4 \\le 1 \\\\\n",
    "x_1 &= 1, x_2 = 0, x_3 = 0\n",
    "\\end{align}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "0398ac4d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "value.(x) = [1.0, 0.0, 0.0, 0.25]\n",
      "objective_value(model) = 12.5\n"
     ]
    }
   ],
   "source": [
    "# Subproblem 1-0-0\n",
    "model = Model(Xpress.Optimizer)\n",
    "@variable(model, 0 ≤ x[1:4] ≤ 1)\n",
    "@objective(model, Max, 12x[1] + x[2] + 10x[3] + 2x[4])\n",
    "\n",
    "@constraint(model, 16x[1] + 2x[2] + 10x[3] + 8x[4] ≤ 18)\n",
    "@constraint(model, x[1] == 1)\n",
    "@constraint(model, x[2] == 0)\n",
    "@constraint(model, x[3] == 0)\n",
    "\n",
    "solve(model, x);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "51486822",
   "metadata": {},
   "source": [
    "Fathom branch with objective value 12.5 < z*."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c7c06aa",
   "metadata": {},
   "source": [
    "**Subproblem 1-0-1: Fixing $x_1 = 1, x_2 = 0, x_3 = 1$**\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "Max.&\\; 12x_1 + x_2 + 10x_3 + 2x_4 \\\\\n",
    "s.t.&\\; 16x_1 + 2x_2 + 10x_3 + 8x_4 \\le 18 \\\\\n",
    "0 &\\le x_4 \\le 1 \\\\\n",
    "x_1 &= 1, x_2 = 0, x_3 = 1\n",
    "\\end{align}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "17e0b706",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The model is infeasible!\n"
     ]
    }
   ],
   "source": [
    "# Subproblem 1-0-1\n",
    "model = Model(Xpress.Optimizer)\n",
    "@variable(model, 0 ≤ x[1:4] ≤ 1)\n",
    "@objective(model, Max, 12x[1] + x[2] + 10x[3] + 2x[4])\n",
    "\n",
    "@constraint(model, 16x[1] + 2x[2] + 10x[3] + 8x[4] ≤ 18)\n",
    "@constraint(model, x[1] == 1)\n",
    "@constraint(model, x[2] == 0)\n",
    "@constraint(model, x[3] == 1)\n",
    "\n",
    "solve(model, x);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06f26c51",
   "metadata": {},
   "source": [
    "Fathom infeasible subproblem."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6bd314e",
   "metadata": {},
   "source": [
    "Hence, all possible branches have now been explored, and the optimal integer-valued solution is as follows:\n",
    "\n",
    "```\n",
    "value.(x) = [1.0, 1.0, 0.0, 0.0]\n",
    "objective_value(model) = 13.0\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f49d96fb",
   "metadata": {},
   "source": [
    "The above solution can be verified by solving the ILP directly below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "a9064c60",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "value.(x) = [1.0, 1.0, -0.0, -0.0]\n",
      "objective_value(model) = 13.0\n"
     ]
    }
   ],
   "source": [
    "model = Model(Xpress.Optimizer)\n",
    "@variable(model, x[1:4], Bin)\n",
    "@objective(model, Max, 12x[1] + x[2] + 10x[3] + 2x[4])\n",
    "\n",
    "@constraint(model, 16x[1] + 2x[2] + 10x[3] + 8x[4] ≤ 18)\n",
    "\n",
    "solve(model, x);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d6145d21",
   "metadata": {},
   "source": [
    "Verified. Branch-and-bound successfully found an optimal solution for the given ILP."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7b08831",
   "metadata": {},
   "source": [
    "## Question 3: Vertex Cover\n",
    "\n",
    "Given a graph $G = (V, E)$ (vertices and edges), the minimum vertex cover problem can be formulated as a minimisation of the number of vertices selected, such that every edge in the graph is covered (at least one vertex of an edge must be in the cover set).\n",
    "\n",
    "Considering a set of binary decision variables $x_i$ that receive value 1 if vertex $i$  is selected, and 0 if it is not selected, the resulting mathematical programming formulation (Integer Linear Program or ILP) is:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "Min.&\\; \\sum_{i \\in V} x_i \\\\\n",
    "s.t.&\\; x_u + x_v \\ge 1 \\;\\;\\forall \\{u, v\\} \\in E \\\\\n",
    "x_i &\\in \\{0, 1\\} \\;\\;\\forall i \\in V\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Given an undirected, unweighted graph:\n",
    "$$\n",
    "V = \\{1, 2, 3, 4, 5, 6\\} \\\\\n",
    "E = \\{\\{1, 2\\}, \\{1, 3\\}, \\{2, 3\\}, \\{3, 4\\}, \\{4, 5\\}, \\{4, 6\\}, \\{5, 6\\}\\}\n",
    "$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "6ed8a2ef",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Graph G = (V, E)\n",
    "V = [1, 2, 3, 4, 5, 6]\n",
    "E = [\n",
    "    (1, 2),\n",
    "    (1, 3),\n",
    "    (2, 3),\n",
    "    (3, 4),\n",
    "    (4, 5),\n",
    "    (4, 6),\n",
    "    (5, 6)\n",
    "]\n",
    "N = 6;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "148a48af",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "value.(x) = [1.0, -0.0, 1.0, -0.0, 1.0, 1.0]\n",
      "objective_value(model) = 4.0\n"
     ]
    }
   ],
   "source": [
    "model = Model(Xpress.Optimizer)\n",
    "\n",
    "# Decision variables: x[i] = 1 if vertex i is included, else 0\n",
    "@variable(model, x[1:N], Bin)\n",
    "@objective(model, Min, sum(x))\n",
    "\n",
    "# Constraints: every edge of G must be covered\n",
    "for (u, v) in E\n",
    "    # At least one of x[u] or x[v] should be selected\n",
    "    @constraint(model, x[u] + x[v] ≥ 1)\n",
    "end\n",
    "\n",
    "solve(model, x);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7fb68418",
   "metadata": {},
   "source": [
    "The solution suggests that the **minimum vertex cover** $S_1 = \\{1, 3, 5, 6\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "854c98af",
   "metadata": {},
   "source": [
    "Next, we can consider the LP relaxation of the ILP formulation above.\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "Min.&\\; \\sum_{i \\in V} x_i \\\\\n",
    "s.t.&\\; x_u + x_v \\ge 1 \\;\\;\\forall \\{u, v\\} \\in E \\\\\n",
    "0 &\\le x_i \\le 1 \\;\\;\\forall i \\in V\n",
    "\\end{align}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "3f44744e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "value.(x) = [0.5, 0.5, 0.5, 0.5, 0.5, 0.5]\n",
      "objective_value(model) = 3.0\n"
     ]
    }
   ],
   "source": [
    "model = Model(Xpress.Optimizer)\n",
    "@variable(model, 0 ≤ x[1:N] ≤ 1)\n",
    "@objective(model, Min, sum(x))\n",
    "\n",
    "for (u, v) in E\n",
    "    @constraint(model, x[u] + x[v] ≥ 1)\n",
    "end\n",
    "\n",
    "solve(model, x);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f45d01d0",
   "metadata": {},
   "source": [
    "From the super-optimal fractional solution $S_2$ of the LP relaxation above, we can obtain a legal integral solution: the set of vertices, $S_3 = \\{1, 2, 3, 4, 5, 6\\}$. \n",
    "\n",
    "All 6 vertices are included in the set, since each of the decision variables in $S_2$ has a value $ \\ge 0.5$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c630e43e",
   "metadata": {},
   "source": [
    "Cardinality of $S_3$ is 6, whereas that of $S_1$ is only 4. This is significant because the LP relaxation of any minimum vertex cover problem is a 2-approximation problem, i.e. the approximation yields a result that is at most twice (in terms of set cardinality in this problem) of the optimal solution."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.6.2",
   "language": "julia",
   "name": "julia-1.6"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}