Question 4 of 8: Integer Programming Model for the Cutting-Stock Problem
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Exams — May 2016 — 98-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 160 marks across 8 questions (each worth 20) and only 100 marks are required, so a candidate would normally answer 5 — all eight are solved below for completeness.
Reference texts: Hillier & Lieberman, Introduction to Operations Research (11th ed., McGraw-Hill) — linear programming and the revised simplex method (ch. 3–5), network optimization models (ch. 9), integer programming (ch. 12), decision analysis (ch. 16), and queueing theory (ch. 17).
Question 4: Integer Programming Model for the Cutting-Stock Problem (20 marks)
Given. Jumbo reel width 150 cm; standard widths 30, 45, 60, 90 cm with demands 200, 150, 100, 50 rolls respectively; Pattern #1 = five 30 cm pieces (0 trim).
Given data — demand by standard width
Width (cm)
30
45
60
90
Demand (rolls)
200
150
100
50
Find. The integer programming model — decision variables, objective, constraints — that decides how many jumbo reels to cut by each feasible pattern to meet demand at minimum total waste. Formulate only, do not solve.
Fig. 4 — two example cutting patterns on a 150 cm jumbo reel: Pattern 1 (five 30 cm pieces, no trim) and Pattern 4 (three 30 cm + one 45 cm piece, 15 cm trim).
Enumerate the efficient cutting patterns. A pattern $(a,b,c,d)$ uses $a$ pieces of 30 cm, $b$ of 45 cm, $c$ of 60 cm and $d$ of 90 cm, with $30a+45b+60c+90d\le150$; a pattern is "efficient" (worth including) only if its trim $150-(30a+45b+60c+90d)<30$ — otherwise one more 30 cm piece would always fit. Enumerating all combinations gives exactly 11 efficient patterns:
All 11 efficient cutting patterns
Pattern $p$
30 cm
45 cm
60 cm
90 cm
Trim (cm)
1
5
0
0
0
0
2
2
2
0
0
0
3
3
0
1
0
0
4
3
1
0
0
15
5
0
2
1
0
0
6
0
3
0
0
15
7
1
0
2
0
0
8
1
1
1
0
15
9
2
0
0
1
0
10
0
0
1
1
0
11
0
1
0
1
15
Define decision variables.$y_p\ge0$ integer = number of jumbo reels cut according to pattern $p=1,\dots,11$; $s_w\ge0$ integer = surplus (over-production) of standard width $w\in\{30,45,60,90\}$ beyond what is demanded.
Write the demand-satisfaction constraint for each width. Letting $a_{p,w}$ be the number of width-$w$ pieces produced by pattern $p$ (Step 1's table) and $D_w$ its demand, total production of width $w$ must exactly equal demand plus any surplus:
$$\sum_{p=1}^{11} a_{p,w}\,y_p = D_w + s_w,\qquad w\in\{30,45,60,90\}.$$
Assemble the complete IP model. Total waste is trim loss (per reel cut) plus surplus reels (each wasting its own full width):
$$\text{Minimize } W=\sum_{p=1}^{11}\text{trim}_p\,y_p+\sum_{w}w\,s_w$$
$$\text{s.t.}\quad \sum_p a_{p,30}y_p=200+s_{30},\ \ \sum_p a_{p,45}y_p=150+s_{45},\ \ \sum_p a_{p,60}y_p=100+s_{60},\ \ \sum_p a_{p,90}y_p=50+s_{90},$$
$$y_p\ge0\ \text{integer}\ (p=1,\dots,11),\qquad s_w\ge0\ \text{integer}\ (w=30,45,60,90).$$
The model is requested only in this formulated form and is not solved here.
Final results — Question 4 (model summary, not solved)
Item
Value
Number of efficient patterns
11
Decision variables
$y_1,\dots,y_{11}$ (reels per pattern), $s_{30},s_{45},s_{60},s_{90}$ (surplus)
