Redundant disequalities in the Latin Square problem

摘要

This paper studies the redundancy properties of the constraints used when formulating the well known Latin Square problem. This problem is often formulated using either (N − 1)*N 2 binary disequalities or 2*N all_different global constraints. Both formulations contain redundant constraints. A complete classification of all redundant sets of constraints, be they binary or global, is performed for any N.