# Two-dimensional guillotine cutting

*Manufacturing. Markdown version of "Two-dimensional guillotine cutting" from OpenConstraint. Canonical page: https://openconstraint.com/cases/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.

## 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.

**Products the plan can choose from**

| Product | Size | Maximum quantity | Profit per piece |
| --- | --- | --- | --- |
| P1 | 4 × 6 | 3 | 31 |
| P2 | 8 × 2 | 2 | 17 |
| P3 | 2 × 3 | 2 | 7 |
| P4 | 7 × 5 | 2 | 50 |
| P5 | 3 × 6 | 1 | 21 |

Source: [Input: polarizing_film.json](https://github.com/Openconstraint/openconstraint-mcp/blob/37c6803c61544c9c2ea09901899f11469fb851aa/examples/guillotine_cutting/parsed/polarizing_film.json)

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 cut numbers 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.

**Pieces in the optimal pattern**

| Product | Pieces cut | Profit |
| --- | --- | --- |
| P1 | 3 of 3 | 93 |
| P2 | 1 of 2 | 17 |
| P3 | 0 of 2 | 0 |
| P4 | 0 of 2 | 0 |
| P5 | 0 of 1 | 0 |
| Total | 4 | 110 |

**Where each piece sits in the optimal pattern. x and y give each piece’s bottom-left corner, in units from the sheet’s bottom-left corner.**

| Product | Width | Height | x | y |
| --- | --- | --- | --- | --- |
| P2 | 8 | 2 | 0 | 0 |
| P1 | 4 | 6 | 0 | 2 |
| P1 | 4 | 6 | 4 | 2 |
| P1 | 4 | 6 | 8 | 2 |

**The cuts for the optimal pattern, in order. Each cut splits one rectangle that the earlier cuts made.**

| Step | Direction | Position | Rectangle it splits |
| --- | --- | --- | --- |
| 1 | horizontal | y = 2 | 12 × 8 at (0, 0) |
| 2 | vertical | x = 8 | 12 × 2 at (0, 0) |
| 3 | vertical | x = 4 | 12 × 6 at (0, 2) |
| 4 | vertical | x = 8 | 8 × 6 at (4, 2) |

**Total profit:** 110

### 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.

**Pieces in the rule’s pattern**

| Product | Pieces cut | Profit |
| --- | --- | --- |
| P1 | 0 of 3 | 0 |
| P2 | 1 of 2 | 17 |
| P3 | 2 of 2 | 14 |
| P4 | 1 of 2 | 50 |
| P5 | 0 of 1 | 0 |
| Total | 4 | 81 |

**Where each piece sits in the rule’s pattern. x and y give each piece’s bottom-left corner, in units from the sheet’s bottom-left corner.**

| Product | Width | Height | x | y |
| --- | --- | --- | --- | --- |
| P4 | 7 | 5 | 0 | 0 |
| P3 | 2 | 3 | 7 | 0 |
| P3 | 2 | 3 | 9 | 0 |
| P2 | 8 | 2 | 0 | 5 |

**The cuts for the rule’s pattern, in order. Each cut splits one rectangle that the earlier cuts made.**

| Step | Direction | Position | Rectangle it splits |
| --- | --- | --- | --- |
| 1 | horizontal | y = 5 | 12 × 8 at (0, 0) |
| 2 | vertical | x = 7 | 12 × 5 at (0, 0) |
| 3 | vertical | x = 9 | 5 × 5 at (7, 0) |
| 4 | horizontal | y = 3 | 2 × 5 at (7, 0) |
| 5 | vertical | x = 11 | 3 × 5 at (9, 0) |
| 6 | horizontal | y = 3 | 2 × 5 at (9, 0) |
| 7 | horizontal | y = 7 | 12 × 3 at (0, 5) |
| 8 | vertical | x = 8 | 12 × 2 at (0, 5) |

## 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

Python excerpt: one set of variables per node slot:

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.

```python
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]
```

Source: [model.py — Node, lines 82–93, two lines omitted](https://github.com/Openconstraint/openconstraint-mcp/blob/37c6803c61544c9c2ea09901899f11469fb851aa/examples/guillotine_cutting/model.py#L82-L93)

### Building a valid cut tree

Python excerpt: the root rectangle is the whole sheet:

The root node represents the whole sheet.

```python
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)
```

Source: [model.py — solve(), lines 294–298](https://github.com/Openconstraint/openconstraint-mcp/blob/37c6803c61544c9c2ea09901899f11469fb851aa/examples/guillotine_cutting/model.py#L294-L298)

Python excerpt: a used node is a cut or a leaf:

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.

```python
model.add(sum(node.holds) + node.is_cut == node.used)
```

Source: [model.py — solve(), line 234](https://github.com/Openconstraint/openconstraint-mcp/blob/37c6803c61544c9c2ea09901899f11469fb851aa/examples/guillotine_cutting/model.py#L234-L234)

Python excerpt: a leaf is big enough for its piece:

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.

```python
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)
```

Source: [model.py — solve(), lines 283–285](https://github.com/Openconstraint/openconstraint-mcp/blob/37c6803c61544c9c2ea09901899f11469fb851aa/examples/guillotine_cutting/model.py#L283-L285)

### Limiting quantities and maximizing profit

Python excerpt: capping each product at its maximum quantity:

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

```python
for index, product in enumerate(products):
    model.add(sum(node.holds[index] for node in nodes) <= product.max_quantity)
```

Source: [model.py — solve(), lines 358–359](https://github.com/Openconstraint/openconstraint-mcp/blob/37c6803c61544c9c2ea09901899f11469fb851aa/examples/guillotine_cutting/model.py#L358-L359)

Python excerpt: maximizing total profit:

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

```python
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)
```

Source: [model.py — solve(), lines 371–375](https://github.com/Openconstraint/openconstraint-mcp/blob/37c6803c61544c9c2ea09901899f11469fb851aa/examples/guillotine_cutting/model.py#L371-L375)

## 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.

## Implementation

- [openconstraint-mcp](https://github.com/Openconstraint/openconstraint-mcp)
- [How the MCP server runs it](https://openconstraint.com/mcp)