3-dim-packing-1.py

import numpy as np
from amplify import *
from amplify.client import FixstarsClient
import matplotlib.pyplot as plt
import matplotlib.animation as animation
import json
from mpl_toolkits.mplot3d import Axes3D

# 縦、横、奥行き
h, w, d = 8, 8, 8

packs = [
    [
        1, 1, 1
    ],
    [
        3, 1, 2
    ],
    [
        3, 3, 3
    ],
    [
        2, 5, 2
    ],
    [
        5, 5, 5
    ],
    [
        3, 3, 3
    ]
]

# パターンの全列挙
patterns = []
for i in range(len(packs)):
    pack = packs[i]
    pattern = np.array([])

    # 縦方向、横方向、奥方向にどれだけすすめるか
    pattern_h = h - pack[0] + 1
    pattern_w = w - pack[1] + 1
    pattern_d = d - pack[2] + 1

    flag = True
    for x in range(pattern_h):
        for y in range(pattern_w):
            for z in range(pattern_d):
                memo = np.zeros(
                    (
                        h, w, d
                    )
                )
                # 荷物を座標にマスク
                memo[x:x + pack[0], y:y + pack[1], z:z + pack[2]] = 1
                memo = memo.reshape((1, h, w, d))

                # 4次元配列（パターン + 座標）
                if flag:
                    pattern = memo
                    flag = False
                else:
                    pattern = np.append(pattern, memo, axis=0)

    print(pattern.shape)
    patterns.append(pattern)

# 荷物の数とパターン数(パターン数最大はh * w * d）
q = gen_symbols(BinaryPoly, len(packs), h * w * d)

f1 = 0
for x in range(h):
    # 進捗度合いを確認するだけ
    print(x)
    for y in range(w):
        for z in range(d):
            f = 0
            for i in range(len(packs)):
                for j in range(len(patterns[i])):
                    # 座標(x, y, z)に荷物が含まれるか
                    f += q[i][j] * patterns[i][j][x, y, z]
            # 座標(x, y, z)において荷物が重複がしないように　1以下という制約を追加
            f1 += constraint.less_equal(f, 1)

# 一つの荷物につき一つの配置パターンしかできない制約
f2 = sum(
    # 配置パターンのqubitの合計が1になればいい
    constraint.equal_to(sum(q[i][:len(patterns[i])]), 1)
    for i in range(len(packs))
)

f3 = sum(
    # 使わない配置パターンもあるので、それらはqubitの総和が0になるような制約を付け加える
    constraint.equal_to(sum(q[i][len(patterns[i]):]), 0)
    for i in range(len(packs))
    if len(patterns[i]) != h * w * d
)
# すべての制約を足す
f = f1 + f2 + f3

client = FixstarsClient()

# トークン外部流出が怖いのでローカルフォルダが読み込むようにさせた
with open("/home/yuma/.amplify/token.json") as f:
    client.token = json.load(f)["AMPLIFY_TOKEN"]
client.parameters.timeout = 1000  # タイムアウト1i秒

solver = Solver(client)

result = solver.solve(f)

# 1になったパターンが最適そうな解
res = [k for k, v in sorted(result[0].values.items()) if v == 1]

used = np.zeros((len(packs), h, w, d))

for i in range(len(packs)):
    used[i] = patterns[i][res[i] % (h * w * d)]

n_used = np.zeros_like(used)
for i in range(len(packs)):
    n_used[i] = used[i] * (i + 1)

for i in range(d):
    plt.imshow(n_used.sum(axis=0)[:, :, i])
    plt.show()

u_used = n_used.sum(axis=0)

from IPython.display import HTML
import matplotlib.animation as animation

fig = plt.figure(figsize=(5, 5))
ax = Axes3D(fig)

colors = [
    "blue",
    "green",
    "red",
    "yellow",
    "black",
    "brown",
    "lightgreen"

]


def init():
    for _n in range(1, len(packs) + 1):

        memo = np.where(u_used == _n)

        for i in range(len(memo[0])):
            # ax.plot(memo[0][i], memo[1][i], memo[2][i], "s", color=colors[_n], alpha=0.6, s=1)
            ax.scatter3D(memo[0][i], memo[1][i], memo[2][i], "s", color=colors[_n], alpha=0.6, s=300)

    return fig,


def animate(i):
    ax.view_init(elev=30., azim=3.6 * i)
    return fig,


# Animate
ani = animation.FuncAnimation(fig, animate, init_func=init,
                              frames=100, interval=100, blit=True)

writergif = animation.PillowWriter(fps=10)
ani.save('filename.gif', writer=writergif)

ありがとうございます！以下質問となります！

• amplify 初めてなのですが、これは裏側で D-wave 使っているんですかね？使っている qubit 数が 512*6 なので D-wave だとそろそろ危ういのかなと思ってました
• この制約条件だと色々な解が出てくると思いますが、最適な配置ってどういう観点で選んでいますか？
• 荷物がコンテナに入りきらないケースは result がどんな感じになりますか？「5個しか入れられない」のように出てきますかね？

読んでいただき、ありがとうございます！

1. Amplify AE(https://amplify.fixstars.com/ja/engine) というイジングマシンを使っています！

D-waveだとかなり無理がある気がします（全結合だと100ちょいみたいなことを聞いたことがあります　うろ覚えですが）

2. 解にはenergyという解の評価値が出てくるのですが、今回の制約を満たすものしかなく、解の優劣をつけられないので、最初に出てきた解を選んでいます。

優先順位をつけるとして、energyが異なる場合だったら、energyがもっとも低い解を選択しようと思っています。

3. 自分の手元だと解が出てこなくて、result[0]と指定した時点でエラーが出てきます　真面目に動かすときには例外処理をやっておこうと思います

3の補足です
たくさんある荷物の中から入るだけ詰め込むという問題にするならば、荷物自体入れるかいれないかというqubitを用意することで解決できます　そうしたら何かしらの解が出てくると思います