modeling/CourseSchedule.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Course Assignment Problem (a small exploration)\n",
    "\n",
    "We have 500 course exams and 3000 students, each course is ensured to have at least one student enrolled, besides, we have 70 time slot. We want to assign each course exam to a time slot, each time slot is given a cost in advance, each student that have courses exammed at the slot will have corresponding cost (This cost indicates students' welfare, because students will feel angry for assignments such as \"Not willing to have exams at 8:00 A.M., or Not willing to have exams during weekends, or Not willing to have exams at the end of exams weeks\").\n",
    "\n",
    "We hope to assign each course exam to a time slot such that the total cost is minimized. \n",
    "\n",
    "CONSTRS:\n",
    "\n",
    "1. Students cannot have two exams simultaneously at one slot;\n",
    "2. Each course exam must be assigned to a time slot;\n",
    "\n",
    "CAUTION:\n",
    "\n",
    "1. Different students have different number of courses, range from 3 to 10."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Gurobi Optimizer version 11.0.2 build v11.0.2rc0 (mac64[arm] - Darwin 23.5.0 23F79)\n",
      "\n",
      "CPU model: Apple M3 Pro\n",
      "Thread count: 11 physical cores, 11 logical processors, using up to 11 threads\n",
      "\n",
      "Optimize a model with 210500 rows, 35000 columns and 962850 nonzeros\n",
      "Model fingerprint: 0xd9098d38\n",
      "Variable types: 0 continuous, 35000 integer (35000 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 1e+00]\n",
      "  Objective range  [1e+01, 4e+02]\n",
      "  Bounds range     [1e+00, 1e+00]\n",
      "  RHS range        [1e+00, 1e+00]\n",
      "Found heuristic solution: objective 36862.000000\n",
      "Presolve removed 7000 rows and 0 columns\n",
      "Presolve time: 1.70s\n",
      "Presolved: 203500 rows, 35000 columns, 994490 nonzeros\n",
      "Variable types: 0 continuous, 35000 integer (35000 binary)\n",
      "Found heuristic solution: objective 20565.000000\n",
      "\n",
      "Deterministic concurrent LP optimizer: primal simplex, dual simplex, and barrier\n",
      "Showing barrier log only...\n",
      "\n",
      "\n",
      "Use crossover to convert LP symmetric solution to basic solution...\n",
      "Concurrent spin time: 0.16s\n",
      "\n",
      "Solved with barrier\n",
      "\n",
      "Root relaxation: objective 1.325500e+04, 14503 iterations, 2.27 seconds (2.83 work units)\n",
      "\n",
      "    Nodes    |    Current Node    |     Objective Bounds      |     Work\n",
      " Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time\n",
      "\n",
      "H    0     0                    13255.000000    0.00000   100%     -    4s\n",
      "     0     0          -    0      13255.0000 13255.0000  0.00%     -    5s\n",
      "\n",
      "Explored 1 nodes (17000 simplex iterations) in 5.76 seconds (9.96 work units)\n",
      "Thread count was 11 (of 11 available processors)\n",
      "\n",
      "Solution count 3: 13255 20565 36862 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 1.325500000000e+04, best bound 1.325500000000e+04, gap 0.0000%\n",
      "Objective Value: 13255.0\n",
      "Course 0, with 26 students, is allocated to interval 10\n",
      "Course 1, with 40 students, is allocated to interval 59\n",
      "Course 2, with 23 students, is allocated to interval 7\n",
      "Course 3, with 33 students, is allocated to interval 57\n",
      "Course 4, with 23 students, is allocated to interval 18\n",
      "Course 5, with 29 students, is allocated to interval 22\n",
      "Course 6, with 22 students, is allocated to interval 14\n",
      "Course 7, with 22 students, is allocated to interval 45\n",
      "Course 8, with 21 students, is allocated to interval 15\n",
      "Course 9, with 30 students, is allocated to interval 50\n",
      "Course 10, with 26 students, is allocated to interval 56\n",
      "Course 11, with 33 students, is allocated to interval 14\n",
      "Course 12, with 24 students, is allocated to interval 18\n",
      "Course 13, with 28 students, is allocated to interval 16\n",
      "Course 14, with 28 students, is allocated to interval 22\n",
      "Course 15, with 26 students, is allocated to interval 58\n",
      "Course 16, with 18 students, is allocated to interval 56\n",
      "Course 17, with 26 students, is allocated to interval 24\n",
      "Course 18, with 35 students, is allocated to interval 51\n",
      "Course 19, with 30 students, is allocated to interval 8\n",
      "Course 20, with 28 students, is allocated to interval 45\n",
      "Course 21, with 24 students, is allocated to interval 7\n",
      "Course 22, with 21 students, is allocated to interval 10\n",
      "Course 23, with 27 students, is allocated to interval 7\n",
      "Course 24, with 34 students, is allocated to interval 8\n",
      "Course 25, with 20 students, is allocated to interval 17\n",
      "Course 26, with 25 students, is allocated to interval 44\n",
      "Course 27, with 24 students, is allocated to interval 18\n",
      "Course 28, with 30 students, is allocated to interval 25\n",
      "Course 29, with 21 students, is allocated to interval 46\n",
      "Course 30, with 22 students, is allocated to interval 25\n",
      "Course 31, with 23 students, is allocated to interval 15\n",
      "Course 32, with 29 students, is allocated to interval 51\n",
      "Course 33, with 37 students, is allocated to interval 8\n",
      "Course 34, with 24 students, is allocated to interval 56\n",
      "Course 35, with 29 students, is allocated to interval 57\n",
      "Course 36, with 38 students, is allocated to interval 16\n",
      "Course 37, with 28 students, is allocated to interval 25\n",
      "Course 38, with 23 students, is allocated to interval 44\n",
      "Course 39, with 27 students, is allocated to interval 10\n",
      "Course 40, with 27 students, is allocated to interval 23\n",
      "Course 41, with 23 students, is allocated to interval 56\n",
      "Course 42, with 27 students, is allocated to interval 49\n",
      "Course 43, with 28 students, is allocated to interval 23\n",
      "Course 44, with 24 students, is allocated to interval 24\n",
      "Course 45, with 21 students, is allocated to interval 18\n",
      "Course 46, with 18 students, is allocated to interval 60\n",
      "Course 47, with 30 students, is allocated to interval 49\n",
      "Course 48, with 23 students, is allocated to interval 45\n",
      "Course 49, with 27 students, is allocated to interval 17\n",
      "Course 50, with 30 students, is allocated to interval 49\n",
      "Course 51, with 27 students, is allocated to interval 16\n",
      "Course 52, with 24 students, is allocated to interval 24\n",
      "Course 53, with 17 students, is allocated to interval 11\n",
      "Course 54, with 24 students, is allocated to interval 14\n",
      "Course 55, with 27 students, is allocated to interval 43\n",
      "Course 56, with 28 students, is allocated to interval 43\n",
      "Course 57, with 24 students, is allocated to interval 14\n",
      "Course 58, with 25 students, is allocated to interval 25\n",
      "Course 59, with 40 students, is allocated to interval 25\n",
      "Course 60, with 24 students, is allocated to interval 21\n",
      "Course 61, with 28 students, is allocated to interval 7\n",
      "Course 62, with 30 students, is allocated to interval 49\n",
      "Course 63, with 30 students, is allocated to interval 53\n",
      "Course 64, with 30 students, is allocated to interval 15\n",
      "Course 65, with 24 students, is allocated to interval 21\n",
      "Course 66, with 29 students, is allocated to interval 18\n",
      "Course 67, with 21 students, is allocated to interval 8\n",
      "Course 68, with 33 students, is allocated to interval 50\n",
      "Course 69, with 29 students, is allocated to interval 21\n",
      "Course 70, with 31 students, is allocated to interval 53\n",
      "Course 71, with 28 students, is allocated to interval 42\n",
      "Course 72, with 30 students, is allocated to interval 44\n",
      "Course 73, with 23 students, is allocated to interval 42\n",
      "Course 74, with 25 students, is allocated to interval 15\n",
      "Course 75, with 28 students, is allocated to interval 44\n",
      "Course 76, with 20 students, is allocated to interval 9\n",
      "Course 77, with 33 students, is allocated to interval 11\n",
      "Course 78, with 29 students, is allocated to interval 15\n",
      "Course 79, with 25 students, is allocated to interval 22\n",
      "Course 80, with 25 students, is allocated to interval 17\n",
      "Course 81, with 25 students, is allocated to interval 46\n",
      "Course 82, with 27 students, is allocated to interval 42\n",
      "Course 83, with 24 students, is allocated to interval 58\n",
      "Course 84, with 32 students, is allocated to interval 46\n",
      "Course 85, with 27 students, is allocated to interval 51\n",
      "Course 86, with 21 students, is allocated to interval 10\n",
      "Course 87, with 22 students, is allocated to interval 9\n",
      "Course 88, with 27 students, is allocated to interval 25\n",
      "Course 89, with 30 students, is allocated to interval 53\n",
      "Course 90, with 25 students, is allocated to interval 22\n",
      "Course 91, with 26 students, is allocated to interval 42\n",
      "Course 92, with 26 students, is allocated to interval 46\n",
      "Course 93, with 31 students, is allocated to interval 44\n",
      "Course 94, with 25 students, is allocated to interval 42\n",
      "Course 95, with 26 students, is allocated to interval 52\n",
      "Course 96, with 25 students, is allocated to interval 10\n",
      "Course 97, with 26 students, is allocated to interval 56\n",
      "Course 98, with 32 students, is allocated to interval 42\n",
      "Course 99, with 28 students, is allocated to interval 9\n",
      "Course 100, with 27 students, is allocated to interval 24\n",
      "Course 101, with 25 students, is allocated to interval 53\n",
      "Course 102, with 33 students, is allocated to interval 9\n",
      "Course 103, with 35 students, is allocated to interval 45\n",
      "Course 104, with 33 students, is allocated to interval 7\n",
      "Course 105, with 27 students, is allocated to interval 43\n",
      "Course 106, with 28 students, is allocated to interval 52\n",
      "Course 107, with 22 students, is allocated to interval 8\n",
      "Course 108, with 22 students, is allocated to interval 7\n",
      "Course 109, with 19 students, is allocated to interval 8\n",
      "Course 110, with 28 students, is allocated to interval 23\n",
      "Course 111, with 26 students, is allocated to interval 59\n",
      "Course 112, with 22 students, is allocated to interval 46\n",
      "Course 113, with 29 students, is allocated to interval 44\n",
      "Course 114, with 35 students, is allocated to interval 44\n",
      "Course 115, with 24 students, is allocated to interval 14\n",
      "Course 116, with 27 students, is allocated to interval 58\n",
      "Course 117, with 30 students, is allocated to interval 59\n",
      "Course 118, with 26 students, is allocated to interval 56\n",
      "Course 119, with 25 students, is allocated to interval 56\n",
      "Course 120, with 34 students, is allocated to interval 21\n",
      "Course 121, with 27 students, is allocated to interval 17\n",
      "Course 122, with 30 students, is allocated to interval 7\n",
      "Course 123, with 40 students, is allocated to interval 14\n",
      "Course 124, with 26 students, is allocated to interval 16\n",
      "Course 125, with 19 students, is allocated to interval 11\n",
      "Course 126, with 14 students, is allocated to interval 60\n",
      "Course 127, with 29 students, is allocated to interval 52\n",
      "Course 128, with 20 students, is allocated to interval 7\n",
      "Course 129, with 26 students, is allocated to interval 23\n",
      "Course 130, with 32 students, is allocated to interval 11\n",
      "Course 131, with 23 students, is allocated to interval 46\n",
      "Course 132, with 30 students, is allocated to interval 24\n",
      "Course 133, with 26 students, is allocated to interval 42\n",
      "Course 134, with 22 students, is allocated to interval 57\n",
      "Course 135, with 21 students, is allocated to interval 9\n",
      "Course 136, with 21 students, is allocated to interval 15\n",
      "Course 137, with 20 students, is allocated to interval 50\n",
      "Course 138, with 30 students, is allocated to interval 11\n",
      "Course 139, with 23 students, is allocated to interval 7\n",
      "Course 140, with 28 students, is allocated to interval 44\n",
      "Course 141, with 19 students, is allocated to interval 52\n",
      "Course 142, with 32 students, is allocated to interval 10\n",
      "Course 143, with 20 students, is allocated to interval 59\n",
      "Course 144, with 37 students, is allocated to interval 21\n",
      "Course 145, with 24 students, is allocated to interval 25\n",
      "Course 146, with 31 students, is allocated to interval 52\n",
      "Course 147, with 25 students, is allocated to interval 23\n",
      "Course 148, with 27 students, is allocated to interval 10\n",
      "Course 149, with 31 students, is allocated to interval 51\n",
      "Course 150, with 16 students, is allocated to interval 60\n",
      "Course 151, with 21 students, is allocated to interval 56\n",
      "Course 152, with 23 students, is allocated to interval 18\n",
      "Course 153, with 22 students, is allocated to interval 10\n",
      "Course 154, with 21 students, is allocated to interval 46\n",
      "Course 155, with 24 students, is allocated to interval 25\n",
      "Course 156, with 27 students, is allocated to interval 49\n",
      "Course 157, with 27 students, is allocated to interval 42\n",
      "Course 158, with 27 students, is allocated to interval 9\n",
      "Course 159, with 24 students, is allocated to interval 9\n",
      "Course 160, with 23 students, is allocated to interval 14\n",
      "Course 161, with 28 students, is allocated to interval 16\n",
      "Course 162, with 22 students, is allocated to interval 46\n",
      "Course 163, with 30 students, is allocated to interval 43\n",
      "Course 164, with 31 students, is allocated to interval 16\n",
      "Course 165, with 19 students, is allocated to interval 60\n",
      "Course 166, with 31 students, is allocated to interval 23\n",
      "Course 167, with 25 students, is allocated to interval 18\n",
      "Course 168, with 31 students, is allocated to interval 45\n",
      "Course 169, with 19 students, is allocated to interval 53\n",
      "Course 170, with 31 students, is allocated to interval 15\n",
      "Course 171, with 35 students, is allocated to interval 57\n",
      "Course 172, with 31 students, is allocated to interval 22\n",
      "Course 173, with 20 students, is allocated to interval 11\n",
      "Course 174, with 32 students, is allocated to interval 58\n",
      "Course 175, with 23 students, is allocated to interval 60\n",
      "Course 176, with 24 students, is allocated to interval 57\n",
      "Course 177, with 30 students, is allocated to interval 23\n",
      "Course 178, with 21 students, is allocated to interval 53\n",
      "Course 179, with 31 students, is allocated to interval 50\n",
      "Course 180, with 24 students, is allocated to interval 17\n",
      "Course 181, with 37 students, is allocated to interval 43\n",
      "Course 182, with 27 students, is allocated to interval 60\n",
      "Course 183, with 20 students, is allocated to interval 58\n",
      "Course 184, with 21 students, is allocated to interval 10\n",
      "Course 185, with 33 students, is allocated to interval 49\n",
      "Course 186, with 28 students, is allocated to interval 25\n",
      "Course 187, with 33 students, is allocated to interval 59\n",
      "Course 188, with 27 students, is allocated to interval 57\n",
      "Course 189, with 26 students, is allocated to interval 58\n",
      "Course 190, with 27 students, is allocated to interval 10\n",
      "Course 191, with 25 students, is allocated to interval 57\n",
      "Course 192, with 35 students, is allocated to interval 43\n",
      "Course 193, with 18 students, is allocated to interval 16\n",
      "Course 194, with 26 students, is allocated to interval 21\n",
      "Course 195, with 33 students, is allocated to interval 42\n",
      "Course 196, with 27 students, is allocated to interval 25\n",
      "Course 197, with 19 students, is allocated to interval 14\n",
      "Course 198, with 29 students, is allocated to interval 24\n",
      "Course 199, with 23 students, is allocated to interval 52\n",
      "Course 200, with 30 students, is allocated to interval 8\n",
      "Course 201, with 23 students, is allocated to interval 57\n",
      "Course 202, with 35 students, is allocated to interval 44\n",
      "Course 203, with 21 students, is allocated to interval 58\n",
      "Course 204, with 20 students, is allocated to interval 58\n",
      "Course 205, with 28 students, is allocated to interval 57\n",
      "Course 206, with 28 students, is allocated to interval 45\n",
      "Course 207, with 27 students, is allocated to interval 17\n",
      "Course 208, with 19 students, is allocated to interval 60\n",
      "Course 209, with 23 students, is allocated to interval 60\n",
      "Course 210, with 25 students, is allocated to interval 58\n",
      "Course 211, with 23 students, is allocated to interval 52\n",
      "Course 212, with 27 students, is allocated to interval 16\n",
      "Course 213, with 23 students, is allocated to interval 9\n",
      "Course 214, with 29 students, is allocated to interval 56\n",
      "Course 215, with 28 students, is allocated to interval 56\n",
      "Course 216, with 21 students, is allocated to interval 59\n",
      "Course 217, with 25 students, is allocated to interval 24\n",
      "Course 218, with 38 students, is allocated to interval 42\n",
      "Course 219, with 25 students, is allocated to interval 15\n",
      "Course 220, with 25 students, is allocated to interval 58\n",
      "Course 221, with 24 students, is allocated to interval 14\n",
      "Course 222, with 21 students, is allocated to interval 57\n",
      "Course 223, with 22 students, is allocated to interval 45\n",
      "Course 224, with 27 students, is allocated to interval 50\n",
      "Course 225, with 24 students, is allocated to interval 53\n",
      "Course 226, with 18 students, is allocated to interval 52\n",
      "Course 227, with 22 students, is allocated to interval 11\n",
      "Course 228, with 23 students, is allocated to interval 52\n",
      "Course 229, with 27 students, is allocated to interval 11\n",
      "Course 230, with 25 students, is allocated to interval 11\n",
      "Course 231, with 35 students, is allocated to interval 49\n",
      "Course 232, with 32 students, is allocated to interval 44\n",
      "Course 233, with 30 students, is allocated to interval 14\n",
      "Course 234, with 25 students, is allocated to interval 25\n",
      "Course 235, with 24 students, is allocated to interval 21\n",
      "Course 236, with 31 students, is allocated to interval 45\n",
      "Course 237, with 24 students, is allocated to interval 10\n",
      "Course 238, with 27 students, is allocated to interval 46\n",
      "Course 239, with 16 students, is allocated to interval 60\n",
      "Course 240, with 30 students, is allocated to interval 43\n",
      "Course 241, with 27 students, is allocated to interval 25\n",
      "Course 242, with 31 students, is allocated to interval 60\n",
      "Course 243, with 30 students, is allocated to interval 11\n",
      "Course 244, with 34 students, is allocated to interval 18\n",
      "Course 245, with 34 students, is allocated to interval 23\n",
      "Course 246, with 31 students, is allocated to interval 10\n",
      "Course 247, with 26 students, is allocated to interval 14\n",
      "Course 248, with 22 students, is allocated to interval 25\n",
      "Course 249, with 30 students, is allocated to interval 59\n",
      "Course 250, with 28 students, is allocated to interval 10\n",
      "Course 251, with 29 students, is allocated to interval 51\n",
      "Course 252, with 21 students, is allocated to interval 21\n",
      "Course 253, with 22 students, is allocated to interval 52\n",
      "Course 254, with 19 students, is allocated to interval 60\n",
      "Course 255, with 21 students, is allocated to interval 51\n",
      "Course 256, with 23 students, is allocated to interval 49\n",
      "Course 257, with 27 students, is allocated to interval 43\n",
      "Course 258, with 23 students, is allocated to interval 58\n",
      "Course 259, with 25 students, is allocated to interval 21\n",
      "Course 260, with 30 students, is allocated to interval 15\n",
      "Course 261, with 30 students, is allocated to interval 18\n",
      "Course 262, with 28 students, is allocated to interval 18\n",
      "Course 263, with 36 students, is allocated to interval 59\n",
      "Course 264, with 17 students, is allocated to interval 60\n",
      "Course 265, with 22 students, is allocated to interval 17\n",
      "Course 266, with 27 students, is allocated to interval 52\n",
      "Course 267, with 29 students, is allocated to interval 46\n",
      "Course 268, with 29 students, is allocated to interval 17\n",
      "Course 269, with 22 students, is allocated to interval 10\n",
      "Course 270, with 29 students, is allocated to interval 9\n",
      "Course 271, with 26 students, is allocated to interval 56\n",
      "Course 272, with 27 students, is allocated to interval 57\n",
      "Course 273, with 27 students, is allocated to interval 46\n",
      "Course 274, with 21 students, is allocated to interval 46\n",
      "Course 275, with 19 students, is allocated to interval 60\n",
      "Course 276, with 29 students, is allocated to interval 18\n",
      "Course 277, with 26 students, is allocated to interval 60\n",
      "Course 278, with 19 students, is allocated to interval 22\n",
      "Course 279, with 20 students, is allocated to interval 60\n",
      "Course 280, with 26 students, is allocated to interval 22\n",
      "Course 281, with 20 students, is allocated to interval 9\n",
      "Course 282, with 31 students, is allocated to interval 51\n",
      "Course 283, with 28 students, is allocated to interval 45\n",
      "Course 284, with 25 students, is allocated to interval 51\n",
      "Course 285, with 17 students, is allocated to interval 60\n",
      "Course 286, with 26 students, is allocated to interval 7\n",
      "Course 287, with 30 students, is allocated to interval 22\n",
      "Course 288, with 22 students, is allocated to interval 51\n",
      "Course 289, with 26 students, is allocated to interval 59\n",
      "Course 290, with 26 students, is allocated to interval 16\n",
      "Course 291, with 25 students, is allocated to interval 14\n",
      "Course 292, with 27 students, is allocated to interval 22\n",
      "Course 293, with 18 students, is allocated to interval 60\n",
      "Course 294, with 28 students, is allocated to interval 10\n",
      "Course 295, with 21 students, is allocated to interval 59\n",
      "Course 296, with 26 students, is allocated to interval 7\n",
      "Course 297, with 22 students, is allocated to interval 16\n",
      "Course 298, with 28 students, is allocated to interval 53\n",
      "Course 299, with 27 students, is allocated to interval 50\n",
      "Course 300, with 29 students, is allocated to interval 53\n",
      "Course 301, with 23 students, is allocated to interval 42\n",
      "Course 302, with 36 students, is allocated to interval 43\n",
      "Course 303, with 31 students, is allocated to interval 9\n",
      "Course 304, with 27 students, is allocated to interval 24\n",
      "Course 305, with 19 students, is allocated to interval 11\n",
      "Course 306, with 22 students, is allocated to interval 8\n",
      "Course 307, with 31 students, is allocated to interval 58\n",
      "Course 308, with 23 students, is allocated to interval 18\n",
      "Course 309, with 23 students, is allocated to interval 10\n",
      "Course 310, with 29 students, is allocated to interval 15\n",
      "Course 311, with 24 students, is allocated to interval 17\n",
      "Course 312, with 32 students, is allocated to interval 24\n",
      "Course 313, with 30 students, is allocated to interval 23\n",
      "Course 314, with 24 students, is allocated to interval 25\n",
      "Course 315, with 23 students, is allocated to interval 43\n",
      "Course 316, with 26 students, is allocated to interval 44\n",
      "Course 317, with 19 students, is allocated to interval 43\n",
      "Course 318, with 26 students, is allocated to interval 58\n",
      "Course 319, with 27 students, is allocated to interval 17\n",
      "Course 320, with 21 students, is allocated to interval 46\n",
      "Course 321, with 34 students, is allocated to interval 50\n",
      "Course 322, with 25 students, is allocated to interval 16\n",
      "Course 323, with 25 students, is allocated to interval 45\n",
      "Course 324, with 31 students, is allocated to interval 25\n",
      "Course 325, with 29 students, is allocated to interval 14\n",
      "Course 326, with 30 students, is allocated to interval 11\n",
      "Course 327, with 27 students, is allocated to interval 50\n",
      "Course 328, with 26 students, is allocated to interval 11\n",
      "Course 329, with 28 students, is allocated to interval 16\n",
      "Course 330, with 36 students, is allocated to interval 46\n",
      "Course 331, with 31 students, is allocated to interval 22\n",
      "Course 332, with 26 students, is allocated to interval 22\n",
      "Course 333, with 18 students, is allocated to interval 60\n",
      "Course 334, with 25 students, is allocated to interval 9\n",
      "Course 335, with 23 students, is allocated to interval 24\n",
      "Course 336, with 23 students, is allocated to interval 57\n",
      "Course 337, with 28 students, is allocated to interval 59\n",
      "Course 338, with 22 students, is allocated to interval 8\n",
      "Course 339, with 29 students, is allocated to interval 44\n",
      "Course 340, with 28 students, is allocated to interval 18\n",
      "Course 341, with 29 students, is allocated to interval 21\n",
      "Course 342, with 31 students, is allocated to interval 24\n",
      "Course 343, with 23 students, is allocated to interval 46\n",
      "Course 344, with 31 students, is allocated to interval 11\n",
      "Course 345, with 35 students, is allocated to interval 58\n",
      "Course 346, with 35 students, is allocated to interval 42\n",
      "Course 347, with 20 students, is allocated to interval 44\n",
      "Course 348, with 33 students, is allocated to interval 16\n",
      "Course 349, with 20 students, is allocated to interval 23\n",
      "Course 350, with 26 students, is allocated to interval 16\n",
      "Course 351, with 21 students, is allocated to interval 60\n",
      "Course 352, with 28 students, is allocated to interval 24\n",
      "Course 353, with 26 students, is allocated to interval 22\n",
      "Course 354, with 31 students, is allocated to interval 58\n",
      "Course 355, with 28 students, is allocated to interval 8\n",
      "Course 356, with 31 students, is allocated to interval 17\n",
      "Course 357, with 21 students, is allocated to interval 43\n",
      "Course 358, with 18 students, is allocated to interval 52\n",
      "Course 359, with 22 students, is allocated to interval 57\n",
      "Course 360, with 27 students, is allocated to interval 17\n",
      "Course 361, with 26 students, is allocated to interval 7\n",
      "Course 362, with 29 students, is allocated to interval 17\n",
      "Course 363, with 28 students, is allocated to interval 18\n",
      "Course 364, with 24 students, is allocated to interval 51\n",
      "Course 365, with 27 students, is allocated to interval 49\n",
      "Course 366, with 31 students, is allocated to interval 24\n",
      "Course 367, with 19 students, is allocated to interval 59\n",
      "Course 368, with 19 students, is allocated to interval 60\n",
      "Course 369, with 23 students, is allocated to interval 7\n",
      "Course 370, with 25 students, is allocated to interval 46\n",
      "Course 371, with 24 students, is allocated to interval 53\n",
      "Course 372, with 16 students, is allocated to interval 8\n",
      "Course 373, with 35 students, is allocated to interval 8\n",
      "Course 374, with 26 students, is allocated to interval 51\n",
      "Course 375, with 26 students, is allocated to interval 22\n",
      "Course 376, with 26 students, is allocated to interval 23\n",
      "Course 377, with 32 students, is allocated to interval 45\n",
      "Course 378, with 34 students, is allocated to interval 14\n",
      "Course 379, with 26 students, is allocated to interval 51\n",
      "Course 380, with 32 students, is allocated to interval 23\n",
      "Course 381, with 22 students, is allocated to interval 8\n",
      "Course 382, with 31 students, is allocated to interval 9\n",
      "Course 383, with 35 students, is allocated to interval 23\n",
      "Course 384, with 18 students, is allocated to interval 24\n",
      "Course 385, with 31 students, is allocated to interval 52\n",
      "Course 386, with 27 students, is allocated to interval 60\n",
      "Course 387, with 24 students, is allocated to interval 8\n",
      "Course 388, with 34 students, is allocated to interval 44\n",
      "Course 389, with 33 students, is allocated to interval 52\n",
      "Course 390, with 22 students, is allocated to interval 46\n",
      "Course 391, with 32 students, is allocated to interval 21\n",
      "Course 392, with 22 students, is allocated to interval 52\n",
      "Course 393, with 28 students, is allocated to interval 45\n",
      "Course 394, with 16 students, is allocated to interval 60\n",
      "Course 395, with 27 students, is allocated to interval 59\n",
      "Course 396, with 29 students, is allocated to interval 15\n",
      "Course 397, with 24 students, is allocated to interval 58\n",
      "Course 398, with 22 students, is allocated to interval 58\n",
      "Course 399, with 29 students, is allocated to interval 21\n",
      "Course 400, with 26 students, is allocated to interval 50\n",
      "Course 401, with 22 students, is allocated to interval 24\n",
      "Course 402, with 34 students, is allocated to interval 7\n",
      "Course 403, with 24 students, is allocated to interval 60\n",
      "Course 404, with 27 students, is allocated to interval 14\n",
      "Course 405, with 29 students, is allocated to interval 50\n",
      "Course 406, with 26 students, is allocated to interval 15\n",
      "Course 407, with 21 students, is allocated to interval 52\n",
      "Course 408, with 34 students, is allocated to interval 9\n",
      "Course 409, with 24 students, is allocated to interval 53\n",
      "Course 410, with 25 students, is allocated to interval 22\n",
      "Course 411, with 25 students, is allocated to interval 15\n",
      "Course 412, with 24 students, is allocated to interval 8\n",
      "Course 413, with 29 students, is allocated to interval 11\n",
      "Course 414, with 28 students, is allocated to interval 44\n",
      "Course 415, with 31 students, is allocated to interval 53\n",
      "Course 416, with 26 students, is allocated to interval 42\n",
      "Course 417, with 29 students, is allocated to interval 50\n",
      "Course 418, with 23 students, is allocated to interval 43\n",
      "Course 419, with 21 students, is allocated to interval 53\n",
      "Course 420, with 30 students, is allocated to interval 42\n",
      "Course 421, with 24 students, is allocated to interval 8\n",
      "Course 422, with 23 students, is allocated to interval 58\n",
      "Course 423, with 37 students, is allocated to interval 22\n",
      "Course 424, with 35 students, is allocated to interval 49\n",
      "Course 425, with 25 students, is allocated to interval 45\n",
      "Course 426, with 24 students, is allocated to interval 7\n",
      "Course 427, with 24 students, is allocated to interval 51\n",
      "Course 428, with 34 students, is allocated to interval 56\n",
      "Course 429, with 33 students, is allocated to interval 16\n",
      "Course 430, with 26 students, is allocated to interval 57\n",
      "Course 431, with 26 students, is allocated to interval 9\n",
      "Course 432, with 26 students, is allocated to interval 44\n",
      "Course 433, with 27 students, is allocated to interval 7\n",
      "Course 434, with 19 students, is allocated to interval 60\n",
      "Course 435, with 33 students, is allocated to interval 49\n",
      "Course 436, with 34 students, is allocated to interval 56\n",
      "Course 437, with 28 students, is allocated to interval 8\n",
      "Course 438, with 30 students, is allocated to interval 18\n",
      "Course 439, with 23 students, is allocated to interval 25\n",
      "Course 440, with 28 students, is allocated to interval 52\n",
      "Course 441, with 32 students, is allocated to interval 46\n",
      "Course 442, with 23 students, is allocated to interval 50\n",
      "Course 443, with 28 students, is allocated to interval 24\n",
      "Course 444, with 23 students, is allocated to interval 24\n",
      "Course 445, with 24 students, is allocated to interval 58\n",
      "Course 446, with 26 students, is allocated to interval 57\n",
      "Course 447, with 19 students, is allocated to interval 50\n",
      "Course 448, with 26 students, is allocated to interval 7\n",
      "Course 449, with 32 students, is allocated to interval 10\n",
      "Course 450, with 25 students, is allocated to interval 15\n",
      "Course 451, with 22 students, is allocated to interval 7\n",
      "Course 452, with 37 students, is allocated to interval 21\n",
      "Course 453, with 31 students, is allocated to interval 15\n",
      "Course 454, with 23 students, is allocated to interval 43\n",
      "Course 455, with 22 students, is allocated to interval 21\n",
      "Course 456, with 23 students, is allocated to interval 16\n",
      "Course 457, with 30 students, is allocated to interval 22\n",
      "Course 458, with 34 students, is allocated to interval 17\n",
      "Course 459, with 25 students, is allocated to interval 42\n",
      "Course 460, with 33 students, is allocated to interval 10\n",
      "Course 461, with 34 students, is allocated to interval 45\n",
      "Course 462, with 26 students, is allocated to interval 8\n",
      "Course 463, with 33 students, is allocated to interval 52\n",
      "Course 464, with 27 students, is allocated to interval 51\n",
      "Course 465, with 25 students, is allocated to interval 18\n",
      "Course 466, with 27 students, is allocated to interval 49\n",
      "Course 467, with 21 students, is allocated to interval 14\n",
      "Course 468, with 18 students, is allocated to interval 52\n",
      "Course 469, with 24 students, is allocated to interval 22\n",
      "Course 470, with 31 students, is allocated to interval 23\n",
      "Course 471, with 26 students, is allocated to interval 9\n",
      "Course 472, with 24 students, is allocated to interval 10\n",
      "Course 473, with 34 students, is allocated to interval 11\n",
      "Course 474, with 26 students, is allocated to interval 42\n",
      "Course 475, with 33 students, is allocated to interval 50\n",
      "Course 476, with 23 students, is allocated to interval 58\n",
      "Course 477, with 26 students, is allocated to interval 51\n",
      "Course 478, with 26 students, is allocated to interval 17\n",
      "Course 479, with 25 students, is allocated to interval 45\n",
      "Course 480, with 27 students, is allocated to interval 53\n",
      "Course 481, with 29 students, is allocated to interval 42\n",
      "Course 482, with 35 students, is allocated to interval 11\n",
      "Course 483, with 24 students, is allocated to interval 43\n",
      "Course 484, with 28 students, is allocated to interval 42\n",
      "Course 485, with 19 students, is allocated to interval 10\n",
      "Course 486, with 28 students, is allocated to interval 59\n",
      "Course 487, with 17 students, is allocated to interval 60\n",
      "Course 488, with 33 students, is allocated to interval 58\n",
      "Course 489, with 30 students, is allocated to interval 11\n",
      "Course 490, with 39 students, is allocated to interval 14\n",
      "Course 491, with 22 students, is allocated to interval 58\n",
      "Course 492, with 28 students, is allocated to interval 46\n",
      "Course 493, with 28 students, is allocated to interval 56\n",
      "Course 494, with 34 students, is allocated to interval 15\n",
      "Course 495, with 25 students, is allocated to interval 59\n",
      "Course 496, with 32 students, is allocated to interval 17\n",
      "Course 497, with 26 students, is allocated to interval 45\n",
      "Course 498, with 29 students, is allocated to interval 16\n",
      "Course 499, with 26 students, is allocated to interval 57\n",
      "Pass feasibility check? True\n"
     ]
    }
   ],
   "source": [
    "# data generate ... \n",
    "\n",
    "import random\n",
    "import numpy as np\n",
    "import gurobipy as grb\n",
    "\n",
    "\n",
    "def generate_intervals_weights():\n",
    "    weights = np.array([[1] * 7 for _ in range(10)])\n",
    "    weights[0] += 3 # 8:00\n",
    "    weights[5] += 3 # 8:00\n",
    "    weights[4] += 1 # night exam\n",
    "    weights[9] += 1 # night exam \n",
    "    weights[0:5, -2: ] += 2 # weekend \n",
    "    weights[5:10, -2: ] += 4 # weekend\n",
    "    weights[9, -2: ] += 3 # \"goal keeper\"\n",
    "    # The result is just like:\n",
    "    # [[4 4 4 4 4 6 6]\n",
    "    #  [1 1 1 1 1 3 3]\n",
    "    #  [1 1 1 1 1 3 3]\n",
    "    #  [1 1 1 1 1 3 3]\n",
    "    #  [2 2 2 2 2 4 4]\n",
    "    #  [4 4 4 4 4 8 8]\n",
    "    #  [1 1 1 1 1 5 5]\n",
    "    #  [1 1 1 1 1 5 5]\n",
    "    #  [1 1 1 1 1 5 5]\n",
    "    #  [2 2 2 2 2 8 8]]\n",
    "    # Two weeks in total, each day has 5 time slots: 8:00~10:00, 10:30~12:30, 14:00~16:00, 16:30~18:30, 19:00~21:00\n",
    "    # Apparently, students don't like 8:00~10:00, and 19:00~21:00 exams.\n",
    "    # Apparently too, students don't like exams during weekends.\n",
    "    weights = weights.flatten()\n",
    "    return list(weights)\n",
    "\n",
    "def generate_student_course_relation(num_courses, num_students):\n",
    "    # 存储学生参加的课程\n",
    "    student_courses = {}\n",
    "    course_students = {}\n",
    "    # 确保每个课程都有学生参加\n",
    "    for course in range(num_courses):\n",
    "        if course not in course_students:\n",
    "            course_students[course] = []\n",
    "        student = random.randint(0, num_students - 1)\n",
    "        if student in student_courses:\n",
    "            student_courses[student].append(course)\n",
    "        else:\n",
    "            student_courses[student] = [course]\n",
    "        course_students[course].append(student)\n",
    "    \n",
    "    # 生成每个学生参加的课程数在 2~10 之间\n",
    "    for student in range(num_students):\n",
    "        if student not in student_courses:\n",
    "            student_courses[student] = []\n",
    "        while len(student_courses[student]) < random.randint(2, 10):\n",
    "            course = random.randint(0, num_courses - 1)\n",
    "            if course not in student_courses[student] and len(student_courses[student]) < 10:\n",
    "                student_courses[student].append(course)\n",
    "                course_students[course].append(student)\n",
    "    return student_courses, course_students\n",
    "\n",
    "def check_feasibility(result, student_courses, course_students, weights, num_courses, num_students, intervals):\n",
    "    feasible = True\n",
    "    # check if the result is okay ... \n",
    "    # 1. if all courses are assigned ... \n",
    "    if len(result.keys()) != num_courses:\n",
    "        feasible = False\n",
    "    # 2. if students time conflict ... \n",
    "    if not feasible:\n",
    "        return feasible    \n",
    "    for student in range(num_students):\n",
    "        check_interv = set()\n",
    "        for course in student_courses[student]:\n",
    "            if result[course] in check_interv:\n",
    "                print(f\"Wrong! Student {student} has conflict with course {course} at interval {result[course]}\")\n",
    "                feasible = False \n",
    "            else:\n",
    "                check_interv.add(result[course])\n",
    "    return feasible\n",
    "\n",
    "\n",
    "def solver(student_courses, course_students, weights, num_courses, num_students, intervals):\n",
    "    model = grb.Model(\"CourseSchedule\")\n",
    "    x = dict()\n",
    "    for course in range(num_courses):\n",
    "        for interv in range(intervals):\n",
    "            x[course, interv] = model.addVar(\n",
    "                vtype=grb.GRB.BINARY, name= f\"{course}_{interv}\"\n",
    "            )\n",
    "            # if allocate course i to interval j, 0-1 binary\n",
    "\n",
    "    # set objective func\n",
    "    model.modelSense = grb.GRB.MINIMIZE\n",
    "    model.setObjective(grb.quicksum(\n",
    "        x[course, interv] * weights[interv] * len(course_students[course]) for course in range(num_courses) for interv in range(intervals)\n",
    "    ))\n",
    "    # set constraints ... \n",
    "    for course in range(num_courses):\n",
    "        model.addConstr(grb.quicksum(x[course, interv] for interv in range(intervals)) == 1, f\"C_{course}_fill\")\n",
    "    for student in range(num_students):\n",
    "        for interv in range(intervals):\n",
    "            model.addConstr(grb.quicksum(x[course, interv] for course in student_courses[student]) <= 1, f\"C_{student}_{interv}_leq1\")\n",
    "    \n",
    "    model.optimize()\n",
    "    result = dict()\n",
    "    if model.status == grb.GRB.status.OPTIMAL:\n",
    "        ofv = model.getObjective().getValue()\n",
    "        print(f\"Objective Value: {ofv}\")\n",
    "        for course in range(num_courses):\n",
    "            for interv in range(intervals):\n",
    "                if x[course, interv].x > 0.5:\n",
    "                    result[course] = interv\n",
    "                    print(f\"Course {course}, with {len(course_students[course])} students, is allocated to interval {interv}\")\n",
    "    return result    \n",
    "\n",
    "    \n",
    "if __name__ == \"__main__\":\n",
    "    num_courses = 500\n",
    "    num_students = 3000\n",
    "    student_courses, course_students = generate_student_course_relation(num_courses, num_students)\n",
    "    weights = generate_intervals_weights()\n",
    "    intervals = 70\n",
    "    result = solver(student_courses, course_students, weights, num_courses, num_students, intervals)\n",
    "    check = check_feasibility(result, student_courses, course_students, weights, num_courses, num_students, intervals)\n",
    "    print(f\"Pass feasibility check? {check}\")\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# checked for feasibility."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "py310_arm",
   "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.10.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}