0502_cumulative_moving_furniture.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyOY9IOMNrfZvYdYH5Szu9fc",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/lmcanavals/cs_topics/blob/main/0502_cumulative_moving_furniture.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Item ($T_i$) | Movers ($R_i$) | Time in mins ($D_i$)\n",
        "-|-|-\n",
        "Piano | 3 | 30\n",
        "Bed | 3 | 15\n",
        "Char | 1 | 10\n",
        "Table | 2 | 15\n",
        "\n",
        "Time limit = 60\n",
        "Resource limit = 4"
      ],
      "metadata": {
        "id": "Fwz5i28f1-hm"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "id": "ddoXGsoI0z19"
      },
      "outputs": [],
      "source": [
        "!python -m pip install ortools &> /dev/null"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "from ortools.sat.python import cp_model"
      ],
      "metadata": {
        "id": "wcj7kktn07JO"
      },
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "model = cp_model.CpModel()\n",
        "\n",
        "D = [30, 15, 10, 15]\n",
        "R = [3, 3, 1, 2]\n",
        "time_limit = 60\n",
        "resource_limit = 4\n",
        "n = len(D)\n",
        "\n",
        "S = [model.NewIntVar(0, time_limit, f\"S_{i}\") for i in range(n)] # start time\n",
        "E = [model.NewIntVar(0, time_limit, f\"E_{i}\") for i in range(n)] # end time\n",
        "intervals = [model.NewIntervalVar(S[i], D[i], E[i], f\"interval_{i}\") for i in range(n)]\n",
        "\n",
        "model.AddCumulative(intervals, R, resource_limit)\n",
        "\n",
        "obj_var = model.NewIntVar(0, time_limit, 'obj_var')\n",
        "model.AddMaxEquality(obj_var, E)\n",
        "model.Minimize(obj_var)\n",
        "\n",
        "solver = cp_model.CpSolver()\n",
        "if solver.Solve(model) == cp_model.OPTIMAL:\n",
        "    print(f\":) {solver.ObjectiveValue()}\")\n",
        "    print(\"Task\\tStart\\tEnd\")\n",
        "    for i in range(n):\n",
        "        print(f\"{i}\\t{solver.Value(S[i])}\\t{solver.Value(E[i])}\")\n",
        "else:\n",
        "    print(f\":(\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "_QxAaaSY1Tiv",
        "outputId": "b4b8267b-34cb-418d-b1f0-8a577fbf4f73"
      },
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            ":) 60.0\n",
            "Task\tStart\tEnd\n",
            "0\t30\t60\n",
            "1\t0\t15\n",
            "2\t0\t10\n",
            "3\t15\t30\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "mySeN4lA43S6"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}