{ "cells": [ { "cell_type": "markdown", "id": "7c0bce68-45de-4f1d-a607-c86442252695", "metadata": {}, "source": [ "# Mixed-integer Linear Programming (MILP)\n", "\n", "We will learn about basic and advanced implementation of MILP problems through a running example. The example problem that we select is the knapsack problem, which is a very famous $NP$-hard problem.\n", "\n", "\n", "**Knapsack problem**\n", "\n", "* Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. \n", "\n", "* It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. \n", "\n", "* The problem often arises in resource allocation where the decision makers have to choose from a set of non-divisible projects or tasks under a fixed budget or time constraint, respectively.\n", "\n", "* Graphical example: which boxes should be chosen to maximize the amount of money while still keeping the overall weight under or equal to 15 kg? \n", "(Solution: if any number of each box is available, then three yellow boxes and three grey boxes; if only the shown boxes are available, then all but not the green box.)\n", "\n", "![Knapsack](./Knapsack.png) " ] }, { "cell_type": "markdown", "id": "d59c02ba-ec5d-4cbf-8027-ed21cdf5171d", "metadata": {}, "source": [ "**Modeling the problem**\n", "\n", "* We are given a set of $n$ items numbered from 1 up to $n$. We are allowed to select multiple units of the same item.\n", "\n", "* Each item has a weight $w_{i}$ kg,\n", "\n", "* Each item has monetary value $v_{i}$ dollar, \n", "\n", "* We have a bag with maximum weight capacity $W$,\n", "\n", "* Goal: We want to put as many of the items as possible in this bag to maximize the monetary value of the bag\n", "\n", "An optimization problem that will model the situation above is: \n", "\n", "$$\n", "\\begin{array}{ll}\n", "\\underset{x\\in\\mathbf{R}^{n}}{\\mbox{minimize}} & \\sum_{i=1}^{n}v_{i}x_{i}\\\\\n", "\\mbox{subject to} & \\sum_{i=1}^{n}w_{i}x_{i}\\leq W,\\\\\n", " & x_{i}\\in\\{0,1,2,\\ldots\\},\\quad i=1,\\ldots,n.\n", "\\end{array}\n", "$$\n", "\n", "This is a integer optimization problem. \n" ] }, { "cell_type": "markdown", "id": "b7400a6e-f201-4215-8365-1f87135041be", "metadata": {}, "source": [ "Let us first solve the problem using the basic implementation.\n", "\n", "## Basic Implementation" ] }, { "cell_type": "code", "execution_count": 4, "id": "02590852-6565-4a72-bb6e-80dcf31e7b95", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "50" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# 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", "W = 50\n", "n = length(v)" ] }, { "cell_type": "code", "execution_count": 1, "id": "5a49ff3a-4717-4b0b-8516-34f2fd018499", "metadata": {}, "outputs": [], "source": [ "using JuMP, Gurobi" ] }, { "cell_type": "code", "execution_count": 145, "id": "ae813e6b-bf42-4d7d-9a82-f848267cc87d", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Set parameter Username\n", "Academic license - for non-commercial use only - expires 2022-03-13\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": 145, "metadata": {}, "output_type": "execute_result" } ], "source": [ "knapsack_model = Model(Gurobi.Optimizer)" ] }, { "cell_type": "markdown", "id": "03757010-d5e1-4456-9c45-b70c88385342", "metadata": {}, "source": [ "Add the variable $x$ along with the binary constraint." ] }, { "cell_type": "code", "execution_count": 146, "id": "ed8cf970-ac08-41a6-8302-eee88fd1ae36", "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": 146, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(knapsack_model, x[1:n] >= 0, Int)" ] }, { "cell_type": "markdown", "id": "00d14499-3123-4e02-bf55-ddb9f3d352c0", "metadata": {}, "source": [ "Add the objective $v^\\top x$." ] }, { "cell_type": "code", "execution_count": 147, "id": "e1659092-18df-4df9-9748-7de3f282b158", "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": 147, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@objective(knapsack_model, Max, v' * x)" ] }, { "cell_type": "markdown", "id": "a07810bd-e02d-4d53-8f0c-2cebc7091947", "metadata": {}, "source": [ "Add the constraint $w^\\top x \\leq W$." ] }, { "cell_type": "code", "execution_count": 148, "id": "449b8fbf-873d-4e10-9fc0-211f5c874c6a", "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": 148, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@constraint(knapsack_model, w' * x <= W)" ] }, { "cell_type": "code", "execution_count": 149, "id": "0351755c-1923-434b-9c0f-5b64c795ee72", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (win64)\n", "Thread count: 4 physical cores, 8 logical processors, using up to 8 threads\n", "Optimize a model with 1 rows, 50 columns and 50 nonzeros\n", "Model fingerprint: 0x369feda4\n", "Variable types: 0 continuous, 50 integer (0 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", "Found heuristic solution: objective 116.0000000\n", "Presolve removed 1 rows and 50 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 8 available processors)\n", "\n", "Solution count 2: 200 116 \n", "\n", "Optimal solution found (tolerance 1.00e-04)\n", "Best objective 2.000000000000e+02, best bound 2.000000000000e+02, gap 0.0000%\n", "\n", "User-callback calls 178, time in user-callback 0.00 sec\n" ] } ], "source": [ "optimize!(knapsack_model)" ] }, { "cell_type": "code", "execution_count": 152, "id": "8d6f9d8f-9e59-439c-9f77-8d84b045491f", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 50.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]\n" ] } ], "source": [ "println(abs.(value.(x)))" ] }, { "cell_type": "code", "execution_count": 153, "id": "04eb603a-5640-4d07-a7b2-6ba1aed29345", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "200.0" ] }, "execution_count": 153, "metadata": {}, "output_type": "execute_result" } ], "source": [ "objective_value(knapsack_model)" ] }, { "cell_type": "markdown", "id": "1a1f3d0a-0a01-43ac-98f3-ec33b188f255", "metadata": {}, "source": [ "### Implementation through callback\n", "\n", "In practice, the MILP problem that we are interested in solving, comes with specific structure, and callback functions allow us a way to provide the solver with such structure specific insight. \n", "\n", "JuMP provides solver-independent support for three types of callbacks:\n", "\n", "* lazy constraints\n", "* user-cuts\n", "* heuristic solutions." ] }, { "cell_type": "code", "execution_count": null, "id": "3a48ea86-9e20-46b6-9ee5-605afd560e81", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "8e4e8a52-8c8f-420e-914c-b9aa654df738", "metadata": {}, "source": [ "### Lazy constraint\n", "\n", "We see in the solution of the knapsack problem that, it has put all the eggs in one basket. This may not be a desirable solution. So, we want the optimal solution to satisfyi the following condition. We want the maximum difference between the selected quantities of any two items to be no more that $\\alpha$.\n", "This requirement leads to $$2 {n \\choose 2}$$ constraints of the form: $$x_i - x_j \\leq \\alpha \\quad \\forall i \\neq j.$$\n", "\n", "Instead of enumerating all of them and adding them a priori to the model, we may use a technique known as **lazy constraints**.\n", "\n", "In particular, every time our 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 constraint(s) that would make the current solution infeasible.\n", "\n", "\n", "#### Reasons to Use Lazy Constraints\n", "\n", "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", "#### How to implement lazy constraints in `JuMP`\n", "\n", "There are three important steps to providing a lazy constraint callback in JuMP. \n", "\n", "- **Callback function**: a function that will analyze the current solution. This function takes as argument a reference to the callback management code inside JuMP. Currently, the only thing we may query in a callback is the primal value of the variables using the function \"callback_value\". \n", "\n", "- **Lazy constraint**: after analyzing the current solution, we generate a new constraint using the \n", "\n", " \"con = @build_constraint(...)\" \n", " macro and submit it to the model via the MOI interface \n", " \n", " \"MOI.submit(model, MOI.LazyConstraint(cb), con).\"\n", " \n", "- **Lazy constraint callback**: we again use the MOI interface to tell the solver which function should be used for lazy constraint generation \n", "\n", " \"MOI.set(model, MOI.LazyConstraintCallback(), my_callback).\"" ] }, { "cell_type": "code", "execution_count": 7, "id": "297a26dc-b57c-4a51-bd55-3830c70e04b3", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Set parameter Username\n", "Academic license - for non-commercial use only - expires 2022-03-13\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": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "new_knapsack_model = Model(Gurobi.Optimizer)" ] }, { "cell_type": "code", "execution_count": 8, "id": "fc7b3e93-5d65-4583-97dd-269789e338b7", "metadata": {}, "outputs": [], "source": [ "@variable(new_knapsack_model , x[1:n] >= 0, Int);" ] }, { "cell_type": "code", "execution_count": 9, "id": "72228609-deba-4483-ae50-9059b1345d04", "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": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@objective(new_knapsack_model , Max, v' * x)" ] }, { "cell_type": "code", "execution_count": 10, "id": "939c26c5-30b6-4add-b799-a35b248b8840", "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": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@constraint(new_knapsack_model , w' * x <= W)" ] }, { "cell_type": "code", "execution_count": 30, "id": "8c0cdb6a-e6ed-43dc-84bc-cdbf8522f6a9", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Set parameter Username\n", "Academic license - for non-commercial use only - expires 2022-03-13\n", "Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (win64)\n", "Thread count: 4 physical cores, 8 logical processors, using up to 8 threads\n", "Optimize a model with 1 rows, 5 columns and 5 nonzeros\n", "Model fingerprint: 0x51d1e86e\n", "Variable types: 0 continuous, 5 integer (5 binary)\n", "Coefficient statistics:\n", " Matrix range [2e+00, 8e+00]\n", " Objective range [2e+00, 7e+00]\n", " Bounds range [0e+00, 0e+00]\n", " RHS range [1e+01, 1e+01]\n", "Found heuristic solution: objective 8.0000000\n", "Presolve removed 1 rows and 5 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 8 available processors)\n", "\n", "Solution count 2: 16 8 \n", "\n", "Optimal solution found (tolerance 1.00e-04)\n", "Best objective 1.600000000000e+01, best bound 1.600000000000e+01, gap 0.0000%\n", "\n", "User-callback calls 236, time in user-callback 0.06 sec\n" ] } ], "source": [ "function callback_function(cb_data)\n", " if callback_value(x[1]) == 1\n", " con = @build_constraint(x[3] == 1)\n", " MOI.submit(knapsack_model, MOI.LazyConstraint(cb_data), con)\n", " println(\"[🙀 ] The lazy constraint is submitted\", status) \n", " # The status shows if the submitted heuristic solution is accepted or not\n", " end\n", "end\n", "\n", "MOI.set(knapsack_model, MOI.HeuristicCallback(), good_callback_function)\n", "\n", "optimize!(knapsack_model)" ] }, { "cell_type": "code", "execution_count": null, "id": "8bbb814b-a564-4a29-979e-cb1106e0c593", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Julia 1.6.5", "language": "julia", "name": "julia-1.6" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.6.5" } }, "nbformat": 4, "nbformat_minor": 5 }