{ "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 is an introduction to JuMP. The topics described are as follows:\n", "- Installing Julia and JuMP\n", "- Representing vectors in Julia\n", "- Structure of a JuMP model\n", "- Solving general purpose linear programming problem\n", "- Solving general purpose integer programming problem\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 - getting started\n", "--------------------------\n", "\n", "## Julia\n", "\n", "\n", "### What is Julia?\n", "\n", "Julia is a new programming language.\n", "\n", "### Why Julia?\n", "\n", "- Free and open-source\n", "- Syntax similar to MATLAB, speed similar to C\n", "\n", "\n", "## JuMP\n", "\n", "### What is JuMP?\n", "\n", "JuMP is a modelling language for mathematical optimization [1]. It is embedded in Julia.\n", "\n", "### Why JuMP?\n", "\n", "- Very user-friendly\n", "- Speed similar to special purpose commercial modelling language like AMPL\n", "- Solver independent code: same code will run for both commercial and open-source solvers\n", "- Very easy to implement solver callback and problem modification\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Installation\n", "\n", "## Installing Julia and IJulia\n", "\n", "### Installing Julia\n", "\n", "Go to the [download page](http://julialang.org/downloads/ \"downloadJulia\") of Julia, download the appropriate installer and run it. Now you can start an interactive Julia session! \n", "\n", "### Installing IJulia\n", "\n", "IJulia will allow us to create powerful graphical notebooks, which is very convenient for the tutorial. We can insert codes, text, mathematical formulas and multimedia etc. in the same notebook. To install IJulia: \n", "\n", "- Install Anaconda from http://continuum.io/downloads. If you are on Windows, then while running the Anaconda installer please check the options *Add Anaconda to the System Path* and also *Register Anaconda as default Python version of the system*.\n", "\n", "- Now start a Julia interactive session. Type the following `Pkg.add(\"IJulia\")`\n", "\n", "- To open a new notebook\n", " * In the Julia interactive session, run `Using IJulia` and then `notebook()`. It will open the Home for IJulia in your web browser. \n", " \n", " * The directory location can be checked by the command `pwd()`. If you want to change the directory to something else, the before running `Using IJulia` and `notebook()`, run `cd(path to your preferred directory)`, e.g., `cd(\"E:\\\\Dropbox\\\\Julia_Workspaces\")`. \n", " * Click on *New Notebook* on the top right corner. In the new notebook, you can execute any Julia command pressing SHIFT+ENTER.\n", " \n", " \n", "### Installing JuMP\n", " \n", "At first add the JuMP package by running the following code in the notebook:\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "#Pkg.add(\"JuMP\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We need to install a solver package. Let's install the open source solvers GLPK, Cbc and Clp by typing in `Pkg.add(\"GLPKMathProgInterface\")`, `Pkg.add(\"Cbc\")` and `Pkg.add(\"Clp\")` respectively. Let's add the Julia package associated with CPLEX by typing in `Pkg.add(\"CPLEX\")`. The other choices are `\"CPLEX\"`, `\"Cbc\"`, `\"Clp\"`, `\"Gurobi\"`, `\"Xpress\"` and `\"MOSEK\"`. \n", "\n", "It should be noted that, in order to use commercial solvers such as CPLEX, Gurobi, Xpress and Mosek in JuMP, we will require working installations of them with appropriate licences. Both Gurobi and Mosek are free for academic use. CPLEX is free for faculty members and graduate teaching assistants. " ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": true }, "outputs": [], "source": [ "#Pkg.add(\"GLPKMathProgInterface\")" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": true }, "outputs": [], "source": [ "#Pkg.add(\"Cbc\")" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": true }, "outputs": [], "source": [ "#Pkg.add(\"Clp\")" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": true }, "outputs": [], "source": [ "#Pkg.add(\"CPLEX\") # Working installation of CPLEX is needed in advance" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": true }, "outputs": [], "source": [ "#Pkg.add(\"Gurobi\") # Working installation of Gurobi is needed in advance" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": true }, "outputs": [], "source": [ "#Pkg.add(\"Xpress\") # Working installation of Xpress is needed in advance" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If you have not updated your Julia packages in a while, a good idea might be updating them." ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": true }, "outputs": [], "source": [ "#Pkg.update()" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Hello World!\n" ] } ], "source": [ "println(\"Hello World!\")" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false }, "outputs": [], "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" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# The very first example\n", "\n", "At first let us try to solve a very simple and trivial optimization problem using JuMP to check if everything is working properly. \n", "\n", "\n", "\\begin{align}\n", "\\text{minimize} \\qquad & x+y \\\\\n", " \\text{subject to} \\quad \\quad & x+y \\leq 1 \\\\\n", " \\qquad \\qquad & x \\geq 0, y \\geq 0 \\\\\n", " \\qquad \\qquad & x,y \\in \\mathbb{R}\n", "\\end{align}\n", "\n", "\n", "Here is the JuMP code to solve the mentioned problem:" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "JuMP.hasresultvalues(myModel) = true\n", "JuMP.terminationstatus(myModel) == MOI.Success = true\n", "JuMP.primalstatus(myModel) == MOI.FeasiblePoint = true\n", "Objective value: 0.0\n", "x = 0.0\n", "y = 0.0\n" ] } ], "source": [ "#MODEL CONSTRUCTION\n", "#-------------------- \n", "myModel = Model(optimizer = GLPK.GLPKOptimizerLP()) \n", "# Name of the model object. All constraints and variables of an optimization problem are associated \n", "# with a particular model object. The name of the model object does not have to be myModel, it can be yourModel too!\n", "# This Creates an empty Model with solver attached.\n", "\n", "#VARIABLES\n", "#---------\n", "\n", "# A variable is modelled using @variable(name of the model object, variable name and bound, variable type)\n", "# Bound can be lower bound, upper bound or both. If no variable type is defined, then it is treated as \n", "#real. For binary variable write Bin and for integer use Int.\n", "\n", "@variable(myModel, x >= 0) # Models x >=0\n", "\n", "# Some possible variations:\n", "# @variable(myModel, x, Bin) # No bound on x present, but x is a binary variable now\n", "# @variable(myModel, x <= 10) # This one defines a variable with lower bound x <= 10\n", "# @variable(myModel, 0 <= x <= 10, Int) # This one has both lower and upper bound, and x is an integer\n", "\n", "@variable(myModel, y >= 0) # Models y >= 0\n", "\n", "#OBJECTIVE\n", "#---------\n", "\n", "@objective(myModel, Min, x + y) # Sets the objective to be minimized. For maximization use Max\n", "\n", "#CONSTRAINTS\n", "#-----------\n", "\n", "@constraint(myModel, x + y <= 1) # Adds the constraint x + y <= 1\n", "\n", "#THE MODEL IN A HUMAN-READABLE FORMAT (TODO)\n", "#------------------------------------\n", "#println(\"The optimization problem to be solved is:\")\n", "#print(myModel) # Shows the model constructed in a human-readable form\n", "\n", "#SOLVE IT\n", "#--------\n", "JuMP.optimize(myModel) # solves the model\n", "\n", "# TEST SOLVER STATUSES\n", "#---------------------\n", "@show JuMP.hasresultvalues(myModel)\n", "@show JuMP.terminationstatus(myModel) == MOI.Success\n", "@show JuMP.primalstatus(myModel) == MOI.FeasiblePoint\n", "\n", "# DISPLAY THE RESULTS\n", "#--------------------\n", "println(\"Objective value: \", JuMP.objectivevalue(myModel)) # JuMP.objectivevalue(model_name) gives the optimum objective value\n", "println(\"x = \", JuMP.resultvalue(x)) # JuMP.resultvalue(decision_variable) will give the optimum value of the associated decision variable\n", "println(\"y = \", JuMP.resultvalue(y))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This was certainly not the most exciting optimization problem to solve. This was for test purpose only. However, before going into the structure of a JuMP model, let us learn how to represent vectors in Julia.\n", " \n", "# Representing vectors in Julia\n", " \n", " * A column vector, $y=(y_1, y_2, \\ldots, y_n)= \\begin{pmatrix}\n", " y_1 \\\\\n", " y_2 \\\\\n", " . \\\\\n", " . \\\\\n", " y_n\n", " \\end{pmatrix} \\in \\mathbb{R}^n$ will be written in Julia as `[y[1];y[2];...;y[n]]`. \n", " \n", " For example to create column vector $\\begin{pmatrix}\n", " 3 \\\\\n", " 2.4 \\\\\n", " 9.1 \\\\\n", " \\end{pmatrix}$ use: `[3; 2.4; 9.1]`.\n" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "3-element Array{Float64,1}:\n", " 3.0\n", " 2.4\n", " 9.1" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[3; 2.4; 9.1] # Column vector" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* A row vector, $z=(z_1 \\; z_2 \\; \\ldots \\; z_n) \\in \\mathbb{R}^{1 \\times n}$ will be written in Julia as `[z[1] y[2]...z[n]]`. \n", " \n", " For example to create row vector $(1.2 \\; 3.5 \\; 8.21)$ use: `[1.2 3.5 8.21]`.\n", " " ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "1×3 Array{Float64,2}:\n", " 1.2 3.5 8.21" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[1.2 3.5 8.21] # Row vector" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* To create a $m \\times n$ matrix \n", "\n", "$$\n", "A = \\begin{pmatrix}\n", " A_{11} & A_{12} & A_{13} & \\ldots &A_{1n} \\\\\n", " \\ldots & \\ldots & \\ldots & \\ldots & \\ldots \\\\\n", " A_{m1} & A_{m2} & A_{m3} & \\ldots & A_{mn}\n", " \\end{pmatrix}\n", "$$\n", "\n", "write:\n", " \n", " `[A[1,1] A[1,2] A[1,3]... A[1,n];`\n", " ` ... ; `\n", " `A[m,1] A[m,2] ... A[m,n]]`.\n", " \n", " So the matrix \n", " \n", " $$\n", " A = \\begin{pmatrix}\n", " 1 & 1 & 9 & 5 \\\\\n", " 3 & 5 & 0 & 8 \\\\\n", " 2 & 0 & 6 & 13\n", " \\end{pmatrix}\n", " $$ \n", " \n", " is represented in Julia as: \n", " \n", " `A= [\n", " 1 1 9 5;\n", " 3 5 0 8;\n", " 2 0 6 13\n", " ]`" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "3×4 Array{Int64,2}:\n", " 1 1 9 5\n", " 3 5 0 8\n", " 2 0 6 13" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Generating a matrix\n", "A= [\n", " 1 1 9 5;\n", " 3 5 0 8;\n", " 2 0 6 13\n", " ]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " $A_{ij}$ can be accessed by `A[i,j]` ,the $i$th row of the matrix A is represented by `A[i,:]`, the $j$th column of the matrix A is represented by `A[:,j]`. \n", " \n", " The size of a matrix $A$ can be determined by running the command `size(A)`. If we write `numRows, numCols = size(A)`, then `numRows` and `numCols` will contain the total number of rows and columns of A respectively." ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "A has 3 rows and 4 columns \n", "A[3,3] is 6\n", "The 3rd column of A is [9, 0, 6]\n", "The 2nd row of A is [3, 5, 0, 8]\n" ] } ], "source": [ "numRows, numCols = size(A)\n", "println(\n", "\"A has \", numRows, \" rows and \", numCols, \" columns \\n\",\n", "\"A[3,3] is \", A[3,3], \"\\n\",\n", "\"The 3rd column of A is \", A[:,3], \"\\n\",\n", "\"The 2nd row of A is \", A[2,:]\n", ")\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Suppose $x,y \\in \\mathbb{R}^n$. Then $x^T y =\\sum_{i=1}^{n} {x_i y_i}$ is written as `dot(x,y)`. " ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "70" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "y=[1; 2; 3; 4]\n", "x=[5; 6; 7; 8]\n", "xTy=dot(x,y)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Structure of a JuMP model\n", "\n", "Any JuMP model that describes an optimization problem must have four parts: \n", "\n", "- **Model Object**,\n", "- **Optimizer Object**,\n", "- **Variables**, \n", "- **Objective**, \n", "- **Constraints**.\n", "\n", "## Model\n", "\n", "Any instance of an optimization problem corresponds to a model object. This model object is associated with all the variables, constraints and objective of the instance. It is constructed using `modelName = Model()`. At this point a solver/optimizer might be specified or not.\n", "\n", "## Optimizer/Solver\n", "\n", "We can use open source solvers such as:\n", "\n", "* Linear Programming Solver: `ClpOptimizer(), GLPKOptimizerLP()`\n", "* Mixed Integer Programming Solver: `GLPKOptimizerMIP() CbcOptimizer()`\n", "\n", "Or commercial solver such as:\n", "\n", "* LP and MIP: `XpressOptimizer()`, `GurobiOptimizer()`, `CPLEXOptimizer()`\n", "\n", "\n", "There are a few options to handle the solver object:\n", "\n", "### `Automatic` with `optimizer`\n", "\n", "This is the easiest method to use a solver in JuMP. In order to do so, we simply set the solver inside the `Model` constructor:\n", "\n", "`Model(optimizer = GLPK.GLPKOptimizerLP())`\n", "\n", "`Model(mode = JuMP.Automatic, optimizer = GLPK.GLPKOptimizerLP())`\n", "\n", "### `Automatic` with NO `optimizer`\n", "\n", "It is also possible to create a JuMP model with no optimizer attached.\n", "\n", "After the **Model Object** is initialized empty (`Model()`) and all its **Variables**, **Constraints** and **Objective** are set, then we can attach the solver with the two steps:\n", "\n", "`MOIU.resetoptimizer!(myModel, GLPK.GLPKOptimizerLP())`\n", "\n", "`MOIU.attachoptimizer!(myModel)`\n", "\n", "### `Direct` model with a non default `backend`\n", "\n", "Some solvers are able to handle the problem data directly. This is common for LP/MIP solver but not very common for open-source conic solvers.\n", "\n", "In this case we do not set a optimizer, we set a `backend` which is more generic and is able to hold data and not only solving a model.\n", "\n", "`Model(mode = JuMP.Direct, backend = GLPK.GLPKOptimizerLP())`\n", "\n", "### `Manual` model with an `optimizer`\n", "\n", "Similar to the `Automatic`+`optimizer`, but there are less protections from the user getting errors from the solver API. On the other side, nothig happens silently, which might give the user more control.\n", "\n", "`Model(mode = JuMP.Manual, backend = GLPK.GLPKOptimizerLP())`\n", "\n", "this mode requires attaching the solver before the solve step" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "## Variables\n", "Variables are defined using `@variable` macro, which takes up to three input arguments. The *first* argument is the name of the model. Then the *second* argument contains the name of the variable, and a bound on the variable if it exists. The *third* argument is not needed if the variable is real. When the variable is binary or integer, then `Bin` or `Int`, respectively, is used in place of the third argument.\n", "\n", "### Examples of Variables\n", "Suppose the model object is `myModel`. " ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "A JuMP Model" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "myModel = Model(optimizer = GLPK.GLPKOptimizerLP())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- To describe a variable $z \\in \\mathbb{R}$ such that $0 \\leq z \\leq 10$\n", "write" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/latex": [ "$$ z $$" ], "text/plain": [ "z" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(myModel, 0 <= z <= 10)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- Now consider a decision variable $x \\in \\mathbb{R}^n$, and it has a bound $l \\preceq x \\preceq u$, where naturally $l, u \\in \\mathbb{R}^n$. For that we write
\n" ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "10-element Array{Int64,1}:\n", " 10\n", " 11\n", " 12\n", " 13\n", " 14\n", " 15\n", " 16\n", " 17\n", " 18\n", " 19" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# INPUT DATA, CHANGE THEM TO YOUR REQUIREMENT\n", "#-------------------------------------------\n", "n = 10\n", "l = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]\n", "u = [10; 11; 12; 13; 14; 15; 16; 17; 18; 19]" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "10-element Array{JuMP.VariableRef,1}:\n", " x[1] \n", " x[2] \n", " x[3] \n", " x[4] \n", " x[5] \n", " x[6] \n", " x[7] \n", " x[8] \n", " x[9] \n", " x[10]" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# VARIABLE DEFINITION\n", "# ------------------- \n", "@variable(myModel, l[i] <= x[i=1:n] <= u[i])\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- Suppose we have decision variables $x \\in \\mathbb{R}^n$, $y \\in \\mathbb{Z}^m$ and $z \\in \\mathbb \\{0,1\\}^p$ such that $x \\succeq 0$, $a \\preceq y \\preceq b$. Here $a, b \\in \\mathbb{Z}^m$. To express this in JuMP we write" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "3-element Array{Int64,1}:\n", " 3\n", " 4\n", " 7" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# INPUT DATA, CHANGE THEM TO YOUR REQUIREMENT\n", "#-------------------------------------------\n", "n = 4 # dimension of x\n", "m = 3 # dimension of y\n", "p = 2 # dimensin of z\n", "a = [0; 1; 2]\n", "b = [3; 4; 7]" ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "4-element Array{JuMP.VariableRef,1}:\n", " xx[1]\n", " xx[2]\n", " xx[3]\n", " xx[4]" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# VARIABLE DEFINITION\n", "# -------------------\n", "@variable(myModel, xx[i=1:n] >= 0)" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "3-element Array{JuMP.VariableRef,1}:\n", " yy[1]\n", " yy[2]\n", " yy[3]" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(myModel, a[i] <= yy[i=1:m] <= b[i], Int)" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "2-element Array{JuMP.VariableRef,1}:\n", " zz[1]\n", " zz[2]" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(myModel, zz[i=1:p], Bin)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Constraints\n", "Constraints are added by using `@constraint` macro. The first argument is the model object the constraint is associated with, the second argument is the reference to that constraint and the third argument is the constraint description. The constraint reference comes handy when we want to manipulate the constraint later or access the dual variables associated with it. If no constraint reference is needed, then the second argument is the constraint description.
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Examples of Constraints\n", "Let's give some examples on writing constraints in JuMP. Suppose the model name is `yourModel`." ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "A JuMP Model" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "yourModel = Model()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 1 Simple constraints \n", "Consider variables $x, y \\in \\mathbb{R}$ which are coupled by the constraints $5 x +3 y \\leq 5$. We write this as
\n", "`@constraint(yourModel, 5*x + 3*y <= 5)`
\n", "Naturally, `x` and `y` have to be defined first using `@variable` macro." ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "JuMP.ConstraintRef{JuMP.Model,MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64},MathOptInterface.LessThan{Float64}}}(A JuMP Model, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64},MathOptInterface.LessThan{Float64}}(1))" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(yourModel, x)\n", "@variable(yourModel, y)\n", "@constraint(yourModel, 5*x + 3*y <= 5)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 2 References\n", "Here no constraint reference is given. Now suppose we want to get the dual value of some constraint after solving the problem, then we would need a constraint reference to assign to the constraint first. Let's call the constraint reference as `conRef1` (it could be any valid name). Then the same constraint have to be written as:
\n", "`conRef1 = @constraint(yourModel, 6*x + 4*y >= 5)`
\n", "When we would need the dual value after solving the problem we just write `println(JuMP.resultdual(conRef1))`.
" ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "JuMP.ConstraintRef{JuMP.Model,MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64},MathOptInterface.GreaterThan{Float64}}}(A JuMP Model, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64},MathOptInterface.GreaterThan{Float64}}(2))" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "conRef1 = @constraint(yourModel, 6*x + 4*y >= 5) " ] }, { "cell_type": "code", "execution_count": 28, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ret = @constraint(yourModel, conRef2, 6*x + 4*y >= 5)\n", "ret==conRef2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 3 Sums\n", "Consider a variable $x \\in \\mathbb{R}^4$, a coefficient vector $a=(1, -3, 5, -7)$ We want to write a constraint of the form $\\sum_{i=1}^4{a_i x_i} \\leq 3$. In JuMP we write:
\n" ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "JuMP.ConstraintRef{JuMP.Model,MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64},MathOptInterface.LessThan{Float64}}}(A JuMP Model, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64},MathOptInterface.LessThan{Float64}}(4))" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a = [1; -3; 5; 7] \n", "@variable(yourModel, w[1:4])\n", "@constraint(yourModel, sum(a[i]*w[i] for i in 1:4) <= 3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Add constraints in a loop" ] }, { "cell_type": "code", "execution_count": 30, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "3-element Array{JuMP.ConstraintRef{JuMP.Model,C} where C,1}:\n", " JuMP.ConstraintRef{JuMP.Model,MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64},MathOptInterface.GreaterThan{Float64}}}(A JuMP Model, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64},MathOptInterface.GreaterThan{Float64}}(5))\n", " JuMP.ConstraintRef{JuMP.Model,MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64},MathOptInterface.GreaterThan{Float64}}}(A JuMP Model, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64},MathOptInterface.GreaterThan{Float64}}(6))\n", " JuMP.ConstraintRef{JuMP.Model,MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64},MathOptInterface.GreaterThan{Float64}}}(A JuMP Model, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64},MathOptInterface.GreaterThan{Float64}}(7))" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@constraint(yourModel, conRef3[i in 1:3], 6*x + 4*y >= 5*i)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Or just use a regular loop" ] }, { "cell_type": "code", "execution_count": 31, "metadata": { "collapsed": true }, "outputs": [], "source": [ "for i in 1:3\n", " @constraint(yourModel, 6*x + 4*y >= 5*i)\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Objective\n", "Objective is set using `@objective` macro. It has three arguments. The first argument is as usual the model object. The second one is either `Max` if we want to maximize the objective function, or `Min` when we want to minimize. The last argument is the description of the objective which has similar syntax to that of constraint definition.\n", "\n", "### Example of objective\n", "For the previous model, consider the decision variable $w \\in \\mathbb{R}^4$ and cost vector $c = (2, 3 , 4, 5)$. We want to minimize $c^T w$. In JuMP we would write:" ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "collapsed": false }, "outputs": [], "source": [ "c = [2; 3; 4; 5] \n", "@objective(yourModel, Min, sum(c[i]*w[i] for i in 1:4))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "which could also be a maximization" ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "collapsed": true }, "outputs": [], "source": [ "@objective(yourModel, Max, sum(c[i]*w[i] for i in 1:4))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Solving a standard form Linear Programming \n", "problem\n", "Let us try to write the JuMP code for the following standard form optimization problem:\n", "\n", "$$\n", "\\begin{align}\n", "& \\text{minimize} && c^T x \\\\\n", "& \\text{subject to} && A x = b \\\\\n", "& && x \\succeq 0 \\\\\n", "& && x \\in \\mathbb{R}^n\n", "\\end{align}\n", "$$\n", "\n", "\n", "where, $n = 4$, $c=(1, 3, 5, 2)$, $A = \\begin{pmatrix}\n", " 1 & 1 & 9 & 5 \\\\\n", " 3 & 5 & 0 & 8 \\\\\n", " 2 & 0 & 6 & 13\n", " \\end{pmatrix}$ and $b=(7, 3, 5)$. The symbol $\\succeq$ ($\\preceq$) stands for element-wise greater (less) than or equal to.\n", "\n", "### Entering different parts of the code one by one\n", "Let us input different parts of the JuMP code one by one and see the corresponding outputs to detect if everything is okay. Of course we could input the whole code at once." ] }, { "cell_type": "code", "execution_count": 34, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "A JuMP Model" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#MODEL CONSTRUCTION\n", "#------------------\n", "\n", "sfLpModel = Model(optimizer = GLPK.GLPKOptimizerLP()) # Name of the model object" ] }, { "cell_type": "code", "execution_count": 35, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "(3, 4)" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#INPUT DATA\n", "#----------\n", "\n", "c = [1; 3; 5; 2] \n", "\n", "A= [\n", " 1 1 9 5;\n", " 3 5 0 8;\n", " 2 0 6 13\n", " ]\n", "\n", "b = [7; 3; 5] \n", "\n", "m, n = size(A) # m = number of rows of A, n = number of columns of A" ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "4-element Array{JuMP.VariableRef,1}:\n", " x[1]\n", " x[2]\n", " x[3]\n", " x[4]" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#VARIABLES\n", "#---------\n", "\n", "@variable(sfLpModel, x[1:n] >= 0) # Models x >=0\n" ] }, { "cell_type": "code", "execution_count": 37, "metadata": { "collapsed": false }, "outputs": [], "source": [ "#CONSTRAINTS\n", "#-----------\n", "\n", "for i in 1:m # for all rows do the following\n", " @constraint(sfLpModel, sum(A[i,j]*x[j] for j in 1:n) == b[i]) # the ith row \n", " # of A*x is equal to the ith component of b\n", "end # end of the for loop" ] }, { "cell_type": "code", "execution_count": 38, "metadata": { "collapsed": false }, "outputs": [], "source": [ "#OBJECTIVE\n", "#---------\n", "\n", "@objective(sfLpModel, Min, sum(c[j]*x[j] for j in 1:n)) # minimize c'x " ] }, { "cell_type": "code", "execution_count": 39, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The optimization problem to be solved is:\n", "A JuMP Model" ] } ], "source": [ "#THE MODEL IN A HUMAN-READABLE FORMAT (TODO)\n", "#------------------------------------\n", "\n", "println(\"The optimization problem to be solved is:\")\n", "print(sfLpModel) # Shows the model constructed in a human-readable form" ] }, { "cell_type": "code", "execution_count": 40, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "JuMP.hasresultvalues(sfLpModel) = true\n", "JuMP.terminationstatus(sfLpModel) == MOI.Success = true\n", "JuMP.primalstatus(sfLpModel) == MOI.FeasiblePoint = true\n" ] }, { "data": { "text/plain": [ "true" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# finally optimize the model\n", "JuMP.optimize(sfLpModel) # solves the model\n", "\n", "# TEST SOLVER STATUSES\n", "#---------------------\n", "@show JuMP.hasresultvalues(sfLpModel)\n", "@show JuMP.terminationstatus(sfLpModel) == MOI.Success\n", "@show JuMP.primalstatus(sfLpModel) == MOI.FeasiblePoint" ] }, { "cell_type": "code", "execution_count": 41, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Objective value: 4.923076923076923\n", "Optimal solution is x = \n", "[0.423077, 0.346154, 0.692308, 0.0]\n" ] } ], "source": [ "#SOLVE IT AND DISPLAY THE RESULTS\n", "#--------------------------------\n", "\n", "println(\"Objective value: \", JuMP.objectivevalue(sfLpModel)) # getObjectiveValue(model_name) gives the optimum objective value\n", "\n", "println(\"Optimal solution is x = \\n\", JuMP.resultvalue.(x)) # getValue(decision_variable) will give the optimum value \n", " # of the associated decision variable\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### The whole code" ] }, { "cell_type": "code", "execution_count": 42, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "(3, 4)" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "#INPUT DATA\n", "#----------\n", "\n", "c = [1; 3; 5; 2] \n", "\n", "A= [\n", " 1 1 9 5;\n", " 3 5 0 8;\n", " 2 0 6 13\n", " ]\n", "\n", "b = [7; 3; 5] \n", "\n", "m, n = size(A) # m = number of rows of A, n = number of columns of A" ] }, { "cell_type": "code", "execution_count": 43, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.000537 seconds (1.00 k allocations: 62.982 KiB)\n", "JuMP.hasresultvalues(sfLpModel) = true\n", "JuMP.terminationstatus(sfLpModel) == MOI.Success = true\n", "JuMP.primalstatus(sfLpModel) == MOI.FeasiblePoint = true\n", "Objective value: 4.923076923076923\n", "Optimal solution is x = \n", "[0.423077, 0.346154, 0.692308, 0.0]\n" ] } ], "source": [ "#MODEL CONSTRUCTION\n", "#------------------\n", "\n", "sfLpModel = Model(optimizer = GLPK.GLPKOptimizerLP())\n", "\n", "#VARIABLES\n", "#---------\n", "\n", "@variable(sfLpModel, x[1:n] >= 0) # Models x >=0\n", "\n", "#CONSTRAINTS\n", "#-----------\n", "\n", "for i in 1:m # for all rows do the following\n", " @constraint(sfLpModel, sum(A[i,j]*x[j] for j in 1:n) == b[i]) # the ith row \n", " # of A*x is equal to the ith component of b\n", "end # end of the for loop\n", "\n", "#OBJECTIVE\n", "#---------\n", "\n", "@objective(sfLpModel, Min, sum(c[j]*x[j] for j in 1:n)) # minimize c'x \n", "\n", "\n", "#SOLVE IT\n", "#--------\n", "\n", "# finally optimize the model\n", "@time begin\n", "status = JuMP.optimize(sfLpModel) # solves the model\n", "end\n", "\n", "# TEST SOLVER STATUSES\n", "#---------------------\n", "@show JuMP.hasresultvalues(sfLpModel)\n", "@show JuMP.terminationstatus(sfLpModel) == MOI.Success\n", "@show JuMP.primalstatus(sfLpModel) == MOI.FeasiblePoint\n", "\n", "# DISPLAY THE RESULTS\n", "#-------------------------------- \n", "\n", "println(\"Objective value: \", JuMP.objectivevalue(sfLpModel)) # JuMP.objectivevalue(model_name) gives the optimum objective value\n", "\n", "println(\"Optimal solution is x = \\n\", JuMP.resultvalue.(x)) # JuMP.resultvalue(decision_variable) will give the optimum value \n", " # of the associated decision variable\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Modes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Auto + Optimizer" ] }, { "cell_type": "code", "execution_count": 44, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.000516 seconds (923 allocations: 56.656 KiB)\n", "JuMP.hasresultvalues(sfLpModel) = true\n", "JuMP.terminationstatus(sfLpModel) == MOI.Success = true\n", "JuMP.primalstatus(sfLpModel) == MOI.FeasiblePoint = true\n", "Objective value: 4.923076923076923\n", "Optimal solution is x = \n", "[0.423077, 0.346154, 0.692308, 0.0]\n" ] } ], "source": [ "#MODEL INITIALIZATION\n", "#--------------------\n", "\n", "sfLpModel = Model(optimizer = GLPK.GLPKOptimizerLP())\n", "\n", "#Problem construction\n", "#--------------------\n", "\n", "@variable(sfLpModel, x[1:n] >= 0) # Models x >=0\n", "for i in 1:m\n", " @constraint(sfLpModel, sum(A[i,j]*x[j] for j in 1:n) == b[i])\n", "end\n", "\n", "@objective(sfLpModel, Min, sum(c[j]*x[j] for j in 1:n)) # minimize c'x \n", "\n", "#SOLVE IT\n", "#--------\n", "\n", "# finally optimize the model\n", "@time begin\n", "status = JuMP.optimize(sfLpModel) # solves the model\n", "end\n", "\n", "# TEST SOLVER STATUSES and DISPLAY THE RESULTS\n", "#---------------------------------------------\n", "@show JuMP.hasresultvalues(sfLpModel)\n", "@show JuMP.terminationstatus(sfLpModel) == MOI.Success\n", "@show JuMP.primalstatus(sfLpModel) == MOI.FeasiblePoint\n", "\n", "println(\"Objective value: \", JuMP.objectivevalue(sfLpModel))\n", "println(\"Optimal solution is x = \\n\", JuMP.resultvalue.(x))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Enforced auto + optimizer" ] }, { "cell_type": "code", "execution_count": 45, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.000515 seconds (923 allocations: 56.656 KiB)\n", "JuMP.hasresultvalues(sfLpModel) = true\n", "JuMP.terminationstatus(sfLpModel) == MOI.Success = true\n", "JuMP.primalstatus(sfLpModel) == MOI.FeasiblePoint = true\n", "Objective value: 4.923076923076923\n", "Optimal solution is x = \n", "[0.423077, 0.346154, 0.692308, 0.0]\n" ] } ], "source": [ "#MODEL INITIALIZATION\n", "#--------------------\n", "\n", "sfLpModel = Model(mode = JuMP.Automatic, optimizer = GLPK.GLPKOptimizerLP())\n", "\n", "#Problem construction\n", "#--------------------\n", "\n", "@variable(sfLpModel, x[1:n] >= 0) # Models x >=0\n", "for i in 1:m\n", " @constraint(sfLpModel, sum(A[i,j]*x[j] for j in 1:n) == b[i])\n", "end\n", "\n", "@objective(sfLpModel, Min, sum(c[j]*x[j] for j in 1:n)) # minimize c'x \n", "\n", "#SOLVE IT\n", "#--------\n", "\n", "# finally optimize the model\n", "@time begin\n", "status = JuMP.optimize(sfLpModel) # solves the model\n", "end\n", "\n", "# TEST SOLVER STATUSES and DISPLAY THE RESULTS\n", "#---------------------------------------------\n", "@show JuMP.hasresultvalues(sfLpModel)\n", "@show JuMP.terminationstatus(sfLpModel) == MOI.Success\n", "@show JuMP.primalstatus(sfLpModel) == MOI.FeasiblePoint\n", "\n", "println(\"Objective value: \", JuMP.objectivevalue(sfLpModel))\n", "println(\"Optimal solution is x = \\n\", JuMP.resultvalue.(x))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## No Optimizer (at first)" ] }, { "cell_type": "code", "execution_count": 46, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.000083 seconds (39 allocations: 1.016 KiB)\n", "JuMP.hasresultvalues(sfLpModel) = true\n", "JuMP.terminationstatus(sfLpModel) == MOI.Success = true\n", "JuMP.primalstatus(sfLpModel) == MOI.FeasiblePoint = true\n", "Objective value: 4.923076923076923\n", "Optimal solution is x = \n", "[0.423077, 0.346154, 0.692308, 0.0]\n" ] } ], "source": [ "#MODEL INITIALIZATION\n", "#--------------------\n", "\n", "sfLpModel = Model()\n", "\n", "#Problem construction\n", "#--------------------\n", "\n", "@variable(sfLpModel, x[1:n] >= 0) # Models x >=0\n", "for i in 1:m\n", " @constraint(sfLpModel, sum(A[i,j]*x[j] for j in 1:n) == b[i])\n", "end\n", "\n", "@objective(sfLpModel, Min, sum(c[j]*x[j] for j in 1:n)) # minimize c'x \n", "\n", "#SOLVE IT\n", "#--------\n", "# the first step towards solving a model is to initialize a (empty) solver:\n", "solver = GLPK.GLPKOptimizerLP()\n", "\n", "# then the solver is linked to the model by:\n", "MOIU.resetoptimizer!(sfLpModel, solver)\n", "\n", "# to push data into the solver:\n", "MOIU.attachoptimizer!(sfLpModel)\n", "\n", "# finally optimize the model\n", "@time begin\n", "status = JuMP.optimize(sfLpModel) # solves the model\n", "end\n", "\n", "# TEST SOLVER STATUSES and DISPLAY THE RESULTS\n", "#---------------------------------------------\n", "@show JuMP.hasresultvalues(sfLpModel)\n", "@show JuMP.terminationstatus(sfLpModel) == MOI.Success\n", "@show JuMP.primalstatus(sfLpModel) == MOI.FeasiblePoint\n", "\n", "println(\"Objective value: \", JuMP.objectivevalue(sfLpModel))\n", "println(\"Optimal solution is x = \\n\", JuMP.resultvalue.(x))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Direct + backend" ] }, { "cell_type": "code", "execution_count": 47, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.000086 seconds (39 allocations: 1.016 KiB)\n", "JuMP.hasresultvalues(sfLpModel) = true\n", "JuMP.terminationstatus(sfLpModel) == MOI.Success = true\n", "JuMP.primalstatus(sfLpModel) == MOI.FeasiblePoint = true\n", "Objective value: 4.923076923076923\n", "Optimal solution is x = \n", "[0.423077, 0.346154, 0.692308, 0.0]\n" ] } ], "source": [ "#MODEL INITIALIZATION\n", "#--------------------\n", "\n", "sfLpModel = Model(mode = JuMP.Direct, backend = GLPK.GLPKOptimizerLP())\n", "\n", "#Problem construction\n", "#--------------------\n", "\n", "@variable(sfLpModel, x[1:n] >= 0) # Models x >=0\n", "for i in 1:m\n", " @constraint(sfLpModel, sum(A[i,j]*x[j] for j in 1:n) == b[i])\n", "end\n", "\n", "@objective(sfLpModel, Min, sum(c[j]*x[j] for j in 1:n)) # minimize c'x \n", "\n", "#SOLVE IT\n", "#--------\n", "\n", "# finally optimize the model\n", "@time begin\n", "status = JuMP.optimize(sfLpModel) # solves the model\n", "end\n", "\n", "# TEST SOLVER STATUSES and DISPLAY THE RESULTS\n", "#---------------------------------------------\n", "@show JuMP.hasresultvalues(sfLpModel)\n", "@show JuMP.terminationstatus(sfLpModel) == MOI.Success\n", "@show JuMP.primalstatus(sfLpModel) == MOI.FeasiblePoint\n", "\n", "println(\"Objective value: \", JuMP.objectivevalue(sfLpModel))\n", "println(\"Optimal solution is x = \\n\", JuMP.resultvalue.(x))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Manual + optimizer\n", "\n", "### need to attach!" ] }, { "cell_type": "code", "execution_count": 48, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0.000059 seconds (39 allocations: 1.016 KiB)\n", "JuMP.hasresultvalues(sfLpModel) = true\n", "JuMP.terminationstatus(sfLpModel) == MOI.Success = true\n", "JuMP.primalstatus(sfLpModel) == MOI.FeasiblePoint = true\n", "Objective value: 4.923076923076923\n", "Optimal solution is x = \n", "[0.423077, 0.346154, 0.692308, 0.0]\n" ] } ], "source": [ "#MODEL INITIALIZATION\n", "#--------------------\n", "\n", "sfLpModel = Model(mode = JuMP.Manual, optimizer = GLPK.GLPKOptimizerLP())\n", "\n", "#Problem construction\n", "#--------------------\n", "\n", "@variable(sfLpModel, x[1:n] >= 0) # Models x >=0\n", "for i in 1:m\n", " @constraint(sfLpModel, sum(A[i,j]*x[j] for j in 1:n) == b[i])\n", "end\n", "\n", "@objective(sfLpModel, Min, sum(c[j]*x[j] for j in 1:n)) # minimize c'x \n", "\n", "#SOLVE IT\n", "#--------\n", "\n", "# Attention!\n", "MOIU.attachoptimizer!(sfLpModel)\n", "\n", "# finally optimize the model\n", "@time begin\n", "status = JuMP.optimize(sfLpModel) # solves the model\n", "end\n", "\n", "# TEST SOLVER STATUSES and DISPLAY THE RESULTS\n", "#---------------------------------------------\n", "@show JuMP.hasresultvalues(sfLpModel)\n", "@show JuMP.terminationstatus(sfLpModel) == MOI.Success\n", "@show JuMP.primalstatus(sfLpModel) == MOI.FeasiblePoint\n", "\n", "println(\"Objective value: \", JuMP.objectivevalue(sfLpModel))\n", "println(\"Optimal solution is x = \\n\", JuMP.resultvalue.(x))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Solving a standard form Mixed Integer Programming Problem\n", "\n", "Let us try to write the JuMP code for the following standard form optimization problem:\n", "\n", "$$\n", "\\begin{align}\n", "& \\text{minimize} && c^T x + d^T y\\\\\n", "& \\text{subject to} && A x + B y= f \\\\\n", " & && x \\succeq 0, y \\succeq 0 \\\\\n", " & && x \\in \\mathbb{R}^n, y \\in \\mathbb{Z}^p\n", "\\end{align}\n", "$$\n", "\n", "Here, $A \\in \\mathbb{R}^{m \\times n}, B \\in \\mathbb{R}^{m \\times p}, c \\in \\mathbb{R}^n, d \\in \\mathbb{R}^p, f \\in \\mathbb{R}^m$. The data were randomly generated. The symbol $\\succeq$ ($\\preceq$) stands for element-wise greater (less) than or equal to." ] }, { "cell_type": "code", "execution_count": 49, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "3-element Array{Float64,1}:\n", " 0.1716\n", " 0.361 \n", " 0.0705" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "n = 5\n", "p = 4\n", "m = 3\n", "A=\n", "[0.7511 -0.1357 0.7955 -0.4567 0.1356\n", "-0.6670 -0.3326 0.1657 -0.5519 -0.9367\n", " 1.5894 -0.1302 -0.4313 -0.4875 0.4179]\n", "\n", "B=\n", "[-0.09520 -0.28056 -1.33978 0.6506\n", " -0.8581 -0.3518 1.2788 1.5114\n", " -0.5925 1.3477 0.1589 0.03495]\n", "\n", "c=[0.3468,0.8687,0.1200,0.5024,0.2884]\n", "\n", "d=[0.2017,0.2712,0.4997,0.9238]\n", "\n", "f = [0.1716,0.3610,0.0705]\n" ] }, { "cell_type": "code", "execution_count": 50, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "A JuMP Model\n", "Termination status of the problem is Success and primal status is FeasiblePoint\n", "Optimal objective value = 1.070277955983598\n", "Optimal x = [0.0654907, 0.0, 1.62986, 0.0, 1.22151]\n", "Optimal y = [0.0, 0.0, 1.0, 0.0]" ] } ], "source": [ "sfMipModel = Model()\n", "\n", "@variable(sfMipModel, x[1:n] >=0)\n", "@variable(sfMipModel, y[1:p] >= 0, Int)\n", "\n", "@objective(sfMipModel, Min, sum(c[i] * x[i] for i in 1:n)+sum(d[i]*y[i] for i in 1:p))\n", "\n", "for i in 1:m\n", " @constraint(sfMipModel, sum(A[i,j]*x[j] for j in 1:n)+ sum(B[i,j]*y[j] for j in 1:p) == f[i])\n", "end\n", "\n", "print(sfMipModel, \"\\n\")\n", "\n", "solver = GLPK.GLPKOptimizerMIP()\n", "MOIU.resetoptimizer!(sfMipModel, solver)\n", "MOIU.attachoptimizer!(sfMipModel)\n", "JuMP.optimize(sfMipModel) # solves the model\n", " \n", "t_status = JuMP.terminationstatus(sfMipModel)# == MOI.Success\n", "p_status = JuMP.primalstatus(sfMipModel)# == MOI.FeasiblePoint\n", "\n", "st = JuMP.terminationstatus(sfMipModel)\n", "print(\"Termination status of the problem is \", t_status,\" and primal status is \", p_status,\"\\n\")\n", "\n", "if JuMP.hasresultvalues(sfMipModel) && JuMP.terminationstatus(sfMipModel) == MOI.Success && JuMP.primalstatus(sfMipModel) == MOI.FeasiblePoint\n", " print(\"Optimal objective value = \", JuMP.objectivevalue(sfMipModel), \"\\nOptimal x = \", JuMP.resultvalue.(x), \"\\nOptimal y = \", JuMP.resultvalue.(y))\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Reference\n", "\n", "[1] M. Lubin and I. Dunning, “Computing in Operations Research using Julia”, INFORMS Journal on Computing, to appear, 2014. [arXiv:1312.1431](http://arxiv.org/abs/1312.1431)" ] } ], "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 }