Modeling Disjunctions through the Strip Packing Problem

Prepared by: Prof. Alexander Dowling (adowling@nd.edu), Hailey Lynch (hlynch@nd.edu, 2023)

Introduction and Learning Objectives¶

Build a no-overlap GDP for eight rectangles, solve its Big-M and hull reformulations, and inspect the resulting placements. The complete data, coordinate convention, and optimality certificate below supplement the lecture’s formulation activity.

Prerequisite: Logical Modeling and Generalized Disjunctive Programs.

Import Modules¶

# Imports
import sys

if "google.colab" in sys.modules:
    !wget "https://raw.githubusercontent.com/ndcbe/optimization/main/notebooks/helper.py"
    import helper

    helper.easy_install()
else:
    sys.path.insert(0, "../")
    import helper
helper.set_plotting_style()

milp_solver = "appsi_highs"

Pyomo.GDP: Strip Packing Problem¶

We will be looking at the Strip Packing Problem using Pyomo.GDP as an example for modeling disjunctions.

Aldo Vecchietti (1) and Ignacio Grossmann (2)
(1) INGAR – Instituto de Desarrollo y Diseño – CONICET – UTN, Avellaneda 3657 – Santa Fe ‐ Argentina
(2) Carnegie Mellon University, 5000 Forbes Av. ‐ Pittsburgh, PA ‐ USA

Additional Information	Link
Reference	https://www.minlp.org/library/problem/index.php?i=121&lib=GDP
Description	https://www.minlp.org/problems/ver/156/over/Strip-Packing-Overview.pdf
Results	https://www.minlp.org/problems/ver/156/results/Strip-Packing-Results.pdf
Problem Formulation	Sawaya and Grossmann (2005), A cutting plane method for solving linear generalized disjunctive programming problems

Problem Statement¶

Four pairwise no-overlap certificates using bottom-left coordinates.

Use the bottom-left corner $(x_i,y_i)$ of each rectangle, as in the code below. Length $L_i$ runs along $x$ and height $H_i$ runs along $y$ . The fixed strip width is $W=10$ , and rotation is not allowed.

Rectangle $i$	0	1	2	3	4	5	6	7
Length $L_i$	4	3	2	2	3	3	4	4
Height $H_i$	3	3	2	2	3	5	7	7

Let $N=\{0,\ldots,7\}$ , $\mathcal{P}=\{(i,j):i,j\in N,\ i<j\}$ , and $B=\sum_iL_i=25$ . The actual implemented model is

\begin{aligned} \min\quad &\ell\\ \text{subject to}\quad &\ell\ge x_i+L_i,\quad i\in N,\\ &0\le x_i\le B,\quad 0\le y_i\le W-H_i,\quad i\in N,\\ &\ell\ge0,\\ &\begin{bmatrix}Y^1_{ij}\\x_i+L_i\le x_j\end{bmatrix}\lor \begin{bmatrix}Y^2_{ij}\\x_j+L_j\le x_i\end{bmatrix}\lor \begin{bmatrix}Y^3_{ij}\\y_i+H_i\le y_j\end{bmatrix}\lor \begin{bmatrix}Y^4_{ij}\\y_j+H_j\le y_i\end{bmatrix},\quad(i,j)\in\mathcal{P}. \end{aligned}

(1)

Exactly one certificate indicator is selected for each pair. The first two alternatives put one rectangle to the left of the other; the last two put one below the other. Diagonally separated rectangles may satisfy both a horizontal and a vertical inequality. This remains feasible because an unselected indicator does not enforce the opposite of its inequality.

There are $\binom82=28$ disjunctions and $4\binom82=112$ binary indicators after reformulation. The declared $x_i\le25$ is the code’s bound, not a tighter heuristic bound $x_i\le B-L_i$ . The model does not declare an upper bound on $\ell$ ; that variable appears only in global rows and the objective, so its absence does not obstruct hull’s bound requirement for variables inside disjuncts. A feasible length-25 placement exists by putting all rectangles side by side, so the finite coordinate bound preserves at least one optimum.

The original MINLP library formulation uses an upper-left convention in its exposition. Changing that convention requires changing the signs and bounds consistently; the equations above match this notebook’s bottom-left implementation.

Define model in Pyomo with GDP¶

First we will define the model for the Strip Packing Problem in Pyomo.

"""
Instead of using
# import pyomo.environ as pyo
We can import specific functions/objects
"""

