これなに
N Queen問題を題材にした、組合せ最適化で求解するときのTipsです。
結論
制約の順番を変えると、計算時間が変わることがある。
4パターンで検証してみましょう。
N Queen問題を解く
まずは、8x8で実際に解けるのを確認します。
from ortoolpy import pd, addbinvars, model_min, lpSum, addvals
n = 8
df = pd.DataFrame([(i, j) for i in range(n) for j in range(n)],
columns=['X', 'Y'])
addbinvars(df);
m = model_min()
for i in range(n):
m += lpSum(df[df.X == i].Var) == 1
m += lpSum(df[df.Y == i].Var) == 1
for i in range(2 * n - 3):
m += lpSum(df.query(f'X + Y == {i + 1}').Var) <= 1
m += lpSum(df.query(f'X - Y == {i - n + 2}').Var) <= 1
%time m.solve()
addvals(df)
cc = df.Val.astype(int).map('.O'.__getitem__).values.reshape(n, n)
print('\n'.join(''.join(c) for c in cc))
出力
Wall time: 27 ms
..O.....
O.......
......O.
....O...
.......O
.O......
...O....
.....O..
次から 100 x 100 のサイズで4通りの定式化で実行時間を確認します。
パターン1（4.0秒）
m = model_min()
for i in range(n):
m += lpSum(df[df.X == i].Var) == 1
m += lpSum(df[df.Y == i].Var) == 1
for i in range(2 * n - 3):
m += lpSum(df.query(f'X + Y == {i + 1}').Var) <= 1
m += lpSum(df.query(f'X - Y == {i - n + 2}').Var) <= 1
%timeit -r 3 -n 3 m.solve()
3.97 s ± 702 ms per loop (mean ± std. dev. of 3 runs, 3 loops each)
パターン2（4.7秒）
m = model_min()
for i in range(n):
m += lpSum(df[df.X == i].Var) == 1
m += lpSum(df[df.Y == i].Var) == 1
for i in range(2 * n - 3):
m += lpSum(df.query(f'X + Y == {i + 1}').Var) <= 1
for i in range(2 * n - 3):
m += lpSum(df.query(f'X - Y == {i - n + 2}').Var) <= 1
%timeit -r 3 -n 3 m.solve()
4.7 s ± 423 ms per loop (mean ± std. dev. of 3 runs, 3 loops each)
パターン3（2.2秒）
m = model_min()
for i in range(n):
m += lpSum(df[df.X == i].Var) == 1
for i in range(n):
m += lpSum(df[df.Y == i].Var) == 1
for i in range(2 * n - 3):
m += lpSum(df.query(f'X + Y == {i + 1}').Var) <= 1
m += lpSum(df.query(f'X - Y == {i - n + 2}').Var) <= 1
%timeit -r 3 -n 3 m.solve()
2.24 s ± 36.5 ms per loop (mean ± std. dev. of 3 runs, 3 loops each)
パターン4（6.4秒）
m = model_min()
for i in range(n):
m += lpSum(df[df.X == i].Var) == 1
for i in range(n):
m += lpSum(df[df.Y == i].Var) == 1
for i in range(2 * n - 3):
m += lpSum(df.query(f'X + Y == {i + 1}').Var) <= 1
for i in range(2 * n - 3):
m += lpSum(df.query(f'X - Y == {i - n + 2}').Var) <= 1
%timeit -r 3 -n 3 m.solve()
6.44 s ± 129 ms per loop (mean ± std. dev. of 3 runs, 3 loops each)
どうすればよいのか
4パターンは同じ定式化で、制約条件の順番が違うだけです。
しかし、3倍近く計算時間が変わってます。
しかも、nによって傾向が違います。
こういった場合は、今回のように複数パターンを用意して同時に実行し、答えが1つでも見つかったらすべて止める方法が良いかもしれません。
補足
計算は ThinkPad X280 でしました。
ライブラリーのインストールは、pip install ortoolpyです。
100 x 100 のN Queen問題は、0-1変数が1万個あります。
組み合わせは$10^{3010}$です。途方もない組み合わせ数ですが、無料のソフト（PuLP）で2秒ちょっとで解けるのがすごいですね。