{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "88b2044f",
   "metadata": {},
   "source": [
    "# MOSP\n",
    "\n",
    "In a minimization of open stacks problem (MOSP), we are given a set of customers $C = \\{ 0, ..., n-1 \\}$ and a set of products $P = \\{ 0, ..., m-1 \\}$.\n",
    "Each customer $c \\in C$ requests a subset of products $P_c \\subseteq P$.\n",
    "We want to decide the order to produce the products.\n",
    "Once we produced a product $p \\in P_c$, we need to open a stack for customer $c$ to store the product.\n",
    "When we produced all products in $P_c$, we can close the stack for $c$.\n",
    "We want to minimize the maximum number of open stacks at a time.\n",
    "\n",
    "## DP Formulation\n",
    "\n",
    "The approach is to find the order of customers to close stacks instead of the order of products to produce.\n",
    "Once the order of customers is determined, for each customer, products requested by the customer that are not produced yet are consecutively produced in an arbitrary order.\n",
    "\n",
    "When we close the stack for customer $c$, we need to produce all products in $P_c$.\n",
    "If another customer $c'$ requestss a product in $P_c$ and its stack is not opened yet, we need to open the stack for $c'$.\n",
    "In a sense, we can say that $c'$ is a neighbor of $c$.\n",
    "Let $N_c \\subseteq C$ be the set of neighbors including $c$, i.e., $N_c = \\{ c' \\in C \\mid P_{c'} \\cap P_c \\neq \\emptyset \\}$.\n",
    "\n",
    "Let $O$ be the set of customers whose stacks have been opened.\n",
    "When we are producing the products requested by $c$, we need to open new stacks for customers $N_c \\setminus O$.\n",
    "Let $R$ be the set of customers whose stacks are not closed yet.\n",
    "Because the set of customers whose stacks have been opened and not closed is $O \\cap R$, the number of open stacks when producing the products for $c$ is $|(O \\cap R) \\cup (N_c \\setminus O)|$.\n",
    "\n",
    "When we close the stack for $c$, the set of customers whose stacks are not closed becomes $R \\setminus \\{ c \\}$, and the set of customers whose stacks have been opened becomes $O \\cup N_c$.\n",
    "Let $V(R, O)$ be the minimum of the maximum number of open stacks at a time to close the stacks for customers in $R$ when the stacks for customers in $O$ have been opened.\n",
    "Then, the DP formulation is\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "    \\text{compute } & V(C, \\emptyset) \\\\\n",
    "    & V(R, O) = \\begin{cases}\n",
    "        \\min\\limits_{c \\in R} \\max\\left\\{ |(O \\cap R) \\cup (N_c \\setminus O)|,  V(R \\setminus \\{ c \\}, O \\cup N_c) \\right\\} & \\text{if } R \\neq \\emptyset \\\\\n",
    "        0 & \\text{if } R = \\emptyset\n",
    "    \\end{cases} \\\\\n",
    "    & V(R, O) \\geq 0.\n",
    "\\end{align}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05c124c7",
   "metadata": {},
   "source": [
    "## Install DIDPPy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "b18442f1",
   "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": "e67be632",
   "metadata": {},
   "source": [
    "## Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "b8ee875f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Number of customers\n",
    "n = 4\n",
    "# Number of items\n",
    "m = 4\n",
    "# Items requested by customers\n",
    "customer_to_items = [{0}, {0, 1}, {2}, {1}]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2113deb2",
   "metadata": {},
   "source": [
    "## Preprocessiong"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "fc1ea424",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Neighbors\n",
    "neighbors = [[] for _ in range(n)]\n",
    "\n",
    "for i in range(n):\n",
    "    for j in range(n):\n",
    "        if len(customer_to_items[i] & customer_to_items[j]) > 0:\n",
    "            neighbors[i].append(j)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "613c3b37",
   "metadata": {},
   "source": [
    "## Modeling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "7238f24f",
   "metadata": {},
   "outputs": [],
   "source": [
    "import didppy as dp\n",
    "\n",
    "model = dp.Model()\n",
    "\n",
    "customer = model.add_object_type(number=n)\n",
    "\n",
    "# R\n",
    "remaining = model.add_set_var(object_type=customer, target=list(range(n)))\n",
    "# O\n",
    "opened = model.add_set_var(object_type=customer, target=[])\n",
    "\n",
    "neighbor_table = model.add_set_table(neighbors, object_type=customer)\n",
    "\n",
    "for c in range(n):\n",
    "    close = dp.Transition(\n",
    "        name=\"close {}\".format(c),\n",
    "        cost=dp.max(\n",
    "            ((opened & remaining) | (neighbor_table[c] - opened)).len(),\n",
    "            dp.IntExpr.state_cost(),\n",
    "        ),\n",
    "        effects=[\n",
    "            (remaining, remaining.remove(c)),\n",
    "            (opened, opened | neighbor_table[c]),\n",
    "        ],\n",
    "        preconditions=[remaining.contains(c)],\n",
    "    )\n",
    "    model.add_transition(close)\n",
    "\n",
    "model.add_base_case([remaining.is_empty()])\n",
    "\n",
    "model.add_dual_bound(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "764e1157",
   "metadata": {},
   "source": [
    "## Solving"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "208b2f06",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Transitions to apply:\n",
      "\n",
      "close 2\n",
      "close 0\n",
      "close 1\n",
      "close 3\n",
      "\n",
      "Cost: 2\n"
     ]
    }
   ],
   "source": [
    "solver = dp.CABS(model, f_operator=dp.FOperator.Max, 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
}