from pyomo.environ import (
    check_optimal_termination,
    ConcreteModel,
    NonNegativeReals,
    Objective,
    Param,
    Set,
    SolverFactory,
    TransformationFactory,
    Var,
    value,
)

# Strip-packing example from http://minlp.org/library/lib.php?lib=GDP

# This model packs a set of rectangles without rotation or overlap within a
# strip of a given width, minimizing the length of the strip.


def create_model():
    """
    Build the strip packing problem model.

    Return:
    model: Pyomo model

    """

    ## Model
    model = ConcreteModel(name="Rectangles strip packing")

    ## Sets
    model.rectangles = Set(ordered=True, initialize=[0, 1, 2, 3, 4, 5, 6, 7])

    ## Parameters
    # Extent of each rectangle across the width of the strip (y direction)
    model.rect_width = Param(
        model.rectangles, initialize={0: 3, 1: 3, 2: 2, 3: 2, 4: 3, 5: 5, 6: 7, 7: 7}
    )

    # Parameter indexed by each rectangle.
    # rect_length is the extent along the strip (the x direction);
    # rect_width is the extent across the strip (the y direction).
    model.rect_length = Param(
        model.rectangles, initialize={0: 4, 1: 3, 2: 2, 3: 2, 4: 3, 5: 3, 6: 4, 7: 4}
    )

    model.strip_width = Param(initialize=10, doc="Available width of the strip")

    # Upperbound on length (default is sum of lengths of rectangles)
    model.max_length = Param(
        initialize=sum(model.rect_length[i] for i in model.rectangles),
        doc="Maximum length of the strip (if all rectangles were arranged "
        "lengthwise)",
    )

    ## Variables
    # x (length) and y (width) coordinates of each of the rectangles
    model.x = Var(
        model.rectangles,
        bounds=(0, model.max_length),
        doc="Rectangle corner x-position (position across length)",
    )

    # Width bounds
    def w_bounds(b, i):
        return (0, b.strip_width - b.rect_width[i])

    model.y = Var(
        model.rectangles,
        bounds=w_bounds,
        doc="Rectangle corner y-position (position down width)",
    )
    # Strip length
    model.strip_length = Var(domain=NonNegativeReals, doc="Length of strip required.")

    # Rectangle conflicts
    def rec_pairs_filter(b, i, j):
        return i < j

    model.overlap_pairs = Set(
        initialize=model.rectangles * model.rectangles,
        dimen=2,
        filter=rec_pairs_filter,
        doc="Set of possible rectangle conflicts",
    )

    ## Constraints
    @model.Constraint(model.rectangles)
    def strip_ends_after_last_rec(b, i):
        return b.strip_length >= b.x[i] + b.rect_length[i]

    ## Objective
    model.total_length = Objective(expr=model.strip_length, doc="Minimize length")

    ## Insert the no-overlap disjunctions here!

    # Add your solution here

    return model

@model.Disjunction(
    model.overlap_pairs,
    doc="Make sure that none of the rectangles on the strip overlap in "
    "either the x or y dimensions.",
)
def no_overlap(b, i, j):
    return [
        b.x[i] + b.rect_length[i] <= b.x[j],
        b.x[j] + b.rect_length[j] <= b.x[i],
        b.y[i] + b.rect_width[i] <= b.y[j],
        b.y[j] + b.rect_width[j] <= b.y[i],
    ]

Transform and Solve with Big M Relaxation¶

Now we will create the model and use Big-M Relaxation.

Big-M Implementation in Pyomo¶

# Creating the model
model = create_model()

Next, let’s transform the model. The updated model is really big, so we will not print it. This is because the transformation factory replaced the disjunctions with many Big-M constraints.

# Applying Big-M relaxation to the model
# Add your solution here

Finally, we’ll solve the model and examine the solution.

# Solve and print the solution
results = SolverFactory(milp_solver).solve(model, tee=True)
assert check_optimal_termination(results), (
    f"Solve failed: status={results.solver.status}, "
    f"termination={results.solver.termination_condition}"
)
for i in model.rectangles:
    # %.4g, not %s: the solver returns coordinates a few ULPs off a whole
    # number (e.g. 6.999999999999998, -0.0), which is noise, not geometry.
    xi, yi = value(model.x[i]) + 0.0, value(model.y[i]) + 0.0
    print(f"Rectangle {i}: ({xi:.4g}, {yi:.4g})")
