一次式の対称性破壊制約の自動生成

整数計画問題における対称性は、冗長な探索を引き起こし、しばしば対称性破壊制約を使用してできるだけ多くの同等解を取り除きます。我々は、必要とする入力が特定の一元式とグループの置換である任意のベース一元式に対して、代数学的な方法に一組の一元式不等式を作成し、「対称性破壊制約」を使用可能にすることができます。この計算は主要な符号計算ソフトウェアで簡単に実行できます。我々のアプローチをテストするためには数の例を説明する必要があります、それらの特性で大きな対称性が示されていた0-1_bin packingの事例は近づけられる予定です。我々は一時的に置換によって生成されたランダムな二乗破壊制約を作成し、これらの要素を基礎的な整数計画問題に追加します。それはその後Gurobiで解像できるようにします。私たちの簡単な対称性制約、特に少ない変数と置換を使用する場合は、労力時間は著しく減少することに結論づけられます。

arXiv:2602.08297v1 Announce Type: cross Abstract: Symmetry in integer programming causes redundant search and is often handled with symmetry breaking constraints that remove as many equivalent solutions as possible. We propose an algebraic method which allows to generate a random family of polynomial inequalities which can be used as symmetry breakers. The method requires as input an arbitrary base polynomial and a group of permutations which is specific to the integer program. The computations can be easily carried out in any major symbolic computation software. In order to test our approach, we describe a case study on near half-capacity 0-1 bin packing instances which exhibit substantial symmetries. We statically generate random quadratic breakers and add them to a baseline integer programming problem which we then solve with Gurobi. It turns out that simple symmetry breakers, especially combining few variables and permutations, most consistently reduce work time.