Bag rationalisation for a food manufacturer
研究了一家食品制造商如何通过整数规划和图着色方法，在降低成本和减少客户颜色冲突之间权衡，最终推荐8种颜色方案并被采纳。
A food manufacturer has decided to rationalise the types of bags used to pack their products with a view to achieving economies of scale and improved efficiency. Under the new regime, the name and characteristics of the product are to be printed on the bag during packaging, with the bag colour as a secondary distinctive feature. There are several ways of describing the director's conflicting objectives of minimising both cost and customer colour conflicts. We model the problem in two ways: as a Zero-One Integer Programme, and as a variant of a classical Graph Colouring Problem. Problem-specific observations, and data pre-processing, enable us to decompose the originally intractable problem, and to solve it using commercial integer programming software. Our solution compares favourably with that from a heuristic for graph colouring and our recommended allocation of eight colours was accepted for implementation.