model.total_length.display()

Rectangle 0: (7, 0)
Rectangle 1: (4, 0)
Rectangle 2: (0, 0)
Rectangle 3: (2, 0)
Rectangle 4: (0, 7)
Rectangle 5: (0, 2)
Rectangle 6: (7, 3)
Rectangle 7: (3, 3)
total_length : Size=1, Index=None, Active=True
    Key  : Active : Value
    None :   True :  11.0

Extract the Big-M placement¶

Store the solved coordinates and check containment, all pairwise separations, and the selected certificates before replacing the model for the hull solve. These checks use the actual solution, not coordinates from an earlier solver run.

import json
import math
import pyomo.environ as pyo
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import pyomo

def extract_packing(m, method):
    records = [{"id": int(i), "length": pyo.value(m.rect_length[i]),
                "height": pyo.value(m.rect_width[i]),
                "x": pyo.value(m.x[i]), "y": pyo.value(m.y[i])}
               for i in m.rectangles]
    length, width = pyo.value(m.strip_length), pyo.value(m.strip_width)
    tol = 1e-6
    for r in records:
        assert r["x"] >= -tol and r["y"] >= -tol
        assert r["x"] + r["length"] <= length + tol
        assert r["y"] + r["height"] <= width + tol
    certificates = []
    for i, j in m.overlap_pairs:
        a, b = records[i], records[j]
        residuals = [a["x"]+a["length"]-b["x"], b["x"]+b["length"]-a["x"],
                     a["y"]+a["height"]-b["y"], b["y"]+b["height"]-a["y"]]
        assert min(residuals) <= tol
        selected = [k for k,d in enumerate(m.no_overlap[i,j].disjuncts)
                    if pyo.value(d.binary_indicator_var) > 0.5]
        assert len(selected) == 1 and residuals[selected[0]] <= tol
        certificates.append({"pair": [int(i),int(j)], "selected": selected[0],
                             "separation_residuals": residuals})
    variables = list(m.component_data_objects(pyo.Var, active=True))
    rows = list(m.component_data_objects(pyo.Constraint, active=True))
    return {"method": method, "length": length, "width": width, "rectangles": records,
            "certificates": certificates,
            "size": {"binary_variables": sum(v.is_binary() for v in variables),
                     "continuous_variables": sum(not v.is_binary() for v in variables),
                     "equalities": sum(c.equality for c in rows),
                     "inequalities": sum(not c.equality for c in rows)}}

packing_bigm = extract_packing(model, "gdp.bigm")
print(json.dumps(packing_bigm, indent=2))

