{
"cells": [
{
"cell_type": "markdown",
"source": [
"# Interval constraint programming tutorial"
],
"metadata": {}
},
{
"cell_type": "markdown",
"source": [
"## Setup"
],
"metadata": {}
},
{
"cell_type": "markdown",
"source": [
"The `IntervalConstraintProgramming.jl` package can be installed with"
],
"metadata": {}
},
{
"cell_type": "markdown",
"source": [
"```julia-repl\n",
"julia> using Pkg; Pkg.add(\"IntervalConstraintProgramming\")\n",
"```"
],
"metadata": {}
},
{
"cell_type": "markdown",
"source": [
"Once the package is installed, it can be imported. Note that you will need also the `IntervalArithmetic.jl` package."
],
"metadata": {}
},
{
"outputs": [],
"cell_type": "code",
"source": [
"using IntervalArithmetic, IntervalConstraintProgramming"
],
"metadata": {},
"execution_count": null
},
{
"cell_type": "markdown",
"source": [
"## Introduction"
],
"metadata": {}
},
{
"cell_type": "markdown",
"source": [
"Given a domain $X$ and a set of constraint $S$, constraint programming aims to determine\n",
"all points in the domain $X$ that satisfy the constraint $S$."
],
"metadata": {}
},
{
"cell_type": "markdown",
"source": [
"This Julia package allows you to specify a set of constraints on real-valued variables, given by (in)equalities, and rigorously calculate inner and outer approximations to the feasible set, i.e. the set that satisfies the constraints.\n",
"This uses interval arithmetic provided by the `IntervalArithmetic.jl` package, in particular multi-dimensional IntervalBoxes, i.e. Cartesian products of one-dimensional intervals."
],
"metadata": {}
},
{
"cell_type": "markdown",
"source": [
"## Basic usage"
],
"metadata": {}
},
{
"cell_type": "markdown",
"source": [
"The simple way to define a constraint is to use the `@constraint` macro, as the following example demonstrates"
],
"metadata": {}
},
{
"outputs": [],
"cell_type": "code",
"source": [
"S = @constraint x^2 + y^2 <= 1"
],
"metadata": {},
"execution_count": null
},
{
"cell_type": "markdown",
"source": [
"As it can be noticed, the macro itself can figure out that $x$ and $y$ are variables and you do not need to define those separately.\n",
"The output of the macro is an object of type `Separator`.\n",
"To understand what it means, we first need to introduce a few terms.\n",
"- *Inner contractor*: The smallest box containing all points in the domain $X$ that satisfy the constraint $S$.\n",
"- *Outer contractor*: The smallest box containing all points in the domain $X$ that *do not* satisfy the constraint $S$.\n",
"\n",
"The separator is now simply a function that returns the inner and outer contractor when applied to a domain. The domain should have always type `IntervalBox`, even when it is a 1-dimensional box (i.e. an interval).\n",
"Let us look an example on how to get an inner and outer contractor."
],
"metadata": {}
},
{
"outputs": [],
"cell_type": "code",
"source": [
"X = IntervalBox(-100..100, 2)\n",
"\n",
"inner, outer = S(X)\n",
"\n",
"@show inner\n",
"\n",
"@show outer"
],
"metadata": {},
"execution_count": null
},
{
"cell_type": "markdown",
"source": [
"**Note** Points on the boundary are counted both as inner and outer points. In other words if our constraint is e.g. $x\\leq1$, then the inner contractor will be the smallest box\n",
"containing all points in the domain that satisfy $x\\leq 1$ and the outer contractor all points satisfying $x\\geq1$. Not that the equality is kept in both inequalities.\n",
"To better understand this, consider the following example: let us look for the points in the real line $\\mathbb{R}$ satisfying $-1\\leq x\\leq0$, using $X=[-1,1]$ as domain. The \"pen and paper\" solution\n",
"would be that $[-1,0]$ is the inner contractor and $]0,1]$ is the outer contractor. However, we get the following result:"
],
"metadata": {}
},
{
"outputs": [],
"cell_type": "code",
"source": [
"S = @constraint -1<=x<=0\n",
"X = IntervalBox(-1..1, 1)\n",
"\n",
"@show inner, outer = S(X)"
],
"metadata": {},
"execution_count": null
},