{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Foundations of Computational Economics #18\n", "\n", "by Fedor Iskhakov, ANU\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "## Linear programming and optimal transport models\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "\n", "\n", "[https://youtu.be/E1T1AWcMDqE](https://youtu.be/E1T1AWcMDqE)\n", "\n", "Description: Linear programming and optimal transport problems." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Linear programming\n", "\n", "- Finding maximum/minimum of linear function subject to a set of linear inequality constraints \n", "- Classical problem in operations research and economics \n", "\n", "\n", "**Optimal transport problem**\n", "\n", "Minimum cost of transporting a set of goods from $ m $ origins to $ n $ destinations,\n", "where cost of transporting from origin $ i $ to destination $ j $ is given by $ c_{ij} $" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Optimal transport in economics\n", "\n", "- Matching and trade\n", " - matching distribution of workers to distribution of firms\n", " - relation to gravity equation in trade \n", "- Demand estimation and pricing\n", " - relation to discrete choice and nested discrete choice\n", " - quasi-linear hedonic models \n", "- Quantile methods in econometrics " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Graphic representation\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Formal problem statement\n", "\n", "$$\n", "\\min \\sum_{i=1}^{m}\\sum_{j=1}^{n} c_{ij} x_{ij}, \\text{ subject to}\n", "$$\n", "\n", "$$\n", "\\sum_{i=1}^{m} x_{ij} = b_j, j \\in \\{1,\\dots,n\\},\n", "$$\n", "\n", "$$\n", "\\sum_{j=1}^{n} x_{ij} = a_i, i \\in \\{1,\\dots,m\\},\n", "$$\n", "\n", "$$\n", "x_{ij} \\ge 0 \\text{ for all } i,j\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### General linear programming problem\n", "\n", "Linear programming = optimizing linear function on convex polyhedron\n", "\n", "$$\n", "\\max(c \\cdot x) \\text{ subject to } Ax \\le b\n", "$$\n", "\n", "Note that $ Ax \\le b $ includes as special cases\n", "\n", "- $ x_j\\ge 0 $ for some $ j \\in J $, trivially \n", "- $ x_j = D_j $ for some $ j \\in J $ using two inequalities " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Convex polyhedron in 2d (convex polygon)\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Convex polyhedron and objective function\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Convex polyhedron in 3d\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Example: Optimal production portfolio\n", "\n", "Let $ x $ and $ y $ denote production of goods A and B by some firm. The production technology is restricted to have\n", "\n", "$$\n", "\\begin{cases}\n", "y - x &\\le& 4, \\\\\n", "2x - y &\\le&8,\n", "\\end{cases}\n", "$$\n", "\n", "And the resource constraint is given by $ x + 2y \\le 14 $\n", "\n", "Let profits be given by $ \\pi(x,y) = y + 2x $" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Adding the natural non-negativity constraints, in matrix notation we have\n", "\n", "$$\n", "\\max(c^{T}x) \\text{ subject to } Ax \\le b\n", "$$\n", "\n", "$$\n", "c=\n", "\\begin{pmatrix}\n", "2 & 1\n", "\\end{pmatrix},\\;\\;\n", "A=\n", "\\begin{pmatrix}\n", "-1 & 1 \\\\\n", "2 & -1 \\\\\n", "1 & 2 \\\\\n", "-1 & 0 \\\\\n", "0 & -1 \\\\\n", "\\end{pmatrix},\\;\\;\n", "b=\n", "\\begin{pmatrix}\n", "4\\\\\n", "8\\\\\n", "14\\\\\n", "0\\\\\n", "0\n", "\\end{pmatrix}\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Convex polyhedron and objective function\n", "\n", "" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "hide-output": false, "slideshow": { "slide_type": "slide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "iteration 0, current solution [0. 0.]\n", "iteration 1, current solution [4. 0.]\n", "iteration 2, current solution [6. 4.]\n", "iteration 3, current solution [6. 4.]\n", "iteration 3, current solution [6. 4.]\n" ] }, { "data": { "text/plain": [ " con: array([], dtype=float64)\n", " fun: -16.0\n", " message: 'Optimization terminated successfully.'\n", " nit: 3\n", " slack: array([6., 0., 0., 6., 4.])\n", " status: 0\n", " success: True\n", " x: array([6., 4.])" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "import numpy as np\n", "from scipy.optimize import linprog\n", "\n", "c = np.array([-2,-1])\n", "A = np.array([[-1,1],[2,-1],[1,2],[-1,0],[0,-1]])\n", "b = np.array([4,8,14,0,0])\n", "\n", "def outf(arg):\n", " print('iteration %d, current solution %s'%(arg.nit,arg.x))\n", "\n", "linprog(c=c,A_ub=A,b_ub=b,method='simplex',callback=outf)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Further learning resources\n", "\n", "- “Optimal Transport Methods in Economics” by Alfred Galichon, 2016\n", " [https://www.jstor.org/stable/j.ctt1q1xs9h](https://www.jstor.org/stable/j.ctt1q1xs9h) \n", "- Alfred Galichon’s plenary talk at the 2020 Econometric Society World Congress\n", " [https://youtu.be/XYIRkSIExik?t=2256](https://youtu.be/XYIRkSIExik?t=2256) " ] } ], "metadata": { "celltoolbar": "Slideshow", "date": 1612589585.0195599, "download_nb": false, "filename": "18_linear_prog.rst", "filename_with_path": "18_linear_prog", "kernelspec": { "display_name": "Python", "language": "python3", "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.7.6" }, "title": "Foundations of Computational Economics #18" }, "nbformat": 4, "nbformat_minor": 4 }