{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Supplying toilet papers to Walmart stores\n",
    "\n",
    "Suppose you are the distribution manager overseeing all the Walmart grocery stores in California. There are $m$ factories producing toilet papers in the region, which need to be supplied to $n$ Walmart stores in the state.\n",
    "\n",
    "The geographic locations (latitudes and longitudes) of the factories and stores: $x_{i}^{\\text{factory}}\\in\\mathbb{R}^{2}$ and $x_{j}^{\\text{store}}\\in\\mathbb{R}^{2}$ are known, for all $i=1,...,m$, and $j=1,...,n$. At present, Walmart uses its own trucks for this delivery which incur $C_{ij}$ dollars (for fuel cost, travel time etc.) to transport **per unit mass of toilet paper** from the $i$th factory to the $j$th store. A reasonable model is that $C_{ij}$ equals to the squared Euclidean distance:\n",
    "\n",
    "$$C_{ij} = \\|x_{i}^{\\text{factory}} - x_{j}^{\\text{store}}\\|_{2}^{2}, \\quad\\forall\\;(i,j)\\in\\{1,...,m\\}\\times\\{1,...,n\\}.$$\n",
    "\n",
    "This defines a cost matrix $C \\equiv [C_{ij}]$ of size $m\\times n$. The $i$th factory has a fixed (normalized) production capacity $\\alpha_{i}>0$. The $j$th store has a fixed (normalized) storage capacity $\\beta_{j}>0$. Here \"normalized\" means that $\\sum_{i}\\alpha_{i}=\\sum_{j}\\beta_{j}=1$. Toilet papers cannot be stored elsewhere, i.e., all the toilet papers produced must be supplied to the stores."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (a) [12 + 2 + 2 + (1 + 3) = 20 points] Primal problem\n",
    "\n",
    "As the distribution manager, your job is to decide **what is the cheapest way to transport the toilet papers from the factories to the stores**. Suppose you decide that $P_{ij}$ amount of toilet paper mass (say in pound or lb) should be transported from the $i$th factory to the $j$th store. Obviously, $P_{ij} \\geq 0$ for all $(i,j)\\in\\{1,...,m\\}\\times\\{1,...,n\\}$. \n",
    "\n",
    "(i) **Taking the matrix $P \\equiv [P_{ij}]$ of size $m\\times n$ as the decision variable**, clearly set up the optimization problem to be solved. The input parameters for this optimization problem should be the $m\\times n$ matrix $C$, the $m\\times 1$ vector $\\alpha$, and the $n\\times 1$ vector $\\beta$.\n",
    "\n",
    "**Hint:** the Frobenius inner product $\\langle C, P\\rangle = \\text{trace}(C^{\\top}P)$. Also, you may find it helpful to use the column vector of ones $\\mathbf{1}_{m}, \\mathbf{1}_{n}$.\n",
    "\n",
    "(ii) Argue **why** the optimization problem above is convex in $P$.\n",
    "\n",
    "(iii) What is the dimensionality of this problem, that is, it is a convex optimization problem in **how many variables with how many constraints**?\n",
    "\n",
    "(iii) **What type of convex optimization problem** is it? To support your answer, **explain the geometric interpretation of the objective and the constraints**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (b) [20 points] Numerical solution\n",
    "\n",
    "Fix $m=20, n=167$. Write a code in MATLAB/Python/Julia to load the input data from CANVAS Files section: HW problems and solutions: alpha.txt, beta.txt, x\\_stores.txt, x\\_factories.txt, and use cvx/cvxpy/Convex.jl in the same code to solve the optimization problem in part (a). **Report the numerically computed optimal value (minimized cost)** and **submit your code**. \n",
    "\n",
    "**Remark:** It is recommended (but not required) that in your code, you also check if your optimal solution obtained from using cvx/cvxpy/Convex.jl matches with linprog in MATLAB, or with scipy.optimize.linprog in Python."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (c) [(10 + 10 + 10) + ( 8 + 2 ) = 40 points] Duality\n",
    "\n",
    "(i) Starting from the convex optimization problem in matrix variable $P$ deduced in part (a), derive the Lagrangian $L$, the Lagrange dual function $g$, and the dual optimization problem.\n",
    "\n",
    "**Hint:** To handle the inequality constraint $P \\geq 0$ (elementwise), introduce a matricial Lagrange multiplier $\\Lambda$ of size $m\\times n$.\n",
    "\n",
    "(ii) Numerically solve the dual problem using cvx/cvxpy/Convex.jl **in the same code in part (b)**. So your submitted code should solve both the primal and dual problems separately. **Report the numerically computed optimal value of the dual problem, and explain what you observe**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## (d) [20 points] To contract or not\n",
    "\n",
    "A Silicon Valley startup **Brand New Truck Company (BNTC)** has approached you, the Walmart distribution manager in California, claiming that they can lower the cost of transport for you if you give them the contract to transport the toilet papers from the $m$ factories to the $n$ Walmart stores. **Their business model is that they actually do not charge for the transportation process, but only charge variable per unit mass loading cost $\\eta_{1}\\in\\mathbb{R}^{m}$, and variable per unit mass unloading cost $\\eta_{2}\\in\\mathbb{R}^{n}$**. They also guarantee you that \n",
    "\n",
    "$$\\left(\\eta_{1}\\right)_{i} + \\left(\\eta_{2}\\right)_{j} \\leq C_{ij} \\quad\\forall\\;(i,j)\\in\\{1,...,m\\}\\times\\{1,...,n\\},$$\n",
    "\n",
    "and hence, BNTC argues that Walmart cannot loose money by awarding them the contract for toilet paper transport. \n",
    "\n",
    "To maximize revenue, BNTC determines $(\\eta_{1},\\eta_{2})$ by solving\n",
    "\n",
    "\\begin{align*}\n",
    "\\underset{(\\eta_{1},\\eta_{2})}{\\text{maximize}}\\quad &\\eta_{1}^{\\top}\\alpha + \\eta_{2}^{\\top}\\beta\\\\\n",
    "\\qquad\\qquad\\text{s.t.}\\quad &\\eta_{1}\\mathbf{1}_{n}^{\\top} + \\mathbf{1}_{m}\\eta_{2}^{\\top} \\leq C \\quad\\text{(elementwise).}\n",
    "\\end{align*}\n",
    "\n",
    "Is contracting the transport to BNTC profitable for Walmart? **Use the duality results in part (c) to mathematically explain your answer**."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}