{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### CVXBOOK extra exercise 3.18\n",
      "*Heuristic suboptimal solution for Boolean LP*. Solution by Chris Dembia."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import pylab as pl\n",
      "import numpy as np\n",
      "from cvxpy import *"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 85,
     "trusted": false
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "Create data"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = 100\n",
      "m = 300\n",
      "np.random.seed(0)\n",
      "A = np.matrix(np.random.rand(m, n))\n",
      "b = A * np.ones((n, 1)) / 2.0\n",
      "c = -np.random.rand(n, 1)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 86,
     "trusted": false
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "Solve the relaxed problem"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "x = Variable(n)\n",
      "objective = Minimize( c.T * x)\n",
      "constraints = [A * x <= b, x >= 0, x <= 1]\n",
      "p = Problem(objective, constraints)\n",
      "L = p.solve()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 87,
     "trusted": false
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print 'Lower bound: {}'.format(L)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Lower bound: -34.4172236278\n"
       ]
      }
     ],
     "prompt_number": 88,
     "trusted": false
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "x_rlx = np.matrix(p.variables()[0].value)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 89,
     "trusted": false
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "Threshold the relaxed solution"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "N_t = 100\n",
      "tvalues = np.linspace(0, 1, 100)\n",
      "J = np.empty(N_t)\n",
      "max_constr_violation = np.empty(N_t)\n",
      "feasible = np.nan * np.zeros(N_t)\n",
      "\n",
      "for i, t in enumerate(tvalues):\n",
      "    x_hat = x_rlx > t\n",
      "    J[i] = c.T * x_hat\n",
      "    max_constr_violation[i] = np.max(A * x_hat - b)\n",
      "    if max_constr_violation[i] <= 0:\n",
      "        feasible[i] = 0"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 90,
     "trusted": false
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "pl.plot(tvalues, J, label='objective')\n",
      "pl.plot(tvalues, max_constr_violation,\n",
      "        label='max constraint violation')\n",
      "pl.plot(tvalues, feasible -15, lw=2, c='k',\n",
      "        label='feasible range')\n",
      "pl.xlabel('t')\n",
      "pl.legend(frameon=False)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 94,
       "text": [
        "<matplotlib.legend.Legend at 0x5083ed0>"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAAZkAAAEVCAYAAAAy15htAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XlYVNX/B/D3wLCIgMgim4goi+AWfgUxDCfLJU1MxX3X\n1LTtW1qJGaItkKX1q1xKC1xyTxNzaVGRJBRKyq87JiCrsggomyzn98c0EyggAsMwzPv1PPd5Zu7c\ne+5nTjYfzjn3niMRQoCIiEgVdNQdABERtV5MMkREpDJMMkREpDJMMkREpDJMMkREpDJMMkREpDIa\nnWSKi4vbjBw58qCLi0tC3759f79w4UL3K1euuPXu3fsvBweHlNWrVy9Sd4xERNpMqu4AGmP37t3j\nnZycEg8ePDjyhx9+eHblypVB2dnZlp9//vnL3t7esV5eXnEBAQF7HR0dk9UdKxGRNtLoloyPj8/p\nRYsWrQaA8vJyabt27fKTkpI6+/n5RRkaGpaMGTNmX2RkpEzNYRIRaS2Nbsm4ubldAYBnnnnmSFRU\nlN+JEyeePH/+fA/F53Z2dukZGRm2Vc+RSCSc4oCIqAGEEJJHPUejWzIKR44ceebUqVMDZs2aFVZ1\nvxBCIpVKy+8/XgjBTQgsX75c7TG0lI11wbpgXdS9NZRGJ5mwsLBZ586d6wUAnp6e8Xfu3DHJysqy\nUnyelpZmb2trm3H/eXfv3W3OMImItJZGJ5n8/Px227ZtmwoAsbGx3p07d05yc3O7EhUV5VdSUmIY\nERHhP3jw4J/vP2/i3onNHywRkRbS6DGZOXPmfD1x4sSdzs7O12xsbDI3btw4t7y8XDphwoRdZWVl\neosXL/64Q4cOt+4/7869O+oIt8WRyWTqDqHFYF38i3XxL9ZF40ka09emiSQSifDc4Imz88+qOxQi\nIo0hkUggtHXg/1GxJUNE1Dy0M8mUMskQETUH7UwybMkQETULrUwyJeUlKK984PEZIiJqYlqZZIz1\njfmsDBFRM9DKJGOib8JxGaJHIJPJcOjQoRo/c3JywsWLFxtUbnh4OMaNGwcAiIyMhJeXV4NjpJZJ\no5+TaSgTAxOOyxA9AolEAomk5rtXExMTm+QaMpkMcXFxTVIWtRxa2ZIxNTBlS4aoFtu3b4eLiwss\nLCwwffp03L0r71qOjo6Gq6srLCws8OKLL6KsrAwA0LlzZ2VLJiYmBn369IGJiQmGDRuGjAz5rE73\n7t3DwoULYWlpic6dO2PHjh04ffo0Zs+eje+++w7+/v44efIkvLy8kJmZiTZt2qCoqEgZU48ePfDT\nTz8BAN5991107NgRVlZWWLFiRXNWDTWAViYZE322ZIhqcuHCBbzyyivYunUrEhISUFRUhMDAQADy\n5HPw4EH88ccf+PXXX7Fu3ToAULZw8vLyMGbMGISGhiIjIwOenp6YPHkyAOCDDz5ASkoKEhISsH37\ndixcuBCurq4ICwtDQEAAIiIilJMw2tjYwNPTEz//LJ8R6tq1a7h16xaefvppbN68GUeOHMGZM2cQ\nGxuL/fv3Y/Pmzc1dTfQItDPJGJigoLRA3WEQ1UgiaZqtIfbu3Ytp06bBx8cH5ubm+OCDD7Br1y4A\nwKuvvgo3Nzd07twZ77zzDvbv3688TwiBQ4cOwdfXF0OGDIGxsTHef/99xMfHo6CgANu3b8e7776L\n9u3b4/HHH0d4eDjKyspqneH3ueeeww8//AAA2L9/PwICAqCjo4Nt27Zh6dKlsLe3h5OTE5YtW4aI\niIiGfVlqFto5JsOBf2rB1DnTU2ZmJlxcXJTvHR0dkZ2djfLycnTq1Em538nJCbduVZ8WMDU1Ffv2\n7YOOzr9/u0okEty6dQupqano3Lmzcv+oUaPqjOO5557Dk08+CUCeZEJDQ5XX8Pf3r3asr6/vo31J\nalZa25JhdxnRg2xtbZGSkqJ8n5ycDEtLS0ilUiQn/7uKeVJSEjp27PjAubNmzUJlZaVy+9///gdn\nZ2dYW1tXK/err77C5cuXa72ZwNXVFWZmZjh8+DBSU1Ph5+envEZUVJSy/Nu3b2Pnzp1NWQXUxLQz\nybAlQ1SjMWPGYNu2bThz5gxycnKwZMkSTJgwAQCwdu1aXL16FYmJiXjvvfeU+wF5i2X48OE4evQo\nfv75ZxQVFeHTTz/F7NmzAQABAQF45513kJubizNnzmDp0qUwMzMDAJSWltYYy+jRo/HKK68gICBA\nuW/8+PEICgpCamoqbt68idGjRyu71ahl0t4kw5YM0QN69OiBNWvWYOrUqXBxcYGJiQlCQkIAAC+8\n8AKGDh0Kb29vDBkyRJlAFCwtLbF161YsWrQIHTp0wMGDB7Fjxw4AwIoVK9C+fXs4OztjypQp+PLL\nL2FjY4PevXsjOjoaU6dOfeA26dGjRyMxMRETJ/67/tO8efPQr18/eHl5oUePHujbty/mz5/fDDVD\nDaWVU/1/dvozXM29is+f+Vzd4RBpPCcnJxw6dAgeHh7qDoVUiFP9PwLeXUbUNO7du4eCggLo6+ur\nOxRqobQzyXBMhqhJuLi44PHHH0eXLl3UHQq1UNp5CzPvLiNqElXvOCOqCVsyRESkMhqfZBYsWLDe\nxcUloUePHud/+eWXp69cueLWu3fvvxwcHFJWr169qKZz2JIhImoeGt1dduTIkWfS09PtEhISXK5f\nv97l6aef/sXJySnx888/f9nb2zvWy8srLiAgYK+jo2O1Nr2pgSkH/omImoFGt2Ryc3PNZ8yYsRkA\nunTpcr1t27aFSUlJnf38/KIMDQ1LxowZsy8yMlJ2/3nsLiMiah4a3ZKZMmXKt4rXERER/hUVFbo2\nNjaZin12dnbpGRkZtvef90noJyiIKkBwSTBkMhlkMlkzRUxEpBkiIyMRGRnZ+IIUs6Bq6lZYWGj0\n4osvfuHm5nb55MmTfj4+PjGKz9avX//CRx99tLjq8fKvLIThe4ai8F6hIKLWa8aMGeKLL7545PNk\nMpk4dOhQncckJiYKS0vLRyp35syZYu3atXUec+LECdG3b9+HljVw4EBljPUpt7H++e185N9ojW7J\n3L1711gmk0UOGTLkpz///PMxAwOD0qysLCvF52lpafbdunW7XNO5ii4zIz2j5guYiDTCiRMnVFJu\nWFhYk5X1zxP4TV5uU9PoMZkNGza8MGjQoOMffPDBUkNDwxKJRCLc3NyuREVF+ZWUlBhGRET4Dx48\n+OeazuUdZkQPSkpKQo8ePfD222/DxMQEffr0wa+//oo+ffrA2NgYCxYsUB67fv16dOrUCUZGRujf\nvz8uX5b/PffUU0/h66+/BgCcPXsWXbt2RXFx8QPX2r9/v3K25RkzZihX2qxtZc7g4GAsX74cI0eO\nRNu2bTFw4EDk5OQAAH755Rd4eHigbdu28PPzQ2pqKkJDQ7Flyxa8/PLLWL16NTZv3oznn38e/v7+\nykk3g4KCYGNjA2NjYwwePFi5fIFMJsPhw4cBAMbGxtizZw9sbW1hZWWFjRs3AgC6deuGnJwcmJqa\nVvteGRkZMDIyemBlzx9//BEzZ87E2rVrAQDx8fHo168f2rVrB5lMhoSEhAfqqLCwEGPHjoWZmRks\nLCywYMECVFZW4oUXXsDJkyfh7++P7777rl7lRkZG4tlnn0VgYCBMTU3h6uqKM2fO1PNfRiM0pPnT\nUrapU6dutbW1TXd2dk5wdnZOcHFxuXry5Ek/d3f3i87OzgkbNmyYf/85+Ke7rPf63uKP9D8a1Xwk\nam0SExOFVCoVn3zyicjPzxcDBw4U1tbW4uLFiyI+Pl7o6emJ1NRUkZOTI8zMzMT58+dFUVGRmDdv\nnpgzZ44QQohLly4Je3t7kZOTI/r3719jt1NCQoLo0KGDOHPmjMjOzhYymUx89tln4vz588LCwkLE\nxMSInJwcMXbsWPHSSy8JIYRYvny56NChgzhx4oTIzc0Vjz/+uPjggw+EEELY29uLiIgIUVpaKhYs\nWCBeffVVIUT1bqSwsDBhZGQk9u7dK0pLS8Wff/4pOnXqJG7cuCEKCgrEs88+K959910hRPXuMj09\nPTFjxgyRl5cndu/eLYyMjERlZaVISkqqtbusf//+4vvvv1d+VysrK1FeXq6Mp6SkRDg4OIhNmzaJ\nO3fuiFWrVolevXoJIap3l3366afC399fFBQUiBs3boiOHTuKU6dOPRBjfcs1NTUVq1evFoWFheLV\nV18VQ4YMqfe/DWhjd9nWrVun1bT/4sWLD52pz9TAlHeYUYskWdHAZS3vI5Y3bPJbfX19/Pe//wUA\nDBw4EN27d4e7uzsA+Xou+fn5sLS0RExMDLp164aioiLo6+sjM1N+z023bt0wffp0+Pn5wcPDA8OH\nD3/gGrt27cKkSZPg7e0NAFi3bh2ysrKqrcwJyJdtfuKJJ/D55/LJbAcNGqS8Uefpp5/G7du3Aci7\njlJTU1FWVoYvvvhC2Y0EoNrrPn36YOzYsQDkE3ueOHECDg4OyM/Ph56eHgoKHny0oby8HIGBgWjX\nrh3Gjh2LCRMmoLi4uFq591Os7Dlq1Cjlyp66urrKeE6fPg1zc3PMmTMHAPDGG2/g//7v/3Dp0qVq\n5QQEBGDy5MkwMTFBXl4epFIp8vPza7xmfcpt27YtXn/9dQDyheOio6Nr/Q5NRaOTTGOwu4xaqoYm\nh6ZiZPTvOKWOjs4D7xXWrVuHkydPol27dtDV1YWlpaXyswULFiA0NBRr1qyp8RppaWnVVuB0d3eH\nu7s7duzY8cDKnFlZWaioqAAA2NvbV4tF8UP//fffY+XKlVi6dCn69u2Ljz76CI899hgAVFs+wNra\nWvm6vLwcK1asQHx8PCwtLVFYWAhnZ+ca41Us0Fb1+9dl9OjRymRYdWVPhczMzGorjQJAp06dkJmZ\nWS3e7OxsvPXWW8jIyICjoyMqKyvrvO7DyrWzs1Pur23BuKam0WMyjcFnZYgaRgiBsLAwXLhwATEx\nMYiKisKUKVOqHbN8+XIMHToUQUFBNf7Fb21tjdTUVOX7s2fPYsuWLbWuzKloBdT0w1hWVoaSkhIc\nOHAA2dnZGD58OKZPn15j7FXPX7VqFSorK3H27FkcP34cgwcPrvU7P+oPsouLS40reyrc/z2FEEhJ\nSYGNjU214+bPn4/nnnsOf/31FyIiIh5IIPd7WLnNlViq0t4kw5YM0UPV1iVUUVGhbElcuXIFGzZs\nQH5+PoQQiIqKQlxcHA4ePAhjY2PlTQBVjRkzBlu3bkVcXBxyc3Px5ptvIjc3t86VOeuKbfDgwTh2\n7BjKy8thYGCANm3aAJD/qJaUlNT6HaRSKcrLy3H27Fls375d2f1WHxKJBGVlZbXWUU0reyrO8/Hx\nQXZ2NsLCwnDnzh18+OGHsLCwUHZL3h9jcXEx9u7di99//x25ubk1frdHKbc5aW+SYUuGqEZV/9q9\nf7VKxb7p06dDIpHAysoK8+bNQ1BQEOLi4rBp0yYsWLAAn332GaRSKT777DMEBQUhLy+vWhk9e/bE\n6tWrMXHiRHTt2hVdunTByy+/XOPKnIqupvtjUbzX09PDxo0bMWfOHJibm2Pbtm346quvAAD9+/fH\nO++8gy+//PKB81955RVcunQJ5ubmCA4Oxvvvv49du3bh2LFjtdZH1ffW1taws7OrtXVR08qeCvr6\n+jhw4ADWr18Pe3t7HD16FHv27HngGqGhoXj//fdhY2ODmJgYvPXWW1i4cCGKi4vh6+uLGTNm4NCh\nQ/Uqt7b6UzWtXBlTCIHlkcsBACtkK9QcERFRy8eVMR+RqT7vLiMiUjWtTTIckyEiUj3tTTIckyEi\nUjntTTJsyRARqZz2Jhm2ZIiIVE57k4yBCVfHJCJSMe1NMvrsLiMiUjWtTTKcIJOISPW0Nslw4J+o\nZmPHjoWRkRGys7ObtNxZs2Zh3bp1SEpKgpWVVY3HREZGwsvLq0mvS+qltbMwt5G2QVlFGcoryyHV\n0dpqIHrA/v37kZKSUm1W5aagWL0xKSmpScullk1rWzISiQTG+sbsMiOqolu3bgDk08PfunULBQUF\nmDp1KszNzeHi4oL9+/crj61tZcykpCQ8+eSTMDY2hpubm3IpY8XqjYr5soKDg9GuXTu4uLjgwIED\nD8QihMC7776Ljh07wsrKCitW1DwFVHBwMAIDA+Hr64tFixZBCIF58+bB0tIS7dq1w7hx45SrVMpk\nMmzZsgU9e/aEiYkJ5s2bpyzn2LFjcHd3R/v27fHhhx/C1tZWeV5ERATc3d1hamqKiRMn4s4d/m7U\nW0NWOtPkDf+sjCmEEB3XdBRJt5PqWgyOSOtIJBJRVFQkhJCvuLhgwQJRUFAgTp48KczNzcXff/9d\n58qYU6ZMEW+++aYoLS0V3377rejdu7eyrLVr14qkpCQhkUjE888/L/Ly8sTevXuFsbGxyMjIqLYq\nZHh4uOjfv79ITU0V169fF7179xbh4eEPxLt8+XJhYWEhIiMjRVlZmfj++++Fl5eXyMrKEllZWeI/\n//mP2Lp1qxBCiIEDBwovLy+RmJgoLl++LMzMzERMTIzIzc0VFhYW4siRI+L27dtiwoQJQiqVisLC\nQnHt2jVha2srYmNjRV5enpg2bZqYOXNmc/ynaFHQwJUxtbYlA/AOM2qZFLPjNsXWUEIIVFZWYufO\nnVi1ahVMTEzg5+eHyZMn49ChQ2jbti1iYmLQvXt3CCGgr6+vXFVSIpEgJycHeXl5mDRpEuLi4h4o\nG5Cv56JYbdLPzw9Hjx6tFvO2bduwdOlS2Nvbw8nJCcuWLUNERESN8T7zzDMYOHAgpFIpfH19sX//\nflhaWkIIUW3FS4lEgjlz5qBz585wc3NDr169kJOTg0OHDuGJJ57AsGHDYGZmhvfeew8VFRUQQmDn\nzp2YPHkyvLy80K5dO6xZs6bWOOhBGp9kTpw48eSKFSuWA8CVK1fcevfu/ZeDg0PK6tWrFz3sXN5h\nRlS7rKwslJaWwtTUFDo6OtDR0cG6detw69YtSCQSrFu3Dr1798awYcNw/vx5ZfL4+OOPoauri169\nesHT0xP79u17oGxjY2O0b99e+b5Lly64detWtWNSU1Ph7++vvPb48eMfOAaQJ46qK14WFhbilVde\nQa9evTB16tQHllRWrHIJ/LvSZXp6OhwcHJT7q75OTU3FmjVrlHF06NABeXl5ytU6qW4anWRCQ0OX\nzJw5M1wikQgAWLBgwfrPP//85YSEBJfw8PCZycnJjnWdzzvMqCVqSJdEbVtjWFhYoG3btigrK0Nl\nZSUqKyuRkpKCRYsW4Ztvvql1Zczk5GR88sknyMzMxNq1azFr1ixkZWVVK/vu3bvVFghLTEys9uMP\nyFd5jIqKUl779u3b2LlzZ42xVm0BvfXWW3Bzc8O5c+fw448/ok+fPrUeq2BtbY0bN24o31ddtdPW\n1hYrVqxQxnHv3j1cunRJuVon1U2jk0yfPn3Ojh079jsAqKys1ElOTnb08/OLMjQ0LBkzZsy+yMhI\nWV3nc2oZotpJpVKMGDECb731FvLy8vDXX3+hX79+SE9Pr3NlzMDAQHz88ccoKSmBgYEB9PT0oK+v\nr0x8iq48Rbn79u3Db7/9huHDh1dLjOPHj0dQUBBSU1Nx8+ZNjB49Gj/88MMDcd6fTBWrSZaUlODE\niRM4fPiwcjXJmo6XSCR45plncPLkSRw9ehR5eXnKmwx0dHQQEBCATZs2IS4uDoWFhViyZAmCgoKa\nsqpbNY2+d3fIkCE/ZWRk2CYlJXXOycmxsLa2vqn4zM7OLj0jI8O2pvOCg4MBANcvX0fcnTiM9Rjb\nPAETaYCqf+mvXbsW8+fPR+fOnWFubo7Q0FB4eHjAwcEBBw4cgJWVFby8vBAUFIQZM2Zg8+bN+Pjj\njzFnzhyEhoaiY8eO+Oqrr9CuXbtq40Q9e/aEsbExHBwc4ODggD179sDMzKza9efNm4fk5GR4eXmh\nvLwcs2bNwvz582uMt2rMy5Ytw5QpU7B69WqMGzcO7777Lt566y2MHz/+ge+n0KFDB3z77bd4+eWX\nkZeXh/fffx/btm2DVCqFh4cHPvzwQ0yZMgWZmZl46qmnalxSurWJjIxEZGRko8vR+JUxN2/ePCMp\nKanziy++uHbkyJEHY2Ji+gPAhg0bXrh7967x4sWLP656vGJlTAB46fBLcLVwxSv9XlFD5ETUUmRk\nZCA2NhajRo0CAPz999/w9vZGTk6OmiNrObR+ZUwLC4ucrKws5WPEaWlp9ra2thl1nWNiwO4yIpJ3\nDc6ZMwdxcXHIz8/Hhx9+iBEjRqg7rFah1SQZiUQi3NzcrkRFRfmVlJQYRkRE+A8ePPjnus7hLcxE\nBABWVlbYsGEDJkyYABsbGyQkJOCDDz5Qd1itgkaPySgo7i4LDQ1dMmHChF1lZWV6ixcv/rhDhw4P\n3u9YhamBKdLupDVPkETUogUEBCAgIEDdYbQ6Gj8m86iqjsls/nMzjiUew5bRW9QcFRFRy6b1YzIN\nwedkiIhUS7uTjD5XxyQiUiXtTjK8u4yISKW0O8nw7jIiIpXS7iTDlgwRkUppdZIxNTBlS4aISIW0\nOskY6xvj7r27jZ6tloiIatYqHsZsKKmOFAa6Bjh67SgMpYYqv56ORAe9bXrDzNBM5dciImoJtPph\nTACYfWA2EvMSm+Xa9yru4dzNc3C3dMcgp0FwtXCFBA1fvRAAvO290b1D9yaKkIioZg19GFPrk0xz\nKy0vxZm0MziWeAw38m88/IQ6VFRW4Ke/f4K3vTcCBwSiv0P/JoqSiKg6Jpl6UneSaWrFZcUI+zMM\nH/32EYz0jNBWr+0jlzHCZQRe7/86TAxMVBAhEbUGTDL11NqSjEJ5ZTn+yvwLFeLR1h2/V3EPX/7x\nJX65/guWPbEMc/8zF/q6+iqKkog0FZNMPbXWJNNYf2b+iSW/LMGJpBPQlcjXLtfT1cNY97F4zec1\n9LTuqeYIiUidmGTqiUmmbsVlxRCQ109+ST6+if8Ga+PWonuH7hjUeVCNS9c2JwkkeNzhcQzoNEDt\nsRBpEyaZemKSeXT3Ku5h94XdOH/rvLpDQVllGY5eO4rS8lLMfGwmhjkPg1RHfie+no4e3K3coSPR\n6se/iFSCSaaemGQ0nxACv6f/jrA/w/Bbym/K/Xfu3UFZRRmm9JqCab2mwcPKQ41RErUuTDL1xCTT\nup27eQ7bzm3D9v9tx63CWzV2qelKdLHo8UVYPnC5shVERHVjkqknJhntIITAvYp7NX6WXZSNWQdm\nobi8GNvHbIdDO4dmjo5I8zDJ1BOTDAFApajEquhV+OT0J5j3n3kw0DUAIJ/PbrbnbJgamKo5QqKW\nhcsvV7Fs2bL3OnbsmOrt7R2blpZmr+54qOXRkehgyYAliJgYASEESspLUFJegti0WHT7ohu2/LUF\nlaJS3WESabxW15L59ddfn1ixYsXyX3755enNmzfPiIqK8vv666/nKD5nS4Ye5kzqGbx85GVIdaQY\n7jJc3eFAqiPF1F5T0dG0o7pDIS3G7rJ/rFy5MqhTp043Zs6cGV5SUmLYq1evc1evXnVVfM4kQ/VR\nKSqx/X/bcTn7srpDQW5xLvZc3IMgvyAs9FoIXR1ddYdEWqihSabV3Vpz8+ZNax8fn9MAYGhoWHLv\n3r0H5kgJDg5WvpbJZJDJZM0WH2kGHYkOpvaaqu4wlF72fhnzf5iPbf/bhhe9Xqz1rrg+tn3QzbJb\nM0dHrVFkZCQiIyMbXU6ra8m89NJLX4wcOfLg0KFDfwSArl27/v333393VXzOlgxpqkpRibD4MBxL\nPFbj5xWiAqdunIJ5G3MEuAdgYOeBj3yLtgQSPGbzGNrqP/pEq9S6sSXzDxsbm8z09HQ7ACgpKTHU\n19ev+T5WIg2jI9HBnD5zMKfPnFqPqRSViEmJwd5Le7Hs+LJHvsa9inu4knMFw5yHYWL3ifDt5Kuy\nGRQkkMC8jTmnB2rlWl1LJi4uziswMDDk559/Hrx169ZpcXFxXp9//vnLis/ZkiGqW3ZRNvZd2oed\n53fi3M1zKrtOWWUZHNs54iXvlzCl5xS2nlo4DvxX8frrr6/ZvXv3eFdX16t79uwZZ2FhkaP4jEmG\nqGUQQuBY4jF8EfsFfr3xKwY5DWr0DAw2xjYY1HkQBnYeyGedmhiTTD0xyRC1PEl5SYhJiWl0OYl5\niTieeBxn0s7A2dwZRnpGTRDdv5zMnOBp4wlPW084mTk1aVefsb4xLI0sm6y8psYkU09MMkStX0l5\nCc7dPIeyirImK7NCVOBa7jXEZ8YjPiMeqQWpTVY2AOSV5GG252wEy4JbZCuMSaaemGSIqCXKKszC\nkmNLcPTaUXw0+CM83eXpJi2/nUE7GEgNGnw+k0w9MckQUUsWkxKD1358DddvX2/ScksrSjG4y2A8\n1+05DO06FCYGJg89R0eio1yOnUmmnphkiEgbZRdl44erP+D7y9/jeOLxWmcpr6pSVOLGazdgY2zD\nJFNfTDJERPXz2IbHEDYqDJ62npyFmYiImpZ5G3PcLrndqDKYZIiIqEbt27RHbnFuo8pgkiEiohqZ\ntzFHbnEuKioaXgaTDBER1ci8jTluF99GUVHDy2CSISKiGrU3bI/cklwUFja8DCYZIiKqkaK7jC0Z\nIiJqcookw5YMERE1OcWYDJMMERE1ufaG7dldRkREqsHuMiIiUhkmGSIiUhljfWOUVpSioPDhk2nW\nhkmGiIhqJJFI0N6wPbLuNnz+MiYZIiKqlXkbc+QUNnz+Mo1PMmFhYbM2b948Q/E+Ojra183N7Yqj\no2Pyjh07JqkzNiIiTdfYmZg1NsmUlZXpBQYGhrzxxhsfSSQS5QIxc+fO3Xjo0KERf/zxx3/eeeed\nd4uKiozUGScRkSZr36Y98kq1sCWjo6NTOWDAgFNDhw79UbGQTnJysqOVlVWWs7PzNUtLy2xfX9/o\nuLg4L3XHSkSkqczbmCP/XsOTjLQJY2lWurq6FSNGjDj0+++/91Xsu3nzprW9vX2a4r2dnV16RkaG\n7f3nBgcHK1/LZDLIZDIVR0tEpFkiIyMRGRmJhGsJSEnIanA5GptkavLP0srK5UGFEBKpVFp+/3FV\nkwwRET0orTd4AAAURklEQVRI8Qe4JFKCnbsrkR77Y4PK0YgkExISEnj48OHhVfctWrRo9XPPPfd9\n1X02NjaZ6enpdor36enpdra2thnNFScRUWvTvk17FImEBp+vEUkmMDAwJDAwMORhxzk4OKQUFBSY\nXrt2zdnMzCwvNjbW+5tvvpndHDESEbVG5m3MUQwtHJOpqurdZatXr140dOjQH/X09MpWrVr1Zk3d\nZUREVD/mbcxRKml4kpEIIR5+VCvyz7iNusMgItIIMSkxGLTqNZR8cQZVx7zrS2NvYSYiItUzb2OO\ncj0tfE6GiIhUz7yNOSr0mWSIiEgF2rdpD2GQ1+DzmWSIiKhWEiEFyho+OxeTDBER1aq4GJCUmDf4\nfCYZIiKqVWEhoHuPSYaIiFSgsBCQlrVv8PlMMkREVKuiIkCvouEtmVbxxD8RVSeRPPIzc0QqwZYM\nERGpDFsyRK0Qp06ipvLDD8Di/atw5Zu3GnQ+WzJERFSrwkLAWJd3lxERkQoUFQEmUiYZIiJSgcJC\noJ0+kwwREalAYSFgZsjnZIiISAWKioD2hmzJEBGRChQWApZGTDJERKQChYWAWVvOwkxERCpQVAS0\nbdvwGSQ0NskUFxe3GT9+/G4XF5eEvn37/v7nn38+BgDR0dG+bm5uVxwdHZN37NgxSd1xEhFpssJC\noG3bhp+vsU/8h4eHz7SxsclMSEhwiY2N9Z43b95XsbGx3s8///ymQ4cOjTAzM8vz8fE5PWrUqANG\nRkZF6o6XiEgTFRUBRg3vLdPclkxhYWHbyZMnbwcALy+vuLS0NPsbN2506tChwy1nZ+drlpaW2b6+\nvtFxcXFe6o6ViEhTaW1LZvHixR8rXq9du/bF3r17/3Xz5k1re3v7NMV+Ozu79IyMDNv7zw0ODla+\nlslkkMlkKo6WiEizREZGIjIyEgkJwPbtDS9HY5MMAOTk5FgsXLhwXWJiolNERIR/ampqRyGEcoRK\nCCGRSqXl959XNckQEdGDFH+A794NvPoqsHHjigaVoxFJJiQkJPDw4cPDq+5buHDhuuDg4OAXXnhh\nw44dOybp6OhUlpeXS9PT0+0Ux6Snp9vZ2tpmNH/EREStQ2O7yySaOiX4Sy+99IWHh8fFhQsXrqu6\n39PTM37Pnj3jzMzM8gYMGHDq/PnzPaq2ZiQSidDU70xE1NwsLYFLl4AOHSSo2lNUXxqbZJ544olf\nb9y40UlfX/8eABgbG9+Nj4/3PH78+KC5c+du1NPTK1u1atWb/v7+EVXPY5IhIqo/IyMgKwswNtay\nJNNQTDJERPVTWQlIpUB5OaCr27Ako7G3MBMRkWoVFQGGhoBOIzIFkwwREdVIPqVM48pgkiEioho1\n9s4ygEmGiIhq0dgpZQAmGSIiqgVbMkREpDJMMkREpDLsLiMiIpVhS4aIiFSmsJAtGSIiUhE+J0NE\nRCrD7jIiIlIZDvwTEZHKsCVDREQqwyRDREQqw+4yIiJSGbZkiIhIZZhkiIhIZdhdRkREKqPVLZmb\nN29ay2SySBcXlwQ/P7+o9PR0OwCIjo72dXNzu+Lo6Ji8Y8eOSeqOk4hIUzXFtDISIUTTRNPMVq5c\nGWRsbHz39ddfX/PFF1+8lJqa2jE0NHSJh4fHxYiICH8zM7M8Hx+f0+fOnetlZGRUpDhPIpEITf3O\nRESNUVIC7Nkj30pLH358VBRw+TLg6AhIJBIIISSPek1pQwJtCUaOHHmwY8eOqQBQXl4uNTMzy7tx\n40YnKyurLGdn52sA4OvrGx0XF+c1cODAk+qNloio/i5eBK5cabryhABiY4FvvgE8PYGZMwFz84ef\nFxgIdOrUuGtrbJLx9PSMBwAPD4+L2dnZlmfPnu2Tnp5uZ29vn6Y4xs7OLj0jI8P2/nODg4OVr2Uy\nGWQyWTNETET0cKdPAyNHAr6+gOSR2w2169oViI4GXFzqd3xkZOQ/W+Ouq7FJRuHixYseBw4cGLVw\n4cJ1QUFBK6s254QQEqlUWn7/OVWTDBFRS3HhAvDcc8DmzcDw4eqN5f4/wFesWNGgcjQiyYSEhAQe\nPny4WpWPHDny4LRp07ba2tpmDBky5KelS5d+YGNjk6m4AQAA0tPT7WxtbTOaP2IiokeTnAwMGwas\nXq3+BNOUNHbg/7///e+nrq6uVxcuXLhu7969AREREf5btmyZ7unpGb9nz55xZmZmeQMGDDh1/vz5\nHlVbMxz4J6LGuHMH2LJF3q3VlKKjgf/+F3jllaYtt6k0dOBfY5NMWlqa/cSJE3dmZmbadOnS5Xp4\nePhMW1vbjOPHjw+aO3fuRj09vbJVq1a96e/vH1H1PCYZotZPCODSJfndVE2ltBTYtUueYJ58Uj5u\noqvbdOVbWwNDhjRdeU1N65JMQzHJELVu8fHAokVAQgJgZdV05Uok8iSwYEHj77jSRFp3CzMRtR7Z\n2cCpU40rQwjgwAHg6FEgOBh4/nlAyl84teN/AiJSm6Ii4NNPgTVrAG9vQF+/ceX16gVcvQqYmjZN\nfNR4TDJEVKPffwd++UV15RcXA19/LX8e5PRpwNlZddci9WGSIaJqMjKApUuBH38EJk0C9PRUcx2J\nBNi3T96CodaLSYaolamsBH7+WT7v1KO6cwfYvl0+nnH5MrudqPGYZIg0SEkJkJJS82dlZcDBg8CX\nXwJmZoC//6O3QoyN2XVFTYtJhkgDFBQAGzYAn3win3pdp5ZFOgYMAHbuBLy8mnbeK6KGYpIhqsGd\nO8DWrfKpPtTt7l1g9275Mxo//QT07KnuiIjqj0mGtJoQ8oSicPMmsH49EB4OPPUU0Lev2kJTsrKS\nd2F17aruSIgeHZMMaa1Tp4DXX5fPfKuYHsTICJg2Tf7UuKOjeuMjag2YZKhVKiwEMjNr/qygAAgJ\nkbcOQkLkt+nWNsZBRI3DJEOtyl9/ybu7du0C2revefBbRweYPl3eJdbY9cuJqG5MMqRx7twBjh+X\nz1F14cK/+/PygNu3gXnz5Pvt7Govg4iaB2dhpocqKJA/AR4dre5IgIoKIDER8PGRL/DUp8+/4yn6\n+vKBek6KSNT0OAszqcTRo/KWwdChwKZNLWPswtUVaNtW3VEQUX0wyRAAeQvhwAHg2DH5bb0AkJ4u\nH+P45hvg6afVGx8RaSZ2l7UiWVnyZPEoysqA774DPvtMvjLfhAn/Treurw9MnCifaoSItBu7y7SU\nEPJB8JUr5a0OQ8NHL2PgQPmkiD4+TR8fEWk3Jhk1qKiQd0tdvtz4cvbuBXJygGXL5K0ODnoTUUui\n8d1lt2/fbt+9e/cL6enpdgAQHR3tO3v27G9KSkoMQ0NDl0yaNGlH1ePv7y67cUN+62tzKCoC9u8H\ntm2T317r49P4SQwffxwYN+7fO6yIiFShod1lGp9kZs2aFbZr164JRUVFRgDg4eFxMSIiwt/MzCzP\nx8fn9Llz53oZGRkVKY6/P8mYmwP29s0zY61UKp/kcNo0oHt31V+PiKipaOWYzJEjR54xNTUtsLa2\nvgkAycnJjlZWVlnOzs7XAMDX1zc6Li7Oa+DAgSdrOj8/Xz7wfe4cp0UnIlIFjU0yBQUFpiEhIYFH\njhx5JiIiwh8Abt68aW1vb5+mOMbOzi49IyPD9v5zg4ODAQC3bgHm5jJIJLJmipqISDNERkYiMjKy\n0eVobJJ58803Vy1btuy9tm3bFir2/dMVpmyTCCEkUqm0/P5zFUnmyBHg77+bI1oiIs0ik8kgk8mU\n71esWNGgcjQiyYSEhAQePnx4eNV9aWlp9idPnhyoeO3h4XHx6NGjwxQ3AABAenq6na2tbUZt5d64\nAXTqpLq4iYi0ncYP/AOAk5NTYmJiohMAeHp6xu/Zs2ecmZlZ3oABA06dP3++R9XWTNWB/2XL5A8c\nBgWpKXAiIg2hlQP/ChKJRJkpV69evWjo0KE/6unpla1aterNmrrLFFJSgCqtQSIiamKtoiXzKKq2\nZAYNks8uzHm5iIjq1tCWTAuYU1d9btwAHBzUHQURUeultS0ZIYA2bYDcXK6OSET0MGzJPKKsLPns\nwkwwRESqo7VJJiWFXWVERKrGJENERCqjtUmGg/5ERKqntUkmJYVP+xMRqZpWJxm2ZIiIVItJhoiI\nVEZrkwzHZIiIVE8rH8YsKxMwMgIKCwE9PXVHRETU8vFhzEeQkQFYWTHBEBGpmlYmGY7HEBE1DyYZ\nIiJSGa1MMhz0JyJqHlqZZNiSISJqHlqbZPi0PxGR6mltkmFLhohI9bQyyXBMRi4yMlLdIbQYrIt/\nsS7+xbpoPI1NMrm5uebGxsZ3XVxcElxcXBLefPPNVQAQHR3t6+bmdsXR0TF5x44dk2o6Nz8fsLZu\n3nhbIv4P9C/Wxb9YF/9iXTSeVN0BNFRCQoLLtGnTtq5fv35B1f1z587deOjQoRFmZmZ5Pj4+p0eN\nGnXAyMioqOoxdnaAjsamVyIizaGxP7XXrl1zjouL8/Lw8Lg4YsSIQxkZGbbJycmOVlZWWc7Oztcs\nLS2zfX19o+Pi4rzuP5ddZUREzUQIoZHbt99+O/njjz9eVFlZKfn6669njx07dm9sbKzXpEmTtiuO\nWbJkSciOHTsmVj0PgODGjRs3bo++NeS3WmO7yyZPnrxd8Xr27NnfrFy5MkgikYiqE7gJISRSqbS8\n6nkNmeCNiIgaRiOSTEhISODhw4eHV933+uuvrxk0aNDxdu3a5QNAmzZtim1sbDLT09PtFMekp6fb\n2draZjR3vEREJKexU/0HBgaGGBgYlAYHBwcfOHBg1HfffTd2y5Yt0z09PeP37NkzzszMLG/AgAGn\nzp8/3+P+1gwRETUPjU0y+fn57QICAvZev369i6ur69UtW7ZMt7Kyyjp+/PiguXPnbtTT0ytbtWrV\nm/7+/hHqjpWISGupewBfldvbb7/9nr29faqXl1dsamqqfdXP9u3bN9rJyel6ly5d/j5+/PiT6o5V\nnXWxadOmOS4uLle7du167aOPPlqs7ljVWReKbf78+RvCw8NnqDtWddZFTEyMj4eHx4UuXbr8vWHD\nhvnqjlWddfHll1/Oc3Z2TnBxcbm6cePG59Udq6q348ePPxkcHLz8/v0N+d1U+5dR1RYVFfXEU089\n9YsQAuHh4TNmz579teKzu3fvtu3ateu17Oxsi6tXr7q4u7tfVHe86qqL3Nzc9i4uLlfz8/NNCwsL\njfr163f63LlzPdUdszrqQrEdO3ZskLGx8Z3NmzdPV3e86qqL8vJy3a5du167ePGie3FxsWHPnj3P\n5ebmtld3zOqoC8XvRVFRUZuqr9Uds6q2kJCQJZ06dUpesWJFUNX9Df3d1NjnZB7mxIkTT06dOnUb\nAEyYMGHXr7/++oTis99//72vr69vtIWFRY6Li0uClZVVVnJysqP6olWtuuri5s2b1uPGjdtjampa\nYGRkVNSvX78zV65ccVNftKpVV10AQFFRkdHKlSuD5s+f/6Vo5Xci1lUXZ8+e7ePk5JTo7u5+ydDQ\nsCQqKsrP2Nj4rvqiVa266kIqlZbr6upWlJaWGpSWlhro6upWtOZx3j59+pwdO3bsd/f/+2/o72ar\nTTI3b960trOzSwcAQ0PDknv37ukrPrt161YHe3v7NMV7Ozu79IyMDFt1xNkc6qqLbt26XX7//fff\nBuSzKERERPj7+PicVlesqlZXXQDA22+//f4bb7zxkYmJyR31RNh86qqL69evd5FKpeXDhg072rNn\nz/9t3759sp6eXpn6olWtuurCwMCgdPz48bvt7e3THBwcUiZMmLCrNdfFkCFDfurdu/df9+9v6O9m\nq00y9z8zo6urW1HbZ0IISWv+R1NXXSisX79+wZNPPnli9erVizp27JjavBE2n7rq4rfffns8Ozvb\ncsSIEYdaeysGqLsuKisrdc6dO9crLCxs1unTp33CwsJmXbp0yV09kapeXXWRkJDgcuTIkWfS0tLs\nU1NTO/7www/PXrt2zVk9kapPQ383NeI5mYao+sxMSUmJob6+/r2aPgPkz9PY2NhkqiPO5lBXXQDy\n+d5u3brVITY21lvx11xrVVddREdH+/7222+Pu7u7X8rOzrbU09Mr09fXvzdp0qQd6otYdR72/8iA\nAQNOKZ4zGzRo0PELFy50d3d3v6SueFWprrqIj4/3fOqpp46ZmZnlAcDgwYN/jo+P93R2dr6mrnjV\nocG/m+oeZFLVFhsb6/XUU0/9UllZKdm8efP0l1566XPFZ6Wlpfqurq5XFANYnp6eZ9Udr7rqIi4u\nrm+/fv1OV1ZWStQdp7rrouoWHBy8vLUP/NdVF4WFhUbu7u4Xs7KyLIuKitr069fvdEJCgrO6Y1ZH\nXVy8eNHd29v7jGLg39vb+8zly5fd1B2zKrfw8PAZ999d1tDfzVbbkvHy8orr1avXOQcHhxRXV9er\nu3fvHr9kyZLQfv36nRk9evT+5cuXr+jTp89ZU1PTgk2bNj2v7nhVqa66yM3NNb9y5Yqbq6vrVcXx\na9eufXHIkCE/qTNmVXnYvwt1x9ecHlYX77333rInnnjiVyGEZPHixR+35r/cH1YX06ZN26oYp3jt\ntdc+cXNzu6LumFVNIpEIAGjs76bGPoxJREQtX6sd+CciIvVjkiEiIpVhkiEiIpVhkiFqIfLz89tt\n3rx5hrrjIGpKTDJELcTt27fbh4eHz1R3HERNiUmGqIWYN2/eV2fOnOm3bNmy99QdC1FT4S3MRC1E\ncnKy48yZM8NPnDjxpLpjIWoqbMkQtRBCC+ZLI+3DJENERCrDJEPUglRWVvL/SWpV+A+aqIWwsLDI\nyczMtAkJCQlUdyxETYUD/0REpDJsyRARkcowyRARkcowyRARkcowyRARkcowyRARkcowyRARkcow\nyRARkcowyRARkcowyRARkcowyRARkcowyRARkcowyRARkcowyRARkcowyRARkcowyRARkcowyRAR\nkcowyRARkcowyRARkcr8P3ACua8VT9khAAAAAElFTkSuQmCC\n",
       "text": [
        "<matplotlib.figure.Figure at 0x4bd8710>"
       ]
      }
     ],
     "prompt_number": 94,
     "trusted": false
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "U = np.min(J[np.where(max_constr_violation <= 0)])\n",
      "print('Upper bound: {}'.format(U))\n",
      "print('Gap: {}'.format(U - L))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Upper bound: -33.5772513453\n",
        "Gap: 0.839972282506\n"
       ]
      }
     ],
     "prompt_number": 92,
     "trusted": false
    }
   ],
   "metadata": {}
  }
 ]
}