
{
"cell_type": "markdown",
"source": [
"The inner contractor is what we expected. For the outer contractor, the key point is that the negation of $-1\\leq x\\leq 0$ is $x\\leq-1 \\cup x\\geq 0$. I.e. the outer contractor looks\n",
"for the smallest box inside the domain $[-1,1]$ which satisfies $x\\leq-1 \\cup x\\geq 0$. This is the smallest box containing $-1$ and $[0, 1]$, i.e. the whole domain $[-1, 1]$.\n",
"Let us take another example with the same constraint but a different domain"
],
"metadata": {}
},
{
"outputs": [],
"cell_type": "code",
"source": [
"X = IntervalBox(-0.5..0.5, 1)\n",
"@show inner, outer = S(X)"
],
"metadata": {},
"execution_count": null
},
{
"cell_type": "markdown",
"source": [
"Now the outer contractor looks for the point inside $[-0.5, 0.5]$ satisfying $x\\leq-1 \\cup x\\geq 0$, i.e $[0, 0.5]$."
],
"metadata": {}
},
{
"cell_type": "markdown",
"source": [
"## First application: set inversion"
],
"metadata": {}
},
{
"cell_type": "markdown",
"source": [
"Given a function $f:\\R^m\\rightarrow\\R^n$ and a set $Y\\subset\\R^n$, set inversion means to find the set $X=f^{-1}(Y)=\\{x\\in\\R^m|f(x)\\in Y\\}$, which is refered as *feasible set*. Generally, the\n",
"image set Y can be represented as a set of constraints on the expression $f(X)$ and solving the set inversion problem means to find the points in $X$ for\n",
"which these constraints are satisfied. As we show in this example, set inversion can be solved using interval constraint programming.\n",
"Let's consider the function $f(x, y) = x^2+y^2$ and let's find the set $X$ for which $f(X)\\in[1, 3]$, i.e. we must find the points $(x, y)$ for which $1\\leq x^2+y^2\\leq 3$.\n",
"Let's define this constraint"
],
"metadata": {}
},
{
"outputs": [],
"cell_type": "code",
"source": [
"S = @constraint 1 <= x^2+y^2 <= 3"
],
"metadata": {},
"execution_count": null
},
{
"cell_type": "markdown",
"source": [
"The strategy to solve this problem is the following, we start with a large interval box, which we know will contain the feasible sets and we iteratively divide the box in smaller boxes,\n",
"keeping track of which boxes are guaranteed to be inside the feasible sets, the boxes that are outside and the boxes that are on the boundary.\n",
"`IntervalConstraintProgramming` offers the function `pave`, to do so, the signature of this function is\n",
"```\n",
"pave(S, X, tol)\n",
"```\n",
"where $S$ is our Separator, $X$ is our starting box and $tol$ is a tolerance parameter. This function returns an object of type `SubPaving`, which stores a list of boxes guaranteed\n",
"to be into the feasible set in the attribute `inner`, as well as a list of boxes on the boundary in the attribute `boundary`."
],
"metadata": {}
},
{
"outputs": [],
"cell_type": "code",
"source": [
"X = IntervalBox(-100..100, 2) # our starting box\n",
"paving = pave(S, X, 0.125)"
],
"metadata": {},
"execution_count": null
},
{
"cell_type": "markdown",
"source": [
"As we can see, the function found in total 164 boxes inside the feasible set and 164 boxes at the boundary. We can now visualize how well\n",
"paving approximates the feasible set"
],
"metadata": {}
},
{
"outputs": [],
"cell_type": "code",
"source": [
"using Plots\n",
"plot(paving.inner, c=\"green\", aspect_ratio=:equal, label=\"inner\")\n",
"plot!(paving.boundary, c=\"gray\", label=\"boundary\")"
],
"metadata": {},
"execution_count": null
},
{
"cell_type": "markdown",
"source": [
"The smallest the tolerance parameter, the better the approximation of the feasible set will be, as the following animation shows"
],
"metadata": {}
},
{
"outputs": [],
"cell_type": "code",
"source": [
"tolerances = append!(collect(1:-0.1:0.1), collect(0.09:-0.01:0.01))\n",
"anim = @animate for tol in tolerances\n",
" paving = pave(S, X, tol)\n",
" plot(paving.inner, c=\"green\", legend=false, title=\"tol=$tol\", aspect_ratio=:equal)\n",
" plot!(paving.boundary, c=\"gray\")\n",
"end\n",
"gif(anim, \"paving_gif.gif\", fps=2)"
],
"metadata": {},
"execution_count": null
},