2D Cutting & Packing

Industrial cutting and packing problems appear in manufacturing, logistics, and chip design. This chapter teaches you to solve them with CP-SAT.

Why Cutting & Packing?

Every physical manufacturing process involves cutting materials:

| Industry | Material | Goal | |----------|----------|------| | Steel mills | Steel plates | Cut shapes with minimum waste | | Garment factories | Fabric rolls | Arrange patterns to save fabric | | Furniture | Wood boards | Cut parts with minimal scrap | | Packaging | Cardboard sheets | Arrange boxes efficiently | | Chip design | Silicon wafers | Place transistors optimally |

Each 1% improvement in material utilization translates to millions in savings for large manufacturing operations.

What Is 2D Bin Packing?

2D Bin Packing asks: given a set of rectangles and a rectangular sheet, can all rectangles be placed without overlapping? Find the arrangement with minimum waste.

This is the 2D generalization of the classic bin packing problem.

How 2D Packing Works with CP-SAT

CP-SAT solves 2D packing using the NoOverlap2D constraint:

from ortools.sat.python import cp_model

# Rectangles to place (width, height)
rectangles = [
    (3, 2), (4, 3), (2, 2), (5, 2),
    (3, 3), (2, 4), (4, 2), (3, 4),
]

bin_width, bin_height = 10, 10
num_items = len(rectangles)

model = cp_model.CpModel()

# Position variables
x = [model.NewIntVar(0, bin_width, f"x_{i}") for i in range(num_items)]
y = [model.NewIntVar(0, bin_height, f"y_{i}") for i in range(num_items)]

# Rotation variables
rotated = [model.NewBoolVar(f"rot_{i}") for i in range(num_items)]

# Width and height (with rotation)
w = [model.NewIntVar(0, bin_width, f"w_{i}") for i in range(num_items)]
h = [model.NewIntVar(0, bin_height, f"h_{i}") for i in range(num_items)]

for i in range(num_items):
    # Normal orientation
    model.Add(w[i] == rectangles[i][0]).OnlyEnforceIf(rotated[i].Not())
    model.Add(h[i] == rectangles[i][1]).OnlyEnforceIf(rotated[i].Not())
    # Rotated 90 degrees
    model.Add(w[i] == rectangles[i][1]).OnlyEnforceIf(rotated[i])
    model.Add(h[i] == rectangles[i][0]).OnlyEnforceIf(rotated[i])
    # Must stay within bounds
    model.Add(x[i] + w[i] <= bin_width)
    model.Add(y[i] + h[i] <= bin_height)

# No overlap between any two rectangles
intervals_x = [model.NewIntervalVar(x[i], w[i], x[i] + w[i], f"ix_{i}")
              for i in range(num_items)]
intervals_y = [model.NewIntervalVar(y[i], h[i], y[i] + h[i], f"iy_{i}")
              for i in range(num_items)]
model.AddNoOverlap2D(intervals_x, intervals_y)

# Solve
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 30
status = solver.Solve(model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f"=== 2D Packing Result ===")
    total_area = bin_width * bin_height
    used_area = 0
    for i in range(num_items):
        xi = solver.Value(x[i])
        yi = solver.Value(y[i])
        wi = solver.Value(w[i])
        hi = solver.Value(h[i])
        rot = "rotated" if solver.Value(rotated[i]) else "normal"
        print(f"Item {i} ({rectangles[i]}): ({xi},{yi})-({xi+wi},{yi+hi}) {rot}")
        used_area += wi * hi
    print(f"\nUtilization: {used_area}/{total_area} = {used_area/total_area:.1%}")
else:
    print("No feasible arrangement")

Visualizing the Result

import matplotlib.pyplot as plt
import matplotlib.patches as patches

fig, ax = plt.subplots(figsize=(8, 8))
ax.set_xlim(0, bin_width)
ax.set_ylim(0, bin_height)
ax.set_aspect("equal")
ax.set_title("2D Packing Result")
ax.grid(True, alpha=0.3)

colors = ["#FF6B6B", "#4ECDC4", "#45B7D1", "#96CEB4",
          "#FFEAA7", "#DDA0DD", "#98D8C8", "#F7DC6F"]

for i in range(num_items):
    xi = solver.Value(x[i])
    yi = solver.Value(y[i])
    wi = solver.Value(w[i])
    hi = solver.Value(h[i])
    rect = patches.Rectangle((xi, yi), wi, hi,
                             linewidth=2, edgecolor="black",
                             facecolor=colors[i % len(colors)], alpha=0.7)
    ax.add_patch(rect)
    ax.text(xi + wi/2, yi + hi/2, str(i),
            ha="center", va="center", fontsize=12, fontweight="bold")

plt.tight_layout()
plt.show()

Cutting Stock Problem

The cutting stock problem is a variant where you have large sheets and need to cut smaller pieces, minimizing the number of sheets used.

This is solved similarly to bin packing, but the objective is to minimize the number of sheets (or maximize utilization).

Heuristic Algorithms

For large instances (50+ rectangles), CP-SAT becomes slow. Use heuristic algorithms:

| Algorithm | Strategy | Speed | Quality | |-----------|----------|:-----:|:-------:| | First Fit Decreasing | Sort largest first, place in first bin that fits | Fast | Medium | | Best Fit Decreasing | Sort largest first, place where least space remains | Fast | Medium-High | | Bottom-Left | Place each rectangle at the lowest-leftmost free position | Fast | Medium | | Guillotine Cut | Simulate straight cuts like real cutting machines | Medium | Medium-High | | Maximal Rectangles | Track all maximal empty rectangles | Slow | High |

Real-World Applications

1. Steel Plate Nesting

Shipbuilding and aerospace companies optimize metal cutting to reduce waste. Each 1% improvement saves millions of dollars annually.

2. Warehouse Pallet Loading

Maximize boxes per pallet to reduce shipping costs and fuel consumption.

3. Furniture Manufacturing

Optimize cutting furniture parts from standard-sized wood boards. Typical factories save 5-15% material.

4. Chip Design (VLSI)

Placing transistors on silicon wafers is an extremely large-scale 2D packing problem with electronic constraints.

Problem Variants

| Problem | Description | Application | |---------|-------------|-------------| | 2D Packing | Place rectangles in fixed container | Container loading | | Cutting Stock | Cut parts from large sheets | Manufacturing | | Strip Packing | Place on fixed-width infinite strip | Circuit layout | | Irregular Nesting | Place irregular shapes | Garment manufacturing |

Summary

2D Cutting and Packing problems are direct industrial applications of combinatorial optimization. CP-SAT handles small to medium instances exactly, while heuristics scale to larger problems.

Key takeaways:

  • 2D packing = place rectangles on sheet without overlap
  • NoOverlap2D constraint enables direct CP-SAT modeling
  • Rotation support adds flexibility and improves utilization
  • CP-SAT works for up to ~50 rectangles
  • Heuristics (FFD, Bottom-Left) scale to hundreds of items
  • Real applications in manufacturing, logistics, and chip design

What's Next: Knapsack Selection

The next chapter applies knapsack concepts to project selection and budget allocation - deciding which projects to fund under resource constraints with dependencies and mutual exclusion rules.

Practical Tips for 2D Packing

| Tip | Description | |-----|-------------| | Sort by area | Place larger rectangles first for better utilization | | Allow rotation | 90-degree rotation improves packing by 5-15% | | Use symmetry breaking | Fix first rectangle position to reduce search space | | Set reasonable timeout | 30-60 seconds for CP-SAT, then accept best found | | Consider strip packing | For very long narrow sheets, use strip packing variant |

The Vibe Coding Approach

"I need to pack 30 rectangular items onto a 120x80 cm sheet. Each item has width and height, can be rotated 90 degrees. Use OR-Tools CP-SAT with AddNoOverlap2D constraint. Maximize utilization."

The AI will generate the complete packing model with rotation, bounds, and no-overlap constraints.

Unlock Full Tutorial

This chapter is paid content. Join the project to unlock over 5000 words of deep analysis, including 10+ god-tier Prompts and real Source Code examples!

๐Ÿ’ณ View Payment Plans (NT$ 99)Already purchased? Click here to login