{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["## Resources\n", "\n", "### Maths\n", "\n", "* [Linear Programming](https://brilliant.org/wiki/linear-programming/)\n", "* [Optimization | Brilliant Math & Science Wiki](https://brilliant.org/wiki/optimization-problems/)\n", "* [System of Inequalities | Brilliant Math & Science Wiki](https://brilliant.org/wiki/systems-of-inequalities/)\n", "\n", "### Python\n", "\n", "* [Hands-On Linear Programming: Optimization With Python](https://realpython.com/linear-programming-python/#linear-programming-examples)\n", "* [SciPy](https://scipy.org/)\n", "* [PuLP](https://coin-or.github.io/pulp/)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Install the packages\n", "\n", "`python -m pip install -U \"scipy==1.4.*\" \"pulp==2.1\"`"]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["Solver <class 'pulp.apis.coin_api.PULP_CBC_CMD'> available\n", "Solver <class 'pulp.apis.cplex_api.CPLEX_DLL'> unavailable\n", "Solver <class 'pulp.apis.cplex_api.CPLEX_CMD'> unavailable\n", "Solver <class 'pulp.apis.cplex_api.CPLEX_PY'> unavailable\n", "Solver <class 'pulp.apis.coin_api.COIN_CMD'> unavailable\n", "Solver <class 'pulp.apis.coin_api.COINMP_DLL'> unavailable\n", "Solver <class 'pulp.apis.glpk_api.GLPK_CMD'> unavailable\n", "Solver <class 'pulp.apis.xpress_api.XPRESS'> unavailable\n", "Solver <class 'pulp.apis.gurobi_api.GUROBI'> unavailable\n", "Solver <class 'pulp.apis.gurobi_api.GUROBI_CMD'> unavailable\n", "Solver <class 'pulp.apis.glpk_api.PYGLPK'> unavailable\n", "Solver <class 'pulp.apis.coin_api.YAPOSIB'> unavailable\n", "Solver <class 'pulp.apis.choco_api.PULP_CHOCO_CMD'> available\n", "Solver <class 'pulp.apis.mipcl_api.MIPCL_CMD'> unavailable\n", "Solver <class 'pulp.apis.mosek_api.MOSEK'> unavailable\n", "\t Testing zero subtraction\n", ".\t Testing inconsistant lp solution\n", ".\t Testing continuous LP solution\n", ".\t Testing maximize continuous LP solution\n", ".\t Testing unbounded continuous LP solution\n", ".\t Testing Long Names\n", ".\t Testing repeated Names\n", ".\t Testing zero constraint\n", ".\t Testing zero objective\n", ".\t Testing LpVariable (not LpAffineExpression) objective\n", ".\t Testing Long lines in LP\n", ".\t Testing LpAffineExpression divide\n", ".\t Testing MIP solution\n", ".\t Testing MIP solution with floats in objective\n", ".\t Testing MIP relaxation\n", ".\t Testing feasibility problem (no objective)\n", ".\t Testing an infeasible problem\n", ".\t Testing an integer infeasible problem\n", ".\t Testing column based modelling\n", "..\t Testing dual variables and slacks reporting\n", "...\t Testing fractional constraints\n", ".\t Testing elastic constraints (no change)\n", ".\t Testing elastic constraints (freebound)\n", ".\t Testing elastic constraints (penalty unchanged)\n", ".\t Testing elastic constraints (penalty unbounded)\n", ".\t Testing zero subtraction\n", ".\t Testing inconsistant lp solution\n", ".\t Testing continuous LP solution\n", ".\t Testing maximize continuous LP solution\n", ".\t Testing unbounded continuous LP solution\n", ".\t Testing Long Names\n", ".\t Testing repeated Names\n", ".\t Testing zero constraint\n", ".\t Testing zero objective\n", ".\t Testing LpVariable (not LpAffineExpression) objective\n", "..\t Testing LpAffineExpression divide\n", ".\t Testing MIP solution\n", ".\t Testing MIP solution with floats in objective\n", ".\t Testing MIP relaxation\n", ".\t Testing feasibility problem (no objective)\n", ".\t Testing an infeasible problem\n", ".\t Testing an integer infeasible problem\n", ".\t Testing column based modelling\n", ".....\t Testing fractional constraints\n", ".\t Testing elastic constraints (no change)\n", ".\t Testing elastic constraints (freebound)\n", ".\t Testing elastic constraints (penalty unchanged)\n", ".\t Testing elastic constraints (penalty unbounded)\n", "..................{'a': 53.0, 'b': 45.3, 'c': 459.2}\n", "..........................\n", "----------------------------------------------------------------------\n", "Ran 99 tests in 24.032s\n", "\n", "OK\n"]}], "source": ["!pulptest"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## To define and solve optimization problems with SciPy"]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": ["from scipy.optimize import linprog"]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": ["from IPython.display import Image"]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [{"data": {"text/html": ["<img src=\"https://bit.ly/3a6qEkq\"/>"], "text/plain": ["<IPython.core.display.Image object>"]}, "metadata": {}, "output_type": "display_data"}, {"data": {"text/html": ["<img src=\"https://bit.ly/3krYDsb\"/>"], "text/plain": ["<IPython.core.display.Image object>"]}, "metadata": {}, "output_type": "display_data"}], "source": ["for url in (\"https://bit.ly/3a6qEkq\", \"https://bit.ly/3krYDsb\"):\n", "    display(Image(url=url))"]}, {"cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": ["obj = (\n", "    -1,\n", "    -2,\n", ")\n", "lhs_ineq = (\n", "    (2, 1,),\n", "    (-4, 5,),\n", "    (1, -2),\n", ")\n", "rhs_ineq = (\n", "    20,\n", "    10,\n", "    2,\n", ")\n", "lhs_eq = ((-1, 5,),)\n", "rhs_eq = (15,)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["> The next step is to define the bounds for each variable in the same order as the coefficients. In this case, they\u2019re both between zero and positive infinity\n", "\n", "bounds of x\n", "\n", "bounds of y\n", "\n", "They happen to be the same so create once and multiply by 2."]}, {"cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [{"data": {"text/plain": ["((0, inf), (0, inf))"]}, "execution_count": 9, "metadata": {}, "output_type": "execute_result"}], "source": ["(bnd := ((0, float(\"inf\"),),) * 2)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Optimize and Solve"]}, {"cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [{"data": {"text/plain": ["     con: array([0.])\n", "     fun: -16.818181818181817\n", " message: 'Optimization terminated successfully.'\n", "     nit: 3\n", "   slack: array([ 0.        , 18.18181818,  3.36363636])\n", "  status: 0\n", " success: True\n", "       x: array([7.72727273, 4.54545455])"]}, "execution_count": 16, "metadata": {}, "output_type": "execute_result"}], "source": ["(opt := linprog(\n", "    c=obj,\n", "    A_ub=lhs_ineq,\n", "    b_ub=rhs_ineq,\n", "    A_eq=lhs_eq,\n", "    b_eq=rhs_eq,\n", "    bounds=bnd,\n", "    method=\"revised simplex\",\n", "))"]}, {"cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [{"data": {"text/plain": ["-16.818181818181817"]}, "execution_count": 18, "metadata": {}, "output_type": "execute_result"}], "source": ["opt.fun"]}, {"cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [{"data": {"text/plain": ["array([7.72727273, 4.54545455])"]}, "execution_count": 19, "metadata": {}, "output_type": "execute_result"}], "source": ["opt.x"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Side bar: YouTube video on how to so"]}], "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.8.5"}, "nikola": {"category": "", "date": "2020-08-08 14:58:40 UTC", "description": "Note from Hands-On Linear Programming: Optimization With Python tutorial", "link": "", "slug": "linear-programming-with-python", "tags": "maths, python, science, scipy, pulp", "title": "Linear Programming with Python", "type": "text"}, "toc": {"base_numbering": 1, "nav_menu": {}, "number_sections": true, "sideBar": true, "skip_h1_title": false, "title_cell": "Table of Contents", "title_sidebar": "Contents", "toc_cell": false, "toc_position": {}, "toc_section_display": true, "toc_window_display": true}}, "nbformat": 4, "nbformat_minor": 2}