Knapsack_Lp_Milp.ipynb

{
  "cells": [
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "source": [
        "#r \"nuget:Google.OrTools\"\n",
        "\n",
        "using Google.OrTools.LinearSolver;\n",
        "using System.Linq; "
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/html": "<div><div></div><div></div><div><strong>Installed Packages</strong><ul><li><span>Google.OrTools, 9.3.10497</span></li></ul></div></div>"
          },
          "execution_count": 1,
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "source": [
        "//We prepare a function to call the solver solve. Code reuse!\n",
        "public static void SolveAndPrint(this Solver solver, int nItems, double[] weights)\n",
        "{\n",
        "    var resultStatus = solver.Solve();\n",
        "\n",
        "    // Check that the problem has an optimal solution.\n",
        "    if (resultStatus != Solver.ResultStatus.OPTIMAL)\n",
        "    {\n",
        "        Console.WriteLine(\"The problem does not have an optimal solution!\");\n",
        "        return;\n",
        "    }\n",
        "\n",
        "    Console.WriteLine(\"Problem solved in \" + solver.WallTime() + \" milliseconds\");\n",
        "\n",
        "    // The objective value of the solution.\n",
        "    Console.WriteLine(\"Optimal objective value = \" + solver.Objective().Value());\n",
        "\n",
        "    display(solver.variables().Select(a => new { Name  = a.Name(), Value = a.SolutionValue() }));\n",
        "    \n",
        "    // displaying solution weight (custom to this problem)\n",
        "    double totalWeight = 0.0; \n",
        "    for(int i = 0; i < nItems; i++)\n",
        "        totalWeight += solver.variables()[i].SolutionValue() * weights[i]; \n",
        "\n",
        "    display(new { Name = \"Total Weight\", Weight = totalWeight});\n",
        "}"
      ],
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# Applications of linear programming"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Knapsack Problem \n",
        "\n",
        "The knapsack problem defines a bag that was a maximal weight of $W$, which we can fill from a set of items each with a weight of $w_i$ and a value of $v_i$. Typically, the problem is defined with an $x_i \\in \\{0,1\\}$ (binary) variable set to either 0 or 1 knapsack where each item is either taken or not. \n",
        "\n",
        "Here we are going to allow fractional parts of the items to be taken so that we can solve it as a linear problem (also known as a [linear relaxation](https://en.wikipedia.org/wiki/Linear_programming_relaxation)), allowing $x_i \\in [0,1]$. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### linear relaxation \n",
        "\n",
        "The relaxed linear model of the knapsack problem is formulated as follows: \n",
        "\n",
        "$$\n",
        "\\begin{aligned}\n",
        "\\text{Obj:} \\max \\sum ^{n}_{i=1}\\left(x_{i} v_{i}\\right)\n",
        "\\\\st: \\qquad 0 \\leq x_{i} \\leq 1\n",
        "\\\\ \\qquad \\quad \\sum ^{n}_{i=1} x_{i}w_{i} \\leq W\n",
        "\\end{aligned}\n",
        "$$"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "source": [
        "//Array of items, weights and totals\n",
        "int nItems = 10; \n",
        "double maxWeight = 220; \n",
        "double[] weights = {31, 27, 12, 39,  2, 69, 66, 29, 45, 58};\n",
        "double[] values =  {24, 27, 26, 15, 19, 33, 30, 28, 65, 42};"
      ],
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The solver is already defined and ```SolveAndPrint(solver);``` will be automatically called when you click run. \n",
        "\n",
        "Of note is that we can use the MakeArray functions of the solver to create a set of variables all in one go. "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "source": [
        "Solver solver = Solver.CreateSolver(\"CLP_LINEAR_PROGRAMMING\");\n",
        "Variable[] Items = solver.MakeNumVarArray(10, 0.0, 1.0, \"Items\");\n",
        "\n",
        "// Maximize revenue \n",
        "Objective objective = solver.Objective();\n",
        "for(int i = 0; i < nItems; i++) objective.SetCoefficient(Items[i], values[i]);\n",
        "objective.SetMaximization();\n",
        "\n",
        "// Weight limit\n",
        "Constraint c0 = solver.MakeConstraint(0, maxWeight);\n",
        "for(int i = 0; i < nItems; i++) c0.SetCoefficient(Items[i], weights[i]);\n",
        "\n",
        "SolveAndPrint(solver, nItems, weights);"
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "Optimal objective value = 238,6521739130435\r\n"
          },
          "execution_count": 1,
          "metadata": {}
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/html": "<table><thead><tr><th><i>index</i></th><th>Name</th><th>Value</th></tr></thead><tbody><tr><td>0</td><td>Items0</td><td><div class=\"dni-plaintext\">1</div></td></tr><tr><td>1</td><td>Items1</td><td><div class=\"dni-plaintext\">1</div></td></tr><tr><td>2</td><td>Items2</td><td><div class=\"dni-plaintext\">1</div></td></tr><tr><td>3</td><td>Items3</td><td><div class=\"dni-plaintext\">0</div></td></tr><tr><td>4</td><td>Items4</td><td><div class=\"dni-plaintext\">1</div></td></tr><tr><td>5</td><td>Items5</td><td><div class=\"dni-plaintext\">0.23188405797101463</div></td></tr><tr><td>6</td><td>Items6</td><td><div class=\"dni-plaintext\">0</div></td></tr><tr><td>7</td><td>Items7</td><td><div class=\"dni-plaintext\">1</div></td></tr><tr><td>8</td><td>Items8</td><td><div class=\"dni-plaintext\">0.9999999999999999</div></td></tr><tr><td>9</td><td>Items9</td><td><div class=\"dni-plaintext\">1</div></td></tr></tbody></table>"
          },
          "execution_count": 1,
          "metadata": {}
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/html": "<table><thead><tr><th>Name</th><th>Weight</th></tr></thead><tbody><tr><td><div class=\"dni-plaintext\">Total Weight</div></td><td><div class=\"dni-plaintext\">220</div></td></tr></tbody></table>"
          },
          "execution_count": 1,
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Notice Item5 and Item8 have partial values that are not 1.0 or 0. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### 0/1 knapsack \n",
        "\n",
        "When we want to solve the original problem were no fractions of the items can be taken, we have to indroduce binary variables, this makes the problem non-linear and we need to solve a MILP problem instead of an LP problem. Adding binary variables to problems allows for many advanced formulations, but come at a high computational cost. Add too many binary variables and your optimizations problems will take too long to solve. \n",
        "\n",
        "$$x_i \\in \\mathbb{Z},\\quad x_i \\in \\{0,1\\}$$\n",
        "\n",
        "In the Google OR tools, we can either use the MakeBoolVarArray or the MakeIntVarArray to create the binary variables we want."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "source": [
        "Solver milp_solver = Solver.CreateSolver(\"CBC_MIXED_INTEGER_PROGRAMMING\");\n",
        "\n",
        "Variable[] Items = milp_solver.MakeBoolVarArray(10, \"Items\");\n",
        "\n",
        "// Maximize revenue \n",
        "Objective objective = milp_solver.Objective();\n",
        "for(int i = 0; i < nItems; i++) objective.SetCoefficient(Items[i], values[i]);\n",
        "objective.SetMaximization();\n",
        "\n",
        "// Weight limit\n",
        "Constraint c0 = milp_solver.MakeConstraint(0, maxWeight);\n",
        "for(int i = 0; i < nItems; i++) c0.SetCoefficient(Items[i], weights[i]);\n",
        "\n",
        "SolveAndPrint(milp_solver, nItems, weights);"
      ],
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": "Optimal objective value = 231\r\n"
          },
          "execution_count": 1,
          "metadata": {}
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/html": "<table><thead><tr><th><i>index</i></th><th>Name</th><th>Value</th></tr></thead><tbody><tr><td>0</td><td>Items0</td><td><div class=\"dni-plaintext\">1</div></td></tr><tr><td>1</td><td>Items1</td><td><div class=\"dni-plaintext\">1</div></td></tr><tr><td>2</td><td>Items2</td><td><div class=\"dni-plaintext\">1</div></td></tr><tr><td>3</td><td>Items3</td><td><div class=\"dni-plaintext\">0</div></td></tr><tr><td>4</td><td>Items4</td><td><div class=\"dni-plaintext\">1</div></td></tr><tr><td>5</td><td>Items5</td><td><div class=\"dni-plaintext\">0</div></td></tr><tr><td>6</td><td>Items6</td><td><div class=\"dni-plaintext\">0</div></td></tr><tr><td>7</td><td>Items7</td><td><div class=\"dni-plaintext\">1</div></td></tr><tr><td>8</td><td>Items8</td><td><div class=\"dni-plaintext\">1</div></td></tr><tr><td>9</td><td>Items9</td><td><div class=\"dni-plaintext\">1</div></td></tr></tbody></table>"
          },
          "execution_count": 1,
          "metadata": {}
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/html": "<table><thead><tr><th>Name</th><th>Weight</th></tr></thead><tbody><tr><td><div class=\"dni-plaintext\">Total Weight</div></td><td><div class=\"dni-plaintext\">204</div></td></tr></tbody></table>"
          },
          "execution_count": 1,
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The objective value of the problem is lower because an integer constraint is more restrictive than a linear one and we no longer have the partial values for the items in the knapsack, and item5 is no longer part of the solution. You may also notice that there is a remaining weight available in the knapsack. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note that if you try to create the Bool or Int array in the relaxed version above, you will still get the same result as before, because the solver for that problem was defined as a ```\"CLP_LINEAR_PROGRAMMING\"``` solver, whereas this code block has a solver defined with ```\"CBC_MIXED_INTEGER_PROGRAMMING\"```. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Notes\n",
        "There is actually a specialised solver for the [knapsack problem](https://developers.google.com/optimization/bin/knapsack) in the OR-Tools which also covers multi-dimensional knapsacks. Here I felt it was useful to contrast the linear and mixed integer solutions."
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": ".NET (C#)",
      "language": "C#",
      "name": ".net-csharp"
    },
    "language_info": {
      "file_extension": ".cs",
      "mimetype": "text/x-csharp",
      "name": "C#",
      "pygments_lexer": "csharp",
      "version": "8.0"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 4
}