Efficient symmetry-breaking formulations for grouping customer orders in a printing shop

This paper deals with a real-world printing shop, where the offset-printing technology is used to imprint customer-specific designs on napkin pouches. The optimization problem consists of allocating the designs to the slots of some printing plates such that the given demand for each design is fulfilled at minimum total overproduction and setup costs; thereby, various technological and organizational constraints arising from the production equipment are to be met. We present two alternative mixed-binary linear programming formulations; a structural difference between the two formulations is that they eliminate symmetric solutions explicitly or implicitly, respectively, from the search space. The computational results for a set of problem instances devised from real-world data indicate that both formulations are able to find optimal solutions for small instances in short CPU times. For larger instances, the implicit formulation performs significantly better in terms of average integrality gap and number of instances solved to feasibility.