{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "title: Variables, Constraints and Objective\n", "---" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Originally Contributed by**: Arpit Bhatia" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "While the last tutorial introduced you to basics of of JuMP code, this tutorial will go in depth focusing on how to work \n", "with different parts of a JuMP program." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "using JuMP\n", "model = Model();" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Variables" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Variable Bounds\n", "All of the variables we have created till now have had a bound. We can also create a free variable." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$$ free_x $$" ], "text/plain": [ "free_x" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(model, free_x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "While creating a variable, instead of using the <= and >= syntax, we can also use the `lower_bound` and `upper_bound` keyword arguments." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$$ keyword_x $$" ], "text/plain": [ "keyword_x" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(model, keyword_x, lower_bound = 1, upper_bound = 2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can query whether a variable has a bound using the `has_lower_bound` and `has_upper_bound` functions. The values of the bound can be obtained \n", "using the `lower_bound` and `upper_bound` functions." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "has_upper_bound(keyword_x)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2.0" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "upper_bound(keyword_x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note querying the value of a bound that does not exist will result in an error." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "ename": "LoadError", "evalue": "Variable free_x does not have a lower bound.", "output_type": "error", "traceback": [ "Variable free_x does not have a lower bound.", "", "Stacktrace:", " [1] error(::String) at ./error.jl:33", " [2] lower_bound(::VariableRef) at /home/mbesancon/.julia/packages/JuMP/e0Uc2/src/variables.jl:422", " [3] top-level scope at In[6]:1", " [4] include_string(::Function, ::Module, ::String, ::String) at ./loading.jl:1091", " [5] execute_code(::String, ::String) at /home/mbesancon/.julia/packages/IJulia/a1SNk/src/execute_request.jl:27", " [6] execute_request(::ZMQ.Socket, ::IJulia.Msg) at /home/mbesancon/.julia/packages/IJulia/a1SNk/src/execute_request.jl:86", " [7] #invokelatest#1 at ./essentials.jl:710 [inlined]", " [8] invokelatest at ./essentials.jl:709 [inlined]", " [9] eventloop(::ZMQ.Socket) at /home/mbesancon/.julia/packages/IJulia/a1SNk/src/eventloop.jl:8", " [10] (::IJulia.var\"#15#18\")() at ./task.jl:356" ] } ], "source": [ "lower_bound(free_x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "JuMP also allows us to change the bounds on variable. We will learn this in the problem modification tutorial." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Containers\n", "We have already seen how to add a single variable to a model using the `@variable` macro. Let's now look at more ways to add \n", "variables to a JuMP model. JuMP provides data structures for adding collections of variables to a model. These data \n", "structures are reffered to as Containers and are of three types - `Arrays`, `DenseAxisArrays`, and `SparseAxisArrays`." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Arrays\n", "JuMP arrays are created in a similar syntax to Julia arrays with the addition of specifying that the indices start with 1. If\n", "we do not tell JuMP that the indices start at 1, it will create a DenseAxisArray instead." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 Array{VariableRef,2}:\n", " a[1,1] a[1,2]\n", " a[2,1] a[2,2]" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(model, a[1:2, 1:2])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "An n-dimensional variable $x \\in {R}^n$ having a bound $l \\preceq x \\preceq u$ ($l, u \\in {R}^n$) is added in the following \n", "manner." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "10-element Array{VariableRef,1}:\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]" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "n = 10\n", "l = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]\n", "u = [10; 11; 12; 13; 14; 15; 16; 17; 18; 19]\n", "\n", "@variable(model, l[i] <= x[i = 1:n] <= u[i])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that while working with Containers, we can also create variable bounds depending upon the indices" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 Array{VariableRef,2}:\n", " y[1,1] y[1,2]\n", " y[2,1] y[2,2]" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(model, y[i = 1:2, j = 1:2] >= 2i + j)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### DenseAxisArrays\n", "DenseAxisArrays are used when the required indices are not one-based integer ranges. The syntax is similar except with an \n", "arbitrary vector as an index as opposed to a one-based range." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "An example where the indices are integers but do not start with one." ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-dimensional DenseAxisArray{VariableRef,2,...} with index sets:\n", " Dimension 1, 2:3\n", " Dimension 2, 1:2:3\n", "And data, a 2×2 Array{VariableRef,2}:\n", " z[2,1] z[2,3]\n", " z[3,1] z[3,3]" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(model, z[i = 2:3, j = 1:2:3] >= 0)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Another example where the indices are an arbitrary vector." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-dimensional DenseAxisArray{VariableRef,2,...} with index sets:\n", " Dimension 1, Base.OneTo(5)\n", " Dimension 2, [\"red\", \"blue\"]\n", "And data, a 5×2 Array{VariableRef,2}:\n", " w[1,red] w[1,blue]\n", " w[2,red] w[2,blue]\n", " w[3,red] w[3,blue]\n", " w[4,red] w[4,blue]\n", " w[5,red] w[5,blue]" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(model, w[1:5,[\"red\", \"blue\"]] <= 1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### SparseAxisArrays\n", "SparseAxisArrays are created when the indices do not form a rectangular set. For example, this applies when indices have a \n", "dependence upon previous indices (called triangular indexing)." ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "JuMP.Containers.SparseAxisArray{VariableRef,2,Tuple{Int64,Int64}} with 12 entries:\n", " [2, 3] = u[2,3]\n", " [2, 2] = u[2,2]\n", " [2, 5] = u[2,5]\n", " [1, 4] = u[1,4]\n", " [3, 3] = u[3,3]\n", " [1, 3] = u[1,3]\n", " [2, 4] = u[2,4]\n", " [1, 1] = u[1,1]\n", " [1, 2] = u[1,2]\n", " [1, 5] = u[1,5]\n", " [3, 4] = u[3,4]\n", " [3, 5] = u[3,5]" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(model, u[i = 1:3, j = i:5])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can also conditionally create variables by adding a comparison check that depends upon the named indices and is separated \n", "from the indices by a semi-colon (;)." ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "JuMP.Containers.SparseAxisArray{VariableRef,1,Tuple{Int64}} with 3 entries:\n", " [9] = v[9]\n", " [3] = v[3]\n", " [6] = v[6]" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(model, v[i = 1:9; mod(i, 3) == 0])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Variable Types" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The last arguement to the `@variable` macro is usually the variable type. Here we'll look at how to specifiy he variable type." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Integer Variables\n", "Integer optimization variables are constrained to the set $x \\in {Z}$" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$$ integer_x $$" ], "text/plain": [ "integer_x" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(model, integer_x, Int)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "or" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$$ integer_z $$" ], "text/plain": [ "integer_z" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(model, integer_z, integer = true)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Binary Variables\n", "Binary optimization variables are constrained to the set $x \\in \\{0, 1\\}$." ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$$ binary_x $$" ], "text/plain": [ "binary_x" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(model, binary_x, Bin)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "or" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$$ binary_z $$" ], "text/plain": [ "binary_z" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(model, binary_z, binary = true)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Semidefinite variables\n", "JuMP also supports modeling with semidefinite variables. A square symmetric matrix X is positive semidefinite if all eigenvalues \n", "are nonnegative." ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 LinearAlgebra.Symmetric{VariableRef,Array{VariableRef,2}}:\n", " psd_x[1,1] psd_x[1,2]\n", " psd_x[1,2] psd_x[2,2]" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(model, psd_x[1:2, 1:2], PSD)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can also impose a weaker constraint that the square matrix is only symmetric (instead of positive semidefinite) as follows:" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2×2 LinearAlgebra.Symmetric{VariableRef,Array{VariableRef,2}}:\n", " sym_x[1,1] sym_x[1,2]\n", " sym_x[1,2] sym_x[2,2]" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(model, sym_x[1:2, 1:2], Symmetric)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Constraints" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [], "source": [ "model = Model()\n", "@variable(model, x)\n", "@variable(model, y)\n", "@variable(model, z[1:10]);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Constraint References\n", "While calling the `@constraint` macro, we can also set up a constraint reference. Such a refference is useful for obtaining\n", "additional information about the constraint such as its dual." ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "con : $ x \\leq 4.0 $" ], "text/plain": [ "con : x ≤ 4.0" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@constraint(model, con, x <= 4)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Containers\n", "Just as we had containers for variables, JuMP also provides `Arrays`, `DenseAxisArrays`, and `SparseAxisArrays` for storing\n", "collections of constraints. Examples for each container type are given below." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Arrays" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3-element Array{ConstraintRef{Model,MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64},MathOptInterface.LessThan{Float64}},ScalarShape},1}:\n", " x ≤ 2.0\n", " 2 x ≤ 3.0\n", " 3 x ≤ 4.0" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@constraint(model, [i = 1:3], i * x <= i + 1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### DenseAxisArrays" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2-dimensional DenseAxisArray{ConstraintRef{Model,MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64},MathOptInterface.LessThan{Float64}},ScalarShape},2,...} with index sets:\n", " Dimension 1, Base.OneTo(2)\n", " Dimension 2, 2:3\n", "And data, a 2×2 Array{ConstraintRef{Model,MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64},MathOptInterface.LessThan{Float64}},ScalarShape},2}:\n", " x ≤ 3.0 x ≤ 4.0\n", " 2 x ≤ 3.0 2 x ≤ 4.0" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@constraint(model, [i = 1:2, j = 2:3], i * x <= j + 1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### SparseAxisArrays" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "JuMP.Containers.SparseAxisArray{ConstraintRef{Model,MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64},MathOptInterface.LessThan{Float64}},ScalarShape},2,Tuple{Int64,Int64}} with 2 entries:\n", " [1, 2] = x ≤ 3.0\n", " [2, 1] = 2 x ≤ 2.0" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@constraint(model, [i = 1:2, j = 1:2; i != j], i * x <= j + 1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Constraints in a Loop\n", "We can add constraints using regular Julia loops" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [], "source": [ "for i in 1:3\n", " @constraint(model, 6x + 4y >= 5i)\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "or use for each loops inside the `@constraint` macro." ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3-element Array{ConstraintRef{Model,MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64},MathOptInterface.GreaterThan{Float64}},ScalarShape},1}:\n", " 6 x + 4 y ≥ 5.0\n", " 6 x + 4 y ≥ 10.0\n", " 6 x + 4 y ≥ 15.0" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@constraint(model, [i in 1:3], 6x + 4y >= 5i)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can also create constraints such as $\\sum _{i = 1}^{10} z_i \\leq 1$" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$ z_{1} + z_{2} + z_{3} + z_{4} + z_{5} + z_{6} + z_{7} + z_{8} + z_{9} + z_{10} \\leq 1.0 $" ], "text/plain": [ "z[1] + z[2] + z[3] + z[4] + z[5] + z[6] + z[7] + z[8] + z[9] + z[10] ≤ 1.0" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@constraint(model, sum(z[i] for i in 1:10) <= 1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Objective\n", "While the recommended way to set the objective is with the @objective macro, the functions `set_objective_sense` and \n", "`set_objective_function` provide an equivalent lower-level interface." ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "objective_value(model) = 0.0\n" ] } ], "source": [ "using GLPK\n", "\n", "model = Model(GLPK.Optimizer)\n", "@variable(model, x >= 0)\n", "@variable(model, y >= 0)\n", "set_objective_sense(model, MOI.MIN_SENSE)\n", "set_objective_function(model, x + y)\n", "\n", "optimize!(model)\n", " \n", "@show objective_value(model);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To query the objective function from a model, we use the `objective_sense`, `objective_function`, and `objective_function_type`\n", "functions." ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "MIN_SENSE::OptimizationSense = 0" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "objective_sense(model)" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$$ x + y $$" ], "text/plain": [ "x + y" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "objective_function(model)" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "GenericAffExpr{Float64,VariableRef}" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "objective_function_type(model)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Vectorized Constraints and Objective\n", "We can also add constraints and objective to JuMP using vectorized linear algebra. We'll illustrate this by solving an LP in\n", "standard form i.e." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\n", "\\begin{align*}\n", "& \\min & c^T x \\\\\n", "& \\;\\;\\text{s.t.} & A x = b \\\\\n", "& & x \\succeq 0 \\\\ \n", "& & x \\in \\mathbb{R}^n\n", "\\end{align*}\n", "$$" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "objective_value(vector_model) = 4.9230769230769225\n" ] } ], "source": [ "vector_model = Model(GLPK.Optimizer)\n", "\n", "A= [ 1 1 9 5;\n", " 3 5 0 8;\n", " 2 0 6 13]\n", "\n", "b = [7; 3; 5]\n", "\n", "c = [1; 3; 5; 2]\n", "\n", "@variable(vector_model, x[1:4] >= 0)\n", "@constraint(vector_model, A * x .== b)\n", "@objective(vector_model, Min, c' * x)\n", "\n", "optimize!(vector_model)\n", "\n", "@show objective_value(vector_model);" ] } ], "metadata": { "kernelspec": { "display_name": "Julia 1.5.1", "language": "julia", "name": "julia-1.5" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.5.1" } }, "nbformat": 4, "nbformat_minor": 2 }