{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "title: Integer Programming\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Originally Contributed by**: Arpit Bhatia"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "While we already know how to set a variable as integer or binary in the `@variable` macro, \n",
    "this tutorial covers other JuMP features for integer programming along with some modelling techniques."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "using JuMP, Random\n",
    "\n",
    "Random.seed!(1234);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Modelling Logical Conditions\n",
    "Generally, in a mathematical programming problem, all constraints must hold. \n",
    "However, we might want to have conditions where we have some logical conditions between constraints.\n",
    "In such cases, we can use binary variables for modelling logical conditions between constraints."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Disjunctive Constraints (OR)\n",
    "Suppose that we are given two constraints $a'x \\geq b$ and $c' x \\geq d$, \n",
    "in which all components of $a$ and $c$ are non-negative. \n",
    "We would like to model a requirement that at least one of the two constraints is satisfied. \n",
    "For this, we defined a binary variable $y$ and impose the constraints:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{align*}\n",
    "a' x \\geq y b \\\\\n",
    "c' x \\geq (1 - y) d \\\\\n",
    "y \\in \\{0,1\\}\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = rand(1:100, 5, 5)\n",
    "c = rand(1:100, 5, 5)\n",
    "b = rand(1:100, 5)\n",
    "d = rand(1:100, 5)\n",
    "\n",
    "model = Model()\n",
    "@variable(model, x[1:5])\n",
    "@variable(model, y, Bin)\n",
    "@constraint(model, a * x .>= y .* b)\n",
    "@constraint(model, c * x .>= (1 - y) .* d);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Conditional Constraints ($\\implies$)\n",
    "Suppose we want to model that a certain linear inequality must be satisfied when some other event occurs. \n",
    "i.e. for a binary variable $z$, we want to model the implication"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{align*}\n",
    "z = 1 \\implies a^Tx\\leq b\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we know in advance an upper bound $a^Tx\\leq b$. Then we can write the above as a linear inequality"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{align*}\n",
    "a^Tx\\leq b + M(1-z)\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = rand(1:100, 5, 5)\n",
    "b = rand(1:100, 5)\n",
    "m = rand(10000:11000, 5)\n",
    "\n",
    "model = Model()\n",
    "@variable(model, x[1:5])\n",
    "@variable(model, z, Bin)\n",
    "@constraint(model, a * x .<=  b .+ (m .* (1 - z)));\n",
    "# If z was a regular Julia variable, we would not have had to use the vectorized dot operator"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Boolean Operators on Binary Variables\n",
    "The following table is useful when we want to model boolean operators in the form of \n",
    "linear inequalities that can be given to a solver."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| Boolean Expression | Constraint                           | \n",
    "|:----------         |                           ----------:|\n",
    "| $z=x \\lor y$       | $x \\leq z,  y \\leq z,  z \\leq x+y$   |\n",
    "| $z=x \\land y$      | $x \\geq z,  y \\geq z,  z+1 \\geq x+y$ | \n",
    "| $z= \\neg x$        | $z = 1 − x$                          | \n",
    "| $x \\implies y$     | $x \\leq y$                           | \n",
    "| $x \\iff y$         | $x = y$                              |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Modelling Integer Variables"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Integer Variables using Constraints\n",
    "We can add binary and integer restrictions to the domain of each variable using the `@constraint` macro as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "model = Model()\n",
    "\n",
    "@variable(model, x)\n",
    "@variable(model, y)\n",
    "@constraint(model, x in MOI.ZeroOne())\n",
    "@constraint(model, y in MOI.Integer());"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Semi-Continuous Variables\n",
    "A semi-continuous variable is a continuous variable \n",
    "between bounds $[l,u]$ that also can assume the value zero. ie.\n",
    "$$\n",
    "x \\in \\{0\\} \\cup \\{l,u\\}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$ a \\in MathOptInterface.Semicontinuous{Float64}(7.45, 22.22) $"
      ],
      "text/plain": [
       "a ∈ MathOptInterface.Semicontinuous{Float64}(7.45, 22.22)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = 7.45\n",
    "u = 22.22\n",
    "@variable(model, a)\n",
    "@constraint(model, a in MOI.Semicontinuous(l, u))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Semi-Integer Variables\n",
    "A semi-integer variable is a variable which asummes integer values\n",
    "between bounds $[l,u]$ and can also assume the value zero. ie."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "x \\in \\{0\\} \\cup (\\{l,u\\} \\cap \\mathbb{Z})\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$ b \\in MathOptInterface.Semiinteger{Int64}(5, 34) $"
      ],
      "text/plain": [
       "b ∈ MathOptInterface.Semiinteger{Int64}(5, 34)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = 5\n",
    "u = 34\n",
    "@variable(model, b)\n",
    "@constraint(model, b in MOI.Semiinteger(l, u))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the bounds specified in `MOI.Semiinteger` must be integral otherwise it would throw an error."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Special Ordered Sets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Special Ordered Sets of type 1 (SOS1)\n",
    "A Special Ordered Set of type 1 is a set of variables, \n",
    "at most one of which can take a non-zero value, all others being at 0. \n",
    "They most frequently apply where a set of variables are actually 0-1 variables: \n",
    "in other words, we have to choose at most one from a set of possibilities."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$ [u_{1}, u_{2}, u_{3}] \\in MathOptInterface.SOS1{Float64}([1.0, 2.0, 3.0]) $"
      ],
      "text/plain": [
       "[u[1], u[2], u[3]] ∈ MathOptInterface.SOS1{Float64}([1.0, 2.0, 3.0])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@variable(model, u[1:3])\n",
    "@constraint(model, u in MOI.SOS1([1.0, 2.0, 3.0]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that we have to pass MOI.SOS1 a weight vector which is essentially an ordering on the variables. \n",
    "If the decision variables are related and have a physical ordering, then the weight vector, \n",
    "although not used directly in the constraint, can help the solver make a better decision in the solution process."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Special Ordered Sets of type 2 (SOS2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A Special Ordered Set of type 2 is a set of non-negative variables, \n",
    "of which at most two can be non-zero, and if two are non-zero these must be consecutive in their ordering."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$ [v_{1}, v_{2}, v_{3}] \\in MathOptInterface.SOS2{Float64}([3.0, 1.0, 2.0]) $"
      ],
      "text/plain": [
       "[v[1], v[2], v[3]] ∈ MathOptInterface.SOS2{Float64}([3.0, 1.0, 2.0])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@variable(model, v[1:3])\n",
    "@constraint(model, v in MOI.SOS2([3.0, 1.0, 2.0]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The ordering provided by the weight vector is more important in this case as \n",
    "the variables need to be consecutive according to the ordering.\n",
    "For example, in the above constraint, the possible pairs are:\n",
    "* Consecutive\n",
    "  * (`x[1]` and `x[3]`) as they correspond to 3 and 2 resp. and thus can be non-zero \n",
    "  * (`x[2]` and `x[3]`) as they correspond to 1 and 2 resp. and thus can be non-zero \n",
    "* Non-consecutive\n",
    "  * (`x[1]` and `x[2]`) as they correspond to 3 and 1 resp. and thus cannot be non-zero"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.5.1",
   "language": "julia",
   "name": "julia-1.5"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}