{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# IAP 2022: Advanced Optimization Session (Session 2)\n", "\n", "**Shuvomoy Das Gupta**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Basic Integer Programming" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Example: Shuvo's COVID isolation\n", "\n", "It is Summer of 2020. Shuvo, unfortunately, gets infected with COVID 19. So he has to isolate in a secure place designated by authority. Now he can take some valuable items with him during the isolation phase. He has $N$ items, each with a weight $w_i$ and a price $p_i$. Because he is feeling weak, he can only carry $C$ kilos. How does he choose what to bring with him so as to maximize the total value?\n", "\n", "\n", "We can model Shuvo's situation as a (pure) integer optimization problem:\n", "\n", "\\begin{align*}\n", "\\max& \\sum_{i=1}^N v_i x_i \\\\\n", "\\text{s.t.}& \\sum_{i=1}^N w_i x_i \\leq C \\\\\n", "& x_i \\in \\{0,1\\}^n, \\quad i = 1,\\ldots,N\n", "\\end{align*}\n", "\n", "Variable $x_i$ expresses if item $i$ is selected or not. In generally this problem is called the $0-1$ knapsack problem.\n" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "50" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "using JuMP, Gurobi, LinearAlgebra\n", "\n", "# Problem data\n", "v = [9, 3, 2, 6, 10, 7, 6, 6, 4, 5, 4, 1, 1, \n", " 6, 3, 2, 3, 2, 10, 7, 9, 8, 3, 10, 8, 5, \n", " 3, 8, 3, 6, 5, 7, 8, 6, 9, 7, 5, 5, 1, 5, \n", " 9, 5, 4, 5, 5, 3, 4, 8, 8, 10]\n", "w = [4, 10, 9, 8, 8, 4, 7, 3, 1, 10, 5, 4, 2, \n", " 3, 9, 9, 9, 5, 8, 8, 4, 2, 6, 10, 5, 7, 7, \n", " 8, 4, 7, 7, 8, 4, 4, 10, 3, 9, 2, 9, 10, 3, \n", " 7, 3, 5, 5, 7, 10, 10, 5, 8]\n", "C = 50\n", "n = length(v)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Add the variable $x$ along with the binary constraint." ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Set parameter TokenServer to value \"flexlm\"\n" ] }, { "data": { "text/plain": [ "A JuMP Model\n", "Feasibility problem with:\n", "Variables: 0\n", "Model mode: AUTOMATIC\n", "CachingOptimizer state: EMPTY_OPTIMIZER\n", "Solver name: Gurobi" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "knapsack_model = Model(Gurobi.Optimizer)" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Set parameter Presolve to value 0\n", "Set parameter Heuristics to value 0\n" ] } ], "source": [ "# I am turing these off just for illustration, \n", "# otherwise Gurobi ends up solving the problem during the presolve phase ๐Ÿ˜ฒ\n", "\n", "set_optimizer_attribute(knapsack_model, \"Presolve\", 0)\n", "\n", "set_optimizer_attribute(knapsack_model, \"Heuristics\", 0)" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "50-element Vector{VariableRef}:\n", " x[1]\n", " x[2]\n", " x[3]\n", " x[4]\n", " x[5]\n", " x[6]\n", " x[7]\n", " x[8]\n", " x[9]\n", " x[10]\n", " x[11]\n", " x[12]\n", " x[13]\n", " โ‹ฎ\n", " x[39]\n", " x[40]\n", " x[41]\n", " x[42]\n", " x[43]\n", " x[44]\n", " x[45]\n", " x[46]\n", " x[47]\n", " x[48]\n", " x[49]\n", " x[50]" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(knapsack_model, x[1:n] >= 0, Bin)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Add the objective $v^\\top x$." ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$$ 9 x_{1} + 3 x_{2} + 2 x_{3} + 6 x_{4} + 10 x_{5} + 7 x_{6} + 6 x_{7} + 6 x_{8} + 4 x_{9} + 5 x_{10} + 4 x_{11} + x_{12} + x_{13} + 6 x_{14} + 3 x_{15} + 2 x_{16} + 3 x_{17} + 2 x_{18} + 10 x_{19} + 7 x_{20} + 9 x_{21} + 8 x_{22} + 3 x_{23} + 10 x_{24} + 8 x_{25} + 5 x_{26} + 3 x_{27} + 8 x_{28} + 3 x_{29} + 6 x_{30} + 5 x_{31} + 7 x_{32} + 8 x_{33} + 6 x_{34} + 9 x_{35} + 7 x_{36} + 5 x_{37} + 5 x_{38} + x_{39} + 5 x_{40} + 9 x_{41} + 5 x_{42} + 4 x_{43} + 5 x_{44} + 5 x_{45} + 3 x_{46} + 4 x_{47} + 8 x_{48} + 8 x_{49} + 10 x_{50} $$" ], "text/plain": [ "9 x[1] + 3 x[2] + 2 x[3] + 6 x[4] + 10 x[5] + 7 x[6] + 6 x[7] + 6 x[8] + 4 x[9] + 5 x[10] + 4 x[11] + x[12] + x[13] + 6 x[14] + 3 x[15] + 2 x[16] + 3 x[17] + 2 x[18] + 10 x[19] + 7 x[20] + 9 x[21] + 8 x[22] + 3 x[23] + 10 x[24] + 8 x[25] + 5 x[26] + 3 x[27] + 8 x[28] + 3 x[29] + 6 x[30] + 5 x[31] + 7 x[32] + 8 x[33] + 6 x[34] + 9 x[35] + 7 x[36] + 5 x[37] + 5 x[38] + x[39] + 5 x[40] + 9 x[41] + 5 x[42] + 4 x[43] + 5 x[44] + 5 x[45] + 3 x[46] + 4 x[47] + 8 x[48] + 8 x[49] + 10 x[50]" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@objective(knapsack_model, Max, v' * x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Add the constraint $w^\\top x \\leq C$." ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$$ 4 x_{1} + 10 x_{2} + 9 x_{3} + 8 x_{4} + 8 x_{5} + 4 x_{6} + 7 x_{7} + 3 x_{8} + x_{9} + 10 x_{10} + 5 x_{11} + 4 x_{12} + 2 x_{13} + 3 x_{14} + 9 x_{15} + 9 x_{16} + 9 x_{17} + 5 x_{18} + 8 x_{19} + 8 x_{20} + 4 x_{21} + 2 x_{22} + 6 x_{23} + 10 x_{24} + 5 x_{25} + 7 x_{26} + 7 x_{27} + 8 x_{28} + 4 x_{29} + 7 x_{30} + 7 x_{31} + 8 x_{32} + 4 x_{33} + 4 x_{34} + 10 x_{35} + 3 x_{36} + 9 x_{37} + 2 x_{38} + 9 x_{39} + 10 x_{40} + 3 x_{41} + 7 x_{42} + 3 x_{43} + 5 x_{44} + 5 x_{45} + 7 x_{46} + 10 x_{47} + 10 x_{48} + 5 x_{49} + 8 x_{50} \\leq 50.0 $$" ], "text/plain": [ "4 x[1] + 10 x[2] + 9 x[3] + 8 x[4] + 8 x[5] + 4 x[6] + 7 x[7] + 3 x[8] + x[9] + 10 x[10] + 5 x[11] + 4 x[12] + 2 x[13] + 3 x[14] + 9 x[15] + 9 x[16] + 9 x[17] + 5 x[18] + 8 x[19] + 8 x[20] + 4 x[21] + 2 x[22] + 6 x[23] + 10 x[24] + 5 x[25] + 7 x[26] + 7 x[27] + 8 x[28] + 4 x[29] + 7 x[30] + 7 x[31] + 8 x[32] + 4 x[33] + 4 x[34] + 10 x[35] + 3 x[36] + 9 x[37] + 2 x[38] + 9 x[39] + 10 x[40] + 3 x[41] + 7 x[42] + 3 x[43] + 5 x[44] + 5 x[45] + 7 x[46] + 10 x[47] + 10 x[48] + 5 x[49] + 8 x[50] โ‰ค 50.0" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@constraint(knapsack_model, w' * x <= C)" ] }, { "cell_type": "code", "execution_count": 44, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Set parameter Heuristics to value 0\n", "Set parameter Presolve to value 0\n", "Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)\n", "Thread count: 48 physical cores, 96 logical processors, using up to 32 threads\n", "Optimize a model with 1 rows, 50 columns and 50 nonzeros\n", "Model fingerprint: 0x0c089da8\n", "Variable types: 0 continuous, 50 integer (50 binary)\n", "Coefficient statistics:\n", " Matrix range [1e+00, 1e+01]\n", " Objective range [1e+00, 1e+01]\n", " Bounds range [0e+00, 0e+00]\n", " RHS range [5e+01, 5e+01]\n", "Variable types: 0 continuous, 50 integer (50 binary)\n", "\n", "Root relaxation: objective 1.040000e+02, 1 iterations, 0.00 seconds (0.00 work units)\n", "\n", " Nodes | Current Node | Objective Bounds | Work\n", " Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time\n", "\n", "* 0 0 0 104.0000000 104.00000 0.00% - 0s\n", "\n", "Explored 1 nodes (1 simplex iterations) in 0.01 seconds (0.00 work units)\n", "Thread count was 32 (of 96 available processors)\n", "\n", "Solution count 1: 104 \n", "\n", "Optimal solution found (tolerance 1.00e-04)\n", "Best objective 1.040000000000e+02, best bound 1.040000000000e+02, gap 0.0000%\n", "\n", "User-callback calls 36, time in user-callback 0.00 sec\n" ] } ], "source": [ "optimize!(knapsack_model)" ] }, { "cell_type": "code", "execution_count": 45, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0]\n" ] } ], "source": [ "println(abs.(value.(x)))" ] }, { "cell_type": "code", "execution_count": 46, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "104.0" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "objective_value(knapsack_model)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Branch-and-bound algorithm: the key algorithm to solve discrete-valued problem\n", "\n", "Integer optimization problems in solvers such are Gurobi are solved using the Branch-and-bound algorithm. Let us try to understand how the basic Branch-and-bound algorithm works through a running example. \n", "\n", "### Toy example\n", "\n", "In particular, consider the following (small) knapsack problem:\n", "\n", "\\begin{align*}\n", " \\max\\:& x + y \\\\\n", " \\text{s.t.}\\:& x + 2y \\leq 1.5 \\\\\n", " & x, y \\in \\{0,1\\}\n", "\\end{align*}\n", "\n", "How would you solve this? " ] }, { "cell_type": "code", "execution_count": 47, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Set parameter TokenServer to value \"flexlm\"\n", "Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)\n", "Thread count: 48 physical cores, 96 logical processors, using up to 32 threads\n", "Optimize a model with 1 rows, 2 columns and 2 nonzeros\n", "Model fingerprint: 0x062dc61b\n", "Variable types: 0 continuous, 2 integer (2 binary)\n", "Coefficient statistics:\n", " Matrix range [1e+00, 2e+00]\n", " Objective range [1e+00, 1e+00]\n", " Bounds range [0e+00, 0e+00]\n", " RHS range [2e+00, 2e+00]\n", "Found heuristic solution: objective 1.0000000\n", "Presolve removed 1 rows and 2 columns\n", "Presolve time: 0.00s\n", "Presolve: All rows and columns removed\n", "\n", "Explored 0 nodes (0 simplex iterations) in 0.00 seconds (0.00 work units)\n", "Thread count was 1 (of 96 available processors)\n", "\n", "Solution count 1: 1 \n", "\n", "Optimal solution found (tolerance 1.00e-04)\n", "Best objective 1.000000000000e+00, best bound 1.000000000000e+00, gap 0.0000%\n", "\n", "User-callback calls 139, time in user-callback 0.00 sec\n", "X is: 1.0 Y is: 0.0\n" ] } ], "source": [ "small_knapsack_model = Model(Gurobi.Optimizer)\n", "@variable(small_knapsack_model , x, Bin)\n", "@variable(small_knapsack_model , y, Bin)\n", "@constraint(small_knapsack_model , x+2*y<=1.5)\n", "@objective(small_knapsack_model , Max, x+y)\n", "optimize!(small_knapsack_model )\n", "println(\"X is: \", value(x), \" Y is: \", value(y))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Branch and Bound Tree\n", "\n", "The simple way is just to consider each possible value for $x$ and $y$ and compare the cost.\n", "\n", "![alt text](img/tree_1.png)\n", "\n", "In the general case, this would lead to $2^N$ possible collections of items. After Shuvo has weighed all of them (and verified that he can lift them at once), he just chooses the best set." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "Let's visualize this approach as a search tree:\n", "\n", "![alt text](img/tree_2.png)\n", "\n", "It's rooted at what we call the _relaxation_: none of variables have integrality enforced. As we go down leaves of the tree, we add pick a variable to _branch_ on, and create two descended nodes that fix that variable to one of its possible values. If we follow the tree all the way to the bottom, we reach our enumeration from before.\n", "\n", "As we go down the arcs of the tree we restrict our problem more and more, we must have that:\n", "\n", "> If node ``q`` is descended from node ``p``, we must have that the optimal cost of subproblem ``q`` cannot be better than that of node ``p``\n", "\n", "When we are solving the subproblem `q`: the following possibilities can happen:\n", "\n", "(i) subproblem `q` is leads to an infeasible solution, so `q` and any of its descendents cannot contain the optimal solution => we can discard it\n", "\n", "(ii) subproblem `q` has an optimal value that is worse than our best found feasible solution so far, so `q` and any of its descendents cannot contain the optimal solution => we can discard it\n", "\n", "(iii) none of (i), (ii) happens, so we need to continue branching on `q` (create more descendents of `q`)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "That is, we can _prune_ the tree and safely discard some nodes, kind of like this:\n", "\n", "![alt text](img/tree_3.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So at the root node the solver is solving the following relaxation:\n", "\n", "\\begin{align*}\n", " \\max\\quad& x + y \\\\\n", " \\text{s.t.}\\quad& x + 2y \\leq 1.5 \\\\\n", " & 0 \\leq x, y \\leq 1 \\\\\n", " & x, y \\in \\{0,1\\}\n", "\\end{align*}\n", "\n", "and subsequently restricting the problem more and more at the descendents.\n", "\n", "What does the relaxation (no integrality restrictions) of this problem look like?\n", "\n", "* First, we solve the LP relaxation and get $(x^*,y^*) = (1,0.25)$.\n", "* This isn't integer feasible, so we branch on $y$. The subproblem with $y = 1$ is infeasible, and the subproblem with $y = 0$ is feasible with solution $(x^*,y^*) = (1,0)$. This is integer feasible, so we update our lower bound. We've also exhausted the tree, so we have our optimal solution!\n", "* The branch-and-bound scheme can end up solving many subproblems, so for it to work well, we need to _prune_ large portions of the tree. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Basic operation of the branch-and-bound algorithm\n", "For a maximization problem, we'll keep track of a global _lower bound_ $LB$ for our problem. Each node ``q`` will have an upper bound $UB_q$ that it inherents from its parent. If we get to the point where we have solved all subproblems (or, ideally, pruned off a great deal of them), we know that we're optimal. To do this we'll also keep track of a list $L$ of subproblems left to solve; initially, it's just the relaxation. The procedure is:\n", "\n", "While $L$ is not empty, pick a subproblem ``q`` out of our list $L$ and solve it. \n", "1. ``if`` ``q`` is infeasible, ``continue``\n", "2. ``if`` the solution is integer feasible, update the lower bound $LB$ if the cost is higher than what we had before\n", "3. ``if`` the relaxation value is less than our global $LB$ ``continue``\n", "4. ``else`` pick a non-integer variable $i$ and _branch_ by adding two subproblems to $L$: \n", " * One with $x_i = 0$\n", " * Another with $x_i = 1$\n", "\n", "Branch-and-bound is sometimes called an _implicit enumeration_ scheme because of step 3: we avoid solving any subproblems that we can prove won't produce the optimal solution.\n", "\n", "For a minimization problem, the role of upper bound and lower bound will be flipped." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### ฮ™mplementation of the Branch and Bound Algorithm in Gurobi\n", "\n", "The \"magic\" of modern MIP solvers largely comes down to pruning massive portions of the tree. Some of this is essentially beyond your control, but there are certain things which you can do. This is the topic of Part II of this IP crash course.\n", "\n", "In what follows, we focus on **Gurobi**, a commercial solver that solves Mixed Integer LPs/QPs/QCQPs. (You can get the full picture of what solvers JuMP supports and what types of problems you can solve with each of them by visiting http://www.juliaopt.org/JuMP.jl/latest/installation/ and scrolling a bit down.)\n", "\n", "What are the ingredients of Gurobi's branch and bound implementation?\n", " - **Presolve**: reduce problem size via removal of redundant constraints and variable substitutions.\n", " - **Sophisticated Implementations of Continuous Optimization Methods**: simplex-based, barrier-based.\n", " - **Cutting Planes**: over the course of the solution process, add cuts that tighten the model and remove potential undesired fractional solution.\n", " - **Heuristics**: e.g., randomized rounding.\n", " - **Branch Variable Selection**: which variable to branch on. `Gurobi` has lot of internal heuristics to do it." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Understanding Gurobi's Output\n", "\n", "Usually Gurobi starts with solves the LP relaxation and reports back:\n", "```\n", "Root relaxation: objective 4.014179e+00, 18 iterations, 0.00 seconds\n", "```\n", "Now it explores the branch-and-bound tree, and updates us as it goes along. Let's look at just the first line:\n", "```\n", " Nodes | Current Node | Objective Bounds | Work\n", " Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time\n", "\n", " 0 0 4.01418 0 7 2.35937 4.01418 70.1% - 0s\n", "```\n", "We see that the information is broken down into four main columns:\n", "\n", "1. ``Nodes``: Global node information\n", " * how many nodes have we looked at\n", " * how many do we have in our queue\n", "2. ``Current Node``\n", " * objective\n", " * depth in the tree\n", " * number of noninteger variables in the solution\n", "3. ``Objective Bounds``\n", " * Best incumbent\n", " * bound at the node (by solving the relaxation)\n", " * the gap between the two\n", "4. ``Work``\n", " * average simplex iterations per node\n", " * total elapsed time" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solver Parameters\n", "Gurobi (and other high-quality solvers such as CPLEX) allow you to tweak a wide range of different parameters; sometimes tuning these can drastically improve performance. It can be kind of intimidating, though: Gurobi has over 100 parameters (and CPLEX has even more!), so which are the important ones?\n", "\n", "Some useful ones:\n", "\n", "Gurobi: \n", "* `TimeLimit`: how long the solver will run before giving up\n", "* `MIPGap`: termination criterion for relative gap $\\frac{UB-LB}{LB}$\n", "* `MIPFocus`: High-level controls on solver priority (proving optimality or increasing bound or finding optimal solution)\n", "* `VarBranch`: MIP branching strategy (pseudocost/strong branching)\n", "* `Cuts`: How aggresive we want to be in our cut generation (higher values improve lower bound but might slow overall process).\n", "\n", "How to set these parameters in JuMP 0.22?\n", " \n", "```\n", "set_optimizer_attribute(model, \"TimeLimit\", 100)\n", "set_optimizer_attribute(model, \"Presolve\", 0)\n", "```\n", "\n", "Is that it? Well, no, but you probably need domain knowledge about your problem to go much further. \n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Mixed-integer programming (MIP)\n", "\n", "Mixed-integer programing problems are similar to integer programming problem but only some variables are integer-valued, where the rest are real-valued. The standard form MIP is defined as: \n", "\n", "$$\n", "\\begin{aligned}\n", "& \\text{minimize} && c^T x + d^T y\\\\\n", "& \\text{subject to} && A x + B y= f \\\\\n", " & && x \\geq 0, y \\geq 0 \\\\\n", " & && x \\in \\mathbb{R}^n, y \\in {\\{0,1\\}}^p,\n", "\\end{aligned}\n", "$$\n", "\n", "where $x,y$ are the decision variables, and the problem data is $A \\in \\mathbb{R}^{m \\times n}, B \\in \\mathbb{R}^{m \\times p}, c \\in \\mathbb{R}^n, d \\in \\mathbb{R}^p, f \\in \\mathbb{R}^m$. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Situations where mixed-integer programming models show up\n", "\n", "Usually shows up in situations where\n", " * modeling do/don't do decisions\n", " * logical conditions\n", " * implications (if something happens do this)\n", " * either/or" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Modeling \"or\" condition using MIP\n", "Modeling logical or statements:\n", "\n", "If we have a constraint such as: \n", "$$\n", "\\bigvee_{i=1,\\ldots,m}(a_{i}^{\\top}x\\geq b_{i}),\n", "$$\n", " which means atleast one of $\\{a_{i}^{\\top}x\\geq b_{i}\\}_{i\\in\\{1,\\ldots,m\\}}$.\n", "We model this through big-M constraint as follows: \n", "\n", "\n", "\\begin{align*}\n", " & y_{i}\\in\\{0,1\\},\\; \\quad i=1,\\ldots,m,\\\\\n", " & a_{i}^{\\top}x\\geq b_{i}-M(1-y_{i}),\\; \\quad i=1,\\ldots,m,\\\\\n", " & \\sum_{i=1}^{m}y_{i}\\geq1.\n", " \\end{align*}\n", "\n", "\n", " Here the big-M is assumed to be a very large positive number. The\n", "variable $y_{i}$ corresponds to the activation of the constraint\n", "$a_{i}^{\\top}x\\geq b_{i}$. Say, $y_{j}=1$ then $a_{j}^{\\top}x\\geq b_{j}-M(1-y_{j})=b_{j}$\n", "which means that the constraint $a_{j}^{\\top}x\\geq b_{j}$ is activated.\n", "Note that the system of inequalities ensure that atleast one of the\n", "$y_{i}$s will be $1$, hence atleast one of $a_{i}^{\\top}x\\geq b_{i}$\n", "will be activated.\n", "\n", "### Modeling implication statment:\n", "\n", "Remember that the logical argument $P\\Rightarrow Q$ is equivalent\n", "to $\\lnot P\\vee Q$ (``not $P$'' or Q), \\emph{i.e.}, atleast one\n", "of $Q$ or $\\lnot P$ will happen. \n", "\n", "So $a^{\\top}x\\geq b\\Rightarrow d^{\\top}x\\geq f$ is equivalent to\n", "\n", "\n", "\\begin{align*}\n", " & \\lnot(a^{\\top}x\\geq b)\\vee(d^{\\top}x\\geq f)\\\\\n", "\\Leftrightarrow & (a^{\\top}x=0)" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "14-element Vector{VariableRef}:\n", " y[1]\n", " y[2]\n", " y[3]\n", " y[4]\n", " y[5]\n", " y[6]\n", " y[7]\n", " y[8]\n", " y[9]\n", " y[10]\n", " y[11]\n", " y[12]\n", " y[13]\n", " y[14]" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(sfMipModel, y[1:p] >= 0, Bin)" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$$ 0.5509762512952924 x_{1} + 0.8301894840196344 x_{2} + 0.232206040486789 x_{3} + 1.393135672910711 x_{4} + 1.8424788005687465 x_{5} + 0.2809901994866778 x_{6} + 0.061642781427148165 x_{7} + 0.27957901049796585 x_{8} + 0.5029564153246902 x_{9} + 1.6571128316959116 x_{10} + 1.9845201668903614 x_{11} + 1.0714598154112318 x_{12} + 0.1961692232512833 x_{13} + 0.3175828833102234 x_{14} + 0.8711819390889186 x_{15} + 2.0223177663654193 y_{1} + 0.9428269115949712 y_{2} + 0.9103775465116974 y_{3} + 0.6179267803651766 y_{4} + 0.6492970400376368 y_{5} + 0.6030128378052168 y_{6} + 0.5322794124977765 y_{7} + 1.2122056218797066 y_{8} + 0.6184661362908869 y_{9} + 0.4227992283182034 y_{10} + 0.7303206991029539 y_{11} + 0.20831525933957853 y_{12} + 0.037796848867822794 y_{13} + 1.2202732838671742 y_{14} $$" ], "text/plain": [ "0.5509762512952924 x[1] + 0.8301894840196344 x[2] + 0.232206040486789 x[3] + 1.393135672910711 x[4] + 1.8424788005687465 x[5] + 0.2809901994866778 x[6] + 0.061642781427148165 x[7] + 0.27957901049796585 x[8] + 0.5029564153246902 x[9] + 1.6571128316959116 x[10] + 1.9845201668903614 x[11] + 1.0714598154112318 x[12] + 0.1961692232512833 x[13] + 0.3175828833102234 x[14] + 0.8711819390889186 x[15] + 2.0223177663654193 y[1] + 0.9428269115949712 y[2] + 0.9103775465116974 y[3] + 0.6179267803651766 y[4] + 0.6492970400376368 y[5] + 0.6030128378052168 y[6] + 0.5322794124977765 y[7] + 1.2122056218797066 y[8] + 0.6184661362908869 y[9] + 0.4227992283182034 y[10] + 0.7303206991029539 y[11] + 0.20831525933957853 y[12] + 0.037796848867822794 y[13] + 1.2202732838671742 y[14]" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@objective(sfMipModel, Min, sum(c[i] * x[i] for i in 1:n)+sum(d[i]*y[i] for i in 1:p))" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [], "source": [ "for i in 1:m\n", " @constraint(sfMipModel, sum(A[i,j]*x[j] for j in 1:n)+ sum(B[i,j]*y[j] for j in 1:p) == f[i])\n", "end" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Set parameter MIPFocus to value 3\n", "Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)\n", "Thread count: 48 physical cores, 96 logical processors, using up to 32 threads\n", "Optimize a model with 13 rows, 29 columns and 377 nonzeros\n", "Model fingerprint: 0x283aaa28\n", "Variable types: 15 continuous, 14 integer (14 binary)\n", "Coefficient statistics:\n", " Matrix range [6e-03, 3e+00]\n", " Objective range [4e-02, 2e+00]\n", " Bounds range [0e+00, 0e+00]\n", " RHS range [5e-01, 8e+00]\n", "Presolve time: 0.00s\n", "Presolved: 13 rows, 29 columns, 360 nonzeros\n", "Variable types: 15 continuous, 14 integer (14 binary)\n", "Root relaxation presolved: 13 rows, 29 columns, 360 nonzeros\n", "\n", "\n", "Root relaxation: objective 6.576195e+00, 19 iterations, 0.00 seconds (0.00 work units)\n", "\n", " Nodes | Current Node | Objective Bounds | Work\n", " Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time\n", "\n", " 0 0 6.57620 0 5 - 6.57620 - - 0s\n", "H 0 0 11.8611889 7.95094 33.0% - 0s\n", " 0 0 9.48852 0 4 11.86119 9.48852 20.0% - 0s\n", "H 0 0 11.4692035 9.48852 17.3% - 0s\n", "\n", "Cutting planes:\n", " Gomory: 10\n", " Lift-and-project: 1\n", " MIR: 14\n", " Flow cover: 24\n", " Inf proof: 3\n", "\n", "Explored 1 nodes (27 simplex iterations) in 0.07 seconds (0.02 work units)\n", "Thread count was 32 (of 96 available processors)\n", "\n", "Solution count 2: 11.4692 11.8612 \n", "\n", "Optimal solution found (tolerance 1.00e-04)\n", "Best objective 1.146920353965e+01, best bound 1.146920353965e+01, gap 0.0000%\n", "\n", "User-callback calls 236, time in user-callback 0.00 sec\n" ] } ], "source": [ "optimize!(sfMipModel)" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "15-element Vector{Float64}:\n", " 0.9899474320258836\n", " 0.9642308227536968\n", " 0.5868159949777088\n", " 0.4630020993740819\n", " 0.901053837606137\n", " 0.5631434853865587\n", " 0.2257929580263573\n", " 0.6532009804572236\n", " 1.5223238215506862\n", " 0.0\n", " 0.54943253051681\n", " 1.1917506578662456\n", " 0.0\n", " 0.8500168300331316\n", " 0.8154952228571157" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x_sol = value.(x) " ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "14-element Vector{Float64}:\n", " -0.0\n", " -0.0\n", " 1.0\n", " 1.0\n", " -0.0\n", " -0.0\n", " 1.0\n", " -0.0\n", " -0.0\n", " 1.0\n", " 1.0\n", " -0.0\n", " -0.0\n", " -0.0" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "y_sol = value.(y)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Speed up the default Gurobi solver by exploiting problem structure\n", "\n", "`Gurobi`'s solver, while very good, is a generic solver, and is not intelligent enough to exploit problem specific insights. So, if you have specific domain knowledge for the problem you are trying to solve, you need to tell `Gurobi` about it, which will speed up the process by orders of magnitude. \n", "\n", "There are 4 ways to provide `Gurobi` with problem specific insights in `JuMP`.\n", "\n", "* Lazy constraint\n", "* User cuts\n", "* Custom heuristic\n", "* Warm-starting\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Lazy constraint\n", "\n", "> * Lazy constraint: Lazy constraints are useful when the full set of constraints is too large to explicitly include in the initial formulation. When a MIP solver reaches a new solution, for example with a heuristic or by solving a problem at a node in the branch-and-bound tree, it will give the user the chance to provide constraints that would make the current solution infeasible.\n", "\n", "Suppose your integer optimization problem is: \n", "\n", "\n", "\\begin{array}{ll}\n", "\\underset{x\\in\\mathbf{R}^{d}}{\\mbox{minimize}} & c^\\top x \\\\\n", "\\mbox{subject to} & Ax \\leq b,\\\\\n", " & x\\succeq0,\\\\\n", " & d_{i}^{\\top}x\\leq h_{i},\\quad i=1,\\ldots,p,\\\\\n", " & x\\in\\{0,1\\}^{d},\n", "\\end{array}\n", "\n", "\n", "where $p$ is a very large number. In fact it does happen in medical\n", "imaging. So, in this case, the problem starts with \n", "\n", "\n", "\\begin{array}{ll}\n", "\\underset{x\\in\\mathbf{R}^{d}}{\\mbox{minimize}} & c^\\top x \\\\\n", "\\mbox{subject to} & Ax \\leq b,\\\\\n", " & x\\succeq0,\\\\\n", " & x\\in\\{0,1\\}^{d},\n", "\\end{array}\n", "\n", "\n", " and once a integer solution is reached, we check if the solution\n", "violates any of the constraints $\\{d_{i}^{\\top}x\\leq h_{i}\\}_{i=1}^{p}$\n", "and add the first one that gets violated. This can be done through the following code:\n", "\n", "```\n", "function good_callback_function(cb_data)\n", " x_current = callback_value.(x)\n", " if x_current violates some condition \"conV\"\n", " con = @build_constraint(x should not violate \"conV\")\n", " MOI.submit(model, MOI.LazyConstraint(cb_data), con)\n", " end\n", "end\n", "```\n" ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [], "source": [ "# data\n", "n = 20\n", "p = 5\n", "m = 5\n", "A = [-0.25149258982896966 0.525287826731042 -0.6656342865169662 -1.2960398772338568 0.9101252450751471 -0.07298248406603706 -1.9148704340623688 -0.5073995272298952 -1.6558511941286744 2.1006659624182586 -0.502359026079171 -0.1708406495941207 1.4161030569819415 0.33735905844690145 -0.10748103771152817 -1.4416340194991104 -0.9578960880328228 -0.1738984790022571 -1.0517643292393826 -0.8271987403702172; -0.8518984622275042 -1.374417162491773 0.35920232369365845 0.8437691247979793 -0.6281577605465152 0.5921264379488904 -0.12756078132890084 -0.44447204507515287 0.7293549470299907 0.715267254601397 -0.9155882952842251 0.35378971887340743 -0.8043683142766567 0.5324223554306367 0.2088297149344946 -0.5594219995662968 0.5632674521223371 -0.2302672262989066 0.7676987968759004 1.0910836780489503; 1.473815753336459 -0.6525879104965642 0.8519411939583414 -0.05756789248416348 -0.7125581880426727 0.4736057460760701 -2.231011632648033 0.5409490591899032 0.1583459153748212 -1.1509507228336586 1.3994115761547934 0.14111034486559706 -0.15123003344570538 -0.547672888665602 -1.9555427017941476 -1.8533179907378834 0.13798098584535193 0.2337797562353011 -0.8404137158789987 0.060446173222487264; 0.6396537082966063 0.856847789735652 1.4805326346158039 0.012324563610194187 1.3977381658753554 1.3342059688961259 -0.4784014905808825 -0.14890693050929457 0.8155899237370289 -0.5697405099766946 1.3446291535605297 0.6840341944716634 1.2484251582871324 1.2891201777341281 -0.2791170028219365 0.43803145770984425 0.4677466100676112 1.3639772554672074 0.8359137382225728 0.8723882764319004; 0.40517145458826054 1.169967487661965 1.7941045258417871 1.035188318563306 1.118495812473751 -0.04027314052794962 0.5438620238342292 -0.8181792084120169 0.08209406151847103 0.6469386439823567 -0.9467882212470308 -0.2866858366079981 0.8836746919594078 -2.0164799655225094 -0.42541330025958685 -0.09145359012880407 0.8920741578367347 -0.5093214870138416 -0.23118339134915017 -1.262095251923206]\n", "D = [-2.0831200526934572 1.5615062392183003 0.18155475431473142 0.7599664330346061 0.2668125999785801 1.2573917809432806 0.04093911087719557 -0.21735884773163816 1.6340683454668137 1.2804063399285137 0.6443447646682994 -0.8939206481655969 -0.22507735354054656 -0.3094500241639488 0.2954219652735186 -0.3880055556581179 -0.9578091110001216 -0.922838957226308 -1.3571981131817064 -0.05064205091038371; 0.6324558903791979 -0.6652227624026216 -1.7276813422697317 -0.689479323056671 -0.7816950255371095 -1.802372714658206 0.14164169531740856 0.46527545010854515 1.1036334528775311 1.305688755430216 0.3797915504580763 1.7602878854059907 0.8155022785101097 -0.6315798865662005 -0.30581893855662595 -0.33305541977514697 -0.8854550960099433 0.03621076189783246 -0.2788693026530316 1.6348184993843053; -2.4242492532538096 0.5770923004878816 0.4961795092913091 -0.04867957395223246 0.6673192113922586 -0.8855274251005092 0.4568856956106312 -0.6097467636667095 -0.3639368866683512 0.5625062854293676 -0.5017933052998168 0.3836052143475206 1.8936021566371188 -0.209665904941543 -1.3278566925429307 0.6736435837748775 -0.5017805315844522 0.6452850279162458 0.7881379044649098 0.45931063639065656; -0.5372061672955294 -0.7867658024064041 0.09657107558669714 -1.0587831441218194 -1.2444111679260363 -0.6885359430850223 -0.4325022650433149 0.7912025990048928 0.1141092892049688 0.918388681602774 0.41101551577580714 1.3817408040581836 -0.030696867637192395 0.7523799268172908 -0.3083505028779359 0.27074896029609724 -0.5303233440211375 -1.1025104074431078 -2.3234729621969272 0.705781546034252; 0.6313935384296541 0.699436081582457 -0.5461167811714385 -0.5108885871403681 -1.59867913729006 -0.7350106637365103 -1.1033454910986003 0.898936477156721 -0.07365263955313238 -0.48330570412807555 1.0944353481674236 0.19009504425867302 -0.5106409146420512 0.647369019147565 -0.40169454919669595 -0.1575677053433486 1.4977052939251785 -0.39775746600800416 1.821753152147404 0.10823903833322045]\n", "c = [-5.724274247670441; 0.872180569098502; -13.289441619771337; -1.284190729811427; -10.090248808669005; 19.226305603166242; -14.323991615118594; -5.8893709748795615; -9.801477473401599; -2.533420139004128; -4.017671140375999; -12.25747413009963; -6.5234635509559205; -18.204822439044932; 10.759517257360242; -2.678837137470244; 2.6260424150728934; -9.929728378562064; -1.08448828496412; -14.883711771646961]\n", "b = [-7.3620594939851545; 1.2864238748369008; -5.191670678971517; 3.4603990262005064; -0.9930993374575348]\n", "h = [-5.110534843409266; -0.12459704540647681; -2.8197063217437384; -1.9945660953801996; 3.5137561922861824];" ] }, { "cell_type": "code", "execution_count": 50, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Set parameter TokenServer to value \"flexlm\"\n", "Set parameter LazyConstraints to value 1\n", "Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)\n", "Thread count: 48 physical cores, 96 logical processors, using up to 32 threads\n", "Optimize a model with 5 rows, 20 columns and 100 nonzeros\n", "Model fingerprint: 0xb04b5cd0\n", "Variable types: 0 continuous, 20 integer (20 binary)\n", "Coefficient statistics:\n", " Matrix range [1e-02, 2e+00]\n", " Objective range [9e-01, 2e+01]\n", " Bounds range [0e+00, 0e+00]\n", " RHS range [1e+00, 7e+00]\n", "[๐Ÿ˜] Current node has an integer solution\n", "[๐Ÿ˜ป] Submitting 1-th constraint d[i]'x <= h[i] as a lazy constraint\n", "Presolve time: 0.00s\n", "Presolved: 5 rows, 20 columns, 100 nonzeros\n", "Variable types: 0 continuous, 20 integer (20 binary)\n", "\n", "Root relaxation: objective -6.474229e+01, 9 iterations, 0.00 seconds (0.00 work units)\n", "\n", " Nodes | Current Node | Objective Bounds | Work\n", " Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time\n", "\n", " 0 0 -64.74229 0 4 - -64.74229 - - 0s\n", " 0 0 -59.68164 0 5 - -59.68164 - - 0s\n", "[๐Ÿ˜] Current node has an integer solution\n", "[๐Ÿ˜ป] Submitting 1-th constraint d[i]'x <= h[i] as a lazy constraint\n", "[๐Ÿ˜] Current node has an integer solution\n", "* 0 0 0 -48.0618899 -48.06189 0.00% - 0s\n", "\n", "Cutting planes:\n", " Gomory: 5\n", " Cover: 3\n", " MIR: 2\n", " StrongCG: 2\n", " RLT: 2\n", " Lazy constraints: 1\n", "\n", "Explored 1 nodes (29 simplex iterations) in 0.11 seconds (0.00 work units)\n", "Thread count was 32 (of 96 available processors)\n", "\n", "Solution count 1: -48.0619 \n", "No other solutions better than -48.0619\n", "\n", "Optimal solution found (tolerance 1.00e-04)\n", "Best objective -4.806188988663e+01, best bound -4.806188988663e+01, gap 0.0000%\n", "\n", "User-callback calls 116, time in user-callback 0.10 sec\n" ] } ], "source": [ "# a proper code is as follows:\n", "\n", "lazy_model = Model(Gurobi.Optimizer)\n", "\n", "@variable(lazy_model, x[1:n], Bin)\n", "\n", "for i in 1:m\n", " @constraint(lazy_model, sum(A[i,j]*x[j] for j in 1:n) <= b[i])\n", "end\n", "\n", "@objective(lazy_model, Min, sum(c[i] * x[i] for i in 1:n))\n", "\n", "\n", "# lazy constraint is added through the following callback function\n", "function my_callback_function(cb_data)\n", " # check the status of the solution at the branch-and-bound tree node \n", " status = callback_node_status(cb_data, lazy_model)\n", " if status == MOI.CALLBACK_NODE_STATUS_FRACTIONAL\n", " # if we enter this block then it means that\n", " # `callback_value(cb_data, x)` is not integer (to some tolerance).\n", " # Our lazy constraint generator requires an\n", " # integer-feasible primal solution, so we can add a `return` here.\n", " return\n", " elseif status == MOI.CALLBACK_NODE_STATUS_INTEGER\n", " # `callback_value(cb_data, x)` is integer (to some tolerance).\n", " println(\"[๐Ÿ˜] Current node has an integer solution\")\n", " else\n", " @assert status == MOI.CALLBACK_NODE_STATUS_UNKNOWN\n", " # `callback_value(cb_data, x)` might be integer feasible or infeasible,\n", " # in such a case it is best if we call our lazy constraint\n", " # @assert ensures that if the node status is none of the three conditions above, \n", " # then it will throw an error\n", " end\n", " x_val = callback_value.(cb_data, x) # load the value of the interim solution at the node \n", " for i in 1:p\n", " if sum(D[i,j]*x_val[j] for j in 1:n) > h[i] + 1e-6 \n", " println(\"[๐Ÿ˜ป] Submitting $(i)-th constraint d[i]'x <= h[i] as a lazy constraint\")\n", " # ๐Ÿ’€ note that we using x_val which is a known vector, not x which is the variable\n", " # also, added a small number 1e-6 to ensure numberical stability\n", " # now add the lazy constraint\n", " con = @build_constraint(sum(D[i,j]*x[j] for j in 1:n) <= h[i])\n", " MOI.submit(lazy_model, MOI.LazyConstraint(cb_data), con) #๐Ÿ’€ need to submit the constraint to our model\n", " break\n", " end\n", " end\n", "end\n", "\n", "MOI.set(lazy_model, MOI.LazyConstraintCallback(), my_callback_function) \n", "# ๐Ÿ’€ need to invoke this command so that JuMP knows that \"my_callback_function\" is used to generate lazy constraints\n", "\n", "optimize!(lazy_model)" ] }, { "cell_type": "code", "execution_count": 51, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "20-element Vector{Float64}:\n", " 1.0\n", " -0.0\n", " -0.0\n", " 1.0\n", " -0.0\n", " -0.0\n", " 1.0\n", " 1.0\n", " -0.0\n", " -0.0\n", " -0.0\n", " 1.0\n", " -0.0\n", " 0.9999999999999992\n", " 1.0\n", " 1.0\n", " 1.0000000000000004\n", " 0.0\n", " 1.0\n", " 0.0" ] }, "execution_count": 51, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x_sol = value.(x)" ] }, { "cell_type": "code", "execution_count": 52, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1.0, 1.0, 1.0000000000000004, 0.0, 1.0, 0.0]\n" ] } ], "source": [ "println(x_sol[15:20])" ] }, { "cell_type": "code", "execution_count": 53, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "10.0" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sum(x_sol)" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "D*x_sol <= h" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "-48.0618898866258" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "lazy_obj_val = objective_value(lazy_model)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### User cuts\n", "\n", "> * User cuts: User cuts, or simply cuts, provide a way for the user to tighten the LP relaxation using problem-specific knowledge that the solver cannot or is unable to infer from the model. Just like with lazy constraints, when a MIP solver reaches a new node in the branch-and-bound tree, it will give the user the chance to provide cuts to make the current relaxed (fractional) solution infeasible in the hopes of obtaining an integer solution. \n", "\n", "```\n", "model = Model(Gurobi.Optimizer)\n", "@variable(model, x <= 10.5, Int)\n", "@objective(model, Max, x)\n", "function my_callback_function(cb_data)\n", " x_val = callback_value(cb_data, x)\n", " con = @build_constraint(x <= floor(x_val))\n", " MOI.submit(model, MOI.UserCut(cb_data), con)\n", "end\n", "MOI.set(model, MOI.UserCutCallback(), my_callback_function)\n", "optimize!(model)\n", "```\n", "\n", "I personally recommend against using user cuts, unless you have a very good idea about the set of integer feasible solutions for your problem. \n", "\n", "* User cuts must not change the set of integer feasible solutions. \n", "\n", "* Equivalently, user cuts can only remove fractional solutions. \n", "\n", "* If you add a cut that removes an integer solution (even one that is not optimal), the solver may return an incorrect solution." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Heuristic solution\n", "\n", "You may want to add a heuristic of your own if you have some special insight into the problem structure that the solver is not aware of, for example, you can consistently take fractional solutions and intelligently guess integer solutions from them. \n", "\n", "Consider the made-up problem:\n", "\n", "\n", "\\begin{array}{ll}\n", "\\underset{x\\in\\mathbf{R}^{d}}{\\mbox{minimize}} & c^\\top x \\\\\n", "\\mbox{subject to} & Ax \\leq b,\\\\\n", " & x\\succeq0,\\\\\n", " & x\\in\\{0,1\\}^{d},\n", "\\end{array}\n", "\n", "\n", "For this problem, suppose from real life information, we know that, if $\\sum_{i=1}^{n} x_i \\leq 10$, then a very good candidate solution is: \n", "\n", "`[1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 0.0, 1.0, 0.0]`.\n", "\n", "Lets see how to implement this as a heuristic solution. " ] }, { "cell_type": "code", "execution_count": 54, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5-element Vector{Float64}:\n", " -7.3620594939851545\n", " 1.2864238748369008\n", " -5.191670678971517\n", " 3.4603990262005064\n", " -0.9930993374575348" ] }, "execution_count": 54, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# data\n", "n = 20\n", "m = 5\n", "A = [-0.25149258982896966 0.525287826731042 -0.6656342865169662 -1.2960398772338568 0.9101252450751471 -0.07298248406603706 -1.9148704340623688 -0.5073995272298952 -1.6558511941286744 2.1006659624182586 -0.502359026079171 -0.1708406495941207 1.4161030569819415 0.33735905844690145 -0.10748103771152817 -1.4416340194991104 -0.9578960880328228 -0.1738984790022571 -1.0517643292393826 -0.8271987403702172; -0.8518984622275042 -1.374417162491773 0.35920232369365845 0.8437691247979793 -0.6281577605465152 0.5921264379488904 -0.12756078132890084 -0.44447204507515287 0.7293549470299907 0.715267254601397 -0.9155882952842251 0.35378971887340743 -0.8043683142766567 0.5324223554306367 0.2088297149344946 -0.5594219995662968 0.5632674521223371 -0.2302672262989066 0.7676987968759004 1.0910836780489503; 1.473815753336459 -0.6525879104965642 0.8519411939583414 -0.05756789248416348 -0.7125581880426727 0.4736057460760701 -2.231011632648033 0.5409490591899032 0.1583459153748212 -1.1509507228336586 1.3994115761547934 0.14111034486559706 -0.15123003344570538 -0.547672888665602 -1.9555427017941476 -1.8533179907378834 0.13798098584535193 0.2337797562353011 -0.8404137158789987 0.060446173222487264; 0.6396537082966063 0.856847789735652 1.4805326346158039 0.012324563610194187 1.3977381658753554 1.3342059688961259 -0.4784014905808825 -0.14890693050929457 0.8155899237370289 -0.5697405099766946 1.3446291535605297 0.6840341944716634 1.2484251582871324 1.2891201777341281 -0.2791170028219365 0.43803145770984425 0.4677466100676112 1.3639772554672074 0.8359137382225728 0.8723882764319004; 0.40517145458826054 1.169967487661965 1.7941045258417871 1.035188318563306 1.118495812473751 -0.04027314052794962 0.5438620238342292 -0.8181792084120169 0.08209406151847103 0.6469386439823567 -0.9467882212470308 -0.2866858366079981 0.8836746919594078 -2.0164799655225094 -0.42541330025958685 -0.09145359012880407 0.8920741578367347 -0.5093214870138416 -0.23118339134915017 -1.262095251923206]\n", "c = [-5.724274247670441; 0.872180569098502; -13.289441619771337; -1.284190729811427; -10.090248808669005; 19.226305603166242; -14.323991615118594; -5.8893709748795615; -9.801477473401599; -2.533420139004128; -4.017671140375999; -12.25747413009963; -6.5234635509559205; -18.204822439044932; 10.759517257360242; -2.678837137470244; 2.6260424150728934; -9.929728378562064; -1.08448828496412; -14.883711771646961]\n", "b = [-7.3620594939851545; 1.2864238748369008; -5.191670678971517; 3.4603990262005064; -0.9930993374575348]\n" ] }, { "cell_type": "code", "execution_count": 55, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Set parameter TokenServer to value \"flexlm\"\n", "Set parameter Presolve to value 0\n", "Set parameter Heuristics to value 0\n", "Set parameter Heuristics to value 0\n", "Set parameter Presolve to value 0\n", "Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)\n", "Thread count: 48 physical cores, 96 logical processors, using up to 32 threads\n", "Optimize a model with 5 rows, 20 columns and 100 nonzeros\n", "Model fingerprint: 0xb04b5cd0\n", "Variable types: 0 continuous, 20 integer (20 binary)\n", "Coefficient statistics:\n", " Matrix range [1e-02, 2e+00]\n", " Objective range [9e-01, 2e+01]\n", " Bounds range [0e+00, 0e+00]\n", " RHS range [1e+00, 7e+00]\n", "Variable types: 0 continuous, 20 integer (20 binary)\n", "\n", "Root relaxation: objective -6.474229e+01, 9 iterations, 0.00 seconds (0.00 work units)\n", "\n", " Nodes | Current Node | Objective Bounds | Work\n", " Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time\n", "\n", " 0 0 -64.74229 0 4 - -64.74229 - - 0s\n", "[๐Ÿผ ] Heuristic condition satisfied\n", "[๐Ÿฏ ] Status of the callback node is: CALLBACK_NODE_STATUS_FRACTIONAL\n", "[๐Ÿฐ ]The values of the variables at the callback node [0.14765863276757993, 0.687383649659036, -0.0, 1.0, -0.0, -0.0, 1.0, 1.0, 1.0, -0.0, -0.0, 1.0, -0.0, 0.6051062159183456, 0.7099143090598492, 1.0, -0.0, -0.0, -0.0, 1.0]\n", "[๐Ÿ™€ ] Status of the submitted heuristic solution is: HEURISTIC_SOLUTION_ACCEPTED\n", "H 0 0 -48.2319356 -59.68164 23.7% - 0s\n", " 0 0 -49.20427 0 5 -48.23194 -49.20427 2.02% - 0s\n", "\n", "Cutting planes:\n", " Gomory: 6\n", " Cover: 3\n", " MIR: 2\n", " RLT: 1\n", "\n", "Explored 1 nodes (18 simplex iterations) in 0.03 seconds (0.00 work units)\n", "Thread count was 32 (of 96 available processors)\n", "\n", "Solution count 1: -48.2319 \n", "No other solutions better than -48.2319\n", "\n", "Optimal solution found (tolerance 1.00e-04)\n", "Best objective -4.823193564500e+01, best bound -4.823193564500e+01, gap 0.0000%\n", "\n", "User-callback calls 48, time in user-callback 0.03 sec\n" ] } ], "source": [ "# a proper code is as follows:\n", "\n", "hrstc_model = Model(Gurobi.Optimizer)\n", "\n", "set_optimizer_attribute(hrstc_model, \"Presolve\", 0)\n", "\n", "set_optimizer_attribute(hrstc_model, \"Heuristics\", 0)\n", "\n", "@variable(hrstc_model, x[1:n], Bin)\n", "\n", "for i in 1:m\n", " @constraint(hrstc_model, sum(A[i,j]*x[j] for j in 1:n) <= b[i])\n", "end\n", "\n", "@objective(hrstc_model, Min, sum(c[i] * x[i] for i in 1:n))\n", "\n", "\n", "# lazy constraint is added through the following callback function\n", "function my_heuristic_callback_function(cb_data)\n", " # load the current values of the variables at a node of the branch-and-bound tree\n", " x_val = callback_value.(cb_data, x)\n", " if sum(x_val) <= 10 # this is the condition for applying the heuristic\n", " println(\"[๐Ÿผ ] Heuristic condition satisfied\")\n", " println(\"[๐Ÿฏ ] Status of the callback node is: $(callback_node_status(cb_data,hrstc_model))\")\n", " # show the status of the callback node\n", " println(\"[๐Ÿฐ ]The values of the variables at the callback node $(x_val)\")\n", " # Load the heuristic solution values in a vertical vector pointwise\n", " heuristic_values = vcat(1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 0.0, 1.0, 0.0)\n", " # Submit the heuristic solution for potentially improving the current solution\n", " status = MOI.submit(\n", " hrstc_model, MOI.HeuristicSolution(cb_data), x, heuristic_values\n", " )\n", " println(\"[๐Ÿ™€ ] Status of the submitted heuristic solution is: \", status) # The status shows if the submitted heuristic solution is accepted or not\n", " end\n", "end\n", "\n", "# IMPORTANT: ๐Ÿ’€ This enables the heuristic\n", "MOI.set(hrstc_model, MOI.HeuristicCallback(), my_heuristic_callback_function)\n", "\n", "optimize!(hrstc_model)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A good resource to understand the cuts is [here](https://optimization.mccormick.northwestern.edu/index.php/Mixed-integer_cuts)." ] }, { "cell_type": "code", "execution_count": 56, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "20-element Vector{Float64}:\n", " 1.0\n", " -0.0\n", " -0.0\n", " 1.0\n", " -0.0\n", " -0.0\n", " 1.0\n", " 1.0\n", " 1.0\n", " -0.0\n", " -0.0\n", " -0.0\n", " -0.0\n", " 1.0\n", " 1.0\n", " 1.0\n", " -0.0\n", " -0.0\n", " 1.0\n", " -0.0" ] }, "execution_count": 56, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x_hrstc_opt = value.(x)" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1.0, -0.0, -0.0, 1.0, -0.0, -0.0, 1.0, 1.0, 1.0, -0.0, -0.0, -0.0, -0.0, 1.0, 1.0, 1.0, -0.0, -0.0, 1.0, -0.0]\n" ] } ], "source": [ "println(x_hrstc_opt)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Warm-starting \n", "\n", "> * Warm-starting: If you know a good feasible solution for your problem, then you can provide `Gurobi` with that solution via `warm-starting`." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Consider the same problem as before:\n", "\n", "\n", "\\begin{array}{ll}\n", "\\underset{x\\in\\mathbf{R}^{d}}{\\mbox{minimize}} & c^\\top x \\\\\n", "\\mbox{subject to} & Ax \\leq b,\\\\\n", " & x\\succeq0,\\\\\n", " & x\\in\\{0,1\\}^{d},\n", "\\end{array}\n", "\n", "\n", "But rather than custom heuristic, we want to feed the candidate solution is as a warm-start point, so `Gurobi` will start from this point and explore the tree from there. \n", "\n", "`x_warm_start = [1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 0.0, 1.0, 0.0]`." ] }, { "cell_type": "code", "execution_count": 57, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Set parameter TokenServer to value \"flexlm\"\n", "Set parameter Presolve to value 0\n", "Set parameter Heuristics to value 0\n", "Set parameter Heuristics to value 0\n", "Set parameter Presolve to value 0\n", "Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)\n", "Thread count: 48 physical cores, 96 logical processors, using up to 32 threads\n", "Optimize a model with 5 rows, 20 columns and 100 nonzeros\n", "Model fingerprint: 0x7cfd95e8\n", "Variable types: 0 continuous, 20 integer (20 binary)\n", "Coefficient statistics:\n", " Matrix range [1e-02, 2e+00]\n", " Objective range [9e-01, 2e+01]\n", " Bounds range [0e+00, 0e+00]\n", " RHS range [1e+00, 7e+00]\n", "\n", "Loaded user MIP start with objective -48.2319\n", "\n", "Variable types: 0 continuous, 20 integer (20 binary)\n", "\n", "Root relaxation: objective -6.474229e+01, 9 iterations, 0.00 seconds (0.00 work units)\n", "\n", " Nodes | Current Node | Objective Bounds | Work\n", " Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time\n", "\n", " 0 0 -64.74229 0 4 -48.23194 -64.74229 34.2% - 0s\n", " 0 0 -48.23194 0 6 -48.23194 -48.23194 0.00% - 0s\n", "\n", "Cutting planes:\n", " Gomory: 3\n", " Cover: 1\n", " MIR: 1\n", " RLT: 3\n", "\n", "Explored 1 nodes (17 simplex iterations) in 0.00 seconds (0.00 work units)\n", "Thread count was 32 (of 96 available processors)\n", "\n", "Solution count 1: -48.2319 \n", "No other solutions better than -48.2319\n", "\n", "Optimal solution found (tolerance 1.00e-04)\n", "Best objective -4.823193564500e+01, best bound -4.823193564500e+01, gap 0.0000%\n", "\n", "User-callback calls 49, time in user-callback 0.00 sec\n" ] } ], "source": [ "# a proper code is as follows:\n", "\n", "x_warm_start = [1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 0.0, 1.0, 0.0];\n", "\n", "ws_model = Model(Gurobi.Optimizer)\n", "\n", "set_optimizer_attribute(ws_model, \"Presolve\", 0)\n", "\n", "set_optimizer_attribute(ws_model, \"Heuristics\", 0)\n", "\n", "@variable(ws_model, x2[1:n], Bin)\n", "\n", "for i in 1:m\n", " @constraint(ws_model, sum(A[i,j]*x2[j] for j in 1:n) <= b[i])\n", "end\n", "\n", "# warm-starting here:\n", "\n", "set_start_value.(x2, x_warm_start)\n", "\n", "\n", "@objective(ws_model, Min, sum(c[i] * x2[i] for i in 1:n))\n", "\n", "optimize!(ws_model)" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "20-element Vector{Float64}:\n", " 1.0\n", " -0.0\n", " -0.0\n", " 1.0\n", " -0.0\n", " -0.0\n", " 1.0\n", " 1.0\n", " 1.0\n", " -0.0\n", " -0.0\n", " -0.0\n", " -0.0\n", " 1.0\n", " 1.0\n", " 1.0\n", " -0.0\n", " -0.0\n", " 1.0\n", " -0.0" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x_ws_opt = value.(x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "As an illustrative example, we will consider the sparse regression problem. The sparse regression is a nonconvex optimization problem with applications to gene expression analysis and signal processing etc.\n", "\n", "**Sparse regression problem.** The sparse regression problem is concerned with approximating a vector $b\\in\\mathbf{R}^{m}$ with a linear combination of at most $k$ columns of a matrix $A\\in\\mathbf{R}^{m\\times n}$ with bounded coefficients. The problem can be written as the following optimization problem \n", "$$\n", "\\begin{array}{ll} \\textrm{minimize} & \\|Ax-b\\|^{2}\\\\ \\textrm{subject to} & \\mathbf{card}(x)\\leq k\\\\ & \\|x\\|_{\\infty}\\leq M, \\end{array} \n", "$$\n", "where $x\\in\\mathbf{R}^{n}$ is the decision variable, and $A\\in\\mathbf{R}^{m\\times n},b\\in\\mathbf{R}^{m},$ and $M\\in\\mathbf{R}$ are problem data. Here, $\\mathbf{card}(x)$ is the number of nonzero components in $x$.\n", "\n", "**Modeling sparse regression problem as a MIQP.** The sparse regression problem can be modeled as the following MIQP: \n", "$$\n", "\\begin{array}{ll} \\textrm{minimize} & \\|Ax-b\\|^{2}\\\\ \\textrm{subject to} & |x_{i}|\\leq My_{i},\\quad i=1,\\ldots,n \\qquad (1)\\\\ & \\sum_{i=1}^{n}y_{i}\\leq k\\\\ & x\\in\\mathbf{R}^{n},y\\in\\{0,1\\}^{n}, \\end{array}\n", "$$\n", "where $x, y$ are decision variables.\n", "\n", "We can write our objective function as \n", "$$\n", "\\begin{align*} \\|Ax-b\\|^{2} & =(Ax-b)^{\\intercal}(Ax-b)\\\\ & =(x^{\\intercal}A^{\\intercal}-b^{\\intercal})(Ax-b)\\\\ & =x^{\\intercal}(A^{\\intercal}A)x+(-2A^{\\intercal}b)^{\\intercal}x+\\|b\\|^{2}, \n", "\\end{align*}\n", "$$\n", "which takes the function in a quadratic form." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Rewriting the objective in a compatible format.** If we define $S=A^{\\intercal}A,$ $c=-2A^{\\intercal}b,$ and $d=\\|b\\|^{2},$ then we can write the objective function as: $$ \\sum_{i=1}^{n}\\sum_{j=1}^{n}S_{ij}x_{i}x_{j}+\\sum_{i=1}^{n}c_{i}x_{i}+d, $$ which is more compatible as an input for `JuMP`.\n", "\n", "**Rewriting the bound constraint in a more compatible format.** Also, for `JuMP`, we write the bound constraint $|x_{i}|\\leq My_{i}$ as two constraints: $x_i \\leq M y_i$, and $-M y_i \\leq x_i$ for $i=1,\\ldots,n$." ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5.652765754068141" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Data, change it accordingly\n", "# ---------------------------\n", "\n", "m = 5\n", "n = 10\n", "A = randn(m,n)\n", "b = randn(m)\n", "M = 1\n", "k = convert(Int64, round(m/3))\n", "\n", "# Renaming a bunch of variables\n", "S = A'*A\n", "c = -2*A'*b\n", "d = norm(b)^2" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Set parameter TokenServer to value \"flexlm\"\n", "Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)\n", "Thread count: 48 physical cores, 96 logical processors, using up to 32 threads\n", "Optimize a model with 21 rows, 20 columns and 50 nonzeros\n", "Model fingerprint: 0x4ad08fc0\n", "Model has 55 quadratic objective terms\n", "Variable types: 10 continuous, 10 integer (10 binary)\n", "Coefficient statistics:\n", " Matrix range [1e+00, 1e+00]\n", " Objective range [1e+00, 7e+00]\n", " QObjective range [1e-01, 3e+01]\n", " Bounds range [0e+00, 0e+00]\n", " RHS range [2e+00, 2e+00]\n", "Found heuristic solution: objective 5.6527658\n", "Presolve time: 0.00s\n", "Presolved: 21 rows, 20 columns, 50 nonzeros\n", "Presolved model has 55 quadratic objective terms\n", "Variable types: 10 continuous, 10 integer (10 binary)\n", "\n", "Root relaxation: objective 1.111026e-01, 65 iterations, 0.00 seconds (0.00 work units)\n", "\n", " Nodes | Current Node | Objective Bounds | Work\n", " Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time\n", "\n", " 0 0 0.11110 0 4 5.65277 0.11110 98.0% - 0s\n", "H 0 0 0.4923181 0.11110 77.4% - 0s\n", " 0 0 0.33538 0 4 0.49232 0.33538 31.9% - 0s\n", " 0 0 0.33538 0 4 0.49232 0.33538 31.9% - 0s\n", " 0 0 0.37953 0 2 0.49232 0.37953 22.9% - 0s\n", " 0 0 0.37953 0 2 0.49232 0.37953 22.9% - 0s\n", " 0 0 0.37953 0 1 0.49232 0.37953 22.9% - 0s\n", "\n", "Explored 1 nodes (99 simplex iterations) in 0.01 seconds (0.00 work units)\n", "Thread count was 32 (of 96 available processors)\n", "\n", "Solution count 3: 0.492318 5.65277 5.65277 \n", "\n", "Optimal solution found (tolerance 1.00e-04)\n", "Best objective 4.923181247866e-01, best bound 4.923181247866e-01, gap 0.0000%\n", "\n", "User-callback calls 193, time in user-callback 0.00 sec\n" ] } ], "source": [ "# Define the model\n", "# ----------------\n", "\n", "model = Model(with_optimizer(Gurobi.Optimizer)) # define name of the model, it could be anything, not necessarily \"model\"\n", "\n", "# Variables\n", "# ---------\n", "\n", "@variable(model, x[1:n]) # define variable x \n", "\n", "@variable(model, y[1:n], Bin) # define the binary variable y\n", "\n", "# Objective\n", "# ---------\n", "\n", "sense = MOI.MIN_SENSE # by this command, we are programatically defining a quadratic objective to be minimized \n", "\n", "@objective(model, sense, sum(S[i,j]*x[i]*x[j] for i in 1:n, j in 1:n)+ sum(c[i]*x[i] for i in 1:n) + d) # define the objective\n", "\n", "# Constraints\n", "# ------------\n", "\n", "@constraint(model, con_lb[i=1:n], -M*y[i] <= x[i]) # lower bound constraint\n", "\n", "@constraint(model, con_ub[i=1:n], x[i] <= M*y[i]) # upper bound constraint\n", "\n", "@constraint(model, con_bd_sum, sum(y[i] for i in 1:n) <= k) # cardinality constraint in terms of y\n", "\n", "# Run the optimizer\n", "# -----------------\n", "\n", "status=optimize!(model) # time to optimize!" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Julia 1.6.1", "language": "julia", "name": "julia-1.6" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.6.1" }, "latex_envs": { "LaTeX_envs_menu_present": true, "autoclose": false, "autocomplete": true, "bibliofile": "biblio.bib", "cite_by": "apalike", "current_citInitial": 1, "eqLabelWithNumbers": true, "eqNumInitial": 1, "hotkeys": { "equation": "Ctrl-E", "itemize": "Ctrl-I" }, "labels_anchors": false, "latex_user_defs": false, "report_style_numbering": false, "user_envs_cfg": false }, "toc": { "base_numbering": 1, "nav_menu": {}, "number_sections": true, "sideBar": true, "skip_h1_title": false, "title_cell": "Table of Contents", "title_sidebar": "Contents", "toc_cell": false, "toc_position": {}, "toc_section_display": true, "toc_window_display": false }, "varInspector": { "cols": { "lenName": 16, "lenType": 16, "lenVar": 40 }, "kernels_config": { "python": { "delete_cmd_postfix": "", "delete_cmd_prefix": "del ", "library": "var_list.py", "varRefreshCmd": "print(var_dic_list())" }, "r": { "delete_cmd_postfix": ") ", "delete_cmd_prefix": "rm(", "library": "var_list.r", "varRefreshCmd": "cat(var_dic_list()) " } }, "types_to_exclude": [ "module", "function", "builtin_function_or_method", "instance", "_Feature" ], "window_display": false } }, "nbformat": 4, "nbformat_minor": 4 }