MILP Phone contract example.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Phone contract choice example\n",
    "================\n",
    "\n",
    "This is a small example of using MILP to choose between options. Also see the spreadsheet solution of the problem.\n",
    "\n",
    "Briefly, we must choose a cell phone contract from one of three providers. A contract costs a certain amount and supplies a certain number of \"free minutes\". We only pay for minutes above this \"free\" amount. Some providers also supply bundles. If we have a contract from that provier, we can add a bundle. To keep things simple in this problem, we will pretend that we can only buy one bundle (or choose not to buy a bundle at all). The problem is to minimise total cost for a known amount of minutes used."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll use [PuLP](https://pythonhosted.org/PuLP/) to solve this problem. The website has some good examples to get you going."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import pulp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We create a LpProblem instance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "p = pulp.LpProblem(\"Phone contract\", pulp.LpMinimize)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Specify how many minutes to use."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "minutes_used = 299"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Define the data for the problem. Providers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "providers = ['MTN', 'Vodacom', 'CellC']\n",
    "contract_cost = dict(zip(providers, [300, 200, 100]))\n",
    "contract_minutes = dict(zip(providers, [200, 250, 150]))\n",
    "contract_call_cost = dict(zip(providers, [1, 2, 3]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can pay extra for some \"free\" minutes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "bundles = ['MTN 1', 'MTN 2', 'Vodacom']\n",
    "bundle_cost = dict(zip(bundles, [20, 30, 50]))\n",
    "bundle_minutes = dict(zip(bundles, [25, 40, 30]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Define the variables used - these will all be determined by the solver. First, binary variables to decide which providers and bundles to choose."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "contract_chosen = pulp.LpVariable.dicts('contract_chosen', providers, cat='Binary')\n",
    "bundle_chosen = pulp.LpVariable.dicts('bundle_chosen', bundles, cat='Binary')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then continuous variables to figure out some internal numbers - we'll keep track of how many minutes we have to pay for and how many minutes we'll use from the bundles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "minutes_paid_for = pulp.LpVariable.dicts('minutes_paid_for', providers, lowBound=0)\n",
    "minutes_from_bundles = pulp.LpVariable.dicts('minutes_from_bundles', providers, lowBound=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "minutes_after_free = {provider: max(minutes_used - contract_minutes[provider], 0) for provider in providers}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Objective function\n",
    "-----------------\n",
    "\n",
    "Our objective is to minimize total cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "p += (sum(contract_chosen[provider]*contract_cost[provider] for provider in providers) +\n",
    "      sum(bundle_chosen[bundle]*bundle_cost[bundle] for bundle in bundles) +\n",
    "      sum(minutes_paid_for[provider]*contract_call_cost[provider] for provider in providers))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Constraints\n",
    "-----------\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Must choose exactly one provider"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "p += sum(contract_chosen[provider] for provider in providers) == 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This equality constraint can be seen as a \"calculation\", we're figuring out how many minutes are supplied by the bundles we've chosen. Note that I've used a naming convention here to find out which bundle belongs to which provider."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for provider in providers:\n",
    "    p += minutes_from_bundles[provider] == sum(bundle_chosen[bundle]*bundle_minutes[bundle] \n",
    "                                               for bundle in bundles \n",
    "                                               if bundle.startswith(provider))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This constraint will figure out how many minutes need to be payed for: note that if the RHS is negative, the minutes paid for will be pushed to zero by the optimisation. The final term is a \"Big M\" constraint relaxation, effectively switching off this constraint for providers which have not been chosen. This can be seen as a logic statement \"If provider x is chosen, we must pay for these minutes, else the constraint is so low that only the zero lower bound holds\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for provider in providers:\n",
    "    p += minutes_paid_for[provider] >= (minutes_after_free[provider] - \n",
    "                                        minutes_from_bundles[provider] -\n",
    "                                        (1-contract_chosen[provider])*minutes_used)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p.solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Provider: Vodacom\n",
      "Bundle: Vodacom\n"
     ]
    }
   ],
   "source": [
    "for provider in providers:\n",
    "    if contract_chosen[provider].value():\n",
    "        print('Provider:', provider)\n",
    "for bundle in bundles:\n",
    "    if bundle_chosen[bundle].value():\n",
    "        print('Bundle:', bundle)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "288.0"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cost = p.objective.value()\n",
    "cost"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}