fixstarsの組合せ最適化問題のイジング模型定式化のメモ

• 数の分割 問題：正の数の集合を２つに分けて、それぞれの和を等しくできるか。

• グラフ分割 問題：無向グラフをノード数が等しくなるように２つに分け、その間のリンク数が最小になるようにしたい。

• クリーク判定 問題：無向グラフに大きさKのクリークがあるか。クリークとは部分完全グラフのこと。完全グラフの全てのノードは互いにつながっている。

• 整数計画問題 問題：ここではバイナリ変数xについての問題を考える。Sx = b かつ cxが最大となるようなxを求める。

• 精密被覆問題 問題：集合Uとその部分集合による被覆Vを考えたときに、Vの要素を直行となるようにとってきてUを覆えるか

• 集合パッキング（これは最大独立集合問題に帰着する） 問題：集合Uとその部分集合による被覆Vを考えたときに、Vの要素を直行となるようにとってきたときの最大の要素数はいくつか

• 頂点被覆問題 問題：無向グラフのすべての辺に対し、端点のどちらかをふくむような集合を考えたとき、その最小の要素数はいくつか

• 充足可能性問題 問題：(x1またはx2)^{x3またはx4}=Trueのような式が与えられたときに、それをみたすような論理値xの組はあるか。

• 最小極大マッチング 問題：無向グラフの辺の部分集合で、端点を共有せず、かつ要素をたすと端点を共有してしまうような辺集合を考えたときに、その要素数の最小値はいくつか

• 整数重みナップザック問題 問題：