
{
"cell_type": "markdown",
"source": [
"## Constraint Programming with ModelingToolkit"
],
"metadata": {}
},
{
"cell_type": "markdown",
"source": [
"The `@constraint` macro is very handy, but it can handle only simple expressions. If you want\n",
"to handle more complicated expressions, you can use `IntervalConstraintProgramming` with `ModelingToolkit`.\n",
"The following example shows how to import the package and define variables"
],
"metadata": {}
},
{
"outputs": [],
"cell_type": "code",
"source": [
"using ModelingToolkit\n",
"vars = @variables x y"
],
"metadata": {},
"execution_count": null
},
{
"cell_type": "markdown",
"source": [
"\\note{At the moment `IntervalConstraintProgramming.jl` does not work with `ModelingToolkit` v4 or higher. Use v3 instead.}"
],
"metadata": {}
},
{
"cell_type": "markdown",
"source": [
"Once you have defined the variables, you can construct a separator using the `Separator` constructor, which take an array of variables\n",
"as first parameter and a function representing the constraint as second parameter, observe"
],
"metadata": {}
},
{
"outputs": [],
"cell_type": "code",
"source": [
"f(x, y) = x + y < 3\n",
"\n",
"S = Separator(vars, f)"
],
"metadata": {},
"execution_count": null
},
{
"cell_type": "markdown",
"source": [
"After that, you can use the separator and the pave function as described before. As an example, let us draw the Julia logo solving a set inversion problem.\n",
"We have already defined the variables, now the equations of the 3 circles are"
],
"metadata": {}
},
{
"outputs": [],
"cell_type": "code",
"source": [
"circle1(x, y) = (x + √3)^2 + (y + 1)^2 - 9/4 < 0\n",
"circle2(x, y) = (x - √3)^2 + (y + 1)^2 - 9/4 < 0\n",
"circle3(x, y) = x^2 + (y - 2)^2 - 9/4 < 0"
],
"metadata": {},
"execution_count": null
},
{
"cell_type": "markdown",
"source": [
"\\note{If you use `ModelingToolkit`, then all inequalities should be strict, e.g. `x+y <= 1 ` is not supported and should be `x + y < 1` instead}"
],
"metadata": {}
},
{
"cell_type": "markdown",
"source": [
"Now we can define the corresponding separators."
],
"metadata": {}
},
{
"outputs": [],
"cell_type": "code",
"source": [
"S1 = Separator(vars, circle1)\n",
"S2 = Separator(vars, circle2)\n",
"S3 = Separator(vars, circle3)"
],
"metadata": {},
"execution_count": null
},
{
"cell_type": "markdown",
"source": [
"Now we can use pave with diferent tolerances to plot the Julia logo"
],
"metadata": {}
},
{
"outputs": [],
"cell_type": "code",
"source": [
"X = IntervalBox(-4..4, 2)\n",
"anim = @animate for tol in 2.0 .^ (0:-1:-6)\n",
" paving1 = pave(S1, X, tol)\n",
" paving2 = pave(S2, X, tol)\n",
" paving3 = pave(S3, X, tol)\n",
" plot(legend=false, aspect_ratio=:equal)\n",
"\n",
" plot!(paving1.boundary, color=:gray, alpha=0.5)\n",
" plot!(paving2.boundary, color=:gray, alpha=0.5)\n",
" plot!(paving3.boundary, color=:gray, alpha=0.5)\n",
"\n",
" plot!(paving1.inner, color=RGB(0.796, 0.235, 0.2))\n",
" plot!(paving2.inner, color=RGB(0.584, 0.345, 0.698))\n",
" plot!(paving3.inner, color=RGB(0.22, 0.596, 0.149))\n",
"end\n",
"\n",
"gif(anim, \"julia_logo.gif\", fps = 1)"
],
"metadata": {},
"execution_count": null
},
{
"cell_type": "markdown",
"source": [
"---\n",
"\n",
"*This notebook was generated using [Literate.jl](https://github.com/fredrikekre/Literate.jl).*"
],
"metadata": {}
}
],
"nbformat_minor": 3,
"metadata": {
"language_info": {
"file_extension": ".jl",
"mimetype": "application/julia",
"name": "julia",
"version": "1.5.0"
},
"kernelspec": {
"name": "julia-1.5",
"display_name": "Julia 1.5.0",
"language": "julia"
}
},
"nbformat": 4
}