{
  "method": "gdp.bigm",
  "length": 11.0,
  "width": 10,
  "rectangles": [
    {
      "id": 0,
      "length": 4,
      "height": 3,
      "x": 7.0,
      "y": -0.0
    },
    {
      "id": 1,
      "length": 3,
      "height": 3,
      "x": 4.0,
      "y": 0.0
    },
    {
      "id": 2,
      "length": 2,
      "height": 2,
      "x": 0.0,
      "y": 0.0
    },
    {
      "id": 3,
      "length": 2,
      "height": 2,
      "x": 2.0,
      "y": 0.0
    },
    {
      "id": 4,
      "length": 3,
      "height": 3,
      "x": -0.0,
      "y": 6.999999999999998
    },
    {
      "id": 5,
      "length": 3,
      "height": 5,
      "x": 0.0,
      "y": 2.0000000000000004
    },
    {
      "id": 6,
      "length": 4,
      "height": 7,
      "x": 6.999999999999998,
      "y": 3.0
    },
    {
      "id": 7,
      "length": 4,
      "height": 7,
      "x": 2.999999999999998,
      "y": 3.0
    }
  ],
  "certificates": [
    {
      "pair": [
        0,
        1
      ],
      "selected": 1,
      "separation_residuals": [
        7.0,
        0.0,
        3.0,
        3.0
      ]
    },
    {
      "pair": [
        0,
        2
      ],
      "selected": 1,
      "separation_residuals": [
        11.0,
        -5.0,
        3.0,
        2.0
      ]
    },
    {
      "pair": [
        0,
        3
      ],
      "selected": 1,
      "separation_residuals": [
        9.0,
        -3.0,
        3.0,
        2.0
      ]
    },
    {
      "pair": [
        0,
        4
      ],
      "selected": 1,
      "separation_residuals": [
        11.0,
        -4.0,
        -3.9999999999999982,
        9.999999999999998
      ]
    },
    {
      "pair": [
        0,
        5
      ],
      "selected": 1,
      "separation_residuals": [
        11.0,
        -4.0,
        0.9999999999999996,
        7.0
      ]
    },
    {
      "pair": [
        0,
        6
      ],
      "selected": 2,
      "separation_residuals": [
        4.000000000000002,
        3.9999999999999982,
        0.0,
        10.0
      ]
    },
    {
      "pair": [
        0,
        7
      ],
      "selected": 2,
      "separation_residuals": [
        8.000000000000002,
        -1.7763568394002505e-15,
        0.0,
        10.0
      ]
    },
    {
      "pair": [
        1,
        2
      ],
      "selected": 1,
      "separation_residuals": [
        7.0,
        -2.0,
        3.0,
        2.0
      ]
    },
    {
      "pair": [
        1,
        3
      ],
      "selected": 1,
      "separation_residuals": [
        5.0,
        0.0,
        3.0,
        2.0
      ]
    },
    {
      "pair": [
        1,
        4
      ],
      "selected": 1,
      "separation_residuals": [
        7.0,
        -1.0,
        -3.9999999999999982,
        9.999999999999998
      ]
    },
    {
      "pair": [
        1,
        5
      ],
      "selected": 1,
      "separation_residuals": [
        7.0,
        -1.0,
        0.9999999999999996,
        7.0
      ]
    },
    {
      "pair": [
        1,
        6
      ],
      "selected": 2,
      "separation_residuals": [
        1.7763568394002505e-15,
        6.999999999999998,
        0.0,
        10.0
      ]
    },
    {
      "pair": [
        1,
        7
      ],
      "selected": 2,
      "separation_residuals": [
        4.000000000000002,
        2.9999999999999982,
        0.0,
        10.0
      ]
    },
    {
      "pair": [
        2,
        3
      ],
      "selected": 0,
      "separation_residuals": [
        0.0,
        4.0,
        2.0,
        2.0
      ]
    },
    {
      "pair": [
        2,
        4
      ],
      "selected": 2,
      "separation_residuals": [
        2.0,
        3.0,
        -4.999999999999998,
        9.999999999999998
      ]
    },
    {
      "pair": [
        2,
        5
      ],
      "selected": 2,
      "separation_residuals": [
        2.0,
        3.0,
        -4.440892098500626e-16,
        7.0
      ]
    },
    {
      "pair": [
        2,
        6
      ],
      "selected": 0,
      "separation_residuals": [
        -4.999999999999998,
        10.999999999999998,
        -1.0,
        10.0
      ]
    },
    {
      "pair": [
        2,
        7
      ],
      "selected": 0,
      "separation_residuals": [
        -0.9999999999999978,
        6.999999999999998,
        -1.0,
        10.0
      ]
    },
    {
      "pair": [
        3,
        4
      ],
      "selected": 2,
      "separation_residuals": [
        4.0,
        1.0,
        -4.999999999999998,
        9.999999999999998
      ]
    },
    {
      "pair": [
        3,
        5
      ],
      "selected": 2,
      "separation_residuals": [
        4.0,
        1.0,
        -4.440892098500626e-16,
        7.0
      ]
    },
    {
      "pair": [
        3,
        6
      ],
      "selected": 0,
      "separation_residuals": [
        -2.9999999999999982,
        8.999999999999998,
        -1.0,
        10.0
      ]
    },
    {
      "pair": [
        3,
        7
      ],
      "selected": 2,
      "separation_residuals": [
        1.0000000000000022,
        4.999999999999998,
        -1.0,
        10.0
      ]
    },
    {
      "pair": [
        4,
        5
      ],
      "selected": 3,
      "separation_residuals": [
        3.0,
        3.0,
        7.999999999999998,
        1.7763568394002505e-15
      ]
    },
    {
      "pair": [
        4,
        6
      ],
      "selected": 0,
      "separation_residuals": [
        -3.9999999999999982,
        10.999999999999998,
        6.999999999999998,
        3.0000000000000018
      ]
    },
    {
      "pair": [
        4,
        7
      ],
      "selected": 0,
      "separation_residuals": [
        2.220446049250313e-15,
        6.999999999999998,
        6.999999999999998,
        3.0000000000000018
      ]
    },
    {
      "pair": [
        5,
        6
      ],
      "selected": 0,
      "separation_residuals": [
        -3.9999999999999982,
        10.999999999999998,
        4.0,
        8.0
      ]
    },
    {
      "pair": [
        5,
        7
      ],
      "selected": 0,
      "separation_residuals": [
        2.220446049250313e-15,
        6.999999999999998,
        4.0,
        8.0
      ]
    },
    {
      "pair": [
        6,
        7
      ],
      "selected": 1,
      "separation_residuals": [
        8.0,
        0.0,
        7.0,
        7.0
      ]
    }
  ],
  "size": {
    "binary_variables": 112,
    "continuous_variables": 17,
    "equalities": 28,
    "inequalities": 120
  }
}

