primal-dual algorithm for vertex cover.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "eaa1d902",
   "metadata": {},
   "source": [
    "# Primal-dual algorithm for vertex cover problem\n",
    "\n",
    "The basic idea of the algorithm in this notebook is that instead of actually solving the dual LP, we can construct a feasible dual solution with the same properties. In this case, constructing the dual solution is much faster than solving the dual LP, and hence leads to a much faster algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "07dde56e",
   "metadata": {},
   "source": [
    "## The Primal-Dual method for approximation algorithm\n",
    "\n",
    "the primal-dual algorithm just tries to find a feasible solution and then reduces the duality gap (in a controlled way) \n",
    "\n",
    "the general form of primal-dual algorithm is explained as bellow:\n",
    "\n",
    "assume x is a soulution for primal algorithm and y is a solution for dual algorithm.\n",
    "\n",
    "<div style=\"background-color:rgba(0, 0, 0, 0.0470588); padding:10px 0;font-family:monospace;padding-left:15px;\">\n",
    "    we pick a feasable y. for example y = 0 <br>\n",
    "    A = $ \\phi $ <br>\n",
    "    l = 0 : l is a counter <br>\n",
    "    while A is not feasible in primal :    <br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp; l = l+1 <br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp; $\\nu$ = Violation(A) <br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp; Increase $ y_k $ uniformly for all $ T_k \\in \\nu $ until \n",
    "     $ \\exists e_l \\notin A : \\sum_{i:e_l \\in T_i} {y_i} = c_i$ <br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp; $ A = A\\cup \\left \\{ e_l \\right \\} $ <br>\n",
    "    output(A)\n",
    "</div>\n",
    "\n",
    "the general form of algorithm is explaind more [here](http://www.cs.toronto.edu/~bor/2420f10/williamson-primal-dual.pdf)\n",
    "\n",
    "now we want to solve vertex cover problem by Primal-Dual algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1acff184",
   "metadata": {},
   "source": [
    "## Vertex cover Problem\n",
    "\n",
    "Given an undirected graph with vertices $ \\in $ V and edges $ \\in $ E and edge of $ v_i $ has weight of $ w_i $, the vertex cover problem is to find minimum size vertex cover.\n",
    "\n",
    "if we illustrate the primal and dual form of this problem, we reach to these two formulas. \n",
    "\n",
    "Primal:\n",
    "\n",
    "$ min \\sum_{u}{w_u x_u} $ <br>\n",
    "$ s.t. $ <br>\n",
    "$ x_u + x_v \\geq 1 \\quad \\forall uv \\in E $ <br>\n",
    "$  x_u \\geq 0 \\quad \\forall u \\in V $\n",
    "\n",
    "Dual:\n",
    "\n",
    "$ max \\sum_{e}{y_e} $ <br>\n",
    "$ s.t. $ <br>\n",
    "$ \\sum_{e:u \\in e}{y_e} \\leq w_u \\quad \\forall u \\in V $ <br>\n",
    "$  y_e \\geq 0 \\quad \\forall e \\in E $\n",
    "\n",
    "we want to construct integer solution x for (P), y for (D)\n",
    "\n",
    "we start with $ x = (0 , ... , 0 ) $ and $ y = (0 , ... , 0 ) $\n",
    "\n",
    "- x has low value but is not feasible\n",
    "- y is feasible but has low value\n",
    "\n",
    "now we are trying to make x feasible, step by step. and in order to make it happen, we use y.\n",
    "\n",
    "the Primal-Dual algorithm for this problem is shown below:\n",
    "\n",
    "<div style=\"background-color:rgba(0, 0, 0, 0.0470588); padding:10px 0;font-family:monospace;padding-left:15px;\">\n",
    "    start with $ x = (0 , ... , 0 ) $ and $ y = (0 , ... , 0 ) $ <br>\n",
    "    Repeat : <br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp; pick e = uv such that $ x_u + x_v < 1 $ (a constraint in primal is not satisfied) <br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp; Increase $ y_e $ such that\n",
    "     $ \\sum_{f: u \\in f} {y_f} = w_u $ or $ \\sum_{f: v \\in f} {y_f} = w_v $ <br>\n",
    "    &nbsp;&nbsp;&nbsp;&nbsp; first case : $ x_u \\leftarrow 1 $    &nbsp;&nbsp; second case : $ x_v \\leftarrow 1 $ <br>\n",
    "    output(A)\n",
    "</div>\n",
    "\n",
    "during execution of algorithm:\n",
    "- y remains feasible throughout the execution\n",
    "- x has fewer and fewer violated constraints\n",
    "\n",
    "in the end :\n",
    "- both are feasible\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f9568d5d",
   "metadata": {},
   "source": [
    "## vertex cover problem in python\n",
    "### we construct a graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c9abec99",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Graph:\n",
    "    def __init__(self, vertices):\n",
    "        self.V = vertices\n",
    "        self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]\n",
    "        self.weights = [0 for _ in range(vertices)]\n",
    "        self.E = 0\n",
    "        self.edges = dict()\n",
    "\n",
    "    def add_edge(self, u, v):\n",
    "        self.graph[u][v] = self.graph[v][u] = 1\n",
    "        self.edges[frozenset((u, v))] = len(self.edges)\n",
    "        self.E += 1\n",
    "\n",
    "    def get_edge(self, u, v):\n",
    "        return self.edges[frozenset([u, v])]\n",
    "\n",
    "\n",
    "g = Graph(7)\n",
    "g.add_edge(0, 1)\n",
    "g.add_edge(1, 2)\n",
    "g.add_edge(3, 1)\n",
    "g.add_edge(2, 3)\n",
    "g.add_edge(0, 3)\n",
    "g.add_edge(3, 4)\n",
    "g.add_edge(0, 4)\n",
    "g.add_edge(3, 5)\n",
    "g.add_edge(3, 6)\n",
    "g.weights = [4, 5, 6, 2, 1, 7, 3]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4c4ef2e0",
   "metadata": {},
   "source": [
    "we want to build this graph\n",
    "\n",
    "<img src=\"graph.png\" alt=\"graph\">\n",
    "\n",
    "## we start Primal-Dual algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "4aff2f4e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 1. initial values of x and y\n",
    "X = [0 for _ in range(g.V)]\n",
    "Y = [0 for _ in range(g.E)]\n",
    "\n",
    "\n",
    "def pick_an_edge(g, X):\n",
    "    for u, v in g.edges:\n",
    "        if X[u] + X[v] < 1 and u != v:\n",
    "            return u, v, g.get_edge(u, v), False\n",
    "    return -1, -1, -1, True\n",
    "\n",
    "\n",
    "while True:\n",
    "    # 2. pick e = uv such that X_u + X_v < 1\n",
    "    u, v, e, are_all_primal_constraints_satisfied = pick_an_edge(g, X)\n",
    "    if are_all_primal_constraints_satisfied:\n",
    "        break\n",
    "    # 3. increase Y_e such that Sigma Y_f = W_u or Sigma Y_f = W_v\n",
    "    ΔW_u = g.weights[u] - sum([Y[g.get_edge(u, i)] for i in range(g.V) if g.graph[i][u] == 1])\n",
    "    ΔW_v = g.weights[v] - sum([Y[g.get_edge(v, i)] for i in range(g.V) if g.graph[i][v] == 1])\n",
    "\n",
    "    if ΔW_u > ΔW_v:\n",
    "        Y[g.get_edge(u, v)] += ΔW_v\n",
    "        X[v] = 1\n",
    "    else:\n",
    "        Y[g.get_edge(u, v)] += ΔW_u\n",
    "        X[u] = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "e10a00c5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "value of x :  [1, 1, 0, 1, 0, 0, 0]\n",
      "value of y :  [4, 1, 0, 2, 0, 0, 0, 0, 0]\n",
      "weight :  11\n"
     ]
    }
   ],
   "source": [
    "print('value of x : ',X)\n",
    "print('value of y : ',Y)\n",
    "print('weight : ', sum([X[i] * g.weights[i] for i in range(g.V)]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d6232fb",
   "metadata": {},
   "source": [
    "- output = {0, 1, 3}\n",
    "- optimal value = {4, 1, 3}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "32924b45",
   "metadata": {},
   "source": [
    "## faster way\n",
    "function of picking edges at previous section takes a long time. we can rewrite the algorithm like bellow:\n",
    "note that we saved edges while we were building the graph. if we didn't do that, we can run a BFS to iterate between edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "e5b88c45",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "value of x :  [1, 1, 0, 1, 0, 0, 0]\n",
      "value of y :  [4, 1, 0, 2, 0, 0, 0, 0, 0]\n",
      "weight :  11\n"
     ]
    }
   ],
   "source": [
    "X = [0 for _ in range(g.V)]\n",
    "Y = [0 for _ in range(g.E)]\n",
    "\n",
    "for u, v in g.edges:\n",
    "    e = g.get_edge(u,v)\n",
    "    ΔW_u = g.weights[u] - sum([Y[g.get_edge(u, i)] for i in range(g.V) if g.graph[i][u] == 1])\n",
    "    ΔW_v = g.weights[v] - sum([Y[g.get_edge(v, i)] for i in range(g.V) if g.graph[i][v] == 1])\n",
    "    if ΔW_u > ΔW_v:\n",
    "        Y[g.get_edge(u, v)] += ΔW_v\n",
    "        X[v] = 1\n",
    "    else:\n",
    "        Y[g.get_edge(u, v)] += ΔW_u\n",
    "        X[u] = 1\n",
    "        \n",
    "print('value of x : ',X)\n",
    "print('value of y : ',Y)\n",
    "print('weight : ', sum([X[i] * g.weights[i] for i in range(g.V)]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f5af7296",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}