Cutting Stock Optimization

Cut stock rolls into the ordered widths using the fewest rolls. Enter the roll length and the order on the Model sheet; Python lists the cutting patterns and finds the best mix.

Cutting Stock Optimization

Overview

A stock roll comes in one fixed width. Orders ask for pieces of several narrower widths. Each way of cutting one roll is a cutting pattern: a count of how many pieces of each width that roll yields. This template chooses how many rolls to cut each way so that every ordered width is made in at least the quantity ordered, using the fewest rolls in total.

You enter the roll length and the order. The template lists every full cutting pattern itself, so you never type patterns. The sample comes from a lecture on column generation in MIT OpenCourseWare course 15.094J, Systems Optimization: a roll 273 units wide and five ordered widths. The best plan uses 230 rolls. The Developer reference gives the source and how the numbers were checked.

Before you start

Requirements. Excel with Python for Excel. The template uses only the sheets in this workbook and no external data. To install and open the add-in, and for how Edit and App mode work, see the Boardflare Notebook Reference.

Only the roll length, the solver time limit and the order are needed. Widths, roll length and quantities are whole numbers. A width longer than the roll cannot be cut and is reported by its cell.

Workbook tour

Sheet and range	What it holds	Kind
Model, B4 (Roll length) and B5 (Solver time limit)	The stock roll length (273 in the sample) and the solver time limit in seconds (60 by default, at most 120).	Editable input
Model, A7:C27 (Item, Width (units), Quantity ordered)	The order: one row per piece, up to 20 rows. Rows 8 to 12 hold the sample; rows 13 to 27 are empty and ready.	Editable input
Results, A5:C15 (Result, Value, Check)	Plan summary: status, message, rolls used, LP lower bound, trim loss, waste, patterns considered, distinct patterns in the plan, and two solver checks: the largest limit violation and the MIP gap. The Check column shows PASS or FAIL for each check once the solve is optimal, and is blank otherwise.	Output
Results, A18:D58 (Pattern, Rolls cut this way, Cuts per roll, Trim per roll)	The cutting plan: each pattern used, how many rolls cut that way, and the pieces and trim on each roll.	Output
Fulfilment, A5:F25 (Item, Width, Ordered, Produced, Overproduction, Status)	Pieces produced against ordered for each width.	Output
Validation, A4:D11 and F5:H11	Published reference values (A4:D11, display only: the checks use the values built into the notebook) and the live check results (F5:H11).	Reference and output
Guide	How the model works, its limits, and the sample source.	Reference

Using the template

First-use walk-through with the sample problem

1. Open the workbook. The Model sheet holds the roll length 273 in B4 and the five sample pieces in A8:C12.
2. Open the Results sheet. Status shows optimal, Rolls used shows 230, and both checks in the Check column (Largest limit violation and MIP gap) show PASS.
3. Look at the cutting plan. It lists each pattern used, how many rolls to cut that way, and the pieces on each roll. Only a few patterns carry the plan.
4. Open the Fulfilment sheet. Each width is produced at least as ordered, and some get a little extra.
5. Open the Validation sheet. Every live result shows PASS.

Enter a new problem

1. In Model!B4, enter the stock roll length.
2. In Model!A8:C27, enter the order: a piece name, its width and the quantity ordered. Fill all three cells of a row, or clear the whole row.
3. Read the Results sheet. The template lists the patterns and chooses the plan.

Change the time limit

Model!B5 sets how long the solver may search, in seconds. The default is 60 and the maximum is 120. Larger problems may need more time. If the status shows that the solver stopped early, raise the limit or reduce the order.

Inputs and settings

The Model sheet is the one place to edit the problem. Only B4, B5 and A7:C27 are read; a filled cell elsewhere in A1:AZ60 is an error that names it.

Every numeric input (B4, B5, the widths and the quantities) takes a number. Excel TRUE and FALSE are rejected by cell name, not counted as 1 or 0. A number stored as text, such as “233”, is read as the number it shows. Text that is not a number is named in the error.

