activities/a07_discrete-optimization.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DSCI 512 Lecture 7 Activities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## T/F questions\n",
    "\n",
    "1. A solver will violate the constraints if this results in huge gains for the objective function.\n",
    "2. Some discrete optimization problems have multiple solutions.\n",
    "3. Some discrete optimization problems have no solutions at all.\n",
    "4. PuLP can be use to solve any optimization problem, but it may be very slow for some problems."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answers:**\n",
    "\n",
    "1. False.\n",
    "2. True.\n",
    "3. True.\n",
    "4. False, it can only be used on linear optimization problems."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Practice question\n",
    "\n",
    "Consider using integer linear programming (ILP) to determine how to optimally spend your time studying for MDS.You have various timeslots to study, e.g. Monday night, Tuesday night, Friday morning, Friday afternoon, etc. You also have various courses to study: 571, 531, 512, 552.\n",
    "\n",
    "Let `x[time][course]` be a binary PuLP variable indicating whether or not you will study for course `course` at time `time`. Translate the following PuLP constraints into English (1 sentence maximum!):\n",
    "\n",
    "#### Part (a)\n",
    "\n",
    "```python\n",
    "for course in courses:\n",
    "    prob += x[\"Friday morning\"][course] + x[\"Friday afternoon\"][course] <= 1\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Possible answers:\n",
    "\n",
    "- For each course, I can study it at most once on Friday morning/afternoon.\n",
    "- For each course, I can't study both Friday morning and Friday afternoons.\n",
    "- I can't study the same course for both Friday morning and Friday afternoon."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part (b) \n",
    "\n",
    "```python\n",
    "for time in times:\n",
    "    prob += pulp.lpSum(x[time][course] for course in courses) == 1\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Possible answers:\n",
    "\n",
    "- For each of the time slots we can only study one subject. \n",
    "- For each of the time slots we will study exactly one course."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```python\n",
    "for course in courses:\n",
    "    prob += pulp.lpSum(x[time][course] for time in times) >= 1\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Possible answer:\n",
    "\n",
    "- We need to study all the of the courses at least once."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Activity: playing around with PuLP\n",
    "\n",
    "- Remove constraint(s) and see what happens to the solution and the optimal objective value.\n",
    "- Add constraint(s) until the problem becomes infeasible. What constraint(s) did you add?\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.10.6 ('dsci512')",
   "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.6"
  },
  "vscode": {
   "interpreter": {
    "hash": "833530e805897aab5e7a30ee530b0bcb4cd19373b840f29eae5897b61b26002e"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}