{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"```{index} disjunctive programming\n",
"```\n",
"```{index} single: AMPL \n",
"```\n",
"\n",
"# Extra material: Strip packing\n",
"\n",
"*Strip packing* (SP) refers to the problem of packing rectangles onto a two dimensional strip of fixed width. \n",
"\n",
"Many variants of this problem have been studied, the most basic is the pack a set of rectangles onto the shortest possible strip without rotation. Other variants allow rotation of the rectangles, require a packing that allows cutting the rectangles out of the strip with edge-to-edge cuts (guillotine packing), extends the strip to three dimensions, or extends the packing to non-rectangular shapes.\n",
"\n",
"The extensive study of strip packing problems is motivated by their many industrial applications including\n",
"\n",
"* placement of macro cells in semiconductor layouts,\n",
"* wood and textile cutting operations,\n",
"* laying out workstations in manufacturing facilities,\n",
"* allocating communications bandwidth between two endpoints,\n",
"* planning and scheduling $CO_2$ utilization for enhanced oil recovery,\n",
"* scheduling allocations of a common resource.\n",
"\n",
"Finding optimal solutions to strip packing problems is combinatorially difficult. Strip packing belongs to a class of problems called \"NP-hard\" for which known solution algorithms require effort that grows exponentially with problem size. For that reason much research on strip packing has been directed towards practical heuristic algorithms for finding good, though not optimal, for industrial applications.\n",
"\n",
"Here we develop AMPL models to find optimal solutions to smaller but economically relevant problems. We use the problem of packing boxes onto shortest possible shelf of fixed width."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"# install dependencies and select solver\n",
"%pip install -q amplpy pandas matplotlib\n",
"\n",
"SOLVER = \"highs\"\n",
"\n",
"from amplpy import AMPL, ampl_notebook\n",
"\n",
"ampl = ampl_notebook(\n",
" modules=[\"highs\"], # modules to install\n",
" license_uuid=\"default\", # license to use\n",
") # instantiate AMPL object and register magics"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Problem Statment\n",
"\n",
"Imagine a collection of $N$ boxes that are to placed on shelf. The shelf depth is $D$, and the dimensions of the boxes are $(w_i, d_i)$ for $i=0, \\ldots, N-1$. The boxes can be rotated, if needed, to fit on the shelf. How wide of a shelf is needed?\n",
"\n",
"We will start by creating a function to generate a table of $N$ boxes. For concreteness, we assume the dimensions are in millimeters."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"
\n",
" \n",
" \n",
" w \n",
" d \n",
" \n",
" \n",
" \n",
" \n",
" 0 \n",
" 82 \n",
" 103 \n",
" \n",
" \n",
" 1 \n",
" 73 \n",
" 48 \n",
" \n",
" \n",
" 2 \n",
" 171 \n",
" 53 \n",
" \n",
" \n",
" 3 \n",
" 73 \n",
" 99 \n",
" \n",
" \n",
" 4 \n",
" 167 \n",
" 85 \n",
" \n",
" \n",
" 5 \n",
" 151 \n",
" 172 \n",
" \n",
" \n",
" 6 \n",
" 54 \n",
" 130 \n",
" \n",
" \n",
" 7 \n",
" 126 \n",
" 94 \n",
" \n",
" \n",
"
\n",
"
\n",
"\n",
"
\n",
" \n",
" \n",
" w \n",
" d \n",
" x1 \n",
" x2 \n",
" y1 \n",
" y2 \n",
" r \n",
" \n",
" \n",
" \n",
" \n",
" 0 \n",
" 82 \n",
" 103 \n",
" 0 \n",
" 82 \n",
" 0 \n",
" 103 \n",
" 0 \n",
" \n",
" \n",
" 1 \n",
" 73 \n",
" 48 \n",
" 82 \n",
" 155 \n",
" 0 \n",
" 48 \n",
" 0 \n",
" \n",
" \n",
" 2 \n",
" 171 \n",
" 53 \n",
" 155 \n",
" 326 \n",
" 0 \n",
" 53 \n",
" 0 \n",
" \n",
" \n",
" 3 \n",
" 73 \n",
" 99 \n",
" 326 \n",
" 399 \n",
" 0 \n",
" 99 \n",
" 0 \n",
" \n",
" \n",
" 4 \n",
" 167 \n",
" 85 \n",
" 399 \n",
" 566 \n",
" 0 \n",
" 85 \n",
" 0 \n",
" \n",
" \n",
" 5 \n",
" 151 \n",
" 172 \n",
" 566 \n",
" 717 \n",
" 0 \n",
" 172 \n",
" 0 \n",
" \n",
" \n",
" 6 \n",
" 54 \n",
" 130 \n",
" 717 \n",
" 771 \n",
" 0 \n",
" 130 \n",
" 0 \n",
" \n",
" \n",
" 7 \n",
" 126 \n",
" 94 \n",
" 771 \n",
" 897 \n",
" 0 \n",
" 94 \n",
" 0 \n",
" \n",
" \n",
"
\n",
"
"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"def pack_boxes_V0(boxes):\n",
" soln = boxes.copy()\n",
" soln[\"x1\"] = soln[\"w\"].cumsum() - soln[\"w\"]\n",
" soln[\"x2\"] = soln[\"w\"].cumsum()\n",
" soln[\"y1\"] = 0\n",
" soln[\"y2\"] = soln[\"d\"]\n",
" soln[\"r\"] = 0\n",
" return soln\n",
"\n",
"\n",
"def show_boxes(soln, D):\n",
" \"\"\"Show bounding boxes on a diagram of the shelf.\"\"\"\n",
" fig, ax = plt.subplots(1, 1, figsize=(14, 4))\n",
" for i, x, y, w, h, r in zip(\n",
" soln.index, soln[\"x1\"], soln[\"y1\"], soln[\"w\"], soln[\"d\"], soln[\"r\"]\n",
" ):\n",
" c = \"g\"\n",
" if r:\n",
" h, w = w, h\n",
" c = \"r\"\n",
" ax.add_patch(Rectangle((x, y), w, h, edgecolor=\"k\", facecolor=c, alpha=0.6))\n",
" xc = x + w / 2\n",
" yc = y + h / 2\n",
" ax.annotate(\n",
" i, (xc, yc), color=\"w\", weight=\"bold\", fontsize=12, ha=\"center\", va=\"center\"\n",
" )\n",
"\n",
" W_lb = (soln[\"w\"] * soln[\"d\"]).sum() / D\n",
" ax.set_xlim(0, 1.1 * soln[\"w\"].sum())\n",
" ax.set_ylim(0, D * 1.1)\n",
" ax.axhline(D, label=\"shelf depth $D$\", lw=0.8)\n",
" ax.axvline(W_lb, label=\"lower bound $W_{lb}$\", color=\"g\", lw=0.8)\n",
" ax.axvline(soln[\"x2\"].max(), label=\"shelf width $W$\", color=\"r\", lw=0.8)\n",
" ax.fill_between([0, ax.get_xlim()[1]], [D, D], color=\"b\", alpha=0.1)\n",
" ax.set_title(f\"shelf width $W$ = {soln['x2'].max():.0f}\")\n",
" ax.set_xlabel(\"width\")\n",
" ax.set_ylabel(\"depth\")\n",
" ax.set_aspect(\"equal\")\n",
" ax.legend(loc=\"upper right\")\n",
"\n",
"\n",
"soln = pack_boxes_V0(boxes)\n",
"display(soln)\n",
"show_boxes(soln, D)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Modeling Strategy\n",
"\n",
"At this point the reader may have some ideas on how to efficiently pack boxes on the shelf. For example, one might start by placing the larger boxes to left edge of the shelf, then rotating and placing the smaller boxes with a goal of minimized the occupied with of the shelf. \n",
"\n",
"Modeling for optimization takes a different approach. The strategy is to describe constraints that must be satisfied for any solution to the problem, then let the solver find the a choice for the decision variables that minimizes width. The constraints include:\n",
"\n",
"* The bounding boxes must fit within the boundaries of the shelf, and to the left of vertical line drawn at $x = W$.\n",
"* The boxes can be rotated 90 degrees.\n",
"* The boxes must not overlap in either the $x$ or $y$ dimensions."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Version 1: An AMPL model to line up the boxes\n",
"\n",
"For this first AMPL model we look to reproduce a lineup of the boxes on the shelf. In the case the problem is to minimize $W$ where\n",
"\n",
"$$\n",
"\\begin{align*}\n",
"& \\min W \\\\\n",
"\\text{subject to:}\\qquad\\qquad \\\\\n",
"x_{i, 2} & = x_{i, 1} + w_i & \\forall i\\\\\n",
"x_{i, 2} & \\leq W & \\forall i\\\\\n",
"x_{i, 1}, x_{i, 2} & \\geq 0 & \\forall i \\\\\n",
"\\\\\n",
"[x_{i, 2} \\leq x_{j,1}] & \\veebar [ x_{j, 2} \\leq x_{i, 1}] & \\forall i < j \\\\\n",
"\\\\\n",
"\\end{align*}\n",
"$$\n",
"\n",
"This first model does not consider rotation or placement of the boxes in the $y$ dimension, so those decisions are not included. \n",
"\n",
"The disjunctive constraints specify relationships between $x_{i,1}$ and $x_{i,2}$ to prevent overlapping positions of boxes on the shelf. The disjunctions require that either that box $i$ is to the left of box $j$ or that box $j$ is the left of box $i$. This is specified as an exclusive or disjunction because both conditions can be true at the same time. This disjunctive relationship must hold for every pair of boxes that are different from each other, but specifying $i$ doesn't overlap with $j$ assures $j$ doesn't overlap $i$. So it is only necessary to specify disjunctions for all pairs $i, j$ where $i < j$.\n",
"\n",
"The corresponding AMPL model is a direct implementation of this model. One feature of the implementation is the use of a set `PAIRS` to identify the disjunctions. Defining this set simplifies coding for the corresponding disjunction.\n"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Overwriting pack_boxes_V1.mod\n"
]
}
],
"source": [
"%%writefile pack_boxes_V1.mod\n",
"\n",
"set BOXES;\n",
"set PAIRS within {BOXES,BOXES};\n",
"\n",
"param w{BOXES};\n",
"\n",
"param W_ub;\n",
"\n",
"var W >= 0, <= W_ub;\n",
"var x1{BOXES} >= 0, <= W_ub;\n",
"var x2{BOXES} >= 0, <= W_ub;\n",
"\n",
"minimize minimize_width: W;\n",
"\n",
"s.t. bounding_box {i in BOXES}:\n",
" x2[i] == x1[i] + w[i];\n",
"s.t. width {i in BOXES}:\n",
" x2[i] <= W;\n",
"s.t. no_overlap {(i, j) in PAIRS}:\n",
" (x2[i] <= x1[j] or x2[j] <= x1[i])\n",
" and not\n",
" (x2[i] <= x1[j] and x2[j] <= x1[i]);"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"HiGHS 1.5.1: \b\b\b\b\b\b\b\b\b\b\b\b\bHiGHS 1.5.1: optimal solution; objective 896.9999999\n",
"344603 simplex iterations\n",
"73081 branching nodes\n",
"absmipgap=0.000150937, relmipgap=1.68269e-07\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"
\n",
" \n",
" \n",
" w \n",
" d \n",
" x1 \n",
" x2 \n",
" y1 \n",
" y2 \n",
" r \n",
" \n",
" \n",
" \n",
" \n",
" 0 \n",
" 82 \n",
" 103 \n",
" 0.0 \n",
" 82.0 \n",
" 0 \n",
" 103 \n",
" 0 \n",
" \n",
" \n",
" 1 \n",
" 73 \n",
" 48 \n",
" 770.0 \n",
" 843.0 \n",
" 0 \n",
" 48 \n",
" 0 \n",
" \n",
" \n",
" 2 \n",
" 171 \n",
" 53 \n",
" 432.0 \n",
" 603.0 \n",
" 0 \n",
" 53 \n",
" 0 \n",
" \n",
" \n",
" 3 \n",
" 73 \n",
" 99 \n",
" 82.0 \n",
" 155.0 \n",
" 0 \n",
" 99 \n",
" 0 \n",
" \n",
" \n",
" 4 \n",
" 167 \n",
" 85 \n",
" 603.0 \n",
" 770.0 \n",
" 0 \n",
" 85 \n",
" 0 \n",
" \n",
" \n",
" 5 \n",
" 151 \n",
" 172 \n",
" 281.0 \n",
" 432.0 \n",
" 0 \n",
" 172 \n",
" 0 \n",
" \n",
" \n",
" 6 \n",
" 54 \n",
" 130 \n",
" 843.0 \n",
" 897.0 \n",
" 0 \n",
" 130 \n",
" 0 \n",
" \n",
" \n",
" 7 \n",
" 126 \n",
" 94 \n",
" 155.0 \n",
" 281.0 \n",
" 0 \n",
" 94 \n",
" 0 \n",
" \n",
" \n",
"
\n",
"
"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"def pack_boxes_V1(boxes):\n",
" # a simple upper bound on shelf width\n",
" W_ub = boxes[\"w\"].sum()\n",
"\n",
" BOXES = list(boxes.index)\n",
" PAIRS = [(i, j) for i in BOXES for j in BOXES if i < j]\n",
"\n",
" m = AMPL()\n",
" m.read(\"pack_boxes_V1.mod\")\n",
"\n",
" m.set[\"BOXES\"] = BOXES\n",
" m.set[\"PAIRS\"] = PAIRS\n",
"\n",
" m.param[\"w\"] = boxes[\"w\"]\n",
" m.param[\"W_ub\"] = int(W_ub)\n",
"\n",
" m.solve(solver=SOLVER)\n",
" assert m.solve_result == \"solved\", m.solve_result\n",
"\n",
" soln = boxes.copy()\n",
" soln[\"x1\"] = m.var[\"x1\"].to_dict()\n",
" soln[\"x2\"] = m.var[\"x2\"].to_dict()\n",
" soln[\"y1\"] = 0\n",
" soln[\"y2\"] = soln[\"y1\"] + soln[\"d\"]\n",
" soln[\"r\"] = 0\n",
" return soln\n",
"\n",
"\n",
"soln = pack_boxes_V1(boxes)\n",
"display(soln)\n",
"show_boxes(soln, D)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Version 2: Rotating boxes\n",
"\n",
"Rotating the boxes is an option for packing the boxes more tightly on the shelf. The boxes can be placed either in their original orientation or in a rotated orientation. This introduces a second exclusive or disjunction to the model that determines the orientation of the bounding box. A boolean indicator variable $r_i$ tracks which boxes were rotated which is used in the `show_boxes` function to show which boxes have been rotated.\n",
"\n",
"$$\n",
"\\begin{align*}\n",
"& \\min W \\\\\n",
"\\text{subject to:}\\qquad\\qquad \\\\\n",
"x_{i, 2} & \\leq W & \\forall i\\\\\n",
"x_{i, 1}, x_{i, 2} & \\geq 0 & \\forall i \\\\\n",
"y_{i, 1} & = 0 & \\forall i \\\\\n",
"\\\\\n",
"[x_{i, 2} \\leq x_{j,1}] & \\veebar [ x_{j, 2} \\leq x_{i, 1}] & \\forall i < j \\\\\n",
"\\\\\n",
"\\begin{bmatrix}\n",
"\\neg r_i \\\\\n",
"x_{i,2} = x_{i,1} + w_i\\\\\n",
"y_{i,2} = y_{i,1} + d_i\\\\\n",
"\\end{bmatrix} & \\veebar \n",
"\\begin{bmatrix}\n",
"r_i \\\\\n",
"x_{i,2} = x_{i,1} + d_i\\\\\n",
"y_{i,2} = y_{i,1} + w_i\\\\\n",
"\\end{bmatrix} & \\forall i < j\n",
"\\end{align*}\n",
"$$\n",
"\n",
"For this version of the model the boxes will be lined up against the edge of the shelf with $y_{i,1} = 0$. Decision variables are now included in the model for rotation $r$ to the $y$ dimension of the bounding boxes."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Overwriting pack_boxes_V2.mod\n"
]
}
],
"source": [
"%%writefile pack_boxes_V2.mod\n",
"\n",
"set BOXES;\n",
"set PAIRS within {BOXES,BOXES};\n",
"\n",
"param w{BOXES};\n",
"param d{BOXES};\n",
"\n",
"param W_ub;\n",
"\n",
"var W >= 0, <= W_ub;\n",
"var x1{BOXES} >= 0, <= W_ub;\n",
"var x2{BOXES} >= 0, <= W_ub;\n",
"var y1{BOXES} >= 0, <= W_ub;\n",
"var y2{BOXES} >= 0, <= W_ub;\n",
"var r{BOXES} binary;\n",
"\n",
"minimize minimize_width: W;\n",
"\n",
"s.t. width {i in BOXES}:\n",
" x2[i] <= W;\n",
"s.t. yloc {i in BOXES}:\n",
" y1[i] == 0;\n",
" \n",
"s.t. rotate {i in BOXES}:\n",
" r[i] == 0 ==> \n",
" (x2[i] == x1[i] + w[i] and y2[i] == y1[i] + d[i])\n",
" else\n",
" (x2[i] == x1[i] + d[i] and y2[i] == y1[i] + w[i]);\n",
"\n",
"s.t. no_overlap {(i, j) in PAIRS}:\n",
" (x2[i] <= x1[j] or x2[j] <= x1[i])\n",
" and not\n",
" (x2[i] <= x1[j] and x2[j] <= x1[i])\n",
" ;"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"HiGHS 1.5.1: \b\b\b\b\b\b\b\b\b\b\b\b\bHiGHS 1.5.1: optimal solution; objective 639.999502\n",
"7.40492e+06 simplex iterations\n",
"1.05588e+06 branching nodes\n",
"absmipgap=0.0608127, relmipgap=9.502e-05\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"
\n",
" \n",
" \n",
" w \n",
" d \n",
" x1 \n",
" x2 \n",
" y1 \n",
" y2 \n",
" r \n",
" \n",
" \n",
" \n",
" \n",
" 0 \n",
" 82 \n",
" 103 \n",
" 1.859995e+02 \n",
" 267.999502 \n",
" 0.0 \n",
" 103.0 \n",
" 0.0 \n",
" \n",
" \n",
" 1 \n",
" 73 \n",
" 48 \n",
" 5.300000e+01 \n",
" 101.000000 \n",
" 0.0 \n",
" 73.0 \n",
" 1.0 \n",
" \n",
" \n",
" 2 \n",
" 171 \n",
" 53 \n",
" 1.421085e-14 \n",
" 53.000000 \n",
" 0.0 \n",
" 171.0 \n",
" 1.0 \n",
" \n",
" \n",
" 3 \n",
" 73 \n",
" 99 \n",
" 5.669995e+02 \n",
" 639.999502 \n",
" 0.0 \n",
" 99.0 \n",
" 0.0 \n",
" \n",
" \n",
" 4 \n",
" 167 \n",
" 85 \n",
" 1.009995e+02 \n",
" 185.999502 \n",
" 0.0 \n",
" 167.0 \n",
" 1.0 \n",
" \n",
" \n",
" 5 \n",
" 151 \n",
" 172 \n",
" 3.619995e+02 \n",
" 512.999502 \n",
" 0.0 \n",
" 172.0 \n",
" 0.0 \n",
" \n",
" \n",
" 6 \n",
" 54 \n",
" 130 \n",
" 5.129995e+02 \n",
" 566.999502 \n",
" 0.0 \n",
" 130.0 \n",
" 0.0 \n",
" \n",
" \n",
" 7 \n",
" 126 \n",
" 94 \n",
" 2.679995e+02 \n",
" 361.999502 \n",
" 0.0 \n",
" 126.0 \n",
" 1.0 \n",
" \n",
" \n",
"
\n",
"
"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"def pack_boxes_V2(boxes):\n",
" W_ub = boxes[\"w\"].sum()\n",
"\n",
" BOXES = list(boxes.index)\n",
" PAIRS = [(i, j) for i in BOXES for j in BOXES if i < j]\n",
"\n",
" m = AMPL()\n",
" m.read(\"pack_boxes_V2.mod\")\n",
"\n",
" m.set[\"BOXES\"] = BOXES\n",
" m.set[\"PAIRS\"] = PAIRS\n",
"\n",
" m.param[\"w\"] = boxes[\"w\"]\n",
" m.param[\"d\"] = boxes[\"d\"]\n",
" m.param[\"W_ub\"] = int(W_ub)\n",
"\n",
" m.solve(solver=SOLVER)\n",
" assert m.solve_result == \"solved\", m.solve_result\n",
"\n",
" soln = boxes.copy()\n",
" soln[\"x1\"] = m.var[\"x1\"].to_dict()\n",
" soln[\"x2\"] = m.var[\"x2\"].to_dict()\n",
" soln[\"y1\"] = m.var[\"y1\"].to_dict()\n",
" soln[\"y2\"] = m.var[\"y2\"].to_dict()\n",
" soln[\"r\"] = m.var[\"r\"].to_dict()\n",
"\n",
" return soln\n",
"\n",
"\n",
"soln = pack_boxes_V2(boxes)\n",
"display(soln)\n",
"show_boxes(soln, D)"
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": []
},
"source": [
"## Version 3: Placing and Rotating boxes in two dimensions\n",
"\n",
"Obviously the packages can be packed closer together by allowing boxes to be stacked deeper into the shelf. New constraints are needed to maintain the bounding boxes within the shelf depth, and to avoid overlaps in the $y$ dimension.\n",
"\n",
"$$\n",
"\\begin{align*}\n",
"& \\min W \\\\\n",
"\\text{subject to:}\\qquad\\qquad \\\\\n",
"x_{i, 2} & \\leq W & \\forall i\\\\\n",
"y_{i, 2} & \\leq D & \\forall i\\\\\n",
"x_{i, 1}, x_{i, 2} & \\geq 0 & \\forall i \\\\\n",
"y_{i, 1}, y_{i, 2} & \\geq 0 & \\forall i \\\\\n",
"\\\\\n",
"\\begin{bmatrix}\n",
"x_{i, 2} \\leq x_{j,1} \\\\\n",
"\\end{bmatrix}\n",
"\\veebar\n",
"\\begin{bmatrix}\n",
"x_{j, 2} \\leq x_{i, 1} \\\\\n",
"\\end{bmatrix}\n",
"& \\veebar \n",
"\\begin{bmatrix}\n",
"y_{i, 2} \\leq y_{j, 1} \\\\\n",
"\\end{bmatrix}\n",
"\\veebar\n",
"\\begin{bmatrix}\n",
"y_{j, 2} \\leq y_{i, 1} \\\\\n",
"\\end{bmatrix}\n",
"& \\forall i < j \\\\\n",
"\\\\\n",
"\\begin{bmatrix}\n",
"\\neg r_i \\\\\n",
"x_{i,2} = x_{i,1} + w_i\\\\\n",
"y_{i,2} = y_{i,1} + d_i\\\\\n",
"\\end{bmatrix} & \\veebar \n",
"\\begin{bmatrix}\n",
"r_i \\\\\n",
"x_{i,2} = x_{i,1} + d_i\\\\\n",
"y_{i,2} = y_{i,1} + w_i\\\\\n",
"\\end{bmatrix} & \\forall i < j\n",
"\\end{align*}\n",
"$$\n"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Overwriting pack_boxes_V3.mod\n"
]
}
],
"source": [
"%%writefile pack_boxes_V3.mod\n",
"\n",
"set BOXES;\n",
"set PAIRS within {BOXES,BOXES};\n",
"\n",
"param w{BOXES};\n",
"param d{BOXES};\n",
"param D;\n",
"\n",
"param W_ub;\n",
"\n",
"var W >= 0, <= W_ub;\n",
"var x1{BOXES} >= 0, <= W_ub;\n",
"var x2{BOXES} >= 0, <= W_ub;\n",
"var y1{BOXES} >= 0, <= W_ub;\n",
"var y2{BOXES} >= 0, <= W_ub;\n",
"var r{BOXES} binary;\n",
"\n",
"minimize minimize_width: W;\n",
"\n",
"s.t. width {i in BOXES}:\n",
" x2[i] <= W;\n",
"s.t. height {i in BOXES}:\n",
" y2[i] <= D;\n",
" \n",
"s.t. rotate {i in BOXES}:\n",
" r[i] == 0 ==> (x2[i] == x1[i] + w[i] and y2[i] == y1[i] + d[i])\n",
" else\n",
" (x2[i] == x1[i] + d[i] and y2[i] == y1[i] + w[i]);\n",
"\n",
"s.t. no_overlap {(i, j) in PAIRS}:\n",
" (x2[i] <= x1[j] or x2[j] <= x1[i] or y2[i] <= y1[j] or y2[j] <= y1[i])\n",
" and not\n",
" (x2[i] <= x1[j] and x2[j] <= x1[i] and y2[i] <= y1[j] and y2[j] <= y1[i])\n",
" ;"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"HiGHS 1.5.1:HiGHS 1.5.1: optimal solution; objective 265.999999\n",
"2.86135e+06 simplex iterations\n",
"140133 branching nodes\n",
"absmipgap=8.4e-05, relmipgap=3.15789e-07\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"
\n",
" \n",
" \n",
" w \n",
" d \n",
" x1 \n",
" x2 \n",
" y1 \n",
" y2 \n",
" r \n",
" \n",
" \n",
" \n",
" \n",
" 0 \n",
" 82 \n",
" 103 \n",
" 0.000000 \n",
" 82.000000 \n",
" 151.0 \n",
" 254.0 \n",
" 0 \n",
" \n",
" \n",
" 1 \n",
" 73 \n",
" 48 \n",
" 217.999999 \n",
" 265.999999 \n",
" 126.0 \n",
" 199.0 \n",
" 1 \n",
" \n",
" \n",
" 2 \n",
" 171 \n",
" 53 \n",
" 94.999999 \n",
" 265.999999 \n",
" 205.0 \n",
" 258.0 \n",
" 0 \n",
" \n",
" \n",
" 3 \n",
" 73 \n",
" 99 \n",
" 0.000000 \n",
" 99.000000 \n",
" 271.0 \n",
" 344.0 \n",
" 1 \n",
" \n",
" \n",
" 4 \n",
" 167 \n",
" 85 \n",
" 99.000000 \n",
" 265.999999 \n",
" 258.0 \n",
" 343.0 \n",
" 0 \n",
" \n",
" \n",
" 5 \n",
" 151 \n",
" 172 \n",
" 0.000000 \n",
" 172.000000 \n",
" 0.0 \n",
" 151.0 \n",
" 1 \n",
" \n",
" \n",
" 6 \n",
" 54 \n",
" 130 \n",
" 82.000000 \n",
" 212.000000 \n",
" 151.0 \n",
" 205.0 \n",
" 1 \n",
" \n",
" \n",
" 7 \n",
" 126 \n",
" 94 \n",
" 171.999999 \n",
" 265.999999 \n",
" 0.0 \n",
" 126.0 \n",
" 1 \n",
" \n",
" \n",
"
\n",
"
"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"def pack_boxes_V3(boxes, D):\n",
" W_ub = boxes[\"w\"].sum()\n",
"\n",
" BOXES = list(boxes.index)\n",
" PAIRS = [(i, j) for i in BOXES for j in BOXES if i < j]\n",
"\n",
" m = AMPL()\n",
" m.read(\"pack_boxes_V3.mod\")\n",
"\n",
" m.set[\"BOXES\"] = BOXES\n",
" m.set[\"PAIRS\"] = PAIRS\n",
"\n",
" m.param[\"w\"] = boxes[\"w\"]\n",
" m.param[\"d\"] = boxes[\"d\"]\n",
" m.param[\"W_ub\"] = int(W_ub)\n",
" m.param[\"D\"] = int(D)\n",
"\n",
" m.solve(solver=SOLVER)\n",
" assert m.solve_result == \"solved\", m.solve_result\n",
"\n",
" r = m.var[\"r\"].to_dict()\n",
" r = {i: int(round(r[i])) for i in r}\n",
"\n",
" soln = boxes.copy()\n",
" soln[\"x1\"] = m.var[\"x1\"].to_dict()\n",
" soln[\"x2\"] = m.var[\"x2\"].to_dict()\n",
" soln[\"y1\"] = m.var[\"y1\"].to_dict()\n",
" soln[\"y2\"] = m.var[\"y2\"].to_dict()\n",
" soln[\"r\"] = r\n",
" return soln\n",
"\n",
"\n",
"soln = pack_boxes_V3(boxes, D)\n",
"display(soln)\n",
"show_boxes(soln, D)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Advanced Topic: Symmetry Breaking\n",
"\n",
"One of the issues in combinatorial problem is the challenge of symmetries. A symmetry is a situation where a change in solution configuration leaves the objective unchanged. Strip packing problems are especially susceptible to symmetries.\n",
"\n",
"Symmetries can significantly increase the effort needed to find and and verify an optimal solution. Trespalacios and Grossmann recently presented modification to the strip packing problem to reduce the number of symmetries. This is described in the following paper and implemented in the accompanying AMPL model.\n",
"\n",
"Trespalacios, F., & Grossmann, I. E. (2017). Symmetry breaking for generalized disjunctive programming formulation of the strip packing problem. Annals of Operations Research, 258(2), 747-759.\n"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Overwriting pack_boxes_V4.mod\n"
]
}
],
"source": [
"%%writefile pack_boxes_V4.mod\n",
"\n",
"set BOXES;\n",
"set PAIRS within {BOXES,BOXES};\n",
"\n",
"param w{BOXES};\n",
"param d{BOXES};\n",
"param D;\n",
"\n",
"param W_ub;\n",
"\n",
"var W >= 0, <= W_ub;\n",
"var x1{BOXES} >= 0, <= W_ub;\n",
"var x2{BOXES} >= 0, <= W_ub;\n",
"var y1{BOXES} >= 0, <= W_ub;\n",
"var y2{BOXES} >= 0, <= W_ub;\n",
"var r{BOXES} binary;\n",
"\n",
"minimize minimize_width: W;\n",
"\n",
"s.t. width {i in BOXES}:\n",
" x2[i] <= W;\n",
"s.t. height {i in BOXES}:\n",
" y2[i] <= D;\n",
" \n",
"s.t. rotate {i in BOXES}:\n",
" r[i] == 0 ==> (x2[i] == x1[i] + w[i] and y2[i] == y1[i] + d[i])\n",
" else\n",
" (x2[i] == x1[i] + d[i] and y2[i] == y1[i] + w[i])\n",
" ;\n",
"\n",
"s.t. no_overlap {(i, j) in PAIRS}:\n",
" x2[i] <= x1[j] or\n",
" x2[j] <= x1[i] or\n",
" (y2[i] <= y1[j] and x2[i] >= x1[j] + 1 and x2[j] >= x1[i] + 1) or\n",
" (y2[j] <= y1[i] and x2[i] >= x1[j] + 1 and x2[j] >= x1[i] + 1);"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"HiGHS 1.5.1: \b\b\b\b\b\b\b\b\b\b\b\b\bHiGHS 1.5.1: optimal solution; objective 266\n",
"1.4118e+06 simplex iterations\n",
"74606 branching nodes\n",
"absmipgap=0.00274, relmipgap=1.03008e-05\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"
\n",
" \n",
" \n",
" w \n",
" d \n",
" x1 \n",
" x2 \n",
" y1 \n",
" y2 \n",
" r \n",
" \n",
" \n",
" \n",
" \n",
" 0 \n",
" 82 \n",
" 103 \n",
" 178.0 \n",
" 260.0 \n",
" 0.0 \n",
" 103.0 \n",
" 0 \n",
" \n",
" \n",
" 1 \n",
" 73 \n",
" 48 \n",
" 0.0 \n",
" 48.0 \n",
" 53.0 \n",
" 126.0 \n",
" 1 \n",
" \n",
" \n",
" 2 \n",
" 171 \n",
" 53 \n",
" 0.0 \n",
" 171.0 \n",
" 0.0 \n",
" 53.0 \n",
" 0 \n",
" \n",
" \n",
" 3 \n",
" 73 \n",
" 99 \n",
" 167.0 \n",
" 266.0 \n",
" 258.0 \n",
" 331.0 \n",
" 1 \n",
" \n",
" \n",
" 4 \n",
" 167 \n",
" 85 \n",
" 0.0 \n",
" 167.0 \n",
" 258.0 \n",
" 343.0 \n",
" 0 \n",
" \n",
" \n",
" 5 \n",
" 151 \n",
" 172 \n",
" 94.0 \n",
" 266.0 \n",
" 107.0 \n",
" 258.0 \n",
" 1 \n",
" \n",
" \n",
" 6 \n",
" 54 \n",
" 130 \n",
" 48.0 \n",
" 178.0 \n",
" 53.0 \n",
" 107.0 \n",
" 1 \n",
" \n",
" \n",
" 7 \n",
" 126 \n",
" 94 \n",
" 0.0 \n",
" 94.0 \n",
" 126.0 \n",
" 252.0 \n",
" 1 \n",
" \n",
" \n",
"
\n",
"
"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"def pack_boxes_V4(boxes, D):\n",
" W_ub = boxes[\"w\"].sum()\n",
"\n",
" BOXES = list(boxes.index)\n",
" PAIRS = [(i, j) for i in BOXES for j in BOXES if i < j]\n",
"\n",
" m = AMPL()\n",
" m.read(\"pack_boxes_V4.mod\")\n",
"\n",
" m.set[\"BOXES\"] = BOXES\n",
" m.set[\"PAIRS\"] = PAIRS\n",
"\n",
" m.param[\"w\"] = boxes[\"w\"]\n",
" m.param[\"d\"] = boxes[\"d\"]\n",
" m.param[\"W_ub\"] = int(W_ub)\n",
" m.param[\"D\"] = int(D)\n",
"\n",
" m.solve(solver=SOLVER)\n",
" assert m.solve_result == \"solved\", m.solve_result\n",
"\n",
" r = m.var[\"r\"].to_dict()\n",
" r = {i: int(round(r[i])) for i in r}\n",
"\n",
" soln = boxes.copy()\n",
" soln[\"x1\"] = m.var[\"x1\"].to_dict()\n",
" soln[\"x2\"] = m.var[\"x2\"].to_dict()\n",
" soln[\"y1\"] = m.var[\"y1\"].to_dict()\n",
" soln[\"y2\"] = m.var[\"y2\"].to_dict()\n",
" soln[\"r\"] = r\n",
"\n",
" return soln\n",
"\n",
"\n",
"soln = pack_boxes_V4(boxes, D)\n",
"display(soln)\n",
"show_boxes(soln, D)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.10.6"
}
},
"nbformat": 4,
"nbformat_minor": 4
}