Efficient symmetry breaking formulations for the job grouping problem

A first remarkable conclusion is that the order of the input data has a significant effect on the LP relaxation bound and CPU times for the ARF and some of the traditional formulations with variable reduction. The CPU time of the formulation with lexicographic ordering constraints on the jobs is also substantially affected, but not its LP bound. A second interesting conclusion is that the ARF is able to solve the problems of a large standard set from the literature to optimality 40 times faster than the traditional formulation and 7 times faster than a specialized Branch-and-Bound algorithm from the literature. For a data set with large instances, the traditional formulation extended with limited lexicographic constraints seems to be the best formulation.