Python :長方形の円の詰め込み：正方形を埋め込むのではなく、円周の重なりを最小にして詰め込む

Question

過去にご相談したものは、円が入る正方形を詰め込んでいることがわかって、円周が重ならないようにするようにすることを考え、プログラムしてみましたが、Python初心者、最適化初心者なので、
c = a * a + b * b
TypeError: Non-constant expressions cannot be multiplied
がでてきます。

コード
from pulp import *
import matplotlib.pyplot as plt

W = 20
UB = 30
a = []
b = []
c = []
sum_radius = []

n = 6
r = [3, 2, 1, 3, 3, 2]

H = LpVariable("H")
x = [LpVariable(f'x{i}', lowBound=0) for i in range(n)]
y = [LpVariable(f'y{i}', lowBound=0) for i in range(n)]
u = [[LpVariable(f'u{i}_{j}', cat=LpBinary) for j in range(n)] for i in range(n)]
v = [[LpVariable(f'v{i}_{j}', cat=LpBinary) for j in range(n)] for i in range(n)]

m = LpProblem(sense=LpMinimize)
m += H

for i in range(n):
    for j in range(n):
        m += {{(x[j] - x[i]) * (x[j] - x[i])} + {(y[j] - y[i]) * (y[j] - y[i])}} >= {(r[i] + r[j]) * (r[i] + r[j])}
        if i < j:
            m += u[i][j] + u[j][i] + v[i][j] + v[j][i] >= 1

for i in range(n):
    m += x[i] <= W-r[i]
    m += y[i] <= H-r[i]
    m += r[i] <= x[i]
    m += r[i] <= y[i]
    

m.solve()

### 描画 ###

fig = plt.figure()
ax = fig.add_subplot(111,aspect='equal')
ax.set_xlim([0,W])
ax.set_ylim([0,UB])

for i in range(n):
    print(f'(x, y) = ({x[i].value()}, {y[i].value()})   r = {r[i]}')
    circ = plt.Circle((x[i].value() ,y[i].value()), r[i])
    ax.add_patch(circ)
    
#グラフのタイトル
plt.title("Sectional View")

#x軸ラベル
plt.xlabel("Hole diameter")

#y軸ラベル
plt.ylabel("depth")

fig.savefig("test1.png")
plt.show()

Comments

[t_obara]

コードが見にくいので、見やすくしてください。

[KAZENOMACHI]

まだ使い方が悪く申し訳ございません。円周を囲む正方形が重ならないようになっていたのを円の中心点の距離がそれぞれの円の半径も大きく詰め込むことになるのかなと、、、、、。

Answer 1

エラー内容を翻訳すると、「定数でない式は掛け算ができない」です。
(x[j] - x[i]) * (x[j] - x[i])の式を展開すると、変数同士の掛け算となり、非線形な制約条件となっています。

pulpライブラリは、デフォルトでは線形計画問題に対応したソルバーしか入っておらず、非線形計画問題には対応していません。

<補足>
・エラー内容は一部を切り取られているように見えるので、全て貼り付けてください。
・「中心間の距離が、半径の和より大きい」という制約条件自体は合っていると思います。すると、u、vの制約式は必要なくなりますね。

Comments

[KAZENOMACHI]

非線形に対応したソルバーはあるのでしょうか？cvxpyも線形ですか？インストールのところでトラブっているのですが。

[KAZENOMACHI]

File "C:\Users\xxxxx\Desktop\ダクト配列NEW円周.py", line 27, in <module>
m += {{(x[j] - x[i]) * (x[j] - x[i])} + {(y[j] - y[i]) * (y[j] - y[i])}} >= {(r[i] + r[j]) * (r[i] + r[j])}

File "C:\Users\xxxxx\Anaconda3\lib\site-packages\pulp\pulp.py", line 826, in __mul__
raise TypeError("Non-constant expressions cannot be multiplied")

TypeError: Non-constant expressions cannot be multiplied

[nanoseeing]

・エラー内容の貼付ありがとうございます。質問をする際は、全文貼り付けるのがマナーだと思いますので。

・cvxpy自体はソルバーではありません。

・非線形計画問題を解きたいのでしたら、こちらの記事が参考になるかと思います。https://ajhjhaf.hatenablog.com/entry/2018/02/12/235015