Résolution du problème N Queen avec l'optimisation continue / combinée

Qu'est-ce que c'est

Voici quelques conseils pour résoudre avec l'optimisation de combinaison basée sur le problème N Queen.

Article original: Résolution du problème de N Queen avec l'optimisation des combinaisons

Conclusion

La modification de l'ordre des contraintes peut modifier le temps de calcul. Vérifions avec 4 modèles.

Résolvez le problème de N Queen

Tout d'abord, vérifiez que vous pouvez réellement le résoudre avec 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))

production

Wall time: 27 ms
..O.....
O.......
......O.
....O...
.......O
.O......
...O....
.....O..

À partir de la suivante, vérifiez le temps d'exécution avec quatre formulations d'une taille de 100 x 100.

Motif 1 (4,0 secondes)

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)

Motif 2 (4,7 secondes)

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)

Motif 3 (2,2 secondes)

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)

Motif 4 (6,4 secondes)

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)

Que devrais-je faire

Les quatre modèles ont la même formulation, seul l'ordre des contraintes est différent. Cependant, le temps de calcul a changé près de trois fois. De plus, la tendance est différente selon n.

Dans un tel cas, il peut être préférable de préparer plusieurs modèles et de les exécuter en même temps comme cette fois, et de tout arrêter si même une seule réponse est trouvée.

Supplément

Le calcul a été effectué sur le ThinkPad X280. L'installation de la bibliothèque est pip install ou toolpy.

Le problème 100 x 100 N Queen a 10 000 variables 0-1. La combinaison est de 10 $ ^ {3010} $. C'est un nombre énorme de combinaisons, mais c'est incroyable que vous puissiez le résoudre en un peu plus de 2 secondes avec un logiciel gratuit (PuLP).