{
 "metadata": {
  "language": "Julia",
  "name": "",
  "signature": "sha256:7bd1a30f0d38272fcaeaf39f938f2dd648a3becac47cd78582d1ac4446e46814"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Binary (or 0-1) knapsack problem\n",
      "Given a knapsack of some capacity $C$ and $n$ objects with object $i$ having weight $w_i$ and profit $p_i$, the goal is to choose some subset of the objects that can fit in the knapsack (i.e. the sum of their weights is no more than $C$) while maximizing profit.\n",
      "\n",
      "This can be formulated as a mixed-integer program as:\n",
      "$$\n",
      "\\begin{array}{ll}\n",
      "  \\mbox{maximize} & x' p \\\\\n",
      "    \\mbox{subject to} & x \\in \\{0, 1\\} \\\\\n",
      "  & w' x <= C \\\\\n",
      "\\end{array}\n",
      "$$\n",
      "\n",
      "$x$ is a vector is size $n$ where $x_i$ is one if we chose to keep the object in the knapsack, 0 otherwise."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Data taken from http://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html\n",
      "w = [23; 31; 29; 44; 53; 38; 63; 85; 89; 82]\n",
      "C = 165 \n",
      "p =  [92; 57; 49; 68; 60; 43; 67; 84; 87; 72];\n",
      "n = length(weights)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 16,
       "text": [
        "10"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "using Convex, GLPKMathProgInterface\n",
      "x = Variable(n, :Bin)\n",
      "problem = maximize(dot(p, x), dot(w, x) <= C)\n",
      "solve!(problem, GLPKSolverMIP())"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 17
    }
   ],
   "metadata": {}
  }
 ]
}