{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Mixed-integer programming\n",
"\n",
"Operations research often involves models where you need discrete decisions. \n",
"\n",
"Suppose Iain wants to carry items to the pawn shop to get some extra cash. He has $N$ items, each with a weight $w_i$ and a price $p_i$. Iain hasn't been to the gym lately, so he can only carry $C$ kilos. How does he choose what to bring with him?\n",
"\n",
"We can model this as an integer optimization problem:\n",
"\n",
"\\begin{align*}\n",
"\\max& \\sum_{i=1}^N p_i x_i \\\\\n",
"\\text{s.t.}& \\sum_{i=1}^N w_i x_i \\leq C \\\\\n",
"& x_i \\in \\{0,1\\} \\quad \\forall i = 1,\\ldots,N\n",
"\\end{align*}\n",
"\n",
"In particular, let us work through the following example:\n",
"\n",
"\\begin{align*}\n",
" \\max\\:& x_1 + x_2 \\\\\n",
" \\text{s.t.}\\:& x_1 + 2x_2 \\leq 1.5 \\\\\n",
" & x_1, x_2 \\in \\{0,1\\}\n",
"\\end{align*}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Discussion**: Suppose you have a solver that can only solve linear optimization problems. How might you try to solve it?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Branch-and-Bound\n",
"One way is to enumerate each possible value for the decision variables $x_1=x, x_2=y$ and compare the cost. Let's visualize this approach as a search tree:\n",
"\n",
"![Full Tree](http://www.mit.edu/~huchette/.tmp/fulltree.svg)\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`` is no more than that for node ``p``\n",
"\n",
"This leads us to a powerful tool in solving these enumeration problems: \n",
"\n",
">If I can show you that the optimal cost for subproblem ``q`` is _less_ than the optimal cost for the original problem, the same is true for any descendent of ``q``. \n",
"\n",
"That is, we can _prune_ the tree and safely discard some nodes, kind of like this:\n",
"![Pruning](http://www.mit.edu/~huchette/.tmp/fathom.svg)\n",
"\n",
"**Discussion**: What can we do if we have integer (and not just binary) variables?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Worked Example\n",
"First, we solve the LP relaxation and get $(x_1^*,x_2^*) = (1,0.25)$.\n",
"\n",
"![fig1](http://www.mit.edu/~huchette/.tmp/fig2.svg)\n",
"\n",
"This isn't integer feasible, so we consider two cases for $x_2$: (i) when $x_2=0$ and (ii) when $x_2=1$. The subproblem with $x_2 = 1$ is infeasible, and the subproblem with $x_2 = 0$ is feasible with solution $(x_1^*,x_2^*) = (1,0)$. This is integer feasible, so we update our lower bound. We've also exhausted the tree, so we have our optimal solution!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Implementation in JuMP\n",
"\n",
"Let's solve our simple knapsack problem for Iain and see what the solver spits out."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Optimize a model with 1 rows, 2 columns and 2 nonzeros\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 [1e+00, 1e+00]\n",
" RHS range [2e+00, 2e+00]\n",
"Found heuristic solution: objective 1\n",
"Presolve removed 1 rows and 2 columns\n",
"Presolve time: 0.01s\n",
"Presolve: All rows and columns removed\n",
"\n",
"Explored 0 nodes (0 simplex iterations) in 0.01 seconds\n",
"Thread count was 1 (of 4 available processors)\n",
"\n",
"Solution count 1: 1 \n",
"Pool objective bound 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"
]
},
{
"data": {
"text/plain": [
":Optimal"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"using JuMP, Gurobi\n",
"m = Model(solver=GurobiSolver())\n",
"\n",
"@variable(m, x, Bin) # or Int\n",
"@variable(m, y, Bin)\n",
"\n",
"@constraint(m, x + 2y ≤ 1.5)\n",
"@objective(m, Max, x + y)\n",
"\n",
"solve(m)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This is kind of dull since Gurobi solves this before we ever get to the branch-and-bound tree! Let's cook up a problem that's a little more interesting. What about more items, and more knapsacks! If $N=100$, naïve enumeration would create $2^{100}$ nodes, which would take quite some time. How does the solver actually tackle it?"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"search: \u001b[1mr\u001b[22m\u001b[1ma\u001b[22m\u001b[1mn\u001b[22m\u001b[1md\u001b[22m \u001b[1mr\u001b[22m\u001b[1ma\u001b[22m\u001b[1mn\u001b[22m\u001b[1md\u001b[22mn \u001b[1mr\u001b[22m\u001b[1ma\u001b[22m\u001b[1mn\u001b[22m\u001b[1md\u001b[22m! \u001b[1mr\u001b[22m\u001b[1ma\u001b[22m\u001b[1mn\u001b[22m\u001b[1md\u001b[22mn! \u001b[1mr\u001b[22m\u001b[1ma\u001b[22m\u001b[1mn\u001b[22m\u001b[1md\u001b[22mexp \u001b[1mr\u001b[22m\u001b[1ma\u001b[22m\u001b[1mn\u001b[22m\u001b[1md\u001b[22mperm \u001b[1mr\u001b[22m\u001b[1ma\u001b[22m\u001b[1mn\u001b[22m\u001b[1md\u001b[22mjump \u001b[1mr\u001b[22m\u001b[1ma\u001b[22m\u001b[1mn\u001b[22m\u001b[1md\u001b[22mexp! \u001b[1mr\u001b[22m\u001b[1ma\u001b[22m\u001b[1mn\u001b[22m\u001b[1md\u001b[22mcycle\n",
"\n"
]
},
{
"data": {
"text/markdown": [
"```\n",
"rand([rng], [S], [dims...])\n",
"```\n",
"\n",
"Pick a random element or array of random elements from the set of values specified by `S`; `S` can be\n",
"\n",
" * an indexable collection (for example `1:n` or `['x','y','z']`), or\n",
" * a type: the set of values to pick from is then equivalent to `typemin(S):typemax(S)` for integers (this is not applicable to `BigInt`), and to $[0, 1)$ for floating point numbers;\n",
"\n",
"`S` defaults to `Float64`.\n"
],
"text/plain": [
"```\n",
"rand([rng], [S], [dims...])\n",
"```\n",
"\n",
"Pick a random element or array of random elements from the set of values specified by `S`; `S` can be\n",
"\n",
" * an indexable collection (for example `1:n` or `['x','y','z']`), or\n",
" * a type: the set of values to pick from is then equivalent to `typemin(S):typemax(S)` for integers (this is not applicable to `BigInt`), and to $[0, 1)$ for floating point numbers;\n",
"\n",
"`S` defaults to `Float64`.\n"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"?rand"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Optimize a model with 10 rows, 100 columns and 1000 nonzeros\n",
"Variable types: 0 continuous, 100 integer (100 binary)\n",
"Coefficient statistics:\n",
" Matrix range [1e-03, 1e+00]\n",
" Objective range [2e-03, 1e+00]\n",
" Bounds range [1e+00, 1e+00]\n",
" RHS range [2e+00, 2e+00]\n",
"Found heuristic solution: objective 2.35937\n",
"Presolve time: 0.00s\n",
"Presolved: 10 rows, 100 columns, 1000 nonzeros\n",
"Variable types: 0 continuous, 100 integer (100 binary)\n",
"\n",
"Root relaxation: objective 4.014179e+00, 18 iterations, 0.00 seconds\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",
"H 0 0 3.3780464 4.01418 18.8% - 0s\n",
" 0 0 3.97490 0 9 3.37805 3.97490 17.7% - 0s\n",
" 0 0 3.97490 0 7 3.37805 3.97490 17.7% - 0s\n",
" 0 0 3.97490 0 9 3.37805 3.97490 17.7% - 0s\n",
" 0 0 3.96695 0 10 3.37805 3.96695 17.4% - 0s\n",
" 0 0 3.96609 0 10 3.37805 3.96609 17.4% - 0s\n",
"H 0 0 3.4484278 3.96609 15.0% - 0s\n",
" 0 0 3.95136 0 11 3.44843 3.95136 14.6% - 0s\n",
" 0 0 3.95080 0 12 3.44843 3.95080 14.6% - 0s\n",
" 0 0 3.94530 0 11 3.44843 3.94530 14.4% - 0s\n",
" 0 0 3.94500 0 11 3.44843 3.94500 14.4% - 0s\n",
" 0 0 3.94326 0 11 3.44843 3.94326 14.3% - 0s\n",
" 0 0 3.93269 0 12 3.44843 3.93269 14.0% - 0s\n",
" 0 0 3.92424 0 9 3.44843 3.92424 13.8% - 0s\n",
" 0 0 3.91789 0 11 3.44843 3.91789 13.6% - 0s\n",
" 0 0 3.91730 0 11 3.44843 3.91730 13.6% - 0s\n",
" 0 0 3.91673 0 11 3.44843 3.91673 13.6% - 0s\n",
" 0 2 3.91673 0 11 3.44843 3.91673 13.6% - 0s\n",
"H 105 37 3.5667097 3.83888 7.63% 3.3 0s\n",
"\n",
"Cutting planes:\n",
" Gomory: 2\n",
" Cover: 6\n",
" MIR: 9\n",
"\n",
"Explored 243 nodes (851 simplex iterations) in 0.08 seconds\n",
"Thread count was 4 (of 4 available processors)\n",
"\n",
"Solution count 4: 3.56671 3.44843 3.37805 2.35937 \n",
"Pool objective bound 3.56671\n",
"\n",
"Optimal solution found (tolerance 1.00e-04)\n",
"Best objective 3.566709698969e+00, best bound 3.566709698969e+00, gap 0.0000%\n"
]
},
{
"data": {
"text/plain": [
":Optimal"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"srand(100)\n",
"N = 100\n",
"\n",
"m = Model(solver=GurobiSolver())\n",
"@variable(m, x[1:N], Bin)\n",
"for _ in 1:10\n",
" @constraint(m, dot(rand(N), x) ≤ N / 50)\n",
"end\n",
"\n",
"@objective(m, Max, dot(rand(N), x))\n",
"\n",
"solve(m)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Understanding solver output"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"First, it 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 (lower bound)\n",
" * node upper bound\n",
" * the gap between the two\n",
"4. ``Work``\n",
" * average simplex iterations per node\n",
" * total elapsed time\n",
"\n",
"Finally, we get a neat summary of the cutting planes Gurobi found useful:\n",
"```\n",
"Cutting planes:\n",
" Gomory: 2\n",
" Cover: 6\n",
" MIR: 9\n",
"```\n",
"All told, we explored 243 nodes, much less than the $2^{100}$ we were worried about. All this only took 851 simplex iterations and 0.1 seconds.\n",
"\n",
"Now what about those ``H``s that appear? That tells us that Gurobi ran a heuristic and found a new best solution. You can see for yourself, as the incumbent value increases while the bound remains the same:\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",
"H 0 0 3.3780464 4.01418 18.8% - 0s\n",
"```\n",
"You'll also sometimes see a ``*`` instead of the ``H``, which says that the feasible solution came from branching instead of heuristics."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Sudoku\n",
"\n",
"![Sudoku](http://upload.wikimedia.org/wikipedia/commons/f/ff/Sudoku-by-L2G-20050714.svg)\n",
"\n",
"**Sudoku** is a number puzzle played on a 9x9 grid. The challenge is to place a digit between 1 and 9 inclusive in each empty cell, such that the completed grid obeys the following rules:\n",
"\n",
"* Each row contains the numbers 1 to 9 once and only once.\n",
"* Each column contains the numbers 1 to 9 once and only once.\n",
"* Each 3x3 subgrid contains the numbers 1 to 9 once and only once.\n",
"\n",
"The most natural formulation of this problem would probably be something like\n",
"\n",
"$$x_{i,j} \\in \\{1, 2, \\dots, 9\\}$$\n",
"\n",
"which is of course something we can do with integer programming:\n",
"\n",
"$$1 \\leq x_{i,j} \\leq 9, ~ integer$$\n",
"\n",
"The challenge now is the constraints. One observation is that the numbers 1 to 9 add up to 45, so we could try something like:\n",
"\n",
"$$ \\sum_{j=1}^9 x_{i,j} = 45 $$\n",
"\n",
"We could probably make this work, but we'd need many more constraints. Instead, lets change our **variables**: $x_{i,j,k} = 1$ iff the number $k$ will appear in cell $(i,j)$. We can now use our 0-1 integer programming knowledge to model the problem. Consider the \"row\" constraints: we want each number to appear once and only once. This is equivalent to saying that\n",
"\n",
"$$\\sum_{j=1}^9 x_{i,j,k} = 1 \\quad \\forall i, k$$\n",
"\n",
"We can now model this as a $9\\times 9\\times 9$ dimensional problem - thats a lot of binary variables, surely Gurobi won't like that!"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Optimize a model with 358 rows, 729 columns and 2950 nonzeros\n",
"Variable types: 0 continuous, 729 integer (729 binary)\n",
"Coefficient statistics:\n",
" Matrix range [1e+00, 1e+00]\n",
" Objective range [0e+00, 0e+00]\n",
" Bounds range [1e+00, 1e+00]\n",
" RHS range [1e+00, 1e+00]\n",
"Presolve removed 358 rows and 729 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\n",
"Thread count was 1 (of 4 available processors)\n",
"\n",
"Solution count 1: 0 \n",
"Pool objective bound 0\n",
"\n",
"Optimal solution found (tolerance 1.00e-04)\n",
"Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap -\n",
" 0.737858 seconds (530.36 k allocations: 21.626 MB, 1.14% gc time)\n"
]
}
],
"source": [
"init_vals = [\n",
"3 1 0 0 5 8 0 0 4;\n",
"0 0 9 3 2 0 0 0 0;\n",
"0 2 5 1 0 4 0 9 0;\n",
"0 0 0 0 0 0 3 8 9;\n",
"0 0 8 0 0 0 5 0 0;\n",
"5 4 6 0 0 0 0 0 0;\n",
"0 8 0 2 0 3 6 5 0;\n",
"0 0 0 0 7 1 4 0 0;\n",
"7 0 0 4 8 0 0 2 1]\n",
"\n",
"function sudoku2()\n",
" sudoku = Model(solver=GurobiSolver())\n",
"\n",
" @variable(sudoku, x[i=1:9, j=1:9, k=1:9], Bin)\n",
"\n",
" @constraints sudoku begin\n",
" # Constraint 1 - Only one value appears in each cell\n",
" # Constraint 2 - Each value appears in each row once only\n",
" # Constraint 3 - Each value appears in each column once only\n",
" cell[i=1:9, j=1:9], sum(x[i,j,:]) == 1\n",
" row[i=1:9, k=1:9], sum(x[i,:,k]) == 1\n",
" col[j=1:9, k=1:9], sum(x[:,j,k]) == 1\n",
" # Constraint 4 - Each value appears in each 3x3 subgrid once only\n",
" subgrid[i=1:3:7,j=1:3:7,val=1:9], sum(x[i:i+2,j:j+2,val]) == 1\n",
" end\n",
"\n",
" # Initial solution\n",
" for row in 1:9, col in 1:9\n",
" if init_vals[row,col] != 0\n",
" @constraint(sudoku, x[row, col, init_vals[row, col]] == 1)\n",
" end\n",
" end\n",
" \n",
" solve(sudoku)\n",
" \n",
" getvalue(x)\n",
"end\n",
"@time soln = sudoku2();"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Presolving the Problem\n",
"Can you see the lines\n",
"```\n",
"Optimize a model with 358 rows, 729 columns and 2950 nonzeros\n",
"Presolve removed 358 rows and 729 columns\n",
"```\n",
"? Gurobi was able to use logic to deduce the value of every variable - no linear relaxation required! This \"magic\" is actually how a human might solve it. Consider the following:\n",
"\n",
"We know that $x_{2,6,5}$ is fixed at 1 because it is one of the provided values. So we can actually replace $x_{2,6,5}$ wherever it appears in the constraints with the constant 1:\n",
"\n",
"\"The value 5 must appear in row 2\":\n",
"$$x_{2,1,5} + x_{2,2,5} + x_{2,3,5} + x_{2,4,5} + x_{2,5,5} + x_{2,6,5} + x_{2,7,5} + x_{2,8,5} + x_{2,9,5} = 1$$\n",
"$$\\rightarrow x_{2,1,5} + x_{2,2,5} + x_{2,3,5} + x_{2,4,5} + x_{2,5,5} + 1 + x_{2,7,5} + x_{2,8,5} + x_{2,9,5} = 1$$\n",
"$$\\rightarrow x_{2,1,5} + x_{2,2,5} + x_{2,3,5} + x_{2,4,5} + x_{2,5,5} + x_{2,7,5} + x_{2,8,5} + x_{2,9,5} = 0$$\n",
"\n",
"\"The value 5 must appear in column 6\":\n",
"$$x_{1,6,5} + x_{2,6,5} + x_{3,6,5} + x_{4,6,5} + x_{5,6,5} + x_{6,6,5} + x_{7,6,5} + x_{8,6,5} + x_{9,6,5} = 1$$\n",
"$$x_{1,6,5} + 1 + x_{3,6,5} + x_{4,6,5} + x_{5,6,5} + x_{6,6,5} + x_{7,6,5} + x_{8,6,5} + x_{9,6,5} = 1$$\n",
"$$x_{1,6,5} + x_{3,6,5} + x_{4,6,5} + x_{5,6,5} + x_{6,6,5} + x_{7,6,5} + x_{8,6,5} + x_{9,6,5} = 0$$\n",
"\n",
"and so on. Because all those other variables can only be 0 or 1, and their sum is 0, they must all be 0. Thus Gurobi presolve can perform the following procedure:\n",
"1. Replace all the fixed values with constants\n",
"2. Use constraints to fix variables, e.g. at 0 (or 1)\n",
"3. Go to 1 unless step 2 did nothing.\n",
"\n",
"A small problem arises when there a multiple solutions to the problem - a random selection has to be made. Gurobi will treat this case as \"trying to find a feasible solution\" - it will fix a variable, and follow the implications through.\n",
"\n",
"Gurobi can do similar presolving implications for continuous decisions too, e.g.\n",
"$$x \\in \\{ 0, 1 \\}$$\n",
"$$x \\leq \\frac{1}{2}$$\n",
"\n",
"will presolve to $x = 0$: Gurobi knows that all the variables are integer, so we can safe round down the right-hand-side to the closest integer."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
">**\\[Exercise\\]**: Pre-solve\n",
"\n",
"> What if the right-hand-side is more complicated? What can you do to \"tighten\" the following constraint and the variables in it?\n",
"\n",
"> $$ 6x_1 + 10x_2 + 12x_3 + 19x_4 \\leq 15$$\n",
"\n",
"> Hints:\n",
"> * Can you find common factors in the coefficients?\n",
"> * Can you round anything?\n",
"> * Can you prove things about the variable values?\n",
"\n",
"> (all variables are binary)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
">**\\[Solution\\]**: Pre-solve\n",
"\n",
"> * $6x_1 + 10x_2 + 12x_3 + 19x_4 \\leq 15$\n",
"> * $x_4$ must be 0, because if $x_4$ was 1 then the constaint would be violated\n",
"> * $6x_1 + 10x_2 + 12x_3 \\leq 15$\n",
"> * All coefficients on left are multiples of 2, so divide through by 2\n",
"> * $3x_1 + 5x_2 + 6x_3 \\leq 7.5$\n",
"> * All coefficients are integer, all variables are binary, so can round down the RHS.\n",
"> * $3x_1 + 5x_2 + 6x_3 \\leq 7$\n",
"> * We note though that only one of these variables can be one at a time, or the constraint would be violated, so the best we can do is actually\n",
"> * $x_1 + x_2 + x_3 \\leq 1$"
]
}
],
"metadata": {
"anaconda-cloud": {},
"kernelspec": {
"display_name": "Julia 0.5.0",
"language": "julia",
"name": "julia-0.5"
},
"language_info": {
"file_extension": ".jl",
"mimetype": "application/julia",
"name": "julia",
"version": "0.5.0"
},
"nbpresent": {
"slides": {
"0987fb1e-8692-4c07-bf13-2765ab155665": {
"id": "0987fb1e-8692-4c07-bf13-2765ab155665",
"prev": "b423e3f1-f7cc-40a8-9837-4564a87794a9",
"regions": {
"4d15a73c-6036-4b8e-944f-a44a1f528049": {
"attrs": {
"height": 0.8,
"width": 0.8,
"x": 0.1,
"y": 0.1
},
"content": {
"cell": "3d12821d-d639-4a37-97ff-49eb273333ab",
"part": "whole"
},
"id": "4d15a73c-6036-4b8e-944f-a44a1f528049"
}
}
},
"4a59f3ed-d415-4673-97f3-b44556b6bac8": {
"id": "4a59f3ed-d415-4673-97f3-b44556b6bac8",
"prev": "fe4596bb-70ef-4624-b45a-20bcd83a47c7",
"regions": {
"9558bf43-fbdd-4cbe-bb91-0b6cad0bcb70": {
"attrs": {
"height": 0.8,
"width": 0.8,
"x": 0.1,
"y": 0.1
},
"content": {
"cell": "ab3a2a22-723b-44b9-a831-7337aaecb8b5",
"part": "whole"
},
"id": "9558bf43-fbdd-4cbe-bb91-0b6cad0bcb70"
}
}
},
"5bda978a-a97f-497c-8383-b6f431f15d67": {
"id": "5bda978a-a97f-497c-8383-b6f431f15d67",
"prev": "4a59f3ed-d415-4673-97f3-b44556b6bac8",
"regions": {
"27dbe376-4a87-4d14-b2e1-7d01c143e2ef": {
"attrs": {
"height": 0.8,
"width": 0.8,
"x": 0.1,
"y": 0.1
},
"content": {
"cell": "3704e4c5-2d8e-4e67-bc0a-755a5001087b",
"part": "whole"
},
"id": "27dbe376-4a87-4d14-b2e1-7d01c143e2ef"
}
}
},
"84699e40-46ab-47a4-b726-6e38e629ba21": {
"id": "84699e40-46ab-47a4-b726-6e38e629ba21",
"prev": "0987fb1e-8692-4c07-bf13-2765ab155665",
"regions": {
"f92c2008-be1d-42b7-9d50-d903bd4238cc": {
"attrs": {
"height": 0.8,
"width": 0.8,
"x": 0.1,
"y": 0.1
},
"content": {
"cell": "a077c29f-22dd-4357-bee1-314ae7aba1fe",
"part": "whole"
},
"id": "f92c2008-be1d-42b7-9d50-d903bd4238cc"
}
}
},
"a2b1cb9a-9f42-491d-9f2f-670aa729ff2b": {
"id": "a2b1cb9a-9f42-491d-9f2f-670aa729ff2b",
"prev": null,
"regions": {
"5dd283e0-f53f-4d3f-afba-8f2e7de4c4cf": {
"attrs": {
"height": 0.8,
"width": 0.8,
"x": 0.1,
"y": 0.1
},
"content": {
"cell": "2666b73a-85f8-48c0-b427-b22b4ca58962",
"part": "whole"
},
"id": "5dd283e0-f53f-4d3f-afba-8f2e7de4c4cf"
}
}
},
"b423e3f1-f7cc-40a8-9837-4564a87794a9": {
"id": "b423e3f1-f7cc-40a8-9837-4564a87794a9",
"prev": "a2b1cb9a-9f42-491d-9f2f-670aa729ff2b",
"regions": {
"d7ad4ad1-2b18-4d00-ae33-c514a8a390c0": {
"attrs": {
"height": 0.8,
"width": 0.8,
"x": 0.1,
"y": 0.1
},
"content": {
"cell": "10d660a7-3e61-4fd7-a8e2-c2fca754d719",
"part": "whole"
},
"id": "d7ad4ad1-2b18-4d00-ae33-c514a8a390c0"
}
}
},
"d48b7fb0-3db8-43a5-9904-2c1b228c78bd": {
"id": "d48b7fb0-3db8-43a5-9904-2c1b228c78bd",
"prev": "5bda978a-a97f-497c-8383-b6f431f15d67",
"regions": {
"683fdb2a-3fa3-42df-9468-26bc6ff8d5c3": {
"attrs": {
"height": 0.8,
"width": 0.8,
"x": 0.1,
"y": 0.1
},
"content": {
"cell": "07c00aa9-009f-4830-9b46-745e4b573ea5",
"part": "whole"
},
"id": "683fdb2a-3fa3-42df-9468-26bc6ff8d5c3"
}
}
},
"f8c05f99-70a9-4bf5-9c08-af497d489b09": {
"id": "f8c05f99-70a9-4bf5-9c08-af497d489b09",
"prev": "d48b7fb0-3db8-43a5-9904-2c1b228c78bd",
"regions": {
"23f1988c-4dc0-4543-aeee-30cac2bd547a": {
"attrs": {
"height": 0.8,
"width": 0.8,
"x": 0.1,
"y": 0.1
},
"content": {
"cell": "7b01009a-27db-4a31-8f30-0e7a6e6238af",
"part": "whole"
},
"id": "23f1988c-4dc0-4543-aeee-30cac2bd547a"
}
}
},
"fe4596bb-70ef-4624-b45a-20bcd83a47c7": {
"id": "fe4596bb-70ef-4624-b45a-20bcd83a47c7",
"prev": "84699e40-46ab-47a4-b726-6e38e629ba21",
"regions": {
"9331bbb1-a335-475d-92e5-1450fb47f197": {
"attrs": {
"height": 0.8,
"width": 0.8,
"x": 0.1,
"y": 0.1
},
"content": {
"cell": "2ec49aa5-8e32-412c-8e7e-04127c0b7dc4",
"part": "whole"
},
"id": "9331bbb1-a335-475d-92e5-1450fb47f197"
}
}
}
},
"themes": {}
}
},
"nbformat": 4,
"nbformat_minor": 0
}