{
"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
}