対称性を破る制約

組合せ最適化と呼ばれる数学の分野では、対称性を破る制約法を使用して、対称性を排除し、探索空間のサイズを縮小する制約を追加することで、多くの制約充足問題や最適化問題で対称性を利用することができます。

組み合わせ問題における対称性は探索空間のサイズを大きくするため、すでに探索した解と対称な新しい解を探索するのに時間がかかります。組み合わせ問題の解決時間は、対称性破壊制約と呼ばれる新しい制約を追加することで短縮できます。これにより、対称解の一部が探索空間から排除され、少なくとも 1 つの解の存在が維持されます。^{[1] [2]}

対称性は、現実の多くの組み合わせ問題でよく見られます。たとえば、車両ルーティング問題では、特定の車両が同一である場合があります。有効なルーティング プランの場合、そのような同一車両の順列ごとに、同じ目的関数値を持つ別の有効なルーティング プランが生成されます。