02: Pyomo_glpk_binary_knapshak_maxmize_.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/gulabpatel/LinearProgramming/blob/main/02%3A%20Pyomo_glpk_binary_knapshak_maxmize_.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Video help : https://www.youtube.com/watch?v=pxCogCylmKs"
      ],
      "metadata": {
        "id": "w7TZKCJoxbmo"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "\\begin{align}\n",
        "    \\text{max}~~  & 3 x_1 + 4 x_2 + 5 x_3 + 8 x_4 + 9 x_5 \\\\\n",
        "    \\text{s.t.}~~ & 2 x_1 + 3 x_2 + 4 x_3 + 7 x_4 + 9 x_5 \\le 20 \\\\\n",
        "                  & x_1, x_2, x_3, x_4, x_5 \\in \\{0, 1\\}\n",
        "\\end{align}\n",
        "    "
      ],
      "metadata": {
        "id": "IFDAHIoXq9kc"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "!pip install pyomo\n",
        "!apt install glpk-utils\n",
        "# !pip install glpk"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rXXO0fyBwvLn",
        "outputId": "aafdef4d-a394-4745-b619-95240de7dccb"
      },
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Requirement already satisfied: pyomo in /usr/local/lib/python3.7/dist-packages (6.4.0)\n",
            "Requirement already satisfied: ply in /usr/local/lib/python3.7/dist-packages (from pyomo) (3.11)\n",
            "Reading package lists... Done\n",
            "Building dependency tree       \n",
            "Reading state information... Done\n",
            "glpk-utils is already the newest version (4.65-1).\n",
            "The following packages were automatically installed and are no longer required:\n",
            "  libnvidia-common-460 nsight-compute-2020.2.0\n",
            "Use 'apt autoremove' to remove them.\n",
            "0 upgraded, 0 newly installed, 0 to remove and 42 not upgraded.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "import pyomo.environ as pe\n",
        "import pyomo.opt as po"
      ],
      "metadata": {
        "id": "W0ESIiHTo5MM"
      },
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "solver = po.SolverFactory('glpk') #GNU Linear Programming Kit"
      ],
      "metadata": {
        "id": "AGYhR9Gxt9AU"
      },
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "model = pe.ConcreteModel()\n",
        "\n",
        "model.x1 = pe.Var(domain=pe.Binary)\n",
        "model.x2 = pe.Var(domain=pe.Binary)\n",
        "model.x3 = pe.Var(domain=pe.Binary)\n",
        "model.x4 = pe.Var(domain=pe.Binary)\n",
        "model.x5 = pe.Var(domain=pe.Binary)"
      ],
      "metadata": {
        "id": "KVTiuYAUyEYU"
      },
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "obj_expr = 3*model.x1 + 4*model.x2 + 5*model.x3 + 8*model.x4 + 9*model.x5\n",
        "model.obj = pe.Objective(sense=pe.maximize, expr=obj_expr)"
      ],
      "metadata": {
        "id": "VgmI0uKBya8j"
      },
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "con_expr = 2*model.x1 + 3*model.x2 + 4*model.x3 + 5*model.x4 + 9*model.x5 <= 20\n",
        "model.con = pe.Constraint(expr=con_expr)"
      ],
      "metadata": {
        "id": "P9_isQI4t_As"
      },
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Solve and Postprocess"
      ],
      "metadata": {
        "id": "5yCl71oJz0Nj"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "result = solver.solve(model, tee=True)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ysE6SizJzsDs",
        "outputId": "a58559f3-8d48-456c-d771-8e1c83ea7f76"
      },
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "GLPSOL: GLPK LP/MIP Solver, v4.65\n",
            "Parameter(s) specified in the command line:\n",
            " --write /tmp/tmp7wn23hch.glpk.raw --wglp /tmp/tmp48sljg3o.glpk.glp --cpxlp\n",
            " /tmp/tmpqy2eeepc.pyomo.lp\n",
            "Reading problem data from '/tmp/tmpqy2eeepc.pyomo.lp'...\n",
            "/tmp/tmpqy2eeepc.pyomo.lp:31: warning: lower bound of variable 'x1' redefined\n",
            "/tmp/tmpqy2eeepc.pyomo.lp:31: warning: upper bound of variable 'x1' redefined\n",
            "2 rows, 6 columns, 6 non-zeros\n",
            "5 integer variables, all of which are binary\n",
            "36 lines were read\n",
            "Writing problem data to '/tmp/tmp48sljg3o.glpk.glp'...\n",
            "25 lines were written\n",
            "GLPK Integer Optimizer, v4.65\n",
            "2 rows, 6 columns, 6 non-zeros\n",
            "5 integer variables, all of which are binary\n",
            "Preprocessing...\n",
            "3 constraint coefficient(s) were reduced\n",
            "1 row, 5 columns, 5 non-zeros\n",
            "5 integer variables, all of which are binary\n",
            "Scaling...\n",
            " A: min|aij| =  2.000e+00  max|aij| =  3.000e+00  ratio =  1.500e+00\n",
            "Problem data seem to be well scaled\n",
            "Constructing initial basis...\n",
            "Size of triangular part is 1\n",
            "Solving LP relaxation...\n",
            "GLPK Simplex Optimizer, v4.65\n",
            "1 row, 5 columns, 5 non-zeros\n",
            "*     0: obj =  -0.000000000e+00 inf =   0.000e+00 (5)\n",
            "*     5: obj =   2.500000000e+01 inf =   0.000e+00 (0)\n",
            "OPTIMAL LP SOLUTION FOUND\n",
            "Integer optimization begins...\n",
            "Long-step dual simplex will be used\n",
            "+     5: mip =     not found yet <=              +inf        (1; 0)\n",
            "+     5: >>>>>   2.500000000e+01 <=   2.500000000e+01   0.0% (1; 0)\n",
            "+     5: mip =   2.500000000e+01 <=     tree is empty   0.0% (0; 1)\n",
            "INTEGER OPTIMAL SOLUTION FOUND\n",
            "Time used:   0.0 secs\n",
            "Memory used: 0.1 Mb (60111 bytes)\n",
            "Writing MIP solution to '/tmp/tmp7wn23hch.glpk.raw'...\n",
            "17 lines were written\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "print(pe.value(model.x1))\n",
        "print(pe.value(model.x2))\n",
        "print(pe.value(model.x3))\n",
        "print(pe.value(model.x4))\n",
        "print(pe.value(model.x5))\n",
        "print(pe.value(model.obj))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "S_kMbbXQz7b1",
        "outputId": "ef9bb7aa-62fc-41f4-edde-9345afc9099f"
      },
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1.0\n",
            "0.0\n",
            "1.0\n",
            "1.0\n",
            "1.0\n",
            "25.0\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Model (General)\n",
        "The best way to use Pyomo is to implement the general form of the problem. The instance above is generalized by the formulation below. The set of items is $N$. The coefficients $c_i$ and $a_i$ are the cost and size, respectively of item $i$."
      ],
      "metadata": {
        "id": "RbvQUiG33vOE"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "\\begin{align}\n",
        "    \\text{max}~~  & \\sum_{i \\in N}{c_i x_i} \\\\\n",
        "    \\text{s.t.}~~ & \\sum_{i \\in N}{a_i x_i} \\le b \\\\\n",
        "                  & x_i \\in \\{0, 1\\}, \\forall i \\in N\n",
        "\\end{align}"
      ],
      "metadata": {
        "id": "QtBbZwXh3wCM"
      }
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-nLyqYkL3m1r"
      },
      "source": [
        "## Implement (General)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 9,
      "metadata": {
        "id": "8tXAExwC3m1r"
      },
      "outputs": [],
      "source": [
        "model = pe.ConcreteModel()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 10,
      "metadata": {
        "id": "hcbBOY9W3m1s"
      },
      "outputs": [],
      "source": [
        "model.N = pe.RangeSet(1, 5)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 11,
      "metadata": {
        "id": "u06z3JyF3m1t",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "9fb97203-6159-4fe3-9b71-93c01fcccf88"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "{1, 2, 3, 4, 5}\n"
          ]
        }
      ],
      "source": [
        "print(set(model.N))"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "c = {1: 3, 2: 4, 3: 5, 4: 8, 5: 9}\n",
        "a = {1: 2, 2: 3, 3: 4, 4: 5, 5: 9}\n",
        "b = 20"
      ],
      "metadata": {
        "id": "1W7taJ0N4KRr"
      },
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "model.c = pe.Param(model.N, initialize=c)\n",
        "model.a = pe.Param(model.N, initialize=a)\n",
        "model.b = pe.Param(initialize=b)"
      ],
      "metadata": {
        "id": "c0Hwv4RS4Nci"
      },
      "execution_count": 13,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "For most model components, `print(model.component)` will print the name of the component (a string) and not the value (in most cases, a number)."
      ],
      "metadata": {
        "id": "G3dMbaCk4QCj"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "print(model.c)\n",
        "print(model.c[2])\n",
        "print(model.b)\n",
        "print(model.b.value)\n",
        "print(pe.value(model.b))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "HXt7RSA54PkM",
        "outputId": "efc70efa-9861-417e-ce73-c19c48086b2b"
      },
      "execution_count": 14,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "c\n",
            "4\n",
            "b\n",
            "20\n",
            "20\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "model.x = pe.Var(model.N, domain=pe.Binary)"
      ],
      "metadata": {
        "id": "4DSemROS4eEr"
      },
      "execution_count": 15,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "obj_expr = sum(model.c[i] * model.x[i] for i in model.N)\n",
        "model.obj = pe.Objective(sense=pe.maximize, expr=obj_expr)"
      ],
      "metadata": {
        "id": "R87wBg9_4iDb"
      },
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "con_lhs_expr = sum(model.a[i] * model.x[i] for i in model.N)\n",
        "con_rhs_expr = model.b\n",
        "model.con = pe.Constraint(expr=(con_lhs_expr <= con_rhs_expr))"
      ],
      "metadata": {
        "id": "nsPXCIup42a9"
      },
      "execution_count": 17,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "result = solver.solve(model)"
      ],
      "metadata": {
        "id": "zxLGzhcf5pGU"
      },
      "execution_count": 18,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "After solving, variable values may be accessed either by `pe.value(model.myvar)` or `model.myvar.value`."
      ],
      "metadata": {
        "id": "-8uMMBpT5tfl"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "for i in model.N:\n",
        "    print(pe.value(model.x[i]))\n",
        "print(pe.value(model.obj))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "cPd8RPKe5u5k",
        "outputId": "5190bb35-09b1-475f-c575-fd3a190a411b"
      },
      "execution_count": 19,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1.0\n",
            "0.0\n",
            "1.0\n",
            "1.0\n",
            "1.0\n",
            "25.0\n"
          ]
        }
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3.6",
      "language": "python"
    },
    "language_info": {
      "name": "python",
      "version": "3.6.9",
      "mimetype": "text/x-python",
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "pygments_lexer": "ipython3",
      "nbconvert_exporter": "python",
      "file_extension": ".py"
    },
    "colab": {
      "name": "02: Pyomo_glpk_binary_knapshak_maxmize .ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}