{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "## Disclaimer\n", "This notebook is only working under the versions:\n", "\n", "- JuMP 0.19 (unreleased, but currently in master)\n", "\n", "- MathOptInterface 0.4.1\n", "\n", "- GLPK 0.6.0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Description**: Shows how to solve a network revenue management problem using JuMP.\n", "\n", "**Author**: Iain Dunning\n", "\n", "**License**: \"Creative
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Airline Network Revenue Management\n", "\n", "\n", "\n", "In the airline network revenue management problem we are trying to decide how many tickets for each origin-destination (O-D) pair to sell at each price level. The goal is to maximize revenue, and we cannot sell more tickets than there is demand for, or space on the planes for.\n", "\n", "## Three Flight Problem\n", "\n", "We'll start with a toy problem that has three origin-destination pairs, with two price classes for each pair. The three origin-destination pairs are BOS-MDW, MDW-SFO, or BOS-SFO via MDW. BOS stands for Boston, MDW is Chicago-Midway, and SFO is San Francisco. Each O-D pair has a \"regular\" and \"discount\" fare class. The data we will use is summarized as follows:\n", "\n", "```\n", "PLANE CAPACITY: 166\n", "\n", "BOS-MDW\n", " Regular Discount\n", "Price: 428 190\n", "Demand: 80 120\n", "\n", "BOS-SFO\n", " Regular Discount\n", "Price: 642 224\n", "Demand: 75 100\n", "\n", "MDW-SFO\n", " Regular Discount\n", "Price: 512 190\n", "Demand: 60 110\n", "```" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "3-element Array{Any,1}:\n", " \"C:\\\\Users\\\\joaquimgarcia\\\\AppData\\\\Local\\\\Julia-0.6.0\\\\local\\\\share\\\\julia\\\\site\\\\v0.6\"\n", " \"C:\\\\Users\\\\joaquimgarcia\\\\AppData\\\\Local\\\\Julia-0.6.0\\\\share\\\\julia\\\\site\\\\v0.6\" \n", " \"D:\\\\MOI\" " ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "push!(Base.LOAD_PATH,\"D:\\\\MOI\")" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "MathOptInterface.Utilities" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Load JuMP\n", "using JuMP\n", "using MathOptInterface\n", "# Load solver package\n", "using GLPK\n", "# shortcuts\n", "const MOI = MathOptInterface\n", "const MOIU = MathOptInterface.Utilities" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Model\n", "Now we need to create a `Model`. A `Model` is an object that has associated variables and constraints. We can also pick and customize different solvers to use with the model. In this case we'll assume you a LP solver installed - JuMP will detect it and use it automatically." ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "A JuMP Model" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "nrm = Model(optimizer = GLPK.GLPKOptimizerLP())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can see that JuMP displays the model in a human-readable form.\n", "\n", "### Variables\n", "Now we can create our variables, in the optimization sense. Variables have a name, bounds, and type. For this problem, we need six continuous variables, each with a lower and upper bound on their value.\n", "\n", "Here we will spell out each variable one-by-one - rest assured that later we will do something smarter that will scale to millions of variables!" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "A JuMP Model" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variables(nrm, begin \n", " 0 <= BOStoMDW_R <= 80\n", " 0 <= BOStoMDW_D <= 120\n", " 0 <= BOStoSFO_R <= 75\n", " 0 <= BOStoSFO_D <= 100\n", " 0 <= MDWtoSFO_R <= 60\n", " 0 <= MDWtoSFO_D <= 110\n", "end)\n", "nrm" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Great, now we are getting somewhere!\n", "\n", "### Objective\n", "The objective is to maximize the revenue. We set the objective with `@objective`, which takes three arguments: the model, the sense (`Max` or `Min`), and the expression." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "A JuMP Model" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@objective(nrm, Max, 428*BOStoMDW_R + 190*BOStoMDW_D +\n", " 642*BOStoSFO_R + 224*BOStoSFO_D +\n", " 512*MDWtoSFO_R + 190*MDWtoSFO_D)\n", "nrm" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Constraints\n", "We have only two constraints, one per physical flight: that the number of people on each flight is less than the capacity of the planes. \n", "\n", "We add constraints with `@constraint`, which takes two arguments: the model, and an expression with an inequality in it: `<=`, `==`, `>=`.\n", "\n", "(note that there are other forms of `@constraint` that can be useful sometimes - see the manual or other examples for details)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "A JuMP Model" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@constraint(nrm, BOStoMDW_R + BOStoMDW_D + \n", " BOStoSFO_R + BOStoSFO_D <= 166)\n", "@constraint(nrm, MDWtoSFO_R + MDWtoSFO_D + \n", " BOStoSFO_R + BOStoSFO_D <= 166)\n", "nrm" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Our model is complete!\n", "\n", "## Solve\n", "The easy part! Lets check out the finished model before solving it. We didn't specify a solver before, but JuMP knows we have an LP solver installed, so it will use that." ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# solve problem\n", "JuMP.optimize(nrm)" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "JuMP.hasresultvalues(nrm) = true\n", "JuMP.terminationstatus(nrm) == MOI.Success = true\n", "JuMP.primalstatus(nrm) == MOI.FeasiblePoint = true\n" ] }, { "data": { "text/plain": [ "true" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@show JuMP.hasresultvalues(nrm)\n", "@show JuMP.terminationstatus(nrm) == MOI.Success\n", "@show JuMP.primalstatus(nrm) == MOI.FeasiblePoint" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Inspect the solution\n", "We can use `getvalue()` to inspect the value of solutions" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "80.0" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "JuMP.resultvalue(BOStoMDW_R)" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "11.0" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "JuMP.resultvalue(BOStoMDW_D)" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "collapsed": false }, "outputs": [ { "ename": "LoadError", "evalue": "\u001b[91mUndefVarError: getobjectivevalue not defined\u001b[39m", "output_type": "error", "traceback": [ "\u001b[91mUndefVarError: getobjectivevalue not defined\u001b[39m", "" ] } ], "source": [ "JuMP.getobjectivevalue(nrm)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## General Model\n", "\n", "We'll now code our model in a more general way, to take any number of cities and flights. Hard-coding every variable would be painful and hard to update - it'd be better to *index* the variables, just like in mathematical notation. \n", "\n", "Consider a generalized version of our first problem, where there are flights in both directions and one extra airport YYZ - Toronto!\n", "\n", "Rather than hardcode data, we will generate some random data.\n", "\n", "*(If you don't understand all of this right away, thats OK - its not critical to understanding JuMP)*" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "demand[(:BOS, :YYZ, :REG)] = 90\n" ] }, { "data": { "text/plain": [ "90" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Set the random seed to ensure we always\n", "# get the same stream of 'random' numbers\n", "srand(1988) \n", "\n", "# Lets create a vector of symbols, one for each airport\n", "airports = [:BOS, :MDW, :SFO, :YYZ]\n", "num_airport = length(airports)\n", "\n", "# We'll also create a vector of fare classes\n", "classes = [:REG, :DIS]\n", "\n", "# All the demand and price data for each triple of\n", "# (origin, destination, class) will be stored in\n", "# 'dictionaries', also known as 'maps'.\n", "demand = Dict()\n", "prices = Dict()\n", "\n", "# Generate a demand and price for each pair of airports\n", "# To keep the code simple we will generate info for\n", "# nonsense flights like BOS-BOS and SFO-SFO, but they\n", "# won't appear in our final model.\n", "for origin in airports, dest in airports\n", " # Generate demand:\n", " # - Regular demand is Uniform(50,90)\n", " # - Discount demand is Uniform(100,130)\n", " demand[(origin,dest,:REG)] = rand(50:90) \n", " demand[(origin,dest,:DIS)] = rand(100:130)\n", " # Generate prices:\n", " # - Regular price is Uniform(400,700)\n", " # - Discount price is Uniform(150,300)\n", " prices[(origin,dest,:REG)] = rand(400:700)\n", " prices[(origin,dest,:DIS)] = rand(150:300)\n", "end\n", "\n", "# Finally set all places to have the same capacity\n", "plane_cap = rand(150:200)\n", "\n", "# Lets look at a sample demand at random\n", "@show demand[(:BOS,:YYZ,:REG)]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we have the data, we can build the model." ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "3-dimensional JuMPArray{JuMP.VariableRef,3,...} with index sets:\n", " Dimension 1, Symbol[:BOS, :MDW, :SFO, :YYZ]\n", " Dimension 2, Symbol[:BOS, :MDW, :SFO, :YYZ]\n", " Dimension 3, Symbol[:REG, :DIS]\n", "And data, a 4×4×2 Array{JuMP.VariableRef,3}:\n", "[:, :, :REG] =\n", " x[BOS,BOS,REG] x[BOS,MDW,REG] x[BOS,SFO,REG] x[BOS,YYZ,REG]\n", " x[MDW,BOS,REG] x[MDW,MDW,REG] x[MDW,SFO,REG] x[MDW,YYZ,REG]\n", " x[SFO,BOS,REG] x[SFO,MDW,REG] x[SFO,SFO,REG] x[SFO,YYZ,REG]\n", " x[YYZ,BOS,REG] x[YYZ,MDW,REG] x[YYZ,SFO,REG] x[YYZ,YYZ,REG]\n", "\n", "[:, :, :DIS] =\n", " x[BOS,BOS,DIS] x[BOS,MDW,DIS] x[BOS,SFO,DIS] x[BOS,YYZ,DIS]\n", " x[MDW,BOS,DIS] x[MDW,MDW,DIS] x[MDW,SFO,DIS] x[MDW,YYZ,DIS]\n", " x[SFO,BOS,DIS] x[SFO,MDW,DIS] x[SFO,SFO,DIS] x[SFO,YYZ,DIS]\n", " x[YYZ,BOS,DIS] x[YYZ,MDW,DIS] x[YYZ,SFO,DIS] x[YYZ,YYZ,DIS]" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "nrm2 = Model(optimizer = GLPK.GLPKOptimizerLP())\n", "# Create a variable indexed by 3 things:\n", "# * Origin\n", "# * Destination\n", "# * Class\n", "# And set the upper bound for each variable differently.\n", "# The origins and destinations should be indexed across\n", "# the vector of airports, and the class should be indexed\n", "# across the vector of classes.\n", "# We'll draw the upper bounds from the demand dictionary.\n", "@variable(nrm2, 0 <= x[o=airports,\n", " d=airports,\n", " c=classes] <= demand[(o,d,c)])\n", "# Note that we don't have to split it up across multiple lines,\n", "# its personal preference!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "JuMP displays the variable in a compact form - note that the upper bound is\n", "blank because the upper bound is different for each variable." ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# The objective is just like before, except now we can use\n", "# the sum() functionality provided by JuMP to sum over all\n", "# combinations of origin/destination/class, and provide a\n", "# filter to exclude all cases where\n", "# the origin is equal to the destination\n", "@objective(nrm2, Max, sum(prices[(o,d,c)]*x[o,d,c] for \n", " o in airports, d in airports, c in classes if o != d))" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Adding constraint for hub (MDW) to BOS\n", "Adding constraint for hub (MDW) to SFO\n", "Adding constraint for hub (MDW) to YYZ\n" ] }, { "data": { "text/plain": [ "A JuMP Model" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Next we'll add constraints on flights from the hub\n", "# to any of the non-hub airports.\n", "for d in airports\n", " if d == :MDW\n", " continue\n", " end\n", " println(\"Adding constraint for hub (MDW) to $d\")\n", " @constraint(nrm2, \n", " sum(x[o,d,c] for o in airports, c in classes if o!=d) <= plane_cap)\n", "end\n", "nrm2" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Adding constraint for BOS to hub (MDW)\n", "Adding constraint for SFO to hub (MDW)\n", "Adding constraint for YYZ to hub (MDW)\n" ] }, { "data": { "text/plain": [ "A JuMP Model" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Now flights into the hub\n", "for o in airports\n", " if o == :MDW\n", " continue\n", " end\n", " println(\"Adding constraint for $o to hub (MDW)\")\n", " @constraint(nrm2, \n", " sum(x[o,d,c] for d in airports, c in classes if o!=d) <= plane_cap)\n", "end\n", "nrm2" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# solve problem\n", "JuMP.optimize(nrm2)" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "3-dimensional JuMPArray{Float64,3,...} with index sets:\n", " Dimension 1, Symbol[:BOS, :MDW, :SFO, :YYZ]\n", " Dimension 2, Symbol[:BOS, :MDW, :SFO, :YYZ]\n", " Dimension 3, Symbol[:REG, :DIS]\n", "And data, a 4×4×2 Array{Float64,3}:\n", "[:, :, :REG] =\n", " 0.0 55.0 46.0 81.0\n", " 86.0 0.0 75.0 63.0\n", " 54.0 90.0 0.0 38.0\n", " 0.0 62.0 61.0 0.0\n", "\n", "[:, :, :DIS] =\n", " 0.0 0.0 0.0 0.0\n", " 42.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0\n", " 0.0 59.0 0.0 0.0" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "JuMP.resultvalue.(x)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "metadata": { "anaconda-cloud": {}, "kernelspec": { "display_name": "Julia 0.6.0", "language": "julia", "name": "julia-0.6" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "0.6.0" } }, "nbformat": 4, "nbformat_minor": 0 }