examples/lns_knapsack.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# LNS Example 1: Knapsack\n",
    "\n",
    "The first example is the knapsack problem. We have a set of items $I$ with a weight $w_i$ and a value $v_i$.\n",
    "We want to select a subset of items such that the total weight does not exceed a given capacity $C$ and the total value is maximized.\n",
    "\n",
    "$$\\max \\sum_{i \\in I} v_i x_i$$\n",
    "$$\\text{s.t.} \\sum_{i \\in I} w_i x_i \\leq C$$\n",
    "$$x_i \\in \\{0,1\\}$$\n",
    "\n",
    "This is one of the simplest NP-hard problems and can be solved with a dynamic programming approach in pseudo-polynomial time.\n",
    "CP-SAT is also able to solve many large instances of this problem in an instant.\n",
    "However, its simple structure makes it a good example to demonstrate the use of Large Neighborhood Search, even if the algorithm will\n",
    "not be of much use for this problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "# import all dependencies\n",
    "import typing\n",
    "import math\n",
    "import random\n",
    "\n",
    "from ortools.sat.python import cp_model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Instance Generation\n",
    "\n",
    "First, we need to create some random instances."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Instance generation\n",
    "class Item:\n",
    "    \"\"\"\n",
    "    A simple class to represent an item in the knapsack problem.\n",
    "    Every instance of this class is unique, i.e., two items with\n",
    "    the same weight and value are not equal. Otherwise, we could\n",
    "    only have a single item for each weight and value combination.\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, weight: int, value: int):\n",
    "        self.weight = weight\n",
    "        self.value = value\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"Item({self.weight}, {self.value})\"\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        return id(self) == id(other)\n",
    "\n",
    "    def __hash__(self):\n",
    "        return id(self)\n",
    "\n",
    "\n",
    "class Instance:\n",
    "    \"\"\"\n",
    "    Simple instance container.\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, items: typing.List[Item], capacity: int) -> None:\n",
    "        self.items = items\n",
    "        self.capacity = capacity\n",
    "        assert len(items) > 0\n",
    "        assert capacity > 0\n",
    "\n",
    "\n",
    "def random_instance(num_items: int, ratio: float) -> Instance:\n",
    "    \"\"\"\n",
    "    Creates a random instance of the knapsack problem.\n",
    "    :param num_items: The number of items.\n",
    "    :param ratio: The ratio between capacity and sum of weights.\n",
    "    :return: A list of items and a capacity\n",
    "    \"\"\"\n",
    "    items = []\n",
    "    for i in range(num_items):\n",
    "        weight = random.randint(10, 1000)\n",
    "        value = round(random.triangular(1, 100, 5) * weight)\n",
    "        items.append(Item(weight, value))\n",
    "    capacity = math.ceil(sum(item.weight for item in items) * ratio)\n",
    "    return Instance(items, capacity)\n",
    "\n",
    "\n",
    "def value(items: typing.List[Item]) -> int:\n",
    "    \"\"\"\n",
    "    Returns the total value of a list of items.\n",
    "    \"\"\"\n",
    "    return sum(item.value for item in items)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Greedy Algorithm\n",
    "\n",
    "Next, we need an initial solution.\n",
    "We use a simple greedy algorithm that adds items to the knapsack as long as the capacity is not exceeded.\n",
    "It would be much smarter to sort the items by value/weight ratio and add the items with the highest ratio first.\n",
    "However, this would often create near-optimal solution, and then we wouldn't see much improvement from the LNS."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Simple greedy algorithm for the knapsack problem\n",
    "def greedy_solution(instance: Instance) -> typing.List[Item]:\n",
    "    \"\"\"\n",
    "    A simple greedy algorithm for the knapsack problem.\n",
    "    It is bad on purpose, so we can improve it with local search.\n",
    "    For random instances, the greedy algorithm otherwise often\n",
    "    finds the (nearly) optimal solution and there is nothing to see.\n",
    "    \"\"\"\n",
    "    solution = []\n",
    "    remaining_capacity = instance.capacity\n",
    "    for item in instance.items:\n",
    "        if item.weight <= remaining_capacity:\n",
    "            solution.append(item)\n",
    "            remaining_capacity -= item.weight\n",
    "    return solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exact Solver for Subproblem\n",
    "\n",
    "We will remove items from the knapsack and try to refill it with better items.\n",
    "This subproblem is the Knapsack problem again, and we can solve it with CP-SAT."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exact solver for knapsack\n",
    "\n",
    "\n",
    "def solve_knapsack(\n",
    "    instance: Instance, max_time_in_seconds: float = 90\n",
    ") -> typing.List[Item]:\n",
    "    \"\"\"\n",
    "    Optimal solver for knapsack\n",
    "    \"\"\"\n",
    "    model = cp_model.CpModel()\n",
    "    x = [model.new_bool_var(f\"x_{i}\") for i in range(len(instance.items))]\n",
    "    model.add(\n",
    "        sum(x[i] * item.weight for i, item in enumerate(instance.items))\n",
    "        <= instance.capacity\n",
    "    )\n",
    "    model.maximize(sum(x[i] * item.value for i, item in enumerate(instance.items)))\n",
    "    solver = cp_model.CpSolver()\n",
    "    solver.parameters.max_time_in_seconds = max_time_in_seconds\n",
    "    # solver.parameters.log_search_progress = True\n",
    "    status = solver.solve(model)\n",
    "    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:\n",
    "        if status == cp_model.FEASIBLE:\n",
    "            print(\n",
    "                \"Warning: Solver did not find optimal solution. Returned solution is feasible but not optimal.\"\n",
    "            )\n",
    "        return [\n",
    "            item for i, item in enumerate(instance.items) if solver.value(x[i]) == 1\n",
    "        ]\n",
    "    else:\n",
    "        return []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Large Neighborhood Search for the Knapsack Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Initialization\n",
    "\n",
    "We need to start with an initial solution that is then improved by the LNS algorithm.\n",
    "We use a simple greedy algorithm to generate an initial solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create instance\n",
    "instance = random_instance(1_000_000, 0.1)\n",
    "# compute some initial solution\n",
    "initial_solution = greedy_solution(instance)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Improve the solution via LNS\n",
    "\n",
    "The LNS algorithm is a heuristic that iteratively destroys and repairs parts of the solution.\n",
    "We remove a part of the selected item in the current solution and then select some additional\n",
    "items from the remaining set. Using the exact solver, we find the optimal solution for the\n",
    "remaining capacity using the selected items. This is repeated for some iterations.\n",
    "\n",
    "There are two important parameters for the LNS algorithm:\n",
    "* The size of the subproblem we solve with the exact solver.\n",
    "* The size of items we remove from the current solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "class KnapsackLns:\n",
    "    \"\"\"\n",
    "    Knapsack LNS solver.\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(\n",
    "        self,\n",
    "        instance: Instance,\n",
    "        initial_solution: typing.List[Item],\n",
    "        subproblem_size: int,\n",
    "    ):\n",
    "        self.instance = instance\n",
    "        self.solution = initial_solution\n",
    "        self.subproblem_size = (\n",
    "            subproblem_size  # Number of items to consider in subproblem\n",
    "        )\n",
    "        self.solutions = [initial_solution]\n",
    "\n",
    "    def _remaining_capacity(self):\n",
    "        return self.instance.capacity - sum(item.weight for item in self.solution)\n",
    "\n",
    "    def _remaining_items(self):\n",
    "        return list(set(self.instance.items).difference(self.solution))\n",
    "\n",
    "    def _destroy(self, num_items: int) -> typing.List[Item]:\n",
    "        \"\"\"\n",
    "        Destroy a part of the solution by removing num_items from it.\n",
    "        \"\"\"\n",
    "        num_items = min(len(self.solution), num_items)\n",
    "        assert 0 <= num_items <= self.subproblem_size\n",
    "        items_removed = random.sample(self.solution, num_items)\n",
    "        self.solution = [item for item in self.solution if item not in items_removed]\n",
    "        print(\n",
    "            f\"Removed {len(items_removed)} items from solution. New remaining capacity: {self._remaining_capacity()}\"\n",
    "        )\n",
    "        return items_removed\n",
    "\n",
    "    def _repair(self, I_: typing.List[Item], max_time_in_seconds: float = 90):\n",
    "        \"\"\"\n",
    "        Repair the solution by adding items from I_ to it.\n",
    "        \"\"\"\n",
    "        C_ = self._remaining_capacity()\n",
    "        print(\n",
    "            f\"Repairing solution by considering {len(I_)} items to fill the remaining capacity of {C_}.\"\n",
    "        )\n",
    "        subsolution = solve_knapsack(Instance(I_, C_), max_time_in_seconds)\n",
    "        self.solution += subsolution\n",
    "        assert self._remaining_capacity() >= 0\n",
    "\n",
    "    def perform_lns_iteration(\n",
    "        self, destruction_size: int, max_time_in_seconds: float = 90\n",
    "    ):\n",
    "        # 1. Destroy\n",
    "        assert destruction_size > 0\n",
    "        items_removed = self._destroy(destruction_size)\n",
    "        # 2. Build subproblem for repair\n",
    "        remaining_items = self._remaining_items()\n",
    "        n = min(self.subproblem_size - destruction_size, len(remaining_items))\n",
    "        new_items_to_consider = random.sample(remaining_items, n)\n",
    "        # Add the removed items to the set of items to consider, such that\n",
    "        # we can also find an equally good solution\n",
    "        I_ = list(set(items_removed + new_items_to_consider).difference(self.solution))\n",
    "        # 3. Repair\n",
    "        self._repair(I_, max_time_in_seconds)\n",
    "        self.solutions.append(self.solution)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Run the LNS\n",
    "\n",
    "Play around with the parameters and see how the LNS algorithm improves the solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Removed 1000 items from solution. New remaining capacity: 499228\n",
      "Repairing solution by considering 9993 items to fill the remaining capacity of 499228.\n",
      "iteration 0: 1805895706 (improvement: 1.01254478180439)\n",
      "Removed 1000 items from solution. New remaining capacity: 498662\n",
      "Repairing solution by considering 9981 items to fill the remaining capacity of 498662.\n",
      "iteration 1: 1827800672 (improvement: 1.0248266422380858)\n",
      "Removed 1000 items from solution. New remaining capacity: 496984\n",
      "Repairing solution by considering 9985 items to fill the remaining capacity of 496984.\n",
      "iteration 2: 1849866865 (improvement: 1.0371989007811484)\n",
      "Removed 1000 items from solution. New remaining capacity: 510463\n",
      "Repairing solution by considering 9993 items to fill the remaining capacity of 510463.\n",
      "iteration 3: 1871933620 (improvement: 1.0495714744310944)\n",
      "Removed 1000 items from solution. New remaining capacity: 499582\n",
      "Repairing solution by considering 9987 items to fill the remaining capacity of 499582.\n",
      "iteration 4: 1892435213 (improvement: 1.0610664798967242)\n",
      "Removed 1000 items from solution. New remaining capacity: 516317\n",
      "Repairing solution by considering 9989 items to fill the remaining capacity of 516317.\n",
      "iteration 5: 1914221637 (improvement: 1.0732818752055926)\n",
      "Removed 1000 items from solution. New remaining capacity: 506736\n",
      "Repairing solution by considering 9979 items to fill the remaining capacity of 506736.\n",
      "iteration 6: 1935650197 (improvement: 1.0852966203193295)\n",
      "Removed 1000 items from solution. New remaining capacity: 517704\n",
      "Repairing solution by considering 9994 items to fill the remaining capacity of 517704.\n",
      "iteration 7: 1956950130 (improvement: 1.0972392457656814)\n",
      "Removed 1000 items from solution. New remaining capacity: 503241\n",
      "Repairing solution by considering 9987 items to fill the remaining capacity of 503241.\n",
      "iteration 8: 1976915378 (improvement: 1.1084335288090847)\n",
      "Removed 1000 items from solution. New remaining capacity: 515758\n",
      "Repairing solution by considering 9990 items to fill the remaining capacity of 515758.\n",
      "iteration 9: 1997854149 (improvement: 1.1201736549099477)\n",
      "Removed 1000 items from solution. New remaining capacity: 514311\n",
      "Repairing solution by considering 9994 items to fill the remaining capacity of 514311.\n",
      "iteration 10: 2018110146 (improvement: 1.131530957546225)\n",
      "Removed 1000 items from solution. New remaining capacity: 500349\n",
      "Repairing solution by considering 9993 items to fill the remaining capacity of 500349.\n",
      "iteration 11: 2037891661 (improvement: 1.1426222236270331)\n",
      "Removed 1000 items from solution. New remaining capacity: 494564\n",
      "Repairing solution by considering 9990 items to fill the remaining capacity of 494564.\n",
      "iteration 12: 2057018856 (improvement: 1.1533466200711129)\n",
      "Removed 1000 items from solution. New remaining capacity: 504963\n",
      "Repairing solution by considering 9989 items to fill the remaining capacity of 504963.\n",
      "iteration 13: 2076097912 (improvement: 1.1640440255360958)\n",
      "Removed 1000 items from solution. New remaining capacity: 500825\n",
      "Repairing solution by considering 9991 items to fill the remaining capacity of 500825.\n",
      "iteration 14: 2095861342 (improvement: 1.1751251515671117)\n",
      "Removed 1000 items from solution. New remaining capacity: 505911\n",
      "Repairing solution by considering 9988 items to fill the remaining capacity of 505911.\n",
      "iteration 15: 2115532835 (improvement: 1.1861547295882975)\n",
      "Removed 1000 items from solution. New remaining capacity: 502252\n",
      "Repairing solution by considering 9991 items to fill the remaining capacity of 502252.\n",
      "iteration 16: 2134867720 (improvement: 1.196995575407075)\n",
      "Removed 1000 items from solution. New remaining capacity: 522139\n",
      "Repairing solution by considering 9990 items to fill the remaining capacity of 522139.\n",
      "iteration 17: 2153680177 (improvement: 1.207543501904149)\n",
      "Removed 1000 items from solution. New remaining capacity: 495287\n",
      "Repairing solution by considering 9987 items to fill the remaining capacity of 495287.\n",
      "iteration 18: 2171928684 (improvement: 1.2177752281755945)\n",
      "Removed 1000 items from solution. New remaining capacity: 506532\n",
      "Repairing solution by considering 9995 items to fill the remaining capacity of 506532.\n",
      "iteration 19: 2190020223 (improvement: 1.2279189443095873)\n",
      "Removed 1000 items from solution. New remaining capacity: 511453\n",
      "Repairing solution by considering 9989 items to fill the remaining capacity of 511453.\n",
      "iteration 20: 2208507996 (improvement: 1.238284824252786)\n",
      "Removed 1000 items from solution. New remaining capacity: 490899\n",
      "Repairing solution by considering 9988 items to fill the remaining capacity of 490899.\n",
      "iteration 21: 2226446548 (improvement: 1.2483427623498637)\n",
      "Removed 1000 items from solution. New remaining capacity: 513998\n",
      "Repairing solution by considering 9986 items to fill the remaining capacity of 513998.\n",
      "iteration 22: 2244279352 (improvement: 1.2583414087695592)\n",
      "Removed 1000 items from solution. New remaining capacity: 480333\n",
      "Repairing solution by considering 9991 items to fill the remaining capacity of 480333.\n",
      "iteration 23: 2261838786 (improvement: 1.26818677980016)\n",
      "Removed 1000 items from solution. New remaining capacity: 497322\n",
      "Repairing solution by considering 9990 items to fill the remaining capacity of 497322.\n",
      "iteration 24: 2279212967 (improvement: 1.2779282816217912)\n"
     ]
    }
   ],
   "source": [
    "lns = KnapsackLns(instance, initial_solution, subproblem_size=10_000)\n",
    "for i in range(25):\n",
    "    lns.perform_lns_iteration(destruction_size=1_000)\n",
    "    print(\n",
    "        f\"=> Iteration {i}: {value(lns.solution)} (improvement: {value(lns.solution) / value(lns.solutions[0])})\"\n",
    "    )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Try to compute an optimal solution\n",
    "\n",
    "To have a comparison, we can try to compute an optimal solution with the exact solver."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimal solution: 1800396315\n"
     ]
    }
   ],
   "source": [
    "optimal_solution = solve_knapsack(instance, max_time_in_seconds=900)\n",
    "print(f\"CP-SAT solution: {value(optimal_solution)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "We are able to improve the initial solution via LNS, however, only because we used a bad greedy algorithm.\n",
    "If we had used a better greedy algorithm, the LNS algorithm would not be able to improve the solution by much.\n",
    "However, the LNS algorithm is a very powerful heuristic that can be used to improve solutions for many problems.\n",
    "This example just had the purpose to demonstrate the implementation of LNS."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise\n",
    "\n",
    "Try to generalize the LNS algorithm for Multi-Knapsack problems, where instead of a single knapsack, we have multiple knapsacks with different capacities, and items can have different values and weights for each knapsack.\n",
    "Multi-Knapsack problems can be significantly harder but also of practical interest for many applications, such as scheduling and resource allocation."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "mo310",
   "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.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}