制約充足双対問題

双対問題とは、制約充足問題を、元の問題の各制約を変数として表現し直したものである。双対問題は二項制約のみを含むため、そのような問題に特化したアルゴリズムで解くことができる。制約充足問題の結合グラフと結合木は、その双対問題、あるいは双対問題から冗長な制約をいくつか取り除いた問題を表す グラフである。

二重の問題

制約充足問題の双対問題には、元の問題の各制約に対応する変数が含まれます。その定義域と制約は、元の問題とある種の同値性を保証するように構築されています。特に、双対問題の変数の定義域には、対応する元の制約を満たす各組ごとに1つの要素が含まれます。このように、双対変数は、対応する元の制約が対応する組によって満たされる場合にのみ値を取ることができます。

双対問題の制約により、2つの双対変数は、互いに互換性のない2つの組に対応する値を取ることが禁じられています。これらの制約がない場合、一方の双対変数は組に対応する値を取る一方で、もう一方の双対変数は に対応する値を取り、 には異なる値が割り当てられる可能性があります。 ${\displaystyle x=1,y=2}$ ${\displaystyle y=3,z=1}$ ${\displaystyle y}$

より一般的には、双対問題の制約は、2つの制約によって共有されるすべての変数に同じ値を強制します。2つの双対変数が、いくつかの変数を共有する制約に対応する場合、双対問題はそれらの間の制約を含み、共有されるすべての変数の等価性を強制します。

	双対変数は元の問題の制約です。
	各デュアル変数のドメインは、対応する元の制約の組の集合です。
	デュアル制約は、デュアル変数 (元の制約) が元の変数と等しい値を含む値 (元のタプル) を持つように強制します。 この例では、元の制約と変数 が共有されています。双対問題では、変数と は、で一致するため、値 と を持つことが許されます。 ${\displaystyle C_{1}}$ ${\displaystyle C_{2}}$ ${\displaystyle y}$ ${\displaystyle C_{1}}$ ${\displaystyle C_{2}}$ ${\displaystyle (1,2)}$ ${\displaystyle (2,1)}$ ${\displaystyle y=2}$

双対問題では、すべての制約は2値です。これらの制約はすべて、2つの値（タプル）が1つ以上の元の変数に一致することを強制します。

双対グラフは、双対問題において変数がどのように制約されているかを表すものです。より正確には、双対グラフには各双対変数に対応するノードと、それらの間のすべての制約に対応するエッジが含まれます。さらに、2つの変数間のエッジには、これらの2つの双対変数間で等しく強制されている元の変数がラベル付けされます。

デュアル グラフは、元の問題から直接構築できます。各制約の頂点と、変数を共有する 2 つの制約間のエッジが含まれます。このようなエッジには、これらの共有変数によってラベルが付けられます。

双対グラフ。2つの制約間の辺は、それらの共有変数の等価性を強制する双対制約に対応します。例えば、と の間のラベルが付いた辺は、双対問題にとの間の制約が含まれており、この制約により と で一致する値（タプル）が強制されることを示します。 ${\displaystyle x,y}$ ${\displaystyle C_{1}}$ ${\displaystyle C_{2}}$ ${\displaystyle C_{1}}$ ${\displaystyle C_{2}}$ ${\displaystyle x}$ ${\displaystyle y}$

グラフを結合し、ツリーを結合する

双対グラフでは、一部の制約が不要な場合があります。実際、双対制約は元の変数の等価性を強制しますが、等価性の推移性により、一部の制約は冗長になる可能性があります。例えば、 と が、ラベルに を含むエッジで接続され、 と も接続されている場合、3つの双対変数すべてにおいて の等価性が保証されます。結果として、との間の双対制約での等価性が強制されるものは不要であり、もし存在する場合は削除できます。 ${\displaystyle C_{2}}$ ${\displaystyle C_{1}}$ ${\displaystyle y}$ ${\displaystyle C_{1}}$ ${\displaystyle C_{3}}$ ${\displaystyle y}$ ${\displaystyle C_{2}}$ ${\displaystyle C_{3}}$ ${\displaystyle y}$

の等式は他の二重制約によって強制されるため、との間の等式は削除できます。 ${\displaystyle y}$ ${\displaystyle C_{2}}$ ${\displaystyle C_{3}}$

双対グラフから冗長な辺を削除して得られるグラフは、結合グラフと呼ばれます。それが木の場合は、結合木と呼ばれます。削除された辺はすべて冗長であるため、結合グラフから双対問題を解くことができます。また、結合グラフが木であれば、非巡回制約充足問題に適したアルゴリズムを用いて、問題を効率的に解くことができます。

結合ツリーを検索するには、次のプロパティを使用します。 デュアル グラフに結合ツリーがある場合、対応する制約が等しくなるように強制する変数の数でエッジに重みが付けられると、グラフの最大重みスパニング ツリーはすべて結合ツリーになります。 結合ツリーを検索するアルゴリズムは、次のように進行します。最初のステップでは、エッジに重みが割り当てられます。 2 つのノードが変数を共有する制約を表す場合、それらを結合するエッジに重みが割り当てられます。 2 番目のステップでは、最大重みスパニング ツリーが検索されます。 ツリーが見つかったら、必要な変数の等価性を適用するかどうかがチェックされます。適用される場合、このスパニング ツリーは結合ツリーです。 ${\displaystyle n}$ ${\displaystyle n}$

制約充足問題に結合木が存在するかどうかを判断する別の方法として、問題の双対グラフではなく主グラフを用いる方法があります。制約充足問題の主グラフとは、ノードが問題の変数であり、エッジが同じ制約における2つの変数の存在を表すグラフです。以下の条件を満たす場合、問題の結合木は存在します。

1. 主グラフは弦グラフである。
2. 主グラフのあらゆる最大クリークの変数は制約のスコープであり、逆もまた同様です。この特性は共形性と呼ばれます。

同様に、変数の最大カーディナリティ順序付けを用いることで、弦性をチェックすることができます。この順序付けは、上記の2つの条件が満たされている場合、問題の結合木を見つけるためにも使用できます。順序付けに従って制約を最も高い変数で順序付けすると、結合木を生成するアルゴリズムは最後の制約から最初の制約へと進みます。各ステップにおいて、順序付けにおいてその前にある制約の中で、その制約と変数を共有する数が最大となる制約が接続されます。

拡張機能

すべての制約充足問題が結合木を持つわけではありません。しかし、結合木を獲得するように問題を修正することは可能です。結合木クラスタリングは、結合木を獲得するように問題を修正する具体的な手法です。これは制約をマージすることによって行われ、通常は問題のサイズが大きくなりますが、結果として得られる問題は、結合木を持つすべての問題と同様に簡単に解くことができます。

分解法は、変数をグループ化することで結合木クラスタリングを一般化し、結果として得られる問題が結合木を持つようにします。分解法は木と問題を直接関連付けます。この木のノードは、元の問題に関連付けられた変数および／または制約です。この木に基づいて制約をマージすることで、結合木を持つ問題を作成できます。この結合木は分解木から簡単に導出できます。あるいは、分解木から直接、2項非巡回問題を構築することもできます。

参考文献

• デヒター、リナ (2003). 制約処理. モーガン・カウフマン. ISBN 978-1-55860-890-0
• Downey, Rod; M. Fellows (1997). パラメータ化された複雑性. Springer. ISBN 978-0-387-94883-6
• ゲオルグ・ゴットロブ、ニコラ・レオーネ、フランチェスコ・スカルチェッロ (2001). 「ハイパーツリー分解：概観」MFCS 2001 . pp.  37– 57.^{[リンク切れ]}

参照

• 隠された変革