Optimization problems occur everywhere.
With more automation of the industrial tasks, solving
a problem takes us to the next set of problems with additional criteria, where further
improvement is possible and our investigation goes on.
Industries like paper, steel, leather etc. exhibit one such problem where a large roll of the
material of a known width, needs to be cut into smaller rolls of widths speci ed by customer
orders, using automated machines. Supplier running this factory needs to meet these demands
with lower costs, reducing wastage of the material etc. This leads us to a problem known as
CSP (Cutting Stock Problem), and associated problems.
Typically, optimization problems are hard, and the author has aptly started with practical tips to
tackle them with an interesting quote “It is better to solve the right problem approximately than
to solve the wrong problem exactly”, and stressed the importance of modeling the
requirements.
Whereas formalization of the problem into special purpose languages allows the adoption of
general purpose solvers for the optimization problem, heuristics translate the problem directly
into a possible solution. Author suggests that communication with customers, and observing
how the problem is solved manually, helps in developing good heuristics.
Following along the lines of A. Einstein’s famous aphorism, author here says “intelligent model
is as simple as possible but not simpler”. Such a model needs to have an appropriate level of
abstraction, and has to be scalable. Author suggests that any auxiliary operations, which are
required but not related to optimization could be moved to pre/post processing steps.
Observing that data accuracy is typically around 5%, author suggests how constraints can be
softened using constraint violation variables, and shows how a convex function based on them
can be used to introduce progressive penalty for the constraint violation in the optimization
model. Thus, such a softening method helps in avoiding infeasibility of solutions.
When the optimization problem involves multiple criteria, folding them into a single model with
weights assigned to the di erent criteria, is one possible approach. Author prefers a
lexicographic approach of ranking the criteria and solving the problem for each criterion by
applying bounds on the optimal values of earlier ranked criteria. Though it may extend running
time, this method can generate multiple optimal solutions, which is very good in practice.
Decomposing problems into smaller problems is another method of handling complexity.
Generic methods, such as Benders decomposition is one approach. Second approach is to
nd decomposition speci c to the problem formulation itself. Based on author’s experience,
the model speci c decompositions do not seem to provide global optimum when compared to
the generic model decomposition.
After providing several such practical tips, second part of the book shows the modeling of real
world problems starting with CSP, considering regular winders that produce sets of rolls with
the same diameter but with varying widths. Ful lling customer demand with minimal number of
sets is the main statement of the problem, with minimization of cutting patterns and slitter
moves as additional criteria.
Bin-Packing, i.e., trying to nd smallest number of identical bins required to pack a given set of
items, can be used to solve CSP. Though it is a straightforward representation, author observes
its drawback, which is the proliferation of distinct cutting patterns.
Pattern Based Model is presented next. Here, all feasible patterns are generated as a
preprocessing step, and using a matrix with feasible patterns as columns, constraints on the
fi
fi
fi
fi
ff
fi
fi
pattern activities can be modeled. Author shows how in practice the LP (Linear Programming)
relaxation of the created IP (Integer Programming) model gets employed with successive
rounding. Since the number of patterns can be very large, two methods, viz., o ine column
generation and dynamic column generation are described in detail. Integrality gap, that refers
to the di erence of optimal values between IP formulation and LP relaxation, is higher in bin-
packing, compared to pattern-based methods, and this is shown using a theorem.
An interested reader can nd more engaging details of these formulations, a sequential
heuristic procedure for CSP, minimization of slitter moves, gluing of smaller stock rolls into
larger nished rolls in what is known as SSP (Skiving Stock Problem), CSP with two stage
cutting, warehouse storage space optimization and UCP (unit commitment problem) which
considers scheduling of electricity generation by utilities, in this book.
Overall, the presentation style is very enjoyable, and keeps focus on the practical aspects of
the problems as they occur in the industry. Though practitioners are the primary target
audience, students and academicians can also bene t from the book as a reference to the
current state of the art.
fi
ff
fi
fi
ffl