<jupyter_start><jupyter_text>循環セールスマン問題　オリジナル対応版  問題データのロード<jupyter_code># ライブラリのロード

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from IPython.display import display
# データのロード
# 48件は巡回セールスマン問題のオリジナルデータです

url = 'https://raw.githubusercontent.com/makaishi2/sample-data/master/data/att48.csv'
df = pd.read_csv(url)
display(df.head())
print('size = ', df.values.shape)
# 対象項目数
# N = 25 は10秒程度で解決
# N = 25

# N=30 は4分弱かかる
N = 30

# これ以上の値での結果は未確認
# 絞り込んだデータを使って、初期化と散布図表示

data = df[:N]
data_np = np.array(data)
plt.figure(figsize=(6,6))
plt.scatter(data_np[:,0], data_np[:,1])
plt.grid()
plt.show()
# 距離関数の定義
# 便宜上ユークリッド距離にしています

def distance(i, j):
    return np.sqrt(np.sum((data_np[i,:] - data_np[j,:])** 2))
# コスト配列の定義
c = np.zeros((N,N))

for i in range(N):
    for j in range(N):
        c[i, j] = distance(i, j)<jupyter_output><empty_output><jupyter_text>CPLEXによる問題定義<jupyter_code># CPLEX環境の確認

from docplex.mp.environment import Environment
env = Environment()
env.print_information()<jupyter_output>* system is: Linux 64bit
* Python version 3.6.8, located at: /opt/conda/envs/Python36/bin/python
* docplex is present, version is (2, 10, 150)
* CPLEX library is present, version is 12.9.0.1, located at: /opt/conda/envs/Python36/lib/python3.6/site-packages
* pandas is present, version is 0.24.1<jupyter_text>モデルの宣言<jupyter_code># モデルの宣言

from docplex.mp.model import Model
mdl = Model(name="TSP")
# モデルのパラメータ定義

# スレッド数: 2
mdl.parameters.threads = 2
# 最大時間数: 600秒
mdl.parameters.timelimit = 600<jupyter_output><empty_output><jupyter_text>決定変数の宣言<jupyter_code># 決定変数の宣言

# x : 移動matrix
# i番目のノードからj番目のノードに移動する時 x_ij = 1
# それ以外の場合 x_ij = 0
x = mdl.integer_var_matrix(N, N)

# u: 順序変数
# 0番目のノードの次に移動するノードがiの場合
# u[i] = 1
# その次に移動するノードがjの場合
# u[j] = 2
# .. のように定義する
u = mdl.integer_var_list(N)<jupyter_output><empty_output><jupyter_text>制約の定義<jupyter_code># u(順序変数)の制約
# 最初のノードは0番目 : u[0] = 0
# それ以外の順序変数は1以上 N-1以下

mdl.add_constraint(u[0] == 0)
for i in range(1, N):
    mdl.add_constraint(u[i] >= 1)
    mdl.add_constraint(u[i] <= N-1)
# x(移動matrix)の制約
# 自分から自分への移動はないので、u_ii = 0
# それ以外の場合は u_ij は0か1

for i in range(N):
    for j in range(N):
        if i == j:
            mdl.add_constraint(x[i, j] == 0)
        else:
            mdl.add_constraint(x[i, j] >= 0)
            mdl.add_constraint(x[i, j] <= 1)
# x(移動matirx)に関する縦の制約

for i in range(N):
    mdl.add_constraint(mdl.sum(x[i, j] for j in range(N)) == 1)
# x(移動matirx)に関する横の制約

for j in range(N):
    mdl.add_constraint(mdl.sum(x[i, j] for i in range(N)) == 1)
# 部分路制約
# ループが全体で1つであるための条件
# 参考リンク http://satemochi.blog.fc2.com/blog-entry-24.html

for i in range(1, N):
    for j in range(1, N):
        mdl.add_constraint(u[i] - u[j] + N * x[i,j] <= N -1)<jupyter_output><empty_output><jupyter_text>最適化関数の定義<jupyter_code># 総移動コスト

total_cost = mdl.sum(c[i, j] * x[i, j] for i in range(N) for j in range(N))
# 最適化の定義

mdl.minimize(total_cost)<jupyter_output><empty_output><jupyter_text>制約設定の確認<jupyter_code># 制約設定の確認

mdl.print_information()<jupyter_output>Model: TSP
 - number of variables: 930
   - binary=0, integer=930, continuous=0
 - number of constraints: 2730
   - linear=2730
 - parameters: defaults
 - problem type is: MILP<jupyter_text>問題を解く<jupyter_code># 問題を解く
# ログ出力をONにして、詳細情報も表示します

mdl.solve(log_output = True)
mdl.report()
# 詳細情報の表示

print(mdl.get_solve_details())
# 結果の取得

indexes = [u[i].solution_value for i in range(N)]
matrix = [[x[i, j].solution_value for j in range(N)] for i in range(N)]
ar = np.array(matrix)
# オリジナル散布図の再表示

plt.figure(figsize=(6,6))
plt.scatter(data_np[:,0], data_np[:,1])
plt.grid()
plt.show()
# 結果の散布図上での表示

data_np = np.array(data)
plt.figure(figsize=(6,6))
plt.scatter(data_np[:,0], data_np[:,1])
for i in range(N):
    for j in range(N):
        if ar[i, j] == 1:
            plt.plot(data_np[[i,j],0], data_np[[i,j],1], c='b')
plt.grid()            
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.15531265887137774, 'fraction_numerical': 0.028469750889679714, 'mean_word_length': 4.503496503496503, 'pattern_counts': {'":': 0, '<': 34, '<?xml version=': 0, '>': 33, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '469437', 'license': 'Apache-2.0', 'n_tokens_mistral': 2148, 'n_tokens_neox': 2107, 'n_words': 336, 'path': 'cplex/TSP.ipynb', 'repo_name': 'makaishi2/sample-notebooks', 'size': '3934'}