Transform and Solve with Convex Hull Relaxation¶

We will repeat the procedure above using Convex Hull Relaxation.

Convex Hull Implementation in Pyomo¶

# Creating the model
model = create_model()

# Applying convex hull relaxation to the model
# Add your solution here

# Solve and print the solution
results = SolverFactory(milp_solver).solve(model, tee=True)
assert check_optimal_termination(results), (
    f"Solve failed: status={results.solver.status}, "
    f"termination={results.solver.termination_condition}"
)
for i in model.rectangles:
    # %.4g, not %s: the solver returns coordinates a few ULPs off a whole
    # number (e.g. 6.999999999999998, -0.0), which is noise, not geometry.
    xi, yi = value(model.x[i]) + 0.0, value(model.y[i]) + 0.0
    print(f"Rectangle {i}: ({xi:.4g}, {yi:.4g})")
model.total_length.display()

Extract the hull placement¶

packing_hull = extract_packing(model, "gdp.hull")
print(json.dumps(packing_hull, indent=2))

{
  "method": "gdp.hull",
  "length": 11.0,
  "width": 10,
  "rectangles": [
    {
      "id": 0,
      "length": 4,
      "height": 3,
      "x": 7.0,
      "y": 7.0
    },
    {
      "id": 1,
      "length": 3,
      "height": 3,
      "x": 0.0,
      "y": 2.0
    },
    {
      "id": 2,
      "length": 2,
      "height": 2,
      "x": 2.0,
      "y": 0.0
    },
    {
      "id": 3,
      "length": 2,
      "height": 2,
      "x": 0.0,
      "y": 0.0
    },
    {
      "id": 4,
      "length": 3,
      "height": 3,
      "x": 4.0,
      "y": 0.0
    },
    {
      "id": 5,
      "length": 3,
      "height": 5,
      "x": 0.0,
      "y": 5.0
    },
    {
      "id": 6,
      "length": 4,
      "height": 7,
      "x": 7.0,
      "y": 0.0
    },
    {
      "id": 7,
      "length": 4,
      "height": 7,
      "x": 3.0,
      "y": 3.0
    }
  ],
  "certificates": [
    {
      "pair": [
        0,
        1
      ],
      "selected": 3,
      "separation_residuals": [
        11.0,
        -4.0,
        8.0,
        -2.0
      ]
    },
    {
      "pair": [
        0,
        2
      ],
      "selected": 1,
      "separation_residuals": [
        9.0,
        -3.0,
        10.0,
        -5.0
      ]
    },
    {
      "pair": [
        0,
        3
      ],
      "selected": 3,
      "separation_residuals": [
        11.0,
        -5.0,
        10.0,
        -5.0
      ]
    },
    {
      "pair": [
        0,
        4
      ],
      "selected": 3,
      "separation_residuals": [
        7.0,
        0.0,
        10.0,
        -4.0
      ]
    },
    {
      "pair": [
        0,
        5
      ],
      "selected": 1,
      "separation_residuals": [
        11.0,
        -4.0,
        5.0,
        3.0
      ]
    },
    {
      "pair": [
        0,
        6
      ],
      "selected": 3,
      "separation_residuals": [
        4.0,
        4.0,
        10.0,
        0.0
      ]
    },
    {
      "pair": [
        0,
        7
      ],
      "selected": 1,
      "separation_residuals": [
        8.0,
        0.0,
        7.0,
        3.0
      ]
    },
    {
      "pair": [
        1,
        2
      ],
      "selected": 3,
      "separation_residuals": [
        1.0,
        4.0,
        5.0,
        0.0
      ]
    },
    {
      "pair": [
        1,
        3
      ],
      "selected": 3,
      "separation_residuals": [
        3.0,
        2.0,
        5.0,
        0.0
      ]
    },
    {
      "pair": [
        1,
        4
      ],
      "selected": 0,
      "separation_residuals": [
        -1.0,
        7.0,
        5.0,
        1.0
      ]
    },
    {
      "pair": [
        1,
        5
      ],
      "selected": 2,
      "separation_residuals": [
        3.0,
        3.0,
        0.0,
        8.0
      ]
    },
    {
      "pair": [
        1,
        6
      ],
      "selected": 0,
      "separation_residuals": [
        -4.0,
        11.0,
        5.0,
        5.0
      ]
    },
    {
      "pair": [
        1,
        7
      ],
      "selected": 0,
      "separation_residuals": [
        0.0,
        7.0,
        2.0,
        8.0
      ]
    },
    {
      "pair": [
        2,
        3
      ],
      "selected": 1,
      "separation_residuals": [
        4.0,
        0.0,
        2.0,
        2.0
      ]
    },
    {
      "pair": [
        2,
        4
      ],
      "selected": 0,
      "separation_residuals": [
        0.0,
        5.0,
        2.0,
        3.0
      ]
    },
    {
      "pair": [
        2,
        5
      ],
      "selected": 2,
      "separation_residuals": [
        4.0,
        1.0,
        -3.0,
        10.0
      ]
    },
    {
      "pair": [
        2,
        6
      ],
      "selected": 0,
      "separation_residuals": [
        -3.0,
        9.0,
        2.0,
        7.0
      ]
    },
    {
      "pair": [
        2,
        7
      ],
      "selected": 2,
      "separation_residuals": [
        1.0,
        5.0,
        -1.0,
        10.0
      ]
    },
    {
      "pair": [
        3,
        4
      ],
      "selected": 0,
      "separation_residuals": [
        -2.0,
        7.0,
        2.0,
        3.0
      ]
    },
    {
      "pair": [
        3,
        5
      ],
      "selected": 2,
      "separation_residuals": [
        2.0,
        3.0,
        -3.0,
        10.0
      ]
    },
    {
      "pair": [
        3,
        6
      ],
      "selected": 0,
      "separation_residuals": [
        -5.0,
        11.0,
        2.0,
        7.0
      ]
    },
    {
      "pair": [
        3,
        7
      ],
      "selected": 2,
      "separation_residuals": [
        -1.0,
        7.0,
        -1.0,
        10.0
      ]
    },
    {
      "pair": [
        4,
        5
      ],
      "selected": 2,
      "separation_residuals": [
        7.0,
        -1.0,
        -2.0,
        10.0
      ]
    },
    {
      "pair": [
        4,
        6
      ],
      "selected": 0,
      "separation_residuals": [
        0.0,
        7.0,
        3.0,
        7.0
      ]
    },
    {
      "pair": [
        4,
        7
      ],
      "selected": 2,
      "separation_residuals": [
        4.0,
        3.0,
        0.0,
        10.0
      ]
    },
    {
      "pair": [
        5,
        6
      ],
      "selected": 0,
      "separation_residuals": [
        -4.0,
        11.0,
        10.0,
        2.0
      ]
    },
    {
      "pair": [
        5,
        7
      ],
      "selected": 0,
      "separation_residuals": [
        0.0,
        7.0,
        7.0,
        5.0
      ]
    },
    {
      "pair": [
        6,
        7
      ],
      "selected": 1,
      "separation_residuals": [
        8.0,
        0.0,
        4.0,
        10.0
      ]
    }
  ],
  "size": {
    "binary_variables": 112,
    "continuous_variables": 353,
    "equalities": 140,
    "inequalities": 456
  }
}

