Knowledge based approach to the Cutting Stock Problem

Cutting Stock Problem (CSP) is an instance of a particularly difficult combinatorial optimization problem where a few geometrical patterns must be selected and arranged so as to minimize the total cost of the underlying process. A survey of the literature on CSP reveals that the scope of this famous problem applications has expanded in the recent thirty-five years from pallet loading, packing, and industrial production planning to computer operations to telecommunications. Three major trends of engineering activities are identified and discussed in detail: integration of applications, shift from optimization to control, and construction of new related problems. On the other hand, the notorious difficulties of the popular Linear Programming approach to solving CSP (e.g., handling non-linear constraints and integer solutions) have been only partially remedied by a host of heuristic search schemes. The paper proposes a learning expert system CUT addressing the above difficulties. CUT achieves efficient cutting pattern knowledge acquisition and inference by combining Simulated Annealing and Case Based Reasoning. CUT is implemented in PROLOG. Logic Programming implementation offers the advantages of natural symbolic data processing, declarative programming, and automatic search.