{ "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": {} } ] }