Discussion Questions¶

What does the indexed disjunction decorator create for one rectangle pair?
How many binary indicators are introduced for eight rectangles? Is that number a count of continuous degrees of freedom?
Which coordinate and bound would change if rectangle rotation were permitted?
Do the two methods need to return identical optimal coordinates?
Why does exactly-one certificate selection allow diagonal separation?

Certify the optimal length¶

The total rectangle area is $\sum_i L_iH_i=109$ , so containment in a width-10 strip gives $\ell\ge109/10=10.9$ . A stronger geometric bound is available here. Rectangles 5, 6, and 7 have heights 5, 7, and 7. Every pair has height sum greater than 10, so no pair can be separated vertically inside this strip. Their horizontal intervals must therefore be pairwise disjoint. Their lengths sum to $3+4+4=11$ , implying $\ell\ge11$ .

Each extracted solution is independently checked above for containment and all 28 no-overlap conditions. Each has length 11, attaining the bound, so both are globally optimal for the stated fixed-orientation data. Their one unit of unused area is $10(11)-109$ . This argument certifies the objective without claiming unique coordinates or relying solely on a solver status.

area = sum(r["length"]*r["height"] for r in packing_bigm["rectangles"])
tall = [r for r in packing_bigm["rectangles"] if r["id"] in (5,6,7)]
assert all(a["height"]+b["height"] > packing_bigm["width"]
           for k,a in enumerate(tall) for b in tall[k+1:])
