Question 4 of 10: Fixed-Charge Model — Bookshelf Length Minimization
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Exams — December 2013 — 98-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 200 marks across 10 questions and only 100 marks are required, so a candidate would normally answer a subset — all ten are solved below for completeness.
Reference texts: Hillier & Lieberman, Introduction to Operations Research (11th ed., McGraw-Hill) — linear/integer programming, network optimization, dynamic programming, decision analysis and queueing theory; Nahmias, Production and Operations Analysis — inventory models with planned backorders.
Question 4: Fixed-Charge Model — Bookshelf Length Minimization (20 marks)
Given. Two shelf "families": Small (fits 6&8 in. books, set-up $22) and Large (fits 6,8,10&12 in. books, set-up $25). Per-foot cost depends on the book size stored, not the family: 6 in.=$2.50/ft, 8 in.=$3.50/ft, 10 in.=$4.50/ft, 12 in.=$5.50/ft. Required shelf-length by book size: 6in→10ft, 8in→9ft, 10in→18ft, 12in→12ft.
Book size (in)
Length needed (ft)
Rate ($/ft)
Eligible families
6
10
2.50
Small, Large
8
9
3.50
Small, Large
10
18
4.50
Large only
12
12
5.50
Large only
Find. A mathematical model (mixed-integer, fixed-charge) whose optimal solution gives the length of each book size stored on each eligible shelf family, minimizing total cost. Do not solve.
Approach. Treat each shelf family as a facility with a one-time set-up cost triggered by a binary "open" variable, assign each book size's required footage across its eligible families with book-size-specific per-foot rates, and link the assignment variables to the open variables with a big-$M$ constraint.
Sets. Book sizes $b\in\{6,8,10,12\}$ with required footage $D_b$ and rate $r_b$ as tabulated above; shelf families $f\in\{S,L\}$ with set-up cost $K_S=22,K_L=25$; eligibility $E=\{(6,S),(8,S),(6,L),(8,L),(10,L),(12,L)\}$ (10 and 12 in. books cannot use the Small family).
Decision variables. $x_{bf}\ge0$ = feet of book size $b$ stored on family $f$, for $(b,f)\in E$. $z_f\in\{0,1\}$ = 1 if any shelving of family $f$ is built ($f=S,L$).
Demand-satisfaction constraints. Every book size's required footage must be placed somewhere it is eligible:
$$\sum_{f:(b,f)\in E}x_{bf}=D_b,\qquad b=6,8,10,12.$$
Fixed-charge linking (big-$M$). A family incurs its set-up cost the moment any footage is assigned to it; with $M_f=\sum_{b:(b,f)\in E}D_b$ (an upper bound on footage a family could ever carry):
$$\sum_{b:(b,f)\in E}x_{bf}\le M_f\,z_f,\qquad f=S,L.$$
Objective. Minimize total set-up plus variable cost:
$$\boxed{\min Z = 22\,z_S+25\,z_L+\sum_{(b,f)\in E} r_b\,x_{bf}}$$
subject to Steps 3–4, $x_{bf}\ge0$, $z_f\in\{0,1\}$.
Element
Formulation
Variables
$x_{bf}\ge0$ (feet of size $b$ on family $f$), $z_f\in\{0,1\}$
Objective
$\min\ 22z_S+25z_L+\sum r_b x_{bf}$
Demand
4 constraints, $\sum_f x_{bf}=D_b$
Fixed-charge link
2 constraints, $\sum_b x_{bf}\le M_f z_f$
Check
Assumes the $22 / $25 set-up is a single one-time charge per shelf family if it is used at all (not per book size, and not per linear foot) — the question's phrasing ("shelves to accommodate 6 or 8 inch books cost $22 to set-up") is read as describing the family, since it lists one set-up figure covering both book sizes in that family.
