{ "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:** This notebook describes how to make an optimization model more efficient by exploiting sparsity.\n", "\n", "**Author:** [Shuvomoy Das Gupta](http://scg.utoronto.ca/~shuvomoy.dasgupta/)\n", "\n", "**License:** \"Creative
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.\n", "\n", "# Using Julia+JuMP for optimization - exploiting sparsity \n", "--------------------------\n", "
\n", "\n", "## Introduction\n", "\n", "**What is a sparse data structure?**\n", "\n", "A sparse data structure is one that has a lot of zeros in it. If a matrix has many more zeros than nonzeros, then it is a sparse matrix. \n", "\n", "** Why do we need to exploit sparsity?** \n", "\n", "- Sparsity in the input data increases with the dimension.\n", "\n", "- Exploiting sparsity \n", " * keeps the data size small\n", " * saves memory\n", " * reduces the running time \n", " * improves the efficiency of the model\n", "\n", "\n", "** How to exploit sparsity in Julia?**\n", "\n", "- Define `struct` and create a `dictionary` or an `array` of it." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## A test example: Transportation Problem\n", "Consider a transportation problem which is going to be our test example:\n", "\n", "- ** Problem setup:** Some products have to transported from origin cities to destination cities \n", "\n", "- **Objective:** \n", " * Minimize the total cost of shipment over all **relevant** routes\n", " \n", "- **Decision Variables** \n", " * Find the optimum amount of every product to be shipped from one city to another\n", "\n", "- **Constraints**\n", " * How much of a product a city can supply to other cities is fixed. \n", " * The amount of any product demanded by a city is also fixed. \n", " * The total amount of products shipped between every pair of different cities can not exceed a given limit. \n", "\n", "Suppose there are ten cities and three products in our problem. " ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "3-element Array{Symbol,1}:\n", " :smartphone\n", " :tablet \n", " :laptop " ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cities = \n", "[\n", ":BANGKOK; :LONDON; :PARIS; :SINGAPORE; :NEWYORK; :ISTANBUL; :DUBAI; :KUALALUMPUR; :HONGKONG; :BARCELONA \n", "]\n", "\n", "products = \n", "[\n", ":smartphone; :tablet; :laptop\n", "]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Defining `struct`s\n", "If we do not exploit sparsity, then number of ways we can ship the products from one city to other will be $3 \\times (^{10}P_2+10)=300$. \n", "\n", "Clearly many of them will be redundant, because of reasons like\n", "- a product might not be needed by a city\n", "- a product might not be produced by a city\n", "etc.\n", "\n", "We just need to consider *relevant route*s, where a product can be shipped from one production city to the other demand city. So a *relevant route* can be defined by 3 features:\n", "\n", "- a product\n", "- a city that produces that product\n", "- a city that demands that product\n", "\n", "So, we define an `struct` `Route` as follows:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": true }, "outputs": [], "source": [ "struct Route\n", " p::Symbol # p stands for product\n", " o::Symbol # o stands for origin\n", " d::Symbol # d stands for destination\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here the datatype `Symbol` is a special type of immutable string. Then we create an array of only relevant routes." ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "4-element Array{Route,1}:\n", " Route(:smartphone, :BANGKOK, :SINGAPORE)\n", " Route(:smartphone, :BANGKOK, :NEWYORK) \n", " Route(:smartphone, :BANGKOK, :ISTANBUL) \n", " Route(:smartphone, :BANGKOK, :DUBAI) " ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "routesExample = \n", "[\n", " Route(:smartphone,:BANGKOK,:SINGAPORE);\n", " Route(:smartphone,:BANGKOK,:NEWYORK);\n", " Route(:smartphone,:BANGKOK,:ISTANBUL);\n", " Route(:smartphone,:BANGKOK,:DUBAI);\n", "] " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If we want to access $i$th element of the array by typing in `routes[i]`. When we want to access the product name associated with the $it$h element of the array, we can do so by typing `routes[i].p`.\n" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "Route(:smartphone, :BANGKOK, :NEWYORK)" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "routesExample[2] # Will give the second route " ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ ":DUBAI" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "routesExample[4].d # Will give the demand city of the 4th route" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Creating new arrays efficiently from existing arrays\n", "\n", "Often we need to create new arrays, where the elements of them are extracted from some already existing array conditionally. \n", "\n", "Consider the immutable type `Supply`" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": true }, "outputs": [], "source": [ "struct Supply\n", " p::Symbol # p stands for product name\n", " o::Symbol # o stands for the origin city\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We want to create an array `suppliesExample`, that contains all relevant product-city pairs, where the particular product is produced in that city. Clearly we can construct this array by plucking each product and corresponding city producing it from `routesExample`. This is how we do it efficiently: \n", "\n", "- Create an empty array of type `Supply`\n", "- Add elements to this array by \n", "\n", " * selecting the product and origin from the elements of `routes` \n", " * *push*ing them one by one in `supplies`" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": true }, "outputs": [], "source": [ "suppliesExample = Supply[] # Creates a 0 element array of immutable type Supply\n", "for r in routesExample # For every element of the route route\n", " push!(suppliesExample, Supply(r.p, r.o)) # pick the product and origin city and push it in supplies\n", "end" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "4-element Array{Supply,1}:\n", " Supply(:smartphone, :BANGKOK)\n", " Supply(:smartphone, :BANGKOK)\n", " Supply(:smartphone, :BANGKOK)\n", " Supply(:smartphone, :BANGKOK)" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "suppliesExample" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Dictionary\n", "**What is a dictionary?**\n", "A dictionary is a data type which can be useful in exploiting sparsity.\n", "\n", "**Why is it needed?**\n", " Often we might be interested to index a variable by a composite data type, rather than a number. \n", " \n", "For example, for the transportation problem in consideration, it would be more convenient to index the decision variables in the routes that are present. Let\n", "\n", "$$\n", "\\begin{align}\n", "R=\\{(p,o,d) \\in P \\times C \\times C: \\text{product } p \\text{ has to be transported from city } o \\text{ to city } d\\}\n", "\\end{align}\n", "$$\n", "\n", "be the set of all the routes that are relevant for the problem. So, we can define our decision variables as below:\n", "\n", "$$\n", "\\begin{align}\n", "\\forall (p,o,d) \\in R \\left(x_{(p,o,d)}= \\text{the amount of a product } p \\text{ that is transported from city } o \\text{ city d} \\right)\n", "\\end{align}\n", "$$\n", "\n", "From a data structure point of view, $ \\left(x_{(p,o,d)}\\right)_{(p,o,d) \\in R}$ is a dictionary which\n", "\n", "- takes $(p,o,d) \\in R$ as its **key** and \n", "- has the **value** the optimum amount of the product $p$ to be shipped from city $o$ to city $d$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Efficiently Constructing Dictionary of `struct`s\n", "\n", "Suppose we want to create a dictionary called `costRoutes`. Every element of the dictionary `costRoutes` contains the value of shipping cost along a particular route belonging to the array `routesExample`. So, \n", "\n", "- the **key** to an element belonging to the dictionary is a specific route belonging to the array `routesExample`\n", "- the **value** is the cost for that shipment. \n", "\n", "Suppose the values of the costs are stored in an array named `costCofExample`. " ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "4-element Array{Float64,1}:\n", " 120.0\n", " 205.0\n", " 310.0\n", " 45.0" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "costCofExample = [120; 205; 310; 45.0]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We create the dictionary `costRoutes` similar to an array: \n", "\n", "- we create an empty dictionary, and then\n", "- use the command \n", "`setindex!(name_of_dictionary, value, key)` \n", "or \n", "`name_of_dictionary[key]=value`\n", "to add new elements in the dictionary one by one" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "Dict{Route,Float64} with 0 entries" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "costRoutesExample=Dict{Route, Float64}()# Create an empty dictionary \n", "# where the key is Route and the value is Float64" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "collapsed": true }, "outputs": [], "source": [ "for i in 1:length(routesExample)\n", " costRoutesExample[routesExample[i]]=costCofExample[i]\n", " # routesExample[i] is the key, and costCofExample[i] is the value\n", "end" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "Dict{Route,Float64} with 4 entries:\n", " Route(:smartphone, :BANGKOK, :NEWYORK) => 205.0\n", " Route(:smartphone, :BANGKOK, :DUBAI) => 45.0\n", " Route(:smartphone, :BANGKOK, :SINGAPORE) => 120.0\n", " Route(:smartphone, :BANGKOK, :ISTANBUL) => 310.0" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "costRoutesExample" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "After the dictionary is initialized, we can access the cost associated with some route `routes[i]` by typing in `costRoutes[routes[i]]`" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "45.0" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "costRoutesExample[routesExample[4]]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Or we can input the description of the route itself:" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "Route(:smartphone, :BANGKOK, :ISTANBUL)" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "routesExample[3]" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "310.0" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "costRoutesExample[Route(:smartphone,:BANGKOK,:ISTANBUL)]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Mathematical representation of the transportation problem\n", "\n", "\n", "The problem is a classic transportation problem. We will consider the sparse representation of the problem. Let\n", "\n", "$C=\\text{Set of all cities}$\n", "\n", "$P=\\text{Set of all products}$\n", "\n", "$R=\\{(p,o,d) \\in P \\times C \\times C: \\text{product } p \\text{ has to be transported from city } o \\text{ to city } d\\} $\n", "\n", "$\\forall (p,o,d) \\in R \\quad \\left(c_{(p,o,d)} = \\text{cost of transporting some product } p \\text{ from city } o \\text{ to city } d \\right)$\n", "\n", "$ \\forall p \\in P \\quad \\left(O_p = \\text{Set of all origin cities where a product } p \\text{ is produced}\\right) $\n", "\n", "$ \\forall p \\in P \\quad \\left(D_p = \\text{Set of all destination cities where a product } p \\text{\n", "has to be delivered}\\right) $\n", "\n", "$ \\forall p \\in P \\; \\forall o \\in O_p \\quad \\left(s_{(p,o)} = \\text{the total amount of the product } p \\text{ that can be supplied by city } o\\right) $\n", "\n", "$ \\forall p \\in P \\; \\forall d \\in D_p \\quad \\left(d_{(p,d)} = \\text{the total amount of the product } p \\text{ that is demanded by city } d\\right) $\n", "\n", "Total amount of shipped product between each pair of cities cannot exceed $\\gamma$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The decision variable for this problem is \n", "\n", "$$\n", "\\begin{align}\n", "\\forall (p,o,d) \\in R \\quad \\left(x_{(p,o,d)}= \\text{the amount of a product } p \\text{ that is trasported from city } o \\text{ city d} \\right)\n", "\\end{align}\n", "$$\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The optimization problem can be described as below:\n", "\n", "$$\n", "\\begin{align}\n", "&\\text{minimize} && \\sum_{(p,o,d) \\in R}{c_{(p,o,d)} x_{(p,o,d)}} \\\\\n", "&\\text{subject to} && \\\\\n", "& && \\forall p \\in P \\; \\forall o \\in O_p \\quad \\left(\\sum_{d \\in D_p} x_{(p,o,d)}=s_{(p,o)}\\right) \\\\\n", "& && \\text{ : The amount of any product a city can supply to other cities is fixed} \\\\\n", "& && \\forall p \\in P \\; \\forall d \\in D_p \\quad \\left(\\sum_{o \\in O_p}{x_{(p,o,d)}}=d_{(p,d)}\\right) \\\\\n", "& && \\text{ : The amount of any product demanded by a city is also fixed.} \\\\\n", "& && \\forall o \\in C \\; \\forall d \\in C \\setminus \\{o\\} \\quad \n", " \\left(\\sum_{(p,\\bar{o},\\bar{d}) \\in R \\; : \\; o=\\bar{o} \\wedge d=\\bar{d}}{x_{(p,\\bar{o},\\bar{d})}}\\leq \\gamma\\right) \\\\\n", "& && \\text{ :The total amount of products shipped between every pair of different cities can not exceed a given limit.}\n", "\\end{align}\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Mapping of the mathematical symbols to JuMP\n", "\n", "In the data file, the symbols in the model above are mapped as follows:\n", "\n", "| Mathematical Symbol | In the code | Comment |\n", "|---------------------- :|------------: |-----------:|\n", "| $C$ | `cities` | `cities` is an array of `Symbol`s |\n", "| $P$ | `products` | `products` is an array of `Symbol`s |\n", "| $R$ | `routes` | `routes` is an array of immutable type `Route` |\n", "| $(O_p)_{p \\in P}$ | `orig` | `orig` is a dictionary |\n", "| $(D_p)_{p \\in P}$ | `dest` | `dest` is a dictionary |\n", "| $((s_{(p,o)})_{o \\in O_p})_{p \\in P}$ | `suppliedAmount`| `suppliedAmount` is a dictionary |\n", "| $((d_{(p,d)})_{d \\in D_p})_{p \\in P}$ | `demandedAmount` | `demandedAmount` is a dictionary with key `Customer` and value `Float64` |\n", "| $(x_{(p,o,d)})_{(p,o,d) \\in R}$ | `trans` | `trans` is a dictionary and the variable in the problem |\n", "| $(c_{(p,o,d)})_{(p,o,d) \\in R}$ | `costRoutes` | `costRoutes` is a dictionary |\n", "| $\\gamma$ | `capacity` | It is of type `Float64` |\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Data file" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "collapsed": true }, "outputs": [], "source": [ "#\n", "cities = \n", "[\n", ":BANGKOK; :LONDON; :PARIS; :SINGAPORE; :NEWYORK; :ISTANBUL; :DUBAI; :KUALALUMPUR; :HONGKONG; :BARCELONA \n", "]\n", "\n", "products = \n", "[\n", ":smartphone; :tablet; :laptop\n", "]\n", "\n", "capacity = 700\n", "\n", "struct Route\n", " p::Symbol # p stands for product\n", " o::Symbol # o stands for origin\n", " d::Symbol # d stands for destination\n", "end\n", "\n", "routes = \n", "[\n", " Route(:smartphone,:BANGKOK,:SINGAPORE);\n", " Route(:smartphone,:BANGKOK,:NEWYORK);\n", " Route(:smartphone,:BANGKOK,:ISTANBUL);\n", " Route(:smartphone,:BANGKOK,:DUBAI);\n", " Route(:smartphone,:BANGKOK,:KUALALUMPUR);\n", " Route(:smartphone,:BANGKOK,:HONGKONG);\n", " Route(:smartphone,:BANGKOK,:BARCELONA);\n", " Route(:smartphone,:LONDON,:SINGAPORE);\n", " Route(:smartphone,:LONDON,:NEWYORK);\n", " Route(:smartphone,:LONDON,:ISTANBUL);\n", " Route(:smartphone,:LONDON,:DUBAI);\n", " Route(:smartphone,:LONDON,:KUALALUMPUR);\n", " Route(:smartphone,:LONDON,:HONGKONG);\n", " Route(:smartphone,:LONDON,:BARCELONA); \n", " Route(:smartphone,:PARIS,:SINGAPORE);\n", " Route(:smartphone,:PARIS,:NEWYORK);\n", " Route(:smartphone,:PARIS,:ISTANBUL);\n", " Route(:smartphone,:PARIS,:DUBAI);\n", " Route(:smartphone,:PARIS,:KUALALUMPUR);\n", " Route(:smartphone,:PARIS,:HONGKONG);\n", " Route(:smartphone,:PARIS,:BARCELONA); \n", "\n", " Route(:tablet,:BANGKOK,:SINGAPORE);\n", " Route(:tablet,:BANGKOK,:NEWYORK);\n", " Route(:tablet,:BANGKOK,:ISTANBUL);\n", " Route(:tablet,:BANGKOK,:DUBAI);\n", " Route(:tablet,:BANGKOK,:KUALALUMPUR);\n", " Route(:tablet,:BANGKOK,:HONGKONG);\n", " Route(:tablet,:BANGKOK,:BARCELONA); \n", "\n", " Route(:tablet,:LONDON,:SINGAPORE);\n", " Route(:tablet,:LONDON,:NEWYORK);\n", " Route(:tablet,:LONDON,:ISTANBUL);\n", " Route(:tablet,:LONDON,:DUBAI);\n", " Route(:tablet,:LONDON,:KUALALUMPUR);\n", " Route(:tablet,:LONDON,:HONGKONG);\n", " Route(:tablet,:LONDON,:BARCELONA); \n", "\n", " Route(:tablet,:PARIS,:SINGAPORE);\n", " Route(:tablet,:PARIS,:NEWYORK);\n", " Route(:tablet,:PARIS,:ISTANBUL);\n", " Route(:tablet,:PARIS,:DUBAI);\n", " Route(:tablet,:PARIS,:KUALALUMPUR);\n", " Route(:tablet,:PARIS,:HONGKONG);\n", " Route(:tablet,:PARIS,:BARCELONA); \n", "\n", " Route(:laptop,:BANGKOK,:SINGAPORE);\n", " Route(:laptop,:BANGKOK,:NEWYORK);\n", " Route(:laptop,:BANGKOK,:ISTANBUL);\n", " Route(:laptop,:BANGKOK,:DUBAI);\n", " Route(:laptop,:BANGKOK,:KUALALUMPUR);\n", " Route(:laptop,:BANGKOK,:HONGKONG);\n", " Route(:laptop,:BANGKOK,:BARCELONA); \n", "\n", " Route(:laptop,:LONDON,:SINGAPORE);\n", " Route(:laptop,:LONDON,:NEWYORK);\n", " Route(:laptop,:LONDON,:ISTANBUL);\n", " Route(:laptop,:LONDON,:DUBAI);\n", " Route(:laptop,:LONDON,:KUALALUMPUR);\n", " Route(:laptop,:LONDON,:HONGKONG);\n", " Route(:laptop,:LONDON,:BARCELONA); \n", "\n", " Route(:laptop,:PARIS,:SINGAPORE);\n", " Route(:laptop,:PARIS,:NEWYORK);\n", " Route(:laptop,:PARIS,:ISTANBUL);\n", " Route(:laptop,:PARIS,:DUBAI);\n", " Route(:laptop,:PARIS,:KUALALUMPUR);\n", " Route(:laptop,:PARIS,:HONGKONG);\n", " Route(:laptop,:PARIS,:BARCELONA); \n", "]\n", "\n", "struct Supply\n", " p::Symbol\n", " o::Symbol\n", "end\n", "\n", "#Creating the array supplies\n", "# --------\n", "supplies = Supply[] # Creates a 0 element array of immutable type Supply\n", "for r in routes\n", " push!(supplies, Supply(r.p, r.o))\n", "end\n", "\n", "# Creating suppliedAmount dictionary\n", "# --------------\n", "#It might be better to create this as a dictionary, where the key is the \n", "# element of the array supplies and the value is the corresponding supplied\n", "#amount\n", "\n", "\n", "suppliedAmount = Dict{Supply, Float64}()\n", "for s in supplies\n", " if s.p == :smartphone && s.o == :LONDON\n", " suppliedAmount[s]=800\n", " elseif s.p == :smartphone && s.o==:BANGKOK\n", " suppliedAmount[s]=500\n", " elseif s.p == :smartphone && s.o==:PARIS\n", " suppliedAmount[s]=600\n", " elseif s.p == :tablet && s.o==:BANGKOK\n", " suppliedAmount[s]=1000\n", " elseif s.p == :tablet && s.o==:LONDON\n", " suppliedAmount[s]=1500\n", " elseif s.p == :tablet && s.o == :PARIS\n", " suppliedAmount[s]=1700\n", " elseif s.p == :laptop && s.o == :BANGKOK\n", " suppliedAmount[s]=150\n", " elseif s.p == :laptop && s.o == :LONDON\n", " suppliedAmount[s]=250\n", " elseif s.p == :laptop && s.o == :PARIS\n", " suppliedAmount[s]=400 \n", "end #if\n", "end #for\n", "\n", "struct Customer\n", " p::Symbol\n", " d::Symbol\n", "end\n", "\n", "# Creating customers array, which is an array of custom immutable Customer \n", "# ---------\n", "customers = Customer[]\n", "for r in routes\n", " push!(customers, Customer(r.p, r.d))\n", "end\n", "\n", "\n", "demandedAmount = Dict{Customer, Float64}()\n", "for c in customers\n", "#1\n", " if c.p==:smartphone && c.d==:SINGAPORE\n", " demandedAmount[c]=400 \n", "#2\n", " elseif c.p==:tablet && c.d==:SINGAPORE\n", " demandedAmount[c]=600\n", "#3\n", " elseif c.p==:laptop && c.d==:SINGAPORE\n", " demandedAmount[c]=90\n", "#4\n", " elseif c.p==:smartphone && c.d==:NEWYORK\n", " demandedAmount[c]=200\n", "#5\n", " elseif c.p==:tablet && c.d==:NEWYORK\n", " demandedAmount[c]=650\n", "#6\n", " elseif c.p==:laptop && c.d==:NEWYORK \n", " demandedAmount[c]=110\n", "#7\n", " elseif c.p==:smartphone && c.d==:ISTANBUL\n", " demandedAmount[c]=100\n", "#8\n", " elseif c.p==:tablet && c.d==:ISTANBUL\n", " demandedAmount[c]=300\n", "#9\n", " elseif c.p==:laptop && c.d==:ISTANBUL\n", " demandedAmount[c]=0\n", "#10\n", " elseif c.p==:smartphone && c.d==:DUBAI\n", " demandedAmount[c]=175\n", "#11\n", " elseif c.p==:tablet && c.d==:DUBAI\n", " demandedAmount[c]=350\n", "#12\n", " elseif c.p==:laptop && c.d==:DUBAI\n", " demandedAmount[c]=65\n", "#13\n", " elseif c.p==:smartphone && c.d==:KUALALUMPUR\n", " demandedAmount[c]=550\n", "#14\n", " elseif c.p==:tablet && c.d==:KUALALUMPUR\n", " demandedAmount[c]=950\n", "#15\n", " elseif c.p==:laptop && c.d==:KUALALUMPUR\n", " demandedAmount[c]=185\n", "#16\n", " elseif c.p==:smartphone && c.d==:HONGKONG\n", " demandedAmount[c]=200\n", "#17\n", " elseif c.p==:tablet && c.d==:HONGKONG\n", " demandedAmount[c]=750\n", "#18\n", " elseif c.p==:laptop && c.d==:HONGKONG\n", " demandedAmount[c]=150\n", "#19\n", " elseif c.p==:smartphone && c.d==:BARCELONA\n", " demandedAmount[c]=275\n", "#20\n", " elseif c.p==:tablet && c.d==:BARCELONA\n", " demandedAmount[c]=600\n", "#21 \n", " elseif c.p==:laptop && c.d==:BARCELONA\n", " demandedAmount[c]=200\n", " end\n", "end\n", "\n", "\n", "costCof = \n", "[34; 7; 8; 10; 11; 74; 9; 18; 5; 15; 6; 23; 81; 18; 20; 10; 9; \n", " 13; 25; 85; 13; 40; 17; 7; 16; 20; 80; 9; 24; 5; 15; 11; 23; \n", "90; 22; 19; 15; 16; 15; 24; 100; 21; 37; 12; 9; 16; 14; \n", "88; 9; 28; 13; 17; 8; 32; 100; 18; 28; 15; 18; 16; 30; 102; 15]\n", "\n", "# Creating costRoutes dictionary which contains the costs of the relevant routes\n", "# ----------\n", "costRoutes=Dict{Route, Float64}()\n", "for i in 1:length(routes)\n", " costRoutes[routes[i]]=costCof[i]\n", "end\n", "\n", "# Creating orig, which takes the product as the input and gives the set of origins of that product\n", "# ----\n", "orig = Dict{Symbol, Array}()\n", "for i in 1:length(products)\n", " dummy_array = Symbol[]\n", " for j in 1:length(routes)\n", " #println(i, j, products[i] == routes[j].p)\n", " if products[i] == routes[j].p\n", " push!(dummy_array, routes[j].o)\n", " #println(orig[products[i]])\n", " else \n", " #println(\"Oops, something is not right\")\n", " end #if\n", " end #for \n", " orig[products[i]]=unique(dummy_array)\n", "end #for\n", "\n", "# Creating dest, which takes the product as the input and gives the set of destinations of that product\n", "# ----\n", "dest = Dict{Symbol, Array}()\n", "for i in 1:length(products)\n", " dummy_array = Symbol[]\n", " for j in 1:length(routes)\n", " #println(i, j, products[i] == routes[j].p)\n", " if products[i] == routes[j].p\n", " push!(dummy_array, routes[j].d)\n", " #println(orig[products[i]])\n", " else \n", " #println(\"Oops, something is not right\")\n", " end #if\n", " end #for \n", " dest[products[i]]=unique(dummy_array)\n", "end #for\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Model File" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The optimal objective value is: 178330.0\n", "The optimal solution is, trans= \n", "1-dimensional JuMPArray{Float64,1,...} with index sets:\n", " Dimension 1, Route[Route(:smartphone, :BANGKOK, :SINGAPORE), Route(:smartphone, :BANGKOK, :NEWYORK), Route(:smartphone, :BANGKOK, :ISTANBUL), Route(:smartphone, :BANGKOK, :DUBAI), Route(:smartphone, :BANGKOK, :KUALALUMPUR), Route(:smartphone, :BANGKOK, :HONGKONG), Route(:smartphone, :BANGKOK, :BARCELONA), Route(:smartphone, :LONDON, :SINGAPORE), Route(:smartphone, :LONDON, :NEWYORK), Route(:smartphone, :LONDON, :ISTANBUL) … Route(:laptop, :LONDON, :KUALALUMPUR), Route(:laptop, :LONDON, :HONGKONG), Route(:laptop, :LONDON, :BARCELONA), Route(:laptop, :PARIS, :SINGAPORE), Route(:laptop, :PARIS, :NEWYORK), Route(:laptop, :PARIS, :ISTANBUL), Route(:laptop, :PARIS, :DUBAI), Route(:laptop, :PARIS, :KUALALUMPUR), Route(:laptop, :PARIS, :HONGKONG), Route(:laptop, :PARIS, :BARCELONA)]\n", "And data, a 63-element Array{Float64,1}:\n", " 0.0\n", " 0.0\n", " 0.0\n", " 0.0\n", " 500.0\n", " 0.0\n", " 0.0\n", " 355.0\n", " 50.0\n", " 0.0\n", " 175.0\n", " 20.0\n", " 200.0\n", " 0.0\n", " 45.0\n", " 150.0\n", " 100.0\n", " 0.0\n", " 30.0\n", " 0.0\n", " 275.0\n", " 0.0\n", " 0.0\n", " 0.0\n", " 0.0\n", " 0.0\n", " 565.0\n", " 435.0\n", " 0.0\n", " 650.0\n", " 0.0\n", " 350.0\n", " 315.0\n", " 185.0\n", " 0.0\n", " 600.0\n", " 0.0\n", " 300.0\n", " 0.0\n", " 635.0\n", " 0.0\n", " 165.0\n", " 0.0\n", " 0.0\n", " 0.0\n", " 0.0\n", " 150.0\n", " 0.0\n", " 0.0\n", " 35.0\n", " 0.0\n", " -0.0\n", " 65.0\n", " 0.0\n", " 150.0\n", " 0.0\n", " 55.0\n", " 110.0\n", " 0.0\n", " 0.0\n", " 35.0\n", " 0.0\n", " 200.0\n" ] } ], "source": [ "using JuMP # Need to say it whenever we use JuMP\n", "using MathOptInterface\n", "# shortcuts\n", "const MOI = MathOptInterface\n", "const MOIU = MathOptInterface.Utilities\n", "\n", "using GLPK # Loading the GLPK module for using its solver\n", "\n", "#MODEL CONSTRUCTION\n", "#------------------\n", "transpModel = Model(optimizer = GLPK.GLPKOptimizerLP())\n", "\n", "#VARIABLES\n", "#---------\n", "@variable(transpModel, trans[routes] >= 0) \n", "\n", "#OBJECTIVE\n", "#---------\n", "\n", "@objective(transpModel, Min, sum(costRoutes[l]*trans[l] for l in routes))\n", "\n", "#Constraints\n", "#-----------\n", "\n", "\n", "# First Constraint\n", "# ----------------\n", "\n", "for pr in products\n", " for org in orig[pr]\n", " @constraint(transpModel, sum(trans[Route(pr, org, de)] for de in dest[pr])\n", " ==\n", " suppliedAmount[Supply(pr,org)])\n", " end\n", "end\n", "\n", "#Second Constraint\n", "#-----------------\n", "\n", "for pr in products\n", " for de in dest[pr]\n", " @constraint(transpModel, sum(trans[Route(pr, org, de)] for org in orig[pr])\n", " ==\n", " demandedAmount[Customer(pr,de)])\n", " end\n", "end\n", "\n", "# Final constraint:\n", "# ----------------\n", "for org in cities\n", " for de in cities\n", " if org!=de\n", " @constraint(transpModel, \n", " sum(\n", " trans[r] for r in routes\n", " if r.o == org && r.d==de # This will be used as an filtering condition\n", " )\n", " <=\n", " capacity)\n", " else\n", " continue\n", " end\n", " end\n", "end\n", " \n", "statusMipModel = JuMP.optimize(transpModel) # solves the model\n", "\n", "println(\"The optimal objective value is: \", JuMP.objectivevalue(transpModel))\n", "\n", "println(\"The optimal solution is, trans= \\n\", JuMP.resultvalue.(trans))" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "metadata": { "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": 1 }