{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "dccd53ce",
   "metadata": {},
   "source": [
    "# Bin Packing\n",
    "\n",
    "In a bin packing problem, we are given the set of items $N = \\{ 0, ..., n - 1 \\}$ and bins with capacity $c$.\n",
    "Each item $i \\in N$ has the weight $w_i$.\n",
    "We want to pack the items into bins while minimizing the number of bins.\n",
    "\n",
    "## DP Formulation\n",
    "\n",
    "Consider using bins one by one and packing items one by one.\n",
    "Let $U$ be the set of unpacked items, and $r$ be the remaining capacity of the current bin.\n",
    "Item $i$ can be packed into the current bin only if $w_i \\leq r$.\n",
    "After packing $i$, $U$ becomes $U \\setminus \\{ i \\}$ and $r$ becomes $r - w_i$.\n",
    "\n",
    "When no items fit into the current bin, we need to open a new bin.\n",
    "We can select an arbitrary item as the first item in the new bin without loosing the optimality.\n",
    "\n",
    "It is known that there is a solution that packs item $i$ in the $i$ th bin or earlier.\n",
    "Let $k$ be the number of used bins (including the current bin).\n",
    "Then, we only need to consider items $i$ in $U$ with $i + 1 \\geq k$.\n",
    "We have the following DP model:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "    \\text{compute } & V(N, 0, 0) \\\\\n",
    "    & V(U, r, k) = \\begin{cases}\n",
    "        \\min\\limits_{i \\in U : w_i \\leq r \\land i + 1 \\geq k} V(U \\setminus \\{ i \\}, r - w_i, k) & \\text{if } \\exists i \\in U, w_i \\leq r \\land i + 1 \\geq k \\\\\n",
    "        1 + V(U \\setminus \\{ i \\}, r, k + 1) & \\text{else if } \\exists i \\in U, i \\geq k \\\\\n",
    "        0 & \\text{else if } U = \\emptyset \\\\\n",
    "        \\infty & \\text{otherwise.}\n",
    "    \\end{cases}.\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "If two states $(U, r, k)$ and $(U, r', k')$ have the same set of unpacked items, if $r \\geq r'$ and $k \\leq k'$, $(U, r, k)$ leads to a better solution. Therefore,\n",
    "\n",
    "$$\n",
    "    V(U, r, k) \\leq V(U, r', k') \\text{ if } r \\geq r' \\land k \\leq k'.\n",
    "$$\n",
    "\n",
    "If we ignore the fact that an item cannot be divided for multiple bin, we get the following lower bound:\n",
    "\n",
    "$$\n",
    "    V(U, r, k) \\geq \\left\\lceil \\frac{\\sum_{i \\in U} w_i - r}{c} \\right\\rceil.\n",
    "$$\n",
    "\n",
    "Consider only items $i$ with $w_i \\geq \\frac{c}{2}$.\n",
    "Each bin contains at most one of bins $i$ with $w_i > \\frac{c}{2}$.\n",
    "Similarly, each bin contains at most two bins with $w_i = \\frac{c}{2}$, and such items are not packed in the same bin having items with $t_i > \\frac{c}{2}$.\n",
    "If $r \\geq \\frac{c}{2}$, we can possibly use the current bin to pack the items.\n",
    "Therefore,\n",
    "\n",
    "$$\n",
    "    V(U, r, k) \\geq \\begin{cases}\n",
    "        \\sum\\limits_{ i \\in U : w_i > \\frac{c}{2} } 1 + \\left\\lceil \\sum\\limits_{i \\in U : w_i = \\frac{c}{2}} \\frac{1}{2} \\right\\rceil & \\text{if } r < \\frac{c}{2} \\\\\n",
    "        \\sum\\limits_{ i \\in U : w_i > \\frac{c}{2} } 1 + \\left\\lceil \\sum\\limits_{i \\in U : w_i = \\frac{c}{2}} \\frac{1}{2} \\right\\rceil - 1 & \\text{if } r \\geq \\frac{c}{2}.\n",
    "    \\end{cases}\n",
    "$$\n",
    "\n",
    "Similaly, if we consider only items $i$ with $w_i \\geq \\frac{c}{3}$, we get the following bound:\n",
    "\n",
    "$$\n",
    "    V(U, r, k) \\geq \\begin{cases}\n",
    "        \\left\\lceil \\sum\\limits_{ i \\in U : w_i > \\frac{2c}{3} } 1 + \\sum\\limits_{i \\in U : w_i = \\frac{2c}{3}} \\frac{2}{3} + \\sum\\limits_{i \\in U : w_i \\in (\\frac{c}{3}. \\frac{2c}{3})} \\frac{1}{2} + \\sum\\limits_{i \\in U : w_i = \\frac{c}{3}} \\frac{1}{3} \\right\\rceil & \\text{if } r < \\frac{c}{3} \\\\\n",
    "        \\left\\lceil \\sum\\limits_{ i \\in U : w_i > \\frac{2c}{3} } 1 + \\sum\\limits_{i \\in U : w_i = \\frac{2c}{3}} \\frac{2}{3} + \\sum\\limits_{i \\in U : w_i \\in (\\frac{c}{3}. \\frac{2c}{3})} \\frac{1}{2} + \\sum\\limits_{i \\in U : w_i = \\frac{c}{3}} \\frac{1}{3} \\right\\rceil - 1 & \\text{if } r \\geq \\frac{c}{3} \\\\\n",
    "    \\end{cases}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac433ddd",
   "metadata": {},
   "source": [
    "## Install DIDPPy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c6756083",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Requirement already satisfied: didppy in /home/kuro/tidel/code/didp-rs/didppy/.venv/lib/python3.10/site-packages (0.7.1)\r\n"
     ]
    }
   ],
   "source": [
    "!pip install didppy"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e4c46c70",
   "metadata": {},
   "source": [
    "## Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "982d924e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Number of items\n",
    "n = 5\n",
    "# Capacity\n",
    "c = 5\n",
    "# Weights\n",
    "w = [2, 2, 1, 3, 2]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "589a4514",
   "metadata": {},
   "source": [
    "## Preprocessing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "fc285c1c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# The weight in the first term of the second bound.\n",
    "weight_2_1 = [1 if w[i] > c / 2 else 0 for i in range(n)]\n",
    "# The weight in the second term of the second bound.\n",
    "weight_2_2 = [1 / 2 if w[i] == c / 2 else 0 for i in range(n)]\n",
    "# The weight in the third bound (truncated to three decimal points).\n",
    "weight_3 = [\n",
    "    1.0\n",
    "    if w[i] > c * 2 / 3\n",
    "    else 2 / 3 // 0.001 * 1000\n",
    "    if w[i] == c * 2 / 3\n",
    "    else 0.5\n",
    "    if w[i] > c / 3\n",
    "    else 1 / 3 // 0.001 * 1000\n",
    "    if w[i] == c / 3\n",
    "    else 0.0\n",
    "    for i in range(n)\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d83331e2",
   "metadata": {},
   "source": [
    "## Modeling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "f8e78115",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "import didppy as dp\n",
    "\n",
    "model = dp.Model()\n",
    "\n",
    "item = model.add_object_type(number=n)\n",
    "\n",
    "# U\n",
    "unpacked = model.add_set_var(object_type=item, target=list(range(n)))\n",
    "# r\n",
    "remaining = model.add_int_resource_var(target=0, less_is_better=False)\n",
    "# k (we want to compare the number of bins with the index of an item) \n",
    "number_of_bins = model.add_element_resource_var(\n",
    "    object_type=item,\n",
    "    target=0,\n",
    "    less_is_better=True,\n",
    ")\n",
    "\n",
    "weight = model.add_int_table(w)\n",
    "\n",
    "for i in range(n):\n",
    "    pack = dp.Transition(\n",
    "        name=\"pack {}\".format(i),\n",
    "        cost=dp.IntExpr.state_cost(),\n",
    "        effects=[\n",
    "            (unpacked, unpacked.remove(i)),\n",
    "            (remaining, remaining - weight[i]),\n",
    "        ],\n",
    "        preconditions=[\n",
    "            unpacked.contains(i),\n",
    "            weight[i] <= remaining,\n",
    "            i + 1 >= number_of_bins,\n",
    "        ],\n",
    "    )\n",
    "    model.add_transition(pack)\n",
    "    \n",
    "for i in range(n):\n",
    "    open_new = dp.Transition(\n",
    "        name=\"open a new bin and pack {}\".format(i),\n",
    "        cost=1 + dp.IntExpr.state_cost(),\n",
    "        effects=[\n",
    "            (unpacked, unpacked.remove(i)),\n",
    "            (remaining, c - weight[i]),\n",
    "            (number_of_bins, number_of_bins + 1)\n",
    "        ],\n",
    "        preconditions=[\n",
    "            unpacked.contains(i),\n",
    "            i >= number_of_bins,\n",
    "            weight[i] > remaining,\n",
    "        ]\n",
    "        + [\n",
    "            ~unpacked.contains(j) | (weight[j] > remaining)\n",
    "            for j in range(n)\n",
    "            if i != j\n",
    "        ],\n",
    "    )\n",
    "    model.add_transition(open_new, forced=True)\n",
    "\n",
    "model.add_base_case([unpacked.is_empty()])\n",
    "\n",
    "model.add_dual_bound(\n",
    "    math.ceil((weight[unpacked] - remaining) / c)\n",
    ")\n",
    "\n",
    "weight_2_1_table = model.add_int_table(weight_2_1)\n",
    "weight_2_2_table = model.add_float_table(weight_2_2)\n",
    "model.add_dual_bound(\n",
    "    weight_2_1_table[unpacked]\n",
    "    + math.ceil(weight_2_2_table[unpacked])\n",
    "    - (remaining >= c / 2).if_then_else(1, 0)\n",
    ")\n",
    "\n",
    "weight_3_table = model.add_float_table(weight_3)\n",
    "model.add_dual_bound(\n",
    "    math.ceil(weight_3_table[unpacked])\n",
    "    - (remaining >= c / 3).if_then_else(1, 0)\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad2f4f7d",
   "metadata": {},
   "source": [
    "## Solving"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "8e243b2b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Transitions to apply:\n",
      "\n",
      "open a new bin and pack 0\n",
      "pack 1\n",
      "pack 2\n",
      "open a new bin and pack 3\n",
      "pack 4\n",
      "\n",
      "Cost: 2\n"
     ]
    }
   ],
   "source": [
    "solver = dp.CABS(model, quiet=True)\n",
    "solution = solver.search()\n",
    "\n",
    "print(\"Transitions to apply:\")\n",
    "print(\"\")\n",
    "\n",
    "for t in solution.transitions:\n",
    "    print(t.name)\n",
    "\n",
    "print(\"\")\n",
    "print(\"Cost: {}\".format(solution.cost))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".venv",
   "language": "python",
   "name": ".venv"
  },
  "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.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}