Binpacking.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "324c2620",
   "metadata": {},
   "source": [
    "# LP\n",
    "\n",
    "### Parameters\n",
    "\n",
    "- $L$: size of bin $j \\in J$\n",
    "- $s_i$: size of item $i \\in I$\n",
    "\n",
    "### Variables\n",
    "\n",
    "- $x_{ij}\\in \\{0,1\\}$ takes value $1$ $\\Leftrightarrow$ item $i \\in I$ is placed in bin $j \\in J$\n",
    "- $y_j \\in \\{0,1\\}$ takes value $1$ $\\Leftrightarrow$ bin $j \\in J$ is used\n",
    "\n",
    "### Objective function\n",
    "\n",
    "Minimize total used bins:\n",
    "$$\n",
    "\\min \\; \\sum_{j \\in J} y_j\n",
    "$$\n",
    "\n",
    "### Constraints\n",
    "- Each item should be placed in exactly one bin:\n",
    "$$\n",
    "\\sum_{j \\in J} x_{ij} = 1 \\quad \\forall i\\in I \\tag{1}\n",
    "$$\n",
    "- Size contraints:\n",
    "$$\n",
    "\\sum_{i \\in I} s_i x_{ij} \\le L y_j \\quad \\forall j\\in J \\tag{2}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7ee8e257",
   "metadata": {},
   "source": [
    "# Dantzig-Wolfe decomposition (for column generation)\n",
    "\n",
    "We will decompose the problem so that constraints $(1)$ form the master problem and constraints $(2)$ the subproblem. \n",
    "\n",
    "## Master problem\n",
    "\n",
    "- $\\Omega$: set of all feasible bins (we will build $\\Omega$ dynamically)\n",
    "\n",
    "### Variables\n",
    "\n",
    "- $\\lambda_j \\in \\{0,1\\}$: takes value $1$ $\\Leftrightarrow$ bin $j \\in \\Omega$ is selected\n",
    "\n",
    "### Objective function \n",
    "\n",
    "$$\n",
    "\\min \\sum_{j\\in \\Omega} \\lambda_j\n",
    "$$\n",
    "\n",
    "### Constraints\n",
    "\n",
    "- Each item must be in exactly one bin:\n",
    "$$\n",
    "\\sum_{j \\in \\Omega | i\\in j} \\lambda_j = 1 \\quad \\forall i \\in I \\tag{3}\n",
    "$$\n",
    "\n",
    "## Subproblem\n",
    "\n",
    "### Parameters\n",
    "\n",
    "- $\\pi_i:$ dual variable of constraints $(3)$\n",
    "\n",
    "### Variables\n",
    "\n",
    "- $x_i \\in \\{0,1\\}$: takes value $1$ $\\Leftrightarrow$ item $i \\in I$ is selected for the creation of bin (column)\n",
    "\n",
    "### Objective function\n",
    "The reduced cost of variable $\\lambda_j$ equals \n",
    "$\n",
    "1 - \\sum_{i\\in I} \\pi_i\n",
    "$, the objective function is\n",
    "$$\n",
    "\\min \\; 1- \\sum_{i \\in I}\\pi_i x_i\n",
    "$$\n",
    "\n",
    "### Constraints\n",
    "- Bin must respect size constraints:\n",
    "$$\n",
    "\\sum_{i \\in I}s_i x_i \\le L\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bfdff9b3",
   "metadata": {},
   "source": [
    "# Column generation\n",
    "\n",
    "1. Initialize $\\Omega$\n",
    "2. Solve the linear relaxation of Master Problem\n",
    "3. Solve subproblem, based on dual variable of 2. If column (bin) is found, add it to $\\Omega$ and go to step 2. \n",
    "4. Solve Master Problem with integer variables.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eb931486",
   "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.11.2"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}