length_bound = sum(r["length"] for r in tall)
assert area == 109 and length_bound == 11
assert all(abs(p["length"]-length_bound) < 1e-6 for p in (packing_bigm,packing_hull))
results = {"packings": [packing_bigm,packing_hull], "area": area,
           "area_lower_bound": area/packing_bigm["width"],
           "height_conflict_ids": [5,6,7], "certified_lower_bound": length_bound}
nb_path = "notebooks/2-dev/Modeling_Disjunctions_Strip_Packing.ipynb"
helper.save_results("strip-packing-solution", results, notebook=nb_path,
    source_tag="handout:strip-packing-model",
    source_cells=[(nb_path,t) for t in ("l4:strip-bigm-transform", "l4:strip-bigm-solve",
                  "l4:strip-hull-solve", "l4:strip-extract-bigm", "l4:strip-extract-hull",
                  "l4:strip-archive")],
    solver=f"{milp_solver}; Pyomo {pyomo.__version__}",
    description="Actual Big-M and hull fixed-orientation placements; independent feasibility checks and exact length-11 certificate.")
print(f"Area bound = {area/10:g}; height-conflict bound = {length_bound:g}; both feasible lengths = 11.")

[helper] wrote figures/results/strip-packing-solution.json
Area bound = 10.9; height-conflict bound = 11; both feasible lengths = 11.

Plot the extracted placements¶

Both panels use the same rectangle numbers, color/hatch identities, coordinate convention, and axis scales. Rectangles 5, 6, and 7 carry bold outlines: their pairwise height conflicts supply the length-11 bound. The labels identify geometry; the data archive preserves both selected certificates and all separation residuals.

Verified length-11 Big-M and hull placements for the eight-rectangle instance.

def plot_packings(results):
    from matplotlib.patches import Rectangle
    # Hatch identities follow figures/plots/_house.py, with two extra patterns.
    hatches = ("///", "\\\\\\", "...", "xxx", "|||", "---", "ooo", "+++")
    colors = ("#0072B2", "#D55E00", "#009E73", "#CC79A7", "#56B4E9", "#E69F00", "#F0E442", "#0072B2")
    fig, axes = plt.subplots(1,2,figsize=(10.8,5.1),sharex=True,sharey=True)
    for ax, packing in zip(axes, results["packings"]):
        for r in packing["rectangles"]:
            i = r["id"]
            ax.add_patch(Rectangle((r["x"],r["y"]),r["length"],r["height"],
                         facecolor=colors[i],alpha=0.22,edgecolor="black",hatch=hatches[i],
                         linewidth=2.4 if i in results["height_conflict_ids"] else 1.2))
            # An opaque border and label keep every rectangle distinct in monochrome.
            ax.add_patch(Rectangle((r["x"],r["y"]),r["length"],r["height"],
                         fill=False,edgecolor="black",linewidth=2.4 if i in results["height_conflict_ids"] else 1.2))
            ax.text(r["x"]+r["length"]/2,r["y"]+r["height"]/2,str(i),
                    ha="center",va="center",fontsize=14,fontweight="bold",
                    bbox=dict(facecolor="white",edgecolor="none",pad=1.2))
        ax.set(xlim=(-0.25,11.25),ylim=(-0.25,10.25),xlabel="Along strip, $x$",
               title=f'{packing["method"]}: length {packing["length"]:.4g}')
        ax.set_xticks([0,3,6,9,11]);ax.set_yticks([0,2,4,6,8,10]);ax.set_aspect("equal")
        for spine in ax.spines.values(): spine.set_color("black")
        ax.tick_params(colors="black")
    axes[0].set_ylabel("Across strip, $y$")
    fig.tight_layout()
    return fig

fig = plot_packings(results)
helper.save_figure(fig, "strip-packing-solution")