set-covering.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "07b7c7f0",
   "metadata": {},
   "source": [
    "## Set Covering Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1337d766",
   "metadata": {},
   "source": [
    "![Set Covering - Sample Map](setcoveringmap.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f25a3c2a",
   "metadata": {},
   "source": [
    "- There are 14 street lamps.\n",
    "- A street is considered lit if at least **two** lamps are turned on.\n",
    "- What is the minimum number of lamps that need to be turned on?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "561a4105",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{aligned}\n",
    "\\min z = & x_1 + x_2 + x_3 + \\ldots +  x_{11} + x_{12} + x_{13} + x_{14} \\\\\n",
    "\\text{Subject to:} & \\\\\n",
    "& x_1 + x_2 + x_3 + x_4 \\ge 2 \\\\\n",
    "& x_5 + x_6 + x_7 + x_8 + x_9 \\ge 2\\\\\n",
    "& x_{11} + x_{12} + x_{13} + x_{14}  \\ge 2 \\\\\n",
    "& x_{1} + x_{5} + x_{11} \\ge 2 \\\\\n",
    "& x_{2} + x_{6} \\ge 2 \\\\\n",
    "& x_{3} + x_{7} + x_{12} \\ge 2 \\\\\n",
    "& x_{8} + x_{13} \\ge 2 \\\\\n",
    "& x_{4} + x_{9} + x_{14} \\ge 2 \\\\\n",
    "& x_i \\in \\{0, 1\\} , \\;\\; i = 1, 2, \\ldots , 14 \\\\\n",
    "\\end{aligned}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "38897ba6",
   "metadata": {},
   "outputs": [],
   "source": [
    "using JuMP, HiGHS\n",
    "\n",
    "m = Model(HiGHS.Optimizer)\n",
    "\n",
    "MOI.set(m, MOI.Silent(), true) \n",
    "\n",
    "@variable(m, x[1:14], Bin)\n",
    "\n",
    "@objective(m, Min, sum(x))\n",
    "\n",
    "@constraint(m, sum(x[1:4]) >= 2)\n",
    "@constraint(m, sum(x[5:9]) >= 2)\n",
    "@constraint(m, sum(x[11:14]) >= 2)\n",
    "@constraint(m, x[1] + x[5] + x[11] >= 2)\n",
    "@constraint(m, x[2] + x[6] >= 2)\n",
    "@constraint(m, x[3] + x[7] + x[12] >= 2)\n",
    "@constraint(m, x[8] + x[13] >= 2)\n",
    "@constraint(m, x[4] + x[9] + x[14] >= 2)\n",
    "\n",
    "optimize!(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "630654cb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10.0"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "objective_value(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "c2a38d92",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "14×2 Matrix{Float64}:\n",
       "  1.0  1.0\n",
       "  2.0  1.0\n",
       "  3.0  1.0\n",
       "  4.0  1.0\n",
       "  5.0  0.0\n",
       "  6.0  1.0\n",
       "  7.0  0.0\n",
       "  8.0  1.0\n",
       "  9.0  0.0\n",
       " 10.0  0.0\n",
       " 11.0  1.0\n",
       " 12.0  1.0\n",
       " 13.0  1.0\n",
       " 14.0  1.0"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hcat(1:14, value.(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "72f44c3b",
   "metadata": {},
   "source": [
    "### Modified Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c042f690",
   "metadata": {},
   "source": [
    "- There are 14 street lamps.\n",
    "- A street is considered lit if at least **one** lamp is turned on.\n",
    "- What is the minimum number of lamps that need to be turned on?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "e5f1472f",
   "metadata": {},
   "outputs": [],
   "source": [
    "using JuMP, HiGHS\n",
    "\n",
    "m = Model(HiGHS.Optimizer)\n",
    "\n",
    "MOI.set(m, MOI.Silent(), true) \n",
    "\n",
    "@variable(m, x[1:14], Bin)\n",
    "\n",
    "@objective(m, Min, sum(x))\n",
    "\n",
    "@constraint(m, sum(x[1:4]) >= 1)\n",
    "@constraint(m, sum(x[5:9]) >= 1)\n",
    "@constraint(m, sum(x[11:14]) >= 1)\n",
    "@constraint(m, x[1] + x[5] + x[11] >= 1)\n",
    "@constraint(m, x[2] + x[6] >= 1)\n",
    "@constraint(m, x[3] + x[7] + x[12] >= 1)\n",
    "@constraint(m, x[8] + x[13] >= 1)\n",
    "@constraint(m, x[4] + x[9] + x[14] >= 1)\n",
    "\n",
    "optimize!(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "0ea28f41",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5.0"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "objective_value(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "4116aeed",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "14×2 Matrix{Float64}:\n",
       "  1.0  0.0\n",
       "  2.0  1.0\n",
       "  3.0  0.0\n",
       "  4.0  1.0\n",
       "  5.0  0.0\n",
       "  6.0  0.0\n",
       "  7.0  0.0\n",
       "  8.0  1.0\n",
       "  9.0  0.0\n",
       " 10.0  0.0\n",
       " 11.0  1.0\n",
       " 12.0  1.0\n",
       " 13.0  0.0\n",
       " 14.0  0.0"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hcat(1:14, value.(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "600ff9f2",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.10.0-rc1",
   "language": "julia",
   "name": "julia-1.10"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}