Manufacturing

Two-dimensional guillotine cutting

Many manufacturing processes involve cutting rectangular pieces from a larger sheet. But the material and cutting equipment often restrict how those cuts can be made. Glass, for example, is commonly cut by scoring a line on its surface and then breaking it along that line. Some cutting machines are also limited to straight cuts. For materials such as paper or board, straight cuts are useful when several sheets are stacked and cut together. These constraints make guillotine cutting a natural choice in many applications. Each cut runs straight across the full width or height of the rectangle being cut, splitting it into two smaller rectangles. Each resulting rectangle can then be cut again in the same way. Depending on the application, the goal may be to reduce material waste or maximize the value of the pieces produced. Guillotine cutting is used in industries such as wood processing, glass, plastic, sheet metal, and packaging.

View Markdown

The problem

In this example, an optical materials processor sells rectangular pieces of polarizing film in several standard sizes. To replenish its inventory, the production team plans to cut a large sheet into smaller pieces. Each product size has a known profit contribution per piece. The maximum quantity to produce depends on current stock and the sales plan.

The sheet may not be large enough to meet every replenishment request, and some sizes can be omitted from this run. The planner must decide which sizes to produce, how many pieces of each size to cut, and how to arrange the cuts to maximize total profit.

The sheet and the products

  • One film sheet. A rectangular sheet with a known width and height.
  • Product sizes. Each product has a specified width and height. Its required polarization direction fixes its orientation on the sheet, so width and height cannot be swapped.
  • Quantities and profits. Each product has a maximum replenishment quantity and a fixed profit contribution per piece. The plan may omit a product or include any number of pieces up to its replenishment limit.

A pattern that can be cut

The plan must also specify a complete cutting sequence: which rectangle to cut at each step, in which direction, and at what position. Every selected piece must fit within the sheet, with its edges parallel to the sheet edges and without overlapping another piece.

Maximize the total profit

The plan selects product sizes, quantities, and a cutting pattern to maximize total profit. The layout that uses the most film may not be the most profitable.

Where the data comes from

For this restocking run, the model needs the sheet dimensions. For each product size, it also needs the finished dimensions, the required polarization direction, the maximum replenishment quantity, and the profit contribution per piece. A spreadsheet or CSV file can hold these inputs. Material stock records give the sheet dimensions, or the sheet selected for cutting can be measured. Product specifications give the finished dimensions and the required polarization direction of each piece. The maximum replenishment quantity can be based on inventory and sales records. The profit contribution per piece can be estimated from pricing and cost records. All products must use the same cost basis, so that the model can compare their profits. All width and height measurements should use the same reference direction on the sheet.

A small worked example

This example cuts a sheet of polarizing film measuring 12 × 8 units. The table below lists five products. At their maximum quantities, the pieces would need 204 square units of film, more than the sheet’s 96. The plan must choose how many pieces of each product to cut. No piece may be rotated.

ProductSizeMaximum quantityProfit per piece
P14 × 6331
P28 × 2217
P32 × 327
P47 × 5250
P53 × 6121

Input: polarizing_film.json

Optimal cutting pattern

The optimal cutting pattern below was found by CP-SAT in a run through the OpenConstraint MCP server, with proof that no pattern earns more. The numbers on the figure’s cut lines give the cutting order. Cut 1 runs across the whole sheet, and each later cut splits one rectangle that the earlier cuts made. Cut 2 trims unused film from a piece.

02468101202468P2P1P1P11234
  • Piece labeled with its product
  • Unused no piece is cut from this area
  • Cut numbered in cutting order
ProductPieces cutProfit
P13 of 393
P21 of 217
P30 of 20
P40 of 20
P50 of 10
Total4110

A non-optimal cutting pattern

Intuitively, pieces are considered from highest to lowest profit per piece and placed in the lowest row where they fit. With this rule, P4 comes first, making the bottom row 5 units tall. P1 and P5 are both 6 units tall, so neither fits in that row or in the 3-unit-high space above it. The rule places one P2 piece above P4 and two P3 pieces beside it. The rule earns 81, versus the optimal pattern’s 110. It leaves 33 square units unused, versus 8. The optimal pattern omits P4 and fits three P1 pieces.

02468101202468P4P3P3P212345678
  • Piece labeled with its product
  • Unused no piece is cut from this area
  • Cut numbered in cutting order
ProductPieces cutProfit
P10 of 30
P21 of 217
P32 of 214
P41 of 250
P50 of 10
Total481

The CP model

The constraint programming (CP) model builds a cutting pattern to maximize the selected pieces’ total profit. The Python excerpts below show selected parts of the model.

Representing each region as a node

Each node represents a possible rectangular region in the cut tree. used indicates whether that node belongs to the chosen pattern. (x1, y1) and (x2, y2) give the region’s bottom-left and top-right corners, measured from the original sheet’s bottom-left corner. Its width is x2 - x1, and its height is y2 - y1. For a cut, position gives the x-coordinate of a vertical cut or the y-coordinate of a horizontal cut, using that same origin. holds contains one true-or-false variable per product type. A true value assigns one piece of that type to this node’s region.

class Node(NamedTuple):
    """CP-SAT variables of one node slot in the cut tree."""

    used: cp_model.IntVar
    position: cp_model.IntVar
    x1: cp_model.IntVar
    y1: cp_model.IntVar
    x2: cp_model.IntVar
    y2: cp_model.IntVar
    holds: list[cp_model.IntVar]
model.py — Node, lines 82–93, two lines omitted

Building a valid cut tree

The root node represents the whole sheet.

root: Node = nodes[0]
model.add(root.x1 == 0)
model.add(root.y1 == 0)
model.add(root.x2 == sheet_width)
model.add(root.y2 == sheet_height)
model.py — solve(), lines 294–298

Each used node specifies a cut or holds one piece as a leaf. Linking constraints, omitted here, make the two child rectangles cover their parent exactly without overlapping.

model.add(sum(node.holds) + node.is_cut == node.used)
model.py — solve(), line 234

A leaf’s rectangle must be at least as wide and as tall as the piece it holds. Any space left over in the leaf is unused film.

for product, holds in zip(products, node.holds, strict=True):
    model.add(node.x2 - node.x1 >= product.width).only_enforce_if(holds)
    model.add(node.y2 - node.y1 >= product.height).only_enforce_if(holds)
model.py — solve(), lines 283–285

Limiting quantities and maximizing profit

The model limits the number of pieces of each product to its maximum replenishment quantity.

for index, product in enumerate(products):
    model.add(sum(node.holds[index] for node in nodes) <= product.max_quantity)
model.py — solve(), lines 358–359

The objective is to maximize the total profit of the selected pieces.

profit: cp_model.LinearExpr = cp_model.LinearExpr.weighted_sum(
    [node.holds[index] for node in nodes for index in range(len(products))],
    [product.profit for _ in nodes for product in products],
)
model.maximize(profit)
model.py — solve(), lines 371–375

How the result is checked

Each piece must match a known product in its fixed orientation, fit inside the sheet without overlap, and stay within its product’s quantity limit. An independent checker verifies these rules. It recomputes the pattern’s profit and checks that it matches the reported objective. It also verifies that straight guillotine cuts can separate the pieces. If a cut tree is supplied, it replays the cuts and checks that each piece exactly matches a leaf rectangle. These checks cannot establish whether the encoded rules match the actual cutting process.

An accepted pattern can still earn less than another valid layout. Only the solver’s “optimal” status proves that no pattern earns more for this model and input data.