{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "# Extended formulation"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "In this notebook, we show how to work with the extended formulation of a polyhedron.\n",
    "The convex hull of the union of polyhedra that are H-represented can be obtained\n",
    "as the projection of a H-representation [Theorem 3.3, B85].\n",
    "In order to use the resulting polyhedron as a constraint set in an optimization problem,\n",
    "there is no need to compute the resulting H-representation of this projection.\n",
    "Moreover, other operations such as intersection are also implemented between extended H-representations.\n",
    "We illustrate this with a simple example. We start by defining the H-representation of a square with JuMP."
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "[B85] Balas, E., 1985.\n",
    "*Disjunctive programming and a hierarchy of relaxations for discrete optimization problems*.\n",
    "SIAM Journal on Algebraic Discrete Methods, 6(3), pp.466-486."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "H-representation LPHRep{Float64}:\n4-element iterator of HalfSpace{Float64,SparseArrays.SparseVector{Float64,Int64}}:\n HalfSpace(  [1]  =  -1.0, 1.0)\n HalfSpace(  [2]  =  -1.0, 1.0)\n HalfSpace(  [1]  =  1.0, 1.0)\n HalfSpace(  [2]  =  1.0, 1.0)"
     },
     "metadata": {},
     "execution_count": 1
    }
   ],
   "cell_type": "code",
   "source": [
    "using JuMP\n",
    "model = Model()\n",
    "@variable(model, -1 <= x <= 1)\n",
    "@variable(model, -1 <= y <= 1)\n",
    "using Polyhedra\n",
    "square = hrep(model)"
   ],
   "metadata": {},
   "execution_count": 1
  },
  {
   "cell_type": "markdown",
   "source": [
    "In the following, `diagonal` and `antidiag` are projections of extended Hrepresentations of dimension 7\n",
    "hence `diamond` is a projection of an extended H-representation of dimensions 12."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "Polyhedra.Projection{LPHRep{Float64},Base.OneTo{Int64}}(HyperPlane(  [1 ]  =  1.0\n  [3 ]  =  -1.0\n  [5 ]  =  -1.0, 0.0) ∩ HyperPlane(  [2 ]  =  1.0\n  [4 ]  =  -1.0\n  [6 ]  =  -1.0, 0.0) ∩ HyperPlane(  [1 ]  =  1.0\n  [8 ]  =  -1.0\n  [10]  =  -1.0, 0.0) ∩ HyperPlane(  [2 ]  =  1.0\n  [9 ]  =  -1.0\n  [11]  =  -1.0, 0.0) ∩ HalfSpace(  [3 ]  =  -1.0\n  [7 ]  =  -3.0, 0.0) ∩ HalfSpace(  [4 ]  =  -1.0\n  [7 ]  =  -3.0, 0.0) ∩ HalfSpace(  [3 ]  =  1.0\n  [7 ]  =  1.0, 0.0) ∩ HalfSpace(  [4 ]  =  1.0\n  [7 ]  =  1.0, 0.0) ∩ HalfSpace(  [5 ]  =  -1.0\n  [7 ]  =  -1.0, -1.0) ∩ HalfSpace(  [6 ]  =  -1.0\n  [7 ]  =  -1.0, -1.0) ∩ HalfSpace(  [5 ]  =  1.0\n  [7 ]  =  3.0, 3.0) ∩ HalfSpace(  [6 ]  =  1.0\n  [7 ]  =  3.0, 3.0) ∩ HalfSpace(  [7 ]  =  -1.0, 0.0) ∩ HalfSpace(  [7 ]  =  1.0, 1.0) ∩ HalfSpace(  [8 ]  =  -1.0\n  [12]  =  -3.0, 0.0) ∩ HalfSpace(  [9 ]  =  -1.0\n  [12]  =  1.0, 0.0) ∩ HalfSpace(  [8 ]  =  1.0\n  [12]  =  1.0, 0.0) ∩ HalfSpace(  [9 ]  =  1.0\n  [12]  =  -3.0, 0.0) ∩ HalfSpace(  [10]  =  -1.0\n  [12]  =  -1.0, -1.0) ∩ HalfSpace(  [11]  =  -1.0\n  [12]  =  3.0, 3.0) ∩ HalfSpace(  [10]  =  1.0\n  [12]  =  3.0, 3.0) ∩ HalfSpace(  [11]  =  1.0\n  [12]  =  -1.0, -1.0) ∩ HalfSpace(  [12]  =  -1.0, 0.0) ∩ HalfSpace(  [12]  =  1.0, 1.0), Base.OneTo(2))"
     },
     "metadata": {},
     "execution_count": 2
    }
   ],
   "cell_type": "code",
   "source": [
    "diagonal = convexhull(translate(square, [-2, -2]), translate(square, [2, 2]))\n",
    "antidiag = convexhull(translate(square, [-2,  2]), translate(square, [2, -2]))\n",
    "diamond = diagonal ∩ antidiag"
   ],
   "metadata": {},
   "execution_count": 2
  },
  {
   "cell_type": "markdown",
   "source": [
    "We don't need to compute the result of the projection to solve an optimization problem\n",
    "over `diamond`."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "2-element Array{Float64,1}:\n 0.0\n 2.0"
     },
     "metadata": {},
     "execution_count": 3
    }
   ],
   "cell_type": "code",
   "source": [
    "import GLPK\n",
    "model = Model(GLPK.Optimizer)\n",
    "@variable(model, x[1:2])\n",
    "@constraint(model, x in diamond)\n",
    "@objective(model, Max, x[2])\n",
    "optimize!(model)\n",
    "value.(x)"
   ],
   "metadata": {},
   "execution_count": 3
  },
  {
   "cell_type": "markdown",
   "source": [
    "In the optimization problem, above, the auxiliary variables of the extended formulation\n",
    "are transparently added inside a bridge.\n",
    "To manipulate the auxiliary variables, one can use the extended H-representation directly instead of its projection."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "12-element Array{Float64,1}:\n  0.0 \n  2.0 \n -0.75\n -0.25\n  0.75\n  2.25\n  0.25\n -0.75\n  2.25\n  0.75\n -0.25\n  0.75"
     },
     "metadata": {},
     "execution_count": 4
    }
   ],
   "cell_type": "code",
   "source": [
    "import GLPK\n",
    "model = Model(GLPK.Optimizer)\n",
    "@variable(model, x[1:12])\n",
    "@constraint(model, x in diamond.set)\n",
    "@objective(model, Max, x[2])\n",
    "optimize!(model)\n",
    "value.(x)"
   ],
   "metadata": {},
   "execution_count": 4
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "*This notebook was generated using [Literate.jl](https://github.com/fredrikekre/Literate.jl).*"
   ],
   "metadata": {}
  }
 ],
 "nbformat_minor": 3,
 "metadata": {
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.0.5"
  },
  "kernelspec": {
   "name": "julia-1.0",
   "display_name": "Julia 1.0.5",
   "language": "julia"
  }
 },
 "nbformat": 4
}