

Pythonによる図形詰込みアルゴリズム入門  
<http://www.orsj.or.jp/archive2/or63-12/or63_12_762.pdf>

を参考に下記プログラム（エラーコメントの後）を試しています。n = 11はうまく行きますが、n = 12はエラーになります。エラー解消できますか？

**エラーメッセージ**

[code]

    PulpSolverError                           Traceback (most recent call last)
    <ipython-input-32-fb1f7af9cbf3> in <module>
         40 solver = PULP_CBC_CMD(presolve=1,fracGap = 0,options = ['maxsol 10'],maxSeconds=100)
         41 
    ---> 42 status=m.solve(solver)
         43 
         44 # 時間計測終了
    
    ~\AppData\Local\Continuum\anaconda3\lib\site-packages\pulp\pulp.py in solve(self, solver, **kwargs)
       1669         #time it
       1670         self.solutionTime = -clock()
    -> 1671         status = solver.actualSolve(self, **kwargs)
       1672         self.solutionTime += clock()
       1673         self.restoreObjective(wasNone, dummyVar)
    
    ~\AppData\Local\Continuum\anaconda3\lib\site-packages\pulp\solvers.py in actualSolve(self, lp, **kwargs)
       1365     def actualSolve(self, lp, **kwargs):
       1366         """Solve a well formulated lp problem"""
    -> 1367         return self.solve_CBC(lp, **kwargs)
       1368 
       1369     def available(self):
    
    ~\AppData\Local\Continuum\anaconda3\lib\site-packages\pulp\solvers.py in solve_CBC(self, lp, use_mps)
       1432             pipe.close()
       1433         if not os.path.exists(tmpSol):
    -> 1434             raise PulpSolverError("Pulp: Error while executing "+self.path)
       1435         if use_mps:
       1436             lp.status, values, reducedCosts, shadowPrices, slacks = self.readsol_MPS(
    
    PulpSolverError: Pulp: Error while executing C:\Users\mes83341\AppData\Local\Continuum\anaconda3\lib\site-packages\pulp\solverdir\cbc\win\32\cbc.exe
    
[/code]

**ソースコード**

[code]

    from pulp import *
    import time
    n = 11
    w = [9.1, 4.2, 4.3, 7.4, 5.9,5.8,5.7,5.6,5.5,7.5,4.5,3.3,2.5,8.6,1.5]
    h = [4.1, 10.2, 9.3, 9.4, 10.5,5.6,5.7,5.8,5.9,9.1, 4.2, 4.3, 7.4, 5.9,5.8]
    W = 20
    UB = 50
    m = LpProblem( sense= LpMinimize)
    
    x=[LpVariable("x%d" %i, lowBound =0, upBound = W, cat = 'Integer') for i in range(n)] ###
    y=[LpVariable("y%d" %i, lowBound =0, upBound = UB, cat = 'Integer') for i in range(n)] ###
    
    u=[[LpVariable("u%d%d" %(i,j),cat= LpBinary ) for j in range(n)] for i in range(n)]
    v=[[LpVariable("v%d%d" %(i,j),cat= LpBinary ) for j in range(n)] for i in range(n)]
    H=LpVariable("H")
    m += H
    for i in range(n):
      for j in range(n):
        m += x[i]+w[i] <= x[j] + W*(1-u[i][j])
        m += y[i]+h[i] <= y[j] + UB*(1-v[i][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-w[i]
      m += y[i] <= H-h[i]
    
    # 時間計測開始
    time_start = time.perf_counter()   
    print(time_start)
    
    solver = PULP_CBC_CMD(presolve=1,fracGap = 0.5,options = ['maxsol 10'],maxSeconds=100)  
    
    status=m.solve(solver)
    
    # 時間計測終了
    time_stop = time.perf_counter()   
    ttt=time_stop-time_start
    print(ttt)
    
    print("Obj:",  value(m.objective))
    print ("Status", pulp.LpStatus[status])
    
    UB=value(m.objective)+1##############
    
    for i in range(n):
      print("Box", i, ":", value(x[i]), value(y[i]))
    
    import matplotlib.pyplot as plt
    
    fig = plt.figure ()
    
    ax = fig.add_subplot(111 ,aspect='equal')
    
    W1,H = W,UB
    ax.set_xlim ([0,W1])
    
    ax.set_ylim ([0,H])
    
    for i in range(n):
    
     a,b,c,d = value(x[i]),value(y[i]),w[i],h[i]
    
     rect = plt.Rectangle((a,b),c,d,fc="burlywood",ec="black")
    
     ax.add_patch(rect)
    
    for i in range(n):
     a,b,c,d = value(x[i]),value(y[i]),w[i],h[i]
     rect = plt.Rectangle((a,b),c,d,fc="burlywood",ec="black")
     ax.add_patch(rect)
     ax.text((2*a+c)/2, (2*b+d)/2, i, size = 8, color = "blue")
    
    fig.savefig ("picture .eps")
    
[/code]


CC BY-SA 4.0
2019-06-06T02:02:37.713
55563
2022-09-01T02:19:35.023
2022-09-01T02:19:35.023
3060
34603
question
python
PuLP を使ったコードの実行時にエラー: PulpSolverError


別ルートで回答をもらいました。

変数名が被るのが原因でした．  
u(1,11) と u(11,1) が両方 u111になります．n=１２で初めて起きます．  
例えば，コード下記のように変更すると動きました．  
（%d%dの間にアンダースコア（なんでも良い）を入れる）

もとのコード

[code]

    u=[[LpVariable("u%d%d" %(i,j),cat= LpBinary ) for j in range(n)] for i in range(n)]
    v=[[LpVariable("v%d%d" %(i,j),cat= LpBinary ) for j in range(n)] for i in range(n)]
    
[/code]

修正したコード

[code]

    u=[[LpVariable("u%d_%d" %(i,j),cat= LpBinary ) for j in range(n)] for i in range(n)]
    v=[[LpVariable("v%d_%d" %(i,j),cat= LpBinary ) for j in range(n)] for i in range(n)]
    
[/code]


CC BY-SA 4.0
2019-06-10T05:17:02.157
55672
2022-08-30T07:15:04.210
2022-08-30T07:15:04.210
3060
34603
55563
answer


変数名の被りの一覧は下記のコードで確認できます。

[code]

    from collections import Counter
    variables = [v.name for v in m.variables()]
    counter = Counter(variables)
    for k, v in counter.items():
        if v > 1:
            print('Dupulicate', k, v)
    
[/code]


CC BY-SA 4.0
2022-08-30T07:13:38.267
90833
2022-08-30T07:13:38.267
54208
55563
answer