Data shape. Enter the roll length in Model!B4 and the solver time limit in Model!B5. Enter the order in Model!A7:C27 with headers in row 7: one row per piece, with the piece name, its width and the quantity ordered. Up to 20 order rows (rows 8 to 27) are read. Blank rows are ignored. A used row needs all three cells filled.

Sample data. Model!B4 holds 273 and Model!A8:C12 holds the five sample pieces: Piece A width 18 quantity 233, Piece B width 91 quantity 310, Piece C width 21 quantity 122, Piece D width 136 quantity 157, Piece E width 51 quantity 120. Model!B5 holds 60 seconds.

Scan window and exclusions

The notebook scans Model!A1:AZ60 cell by cell. Anything filled in that window outside the input cells is reported by its cell, not ignored. The title and subtitle in A1:C2 and the labels in A4:A5 hold text only: a number typed there is an error that names the cell, because it would otherwise be ignored. B4 and B5 hold the roll length and time limit. The header in row 7 (Item, Width (units), Quantity ordered) must keep its exact text. Model!A28 and any other cell below the order table, to the right of column C in the order rows, or in column AA to AZ is an error that names the cell. Cells beyond column AZ or row 60 are not read, so a value there does not change the result. Clear the named cell to run the template.

How results are calculated

The template lists every full cutting pattern: a way to cut one roll that fits and cannot take one more piece of any ordered width. It then chooses a whole number of rolls of each pattern so that the pieces cover every order, using the fewest rolls in total. This is a mixed-integer linear program solved with HiGHS. Overproduction is allowed, because each order is a minimum. The model has no trim allowance and no cutting-time or setup cost.

The relaxed value, in which rolls may be fractional, is 228.9982 for the sample. It is a lower bound on what whole rolls can achieve, and the whole-roll answer is 230.

Reading the results

Summary (Results, A5:C15)

Status says whether the plan is optimal. Rolls used is the total number of rolls, which the template minimizes. The LP lower bound is the relaxed value. Waste is the total trim as a share of all roll length.

Largest limit violation is the largest amount by which the plan breaks a limit, as the solver’s own check measures it: the covering rows, the pattern-count bounds and whole-number limits. It shows PASS when that amount is at most 1e-6, and FAIL otherwise. MIP gap is the relative gap HiGHS reports when it stops: how far the plan’s roll count can be from the best possible. It shows PASS when the gap is at most 1e-4, which is HiGHS’s default stopping gap, so an optimal solve passes. Both checks are blank until a solve completes. The MIP gap has no duality gap: this model is a whole-number program, so only the MIP gap applies.

Cutting plan (Results, A18:D58)

Each row is one pattern used. Rolls cut this way is how many rolls to cut that way. Cuts per roll lists the pieces on one roll, and Trim per roll is the unused length on it.

Fulfilment (Fulfilment, A5:F25)

For each order row, Produced is the pieces the plan makes and Overproduction is the excess over the order. Status reads Covered when every ordered piece is made.

Validation basis (Validation, A5:H11)

Two checks compare with the published source values: the optimum of 230 rolls (tolerance 0) and the LP bound of 228.9982 (tolerance 0.00005). The notebook holds these values itself. The published values shown in A4:D11 are for reference only, so editing them cannot change PASS or FAIL. When the roll length or an order width or quantity has been changed, they show the actual value, a Difference of “n/a” and the Status “n/a (model edited)”. Four live checks always apply to the solution: every width is covered; each plan pattern is recomputed from the Model widths and fits the roll, and with its trim it equals the roll length; the counts are whole numbers; and the LP bound is no larger than the optimum. Renaming a piece does not change the model, so the published checks still PASS.

