{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"title: Geometric Problems\n",
"---"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Originally Contributed by**: Arpit Bhatia"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"These problems in this tutorial are drawn from Chapter 8 of the book \n",
"Convex Optimization by Boyd and Vandenberghe[[1]](#c1)"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"using JuMP\n",
"using Ipopt\n",
"using Random\n",
"# for plots\n",
"using Gadfly\n",
"using DataFrames\n",
"\n",
"Random.seed!(1234);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Euclidean Projection on a Hyperplane\n",
"For a given point $x_{0}$ and a set $C$, we refer to any point $z \\in C$ \n",
"which is closest to $x_{0}$ as a projection of $x_{0}$ on $C$. \n",
"The projection of a point $x_{0}$ on a hyperplane $C = \\{x | a' \\cdot x = b\\}$ is given by"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$$\n",
"\\begin{align*}\n",
"\\min && ||x - x_{0}|| \\\\\n",
"s.t. && a' \\cdot x = b \n",
"\\end{align*}\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"******************************************************************************\n",
"This program contains Ipopt, a library for large-scale nonlinear optimization.\n",
" Ipopt is released as open source code under the Eclipse Public License (EPL).\n",
" For more information visit http://projects.coin-or.org/Ipopt\n",
"******************************************************************************\n",
"\n",
"objective_value(projection) = 0.5495962663047205\n",
"value.(x0) = [0.31246382439420256, 0.7621182340850664, 0.5377408631530719, 0.04962273007076046, 0.5165848569335157, 0.8058883387740959, 0.08216859863753713, 0.019039831334964792, 0.22253665470736747, 0.21813451035584153]\n"
]
}
],
"source": [
"x = rand(10)\n",
"a = rand(10)\n",
"b = rand()\n",
"\n",
"projection = Model(optimizer_with_attributes(Ipopt.Optimizer, \"print_level\" => 0))\n",
"@variable(projection, x0[1:10])\n",
"@objective(projection, Min, sum((x - x0) .* (x - x0))) # We minimize the square of the distance here\n",
"@constraint(projection, x0' * a == b) # Point must lie on the hyperplane\n",
"\n",
"optimize!(projection)\n",
"@show objective_value(projection);\n",
"@show value.(x0);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Euclidean Distance Between Polyhedra\n",
"Given two polyhedra $C = \\{x | A_{1} \\cdot x \\leq b1\\}$ and $D = \\{x | A_{2} \\cdot x \\leq b_{2}\\}$, \n",
"the distance between them is the optimal value of the problem:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$$\n",
"\\begin{align*}\n",
"\\min && ||x - y|| \\\\\n",
"s.t. && A_{1} \\cdot x \\leq b_{1} \\\\\n",
"&& A_{2} \\cdot y \\leq b_{2} \n",
"\\end{align*}\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"objective_value(polyhedra_distance) = 5.204170427930421e-18\n"
]
}
],
"source": [
"A_1 = rand(10, 10)\n",
"A_2 = rand(10, 10)\n",
"b_1 = rand(10)\n",
"b_2 = rand(10)\n",
"\n",
"polyhedra_distance = Model(optimizer_with_attributes(Ipopt.Optimizer, \"print_level\" => 0))\n",
"@variable(polyhedra_distance, x[1:10]) # Point closest on the first polyhedron\n",
"@variable(polyhedra_distance, y[1:10]) # Point closest on the second polyhedron\n",
"@objective(polyhedra_distance, Min, sum((x - y) .* (x - y))) # We minimize the square of the distance here as above\n",
"@constraint(polyhedra_distance, A_1 * x .<= b_1) # Point x must lie on the first polyhedron\n",
"@constraint(polyhedra_distance, A_2 * y .<= b_2) # Point y must lie on the second polyhedron\n",
"\n",
"optimize!(polyhedra_distance)\n",
"@show objective_value(polyhedra_distance);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Linear Placement Problem\n",
"We have $N$ points in $\\mathbb{R}^2$, and a list of pairs of points that must be connected by links. \n",
"The positions of some of the $N$ points are fixed; our task is to determine the positions of the remaining points, \n",
"i.e., to place the remaining points. The objective is to place the points so that the distance between the links is minimized, \n",
"i.e. our objective is:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$$\n",
"\\begin{align*}\n",
"\\min && \\sum_{(i,j) \\in A}||p_{i} - p_{j}|| \n",
"\\end{align*}\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"value.(p) = [0.4479096426163183 0.04689817936614968; -0.03193526635198916 -0.6706136210384356; 0.404335805799056 -0.45130815913688466; -0.39429534726904913 -0.13282535401213758; 0.025327039784221204 0.41242076871207006; -0.001652056641941976 -0.43954821308159137; 1.0 1.0; 1.0 -1.0; -1.0 -1.0; -1.0 1.0; 1.0 -0.5; -1.0 -0.2; -0.2 -1.0; 0.1 1.0]\n",
"objective_value(placement) = 20.444740391099113\n"
]
}
],
"source": [
"fixed = [ 1 1 -1 -1 1 -1 -0.2 0.1; # coordinates of fixed points\n",
" 1 -1 -1 1 -0.5 -0.2 -1 1]\n",
"\n",
"M = size(fixed,2) # number of fixed points\n",
"N = 6 # number of free points\n",
"\n",
"A = [ 1 0 0 -1 0 0 0 0 0 0 0 0 0 0; # Matrix on links\n",
" 1 0 -1 0 0 0 0 0 0 0 0 0 0 0;\n",
" 1 0 0 0 -1 0 0 0 0 0 0 0 0 0;\n",
" 1 0 0 0 0 0 -1 0 0 0 0 0 0 0;\n",
" 1 0 0 0 0 0 0 -1 0 0 0 0 0 0;\n",
" 1 0 0 0 0 0 0 0 0 0 -1 0 0 0;\n",
" 1 0 0 0 0 0 0 0 0 0 0 0 0 -1;\n",
" 0 1 -1 0 0 0 0 0 0 0 0 0 0 0;\n",
" 0 1 0 -1 0 0 0 0 0 0 0 0 0 0;\n",
" 0 1 0 0 0 -1 0 0 0 0 0 0 0 0;\n",
" 0 1 0 0 0 0 0 -1 0 0 0 0 0 0;\n",
" 0 1 0 0 0 0 0 0 -1 0 0 0 0 0;\n",
" 0 1 0 0 0 0 0 0 0 0 0 0 -1 0;\n",
" 0 0 1 -1 0 0 0 0 0 0 0 0 0 0;\n",
" 0 0 1 0 0 0 0 -1 0 0 0 0 0 0;\n",
" 0 0 1 0 0 0 0 0 0 0 -1 0 0 0;\n",
" 0 0 0 1 -1 0 0 0 0 0 0 0 0 0;\n",
" 0 0 0 1 0 0 0 0 -1 0 0 0 0 0;\n",
" 0 0 0 1 0 0 0 0 0 -1 0 0 0 0;\n",
" 0 0 0 1 0 0 0 0 0 0 0 -1 0 0;\n",
" 0 0 0 1 0 0 0 0 0 0 0 -1 0 0; \n",
" 0 0 0 0 1 -1 0 0 0 0 0 0 0 0;\n",
" 0 0 0 0 1 0 -1 0 0 0 0 0 0 0;\n",
" 0 0 0 0 1 0 0 0 0 -1 0 0 0 0;\n",
" 0 0 0 0 1 0 0 0 0 0 0 0 0 -1;\n",
" 0 0 0 0 0 1 0 0 -1 0 0 0 0 0;\n",
" 0 0 0 0 0 1 0 0 0 0 -1 0 0 0;]\n",
"\n",
"placement = Model(optimizer_with_attributes(Ipopt.Optimizer, \"print_level\" => 0))\n",
"@variable(placement, p[1:M + N, 1:2]) # A variable array for the coordinates of each point\n",
"@constraint(placement, p[N + 1:N + M, :] .== fixed') # We had a constraint for the fixed points\n",
"dist = A * p # Matrix of differences between coordinates of 2 points with a link\n",
"@objective(placement, Min, sum(dist .* dist)) # We minimize the sum of the square of the distances\n",
"\n",
"optimize!(placement)\n",
"@show value.(p);\n",
"@show objective_value(placement);"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
],
"text/html": [
"\n",
"\n"
],
"text/plain": [
"SVG(152.39999999999998mm, 152.39999999999998mm, IOBuffer(data=UInt8[...], readable=true, writable=true, seekable=true, append=false, size=12551, maxsize=Inf, ptr=12552, mark=-1), nothing, \"img-a1f9bcce\", 0, Compose.SVGPropertyFrame[], Dict{Type,Union{Nothing, Compose.Property}}(Compose.Property{Compose.SVGAttributePrimitive} => nothing,Compose.Property{Compose.FontPrimitive} => nothing,Compose.Property{Compose.StrokeDashPrimitive} => nothing,Compose.Property{Compose.JSIncludePrimitive} => nothing,Compose.Property{Compose.FontSizePrimitive} => nothing,Compose.Property{Compose.FillOpacityPrimitive} => nothing,Compose.Property{Compose.SVGClassPrimitive} => nothing,Compose.Property{Compose.JSCallPrimitive} => nothing,Compose.Property{Compose.StrokePrimitive} => nothing,Compose.Property{Compose.FillPrimitive} => nothing…), OrderedCollections.OrderedDict{Compose.ClipPrimitive,String}(Compose.ClipPrimitive{Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}(Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}[(17.93916666666668mm, 5.0mm), (128.73333333333332mm, 5.0mm), (128.73333333333332mm, 133.11499999999998mm), (17.93916666666668mm, 133.11499999999998mm)]) => \"img-a1f9bcce-13\"), Tuple{Compose.FormPrimitive,String}[], Set{AbstractString}(), true, false, nothing, true, \"img-a1f9bcce-81\", false, 81, Set(AbstractString[\"/home/mbesancon/.julia/packages/Gadfly/USbaq/src/gadfly.js\"]), Set(Tuple{AbstractString,AbstractString}[(\"Snap.svg\", \"Snap\"), (\"Gadfly\", \"Gadfly\")]), AbstractString[\"fig.select(\\\"#img-a1f9bcce-4\\\")\\n .drag(function() {}, function() {}, function() {});\", \"fig.select(\\\"#img-a1f9bcce-6\\\")\\n .data(\\\"color_class\\\", \\\"color_Free_points\\\")\\n.click(Gadfly.colorkey_swatch_click)\\n;\", \"fig.select(\\\"#img-a1f9bcce-7\\\")\\n .data(\\\"color_class\\\", \\\"color_Fixed_points\\\")\\n.click(Gadfly.colorkey_swatch_click)\\n;\", \"fig.select(\\\"#img-a1f9bcce-9\\\")\\n .data(\\\"color_class\\\", \\\"color_Free_points\\\")\\n.click(Gadfly.colorkey_swatch_click)\\n;\", \"fig.select(\\\"#img-a1f9bcce-10\\\")\\n .data(\\\"color_class\\\", \\\"color_Fixed_points\\\")\\n.click(Gadfly.colorkey_swatch_click)\\n;\", \"fig.select(\\\"#img-a1f9bcce-14\\\")\\n .init_gadfly();\"], false, :none, (Measures.BoundingBox{Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((17.93916666666668mm, 5.0mm), (110.79416666666664mm, 128.11499999999998mm)), Compose.UnitBox{Float64,Float64,Float64,Float64}(-1.0374552292962318, 1.0322281754824154, 2.0749104585924636, -2.064456350964831, 0.0mm, 0.0mm, 0.0mm, 0.0mm), Compose.IdentityTransform()))"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# Plotting the points\n",
"df = DataFrame()\n",
"df.x = value.(p)[:,1]\n",
"df.y = value.(p)[:,2]\n",
"df.type = vcat(fill(\"Free points\", N), fill(\"Fixed points\", M))\n",
"plt = plot(df, x = \"x\", y = \"y\", color = \"type\", Geom.point)\n",
"draw(SVG(6inch, 6inch), plt)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Floor Planning\n",
"A floor planning problem consists of rectangles or boxes aligned with the axes which must be placed, \n",
"within some limits such that they do not overlap. The objective is usually to minimize the size \n",
"(e.g., area, volume, perimeter) of the bounding box, which is the smallest box that contains the boxes to be configured and placed.\n",
"We model this problem as follows:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We have N boxes $B_{1}, . . . , B_{N}$ that are to be configured and placed in a rectangle with width $W$ and height $H$, \n",
"and lower left corner at the position $(0, 0)$. The geometry and position of the $i$th box is specified by \n",
"its width $w_{i}$ and height $h_{i}$, and the coordinates $(x_{i}, y_{i})$ of its lower left corner."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The variables in the problem are $x_{i}, y_{i}, w_{i}, h_{i}$ for $i=1, \\ldots, \n",
"N,$ and the width $W$ and height $H$ of the bounding rectangle. In all floor planning problems, \n",
"we require that the cells lie inside the bounding rectangle, $i . e .$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$$\n",
"x_{i} \\geq 0, \\quad y_{i} \\geq 0, \\quad x_{i}+w_{i} \\leq W, \\quad y_{i}+h_{i} \\leq H, \\quad i=1, \\ldots, N\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We also require that the cells do not overlap, except possibly on their boundaries, i.e."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$$\n",
"x_{i}+w_{i} \\leq x_{j} \\quad \\text{or} \\quad x_{j}+w_{j} \\leq x_{i} \\quad \\text{or} \\quad y_{i}+h_{j} \\leq y_{j} \\quad \\text{or} \\quad y_{j}+h_{i} \\leq y_{i}\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"objective_value(floor_planning) = 51.93446154361733\n",
"objective_value(floor_planning) = 51.1562218755639\n",
"objective_value(floor_planning) = 52.669203332919835\n",
"objective_value(floor_planning) = 52.54574619621182\n"
]
}
],
"source": [
"n = 5;\n",
"\n",
"Amin = [ # We'll try this problem with 4 times with different minimum area constraints\n",
"100 100 100 100 100;\n",
" 20 50 80 150 200;\n",
"180 80 80 80 80;\n",
" 20 150 20 200 110]\n",
"\n",
"r = 1\n",
"\n",
"figs=[]\n",
"\n",
"for i = 1:4\n",
" local A = Amin[i, :]\n",
"\n",
" floor_planning = Model(optimizer_with_attributes(Ipopt.Optimizer, \"print_level\" => 0))\n",
" local x, y, w, h, W, H\n",
" @variables(floor_planning, begin\n",
" x[1:n] >= r\n",
" y[1:n] >= r\n",
" w[1:n] >= 0\n",
" h[1:n] >= 0\n",
" W\n",
" H\n",
" end)\n",
"\n",
" @constraints(floor_planning, begin\n",
" x[5] + w[5] + r <= W # No rectangles at the right of Rectangle 5\n",
" x[1] + w[1] + r <= x[3] # Rectangle 1 is at the left of Rectangle 3\n",
" x[2] + w[2] + r <= x[3] # Rectangle 2 is at the left of Rectangle 3\n",
" x[3] + w[3] + r <= x[5] # Rectangle 3 is at the left of Rectangle 5\n",
" x[4] + w[4] + r <= x[5] # Rectangle 4 is at the left of Rectangle 5\n",
" y[4] + h[4] + r <= H # No rectangles on top of Rectangle 4\n",
" y[5] + h[5] + r <= H # No rectangles on top of Rectangle 5\n",
" y[2] + h[2] + r <= y[1] # Rectangle 2 is below Rectangle 1\n",
" y[1] + h[1] + r <= y[4] # Rectangle 1 is below Rectangle 4\n",
" y[3] + h[3] + r <= y[4] # Rectangle 3 is below Rectangle 4\n",
" w .<= 5*h # Aspect ratio constraint\n",
" h .<= 5*w # Aspect ratio constraint\n",
" A .<= h .* w # Area constraint\n",
" end)\n",
"\n",
" @objective(floor_planning, Min, W + H)\n",
"\n",
" optimize!(floor_planning)\n",
"\n",
" @show objective_value(floor_planning);\n",
"\n",
" D = DataFrame(x = value.(x), y = value.(y), x2 = value.(x) .+ value.(w), y2 = value.(y) .+ value.(h))\n",
" local plt = plot(D, xmin = :x, ymin = :y, xmax = :x2, ymax = :y2, Geom.rect)\n",
" push!(figs, plt)\n",
"end"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n"
],
"text/html": [
"\n",
"\n"
],
"text/plain": [
"SVG(152.39999999999998mm, 152.39999999999998mm, IOBuffer(data=UInt8[...], readable=true, writable=true, seekable=true, append=false, size=27574, maxsize=Inf, ptr=27575, mark=-1), nothing, \"img-db140559\", 0, Compose.SVGPropertyFrame[], Dict{Type,Union{Nothing, Compose.Property}}(Compose.Property{Compose.SVGAttributePrimitive} => nothing,Compose.Property{Compose.FontPrimitive} => nothing,Compose.Property{Compose.StrokeDashPrimitive} => nothing,Compose.Property{Compose.JSIncludePrimitive} => nothing,Compose.Property{Compose.FontSizePrimitive} => nothing,Compose.Property{Compose.FillOpacityPrimitive} => nothing,Compose.Property{Compose.SVGClassPrimitive} => nothing,Compose.Property{Compose.JSCallPrimitive} => nothing,Compose.Property{Compose.StrokePrimitive} => nothing,Compose.Property{Compose.FillPrimitive} => nothing…), OrderedCollections.OrderedDict{Compose.ClipPrimitive,String}(Compose.ClipPrimitive{Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}(Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}[(92.35249999999999mm, 81.19999999999999mm), (147.39999999999998mm, 81.19999999999999mm), (147.39999999999998mm, 133.11499999999998mm), (92.35249999999999mm, 133.11499999999998mm)]) => \"img-db140559-4\",Compose.ClipPrimitive{Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}(Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}[(16.152500000000003mm, 81.19999999999999mm), (71.19999999999999mm, 81.19999999999999mm), (71.19999999999999mm, 133.11499999999998mm), (16.152500000000003mm, 133.11499999999998mm)]) => \"img-db140559-44\",Compose.ClipPrimitive{Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}(Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}[(92.35249999999999mm, 5.0mm), (147.39999999999998mm, 5.0mm), (147.39999999999998mm, 56.91499999999999mm), (92.35249999999999mm, 56.91499999999999mm)]) => \"img-db140559-86\",Compose.ClipPrimitive{Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}(Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}[(16.152500000000003mm, 5.0mm), (71.19999999999999mm, 5.0mm), (71.19999999999999mm, 56.91499999999999mm), (16.152500000000003mm, 56.91499999999999mm)]) => \"img-db140559-128\"), Tuple{Compose.FormPrimitive,String}[], Set{AbstractString}(), true, false, nothing, true, \"img-db140559-159\", false, 159, Set(AbstractString[\"/home/mbesancon/.julia/packages/Gadfly/USbaq/src/gadfly.js\"]), Set(Tuple{AbstractString,AbstractString}[(\"Snap.svg\", \"Snap\"), (\"Gadfly\", \"Gadfly\")]), AbstractString[\"fig.select(\\\"#img-db140559-5\\\")\\n .init_gadfly();\", \"fig.select(\\\"#img-db140559-45\\\")\\n .init_gadfly();\", \"fig.select(\\\"#img-db140559-87\\\")\\n .init_gadfly();\", \"fig.select(\\\"#img-db140559-129\\\")\\n .init_gadfly();\"], false, :none, (Measures.BoundingBox{Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}},Tuple{Measures.Length{:mm,Float64},Measures.Length{:mm,Float64}}}((16.152500000000003mm, 5.0mm), (55.047499999999985mm, 51.91499999999999mm)), Compose.UnitBox{Float64,Float64,Float64,Float64}(-1.1753758754101575, 26.04351455702807, 32.350751750820315, -27.087029114056143, 0.0mm, 0.0mm, 0.0mm, 0.0mm), Compose.IdentityTransform()))"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"draw(SVG(6inch, 6inch), vstack(hstack(figs[1], figs[2]), hstack(figs[3], figs[4])))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### References\n",
"\n",
"1. Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511804441"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"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
}