Results checks. The two checks on the Results summary are not in this Validation sheet. The largest limit violation uses a PASS tolerance of 1e-6, the same tolerance the solver uses to decide feasibility. The MIP gap uses a PASS tolerance of 1e-4. The Validation sheet has no gap check, so this tolerance comes from HiGHS: it stops at a relative MIP gap of 1e-4 unless the solver is configured otherwise (this template does not set it). A tighter tolerance would show FAIL on an optimal solve.

Deviation: no sensitivity table

The template does not show shadow prices or a sensitivity table. The whole-roll model is a mixed-integer program, and HiGHS does not report dual values for it. Use the Fulfilment sheet to see which widths get extra pieces.

Saving, sharing and App mode

Save the workbook as usual. The results update when the notebook runs again after you change the Model sheet. For sharing and App mode, follow the Boardflare reference linked in Before you start.

Errors, empty states and limits

Error messages

• error with a cell name: an input is wrong. The message names the cell, for example “Model!B8 width 300 is longer than the Model!B4 roll length 273; no roll can carry it”, or “Model!A13 is blank but the row has other entries.” Fix the named cell.
• Ready: the roll length and the order are both empty. Enter them to run.
• time_limit_feasible: the solver reached the time limit before it could prove the optimum. No rolls count and no cutting plan are shown, because the optimum is not proven. Raise the time limit or reduce the order.
• time_limit_no_solution: the solver reached the time limit before finding any whole-roll plan. Raise the time limit or reduce the order.

Empty state

If Model!B4 and every order row are empty, the Results sheet shows Ready and the message asks for the roll length and an order.

Limitations and when to use this

Use this template when you want the fewest stock rolls for a fixed order of widths. It does not cost waste or cut time, does not sequence the cuts, and does not allow trim beyond the roll.

The model cannot be infeasible for a valid order. Every width is at most the roll length, so each width fits alone in a pattern of its own, and any non-negative quantities can be covered. A width longer than the roll is therefore reported by cell (for example Model!B8) rather than shown as an infeasible result.

• The model reads the roll length (Model!B4), the time limit (Model!B5) and up to 20 order rows (Model!A8:C27).
• The notebook scans Model!A1:AZ60. Filled cells in that window outside the input area are reported by cell name; cells beyond column AZ or row 60 are not read.
• Widths, the roll length and quantities must be whole numbers. A width longer than the roll is reported by cell.
• The number of maximal cutting patterns is capped at 20000, and the pattern search is capped at 500000 steps. A larger count is reported with the inputs to reduce.
• TRUE and FALSE are rejected in any numeric input, by cell name.
• The solver time limit defaults to 60 seconds and is capped at 120 seconds.

Free alternatives

Excel Solver, built into desktop Excel (it is not available in Excel for the web), and the free OpenSolver add-in for Windows Excel (a COIN-OR CBC add-in with no stable release since 2020) can both solve this model as a whole-number program, but Solver’s limit of 200 decision variables counts cutting patterns, so a large order with many maximal patterns can exceed it. This workbook enumerates the maximal cutting patterns itself and solves the whole-roll model with HiGHS through SciPy’s scipy.optimize.milp, running in the browser. What it adds is order entry with a pattern listing and live recalculation, fulfilment and trim checks, an LP bound check beside the whole-roll optimum, two solver checks on the Results summary (the largest limit violation and the MIP gap), and a Validation sheet against the 230-roll optimum and 228.9982 LP bound from the MIT OpenCourseWare 15.094J column generation lecture notes.

Customizing as an author

Edit notebook.py for the optimization and the parsing. Edit workbook.py for the sheets and the layout. Scenario checks live in scenarios.py as literal values. Keep the engine block between the GENERATED ENGINE markers in notebook.py: it is synced from the engine, not edited by hand.

Developer reference

Notebook implementation

The notebook reads the roll length, the time limit and the order from the Model sheet. It scans Model!A1:AZ60 and reports any filled cell outside the inputs by cell name, and it requires the row 7 header text to match. It passes the order to solve_cutting_stock from the engine’s cutting stock builder (templates/optimization/engine/forms/cutting_stock.py), which enumerates the maximal patterns and solves the whole-roll model. The enumeration stops with an error after MAX_PATTERNS = 20000 maximal patterns, or after MAX_WORK = 500000 examined combinations (the search work, which can exceed the pattern count); both limits are named in the error. The summary, cutting plan, fulfilment and validation are published to the anchors listed in workbook.py.

How the calculation/model works

Each variable is a maximal pattern p, and x_p is the number of rolls cut that way: an integer of at least 0. The objective minimizes the sum of x_p. For each ordered width w, the sum over p of a_pw times x_p must be at least the ordered quantity d_w, where a_pw is the number of pieces of width w in pattern p. A pattern is maximal when no further piece of any ordered width fits in it. Restricting to maximal patterns does not change the optimum, because extending a pattern never reduces what it covers.

Over all patterns that fit the 273-unit roll there are 457 non-zero patterns, of which 93 are maximal.

Validation / expected results

Validation basis. The source is the lecture notes “Column Generation” by Teo Chung-Piaw, dated 25 February 2003, in MIT OpenCourseWare course 15.094J, Systems Optimization: https://ocw.mit.edu/courses/15-094j-systems-optimization-models-and-computation-sma-5223-spring-2004/resources/lec6_column1/ . The PDF is also mirrored at https://mitocw.ups.edu.ec/courses/sloan-school-of-management/15-094j-systems-optimization-models-and-computation-sma-5223-spring-2004/lecture-notes/lec6_column1.pdf , which is byte-identical. The roll width, ordered widths and quantities were checked against slide 25. Slide 29 shows a round-up heuristic of 231, which is not an optimum and is not used.

Slide 12 gives an LP value of 228.7106 and an “IP halted” note, which conflict with slide 25. The template follows slide 25, which gives an LP bound of 228.9982 and a whole-roll value of 230. An independent scipy solve over all 457 patterns and over the 93 maximal patterns reproduces both the optimum of 230 and the LP bound of 228.998168.

The optimum is not unique. Across all 230-roll plans, the pieces made range as follows: width 18 from 233 to 248, width 91 from 310 to 312, width 21 from 122 to 134, width 136 from 157 to 158, and width 51 from 120 to 125. The offline scenarios therefore assert the status and the number of rolls, not the pattern counts.

Scenario expectations come from scipy milp: more-demand (width 91 at 320) gives 233 rolls, lower-demand (width 136 at 150) gives 226, and roll 300 gives 211.

Generated-region policy

Text between the BEGIN GENERATED and END GENERATED markers describes the template and is kept in step with the Model layout. Keep it in step when the layout changes.

Changelog

2026-10-28

Results checks: the summary has a Check column with two rows, Largest limit violation (PASS at most 1e-6) and MIP gap (PASS at most 1e-4, HiGHS’s default stopping gap). Each shows blank until the solve is optimal. The plan section moved down two rows: the summary is now A5:C15 and the cutting plan is A18:D58, and the Results anchors follow. Infeasibility repair was not added: no valid sheet input can make this model infeasible, because widths are checked against the roll length, and quantities are whole numbers of zero or more.

2026-10-26

Rebuilt on the cutting stock builder. The Model sheet takes the roll length and an order of up to 20 rows; the template lists the patterns itself. Sample from the MIT lecture: a 273-unit roll and five ordered widths, 230 rolls. Scenarios cover more and less demand, a different roll length, an over-wide piece, a blank state, overflow inside and beyond the scan window, a renamed header, a duplicate width, a partial row, an edited model and a renamed label. The scan window is Model!A1:AZ60; order widths must be distinct.

Validation and input checks: the published values and tolerances moved into the notebook, and the Validation reference cells are display only (text or number edits there do not change PASS or FAIL). A number in a label cell is an error. TRUE and FALSE are rejected in numeric inputs. The verification note no longer names a plan-specific trim, and the source file records the PDF link and checksum.