UbuntuでPythonからTSPを解くためにpyconcordeを実装したい

Question

実現したいこと

Python から TSP を解くために pyconcorde をインストールし、example内の’us_state_capitals.py’を実行したい

発生している問題・分からないこと

pyconcorde のインストール方法（https://github.com/jvkersch/pyconcorde）に従い、Concordeをダウンロードしましたがモジュールがないと言われました。

エラーメッセージ

Traceback (most recent call last):
  File "us_state_capitals.py", line 7, in <module>
    from concorde.tsp import TSPSolver
ModuleNotFoundError: No module named 'concorde.tsp'

該当のソースコード

# -*- coding: utf-8 -*-
from __future__ import division, print_function

import numpy as np
import pandas as pd

from concorde.tsp import TSPSolver

# Source for state capital data:
# http://www.jetpunk.com/data/countries/united-states/state-capitals-list

state_capitals = pd.read_table(
    "us_state_capitals.tsv", header=None, names=["state", "city", "lat", "lon"]
)

# Keep only the lower 48
state_capitals = state_capitals[
    (state_capitals.state != "Alaska") & (state_capitals.state != "Hawaii")
]
state_capitals.reset_index(inplace=True, drop=True)

# Instantiate solver
solver = TSPSolver.from_data(state_capitals.lat, state_capitals.lon, norm="GEO")

# Find tour
tour_data = solver.solve()
assert tour_data.success

solution = state_capitals.iloc[tour_data.tour]
print("Optimal tour:")
print(
    " -> ".join("{r.city}, {r.state}".format(r=row) for _, row in solution.iterrows())
)

# Make a plot
import matplotlib.patches as mpatches
import matplotlib.pyplot as plt
import shapely.geometry as sgeom

import cartopy.crs as ccrs
import cartopy.io.shapereader as shpreader

ax = plt.axes([0, 0, 1, 1], projection=ccrs.LambertConformal())
ax.set_extent([-125, -66.5, 20, 50], ccrs.Geodetic())

shapename = "admin_1_states_provinces_lakes_shp"
states_shp = shpreader.natural_earth(
    resolution="110m", category="cultural", name=shapename
)

ax.background_patch.set_visible(False)
ax.outline_patch.set_visible(False)

tour = sgeom.LineString(list(zip(solution.lon, solution.lat)))
capitals = sgeom.MultiPoint(list(zip(solution.lon, solution.lat)))

for state in shpreader.Reader(states_shp).geometries():
    facecolor = [0.9375, 0.9375, 0.859375]
    edgecolor = "black"

    ax.add_geometries(
        [state], ccrs.PlateCarree(), facecolor=facecolor, edgecolor=edgecolor
    )

ax.add_geometries([tour], ccrs.PlateCarree(), facecolor="none", edgecolor="red")
for lat, lon in zip(solution.lat, solution.lon):
    ax.plot(lon, lat, "ro", transform=ccrs.PlateCarree())

plt.savefig("us_state_capitals.png", bbox_inches="tight")
plt.show()

試したこと・調べたこと

• teratailやGoogle等で検索した
• ソースコードを自分なりに変更した
• 知人に聞いた
• その他

上記の詳細・結果

teratailで「pyconcorde」と検索して見つけた解決方法を試しましたが同様のエラーが発生してしまいました。

補足

環境
OS: Ubuntu 20.04（WSL2）
Python: 3.8（venv使用）
concorde、pyconcorde は GitHub からクローンした最新版

Comments

[fiveHundred]

実際に実行したコマンドを記載してください。
（この際「～というサイトに従い」はNGです。そのサイト通りでないケースが多いので）
エラーから察するに正しくインストールできていません。

[TakaiY]

まずは、上の方の質問と同様です。 指定のサイトにはインストール方法が複数書かれていますし、質問にはダウンロードしたとなっていてインストールしたとは書いていないのも気になります。

concordをインストールした環境で pip list コマンドを実行したときに表示されますか？

example内の’us_state_capitals.py’ はどのように実行しましたか。

上記に依存しますが、その実行した環境で、pip listやpython -m pip list や python3 -m pip listを実行すると結果はどのようになりますか。
プログラム

[warabinu]

ご回答ありがとうございます。
ご指摘いただいた点を踏まえて、以下に実行したコマンドを記載します。

まずリポジトリをクローンしました
cd ~
git clone https://github.com/jvkersch/pyconcorde.git
cd pyconcorde

次にConcordeのダウンロードをしました
cd ~
wget http://www.math.uwaterloo.ca/tsp/concorde/downloads/codes/src/co031219.tgz
tar -xvzf co031219.tgz
cd concorde

次に、Concordeのビルドを行いました
./configure
make

次に、pyconcordeのインストールを行いました
cd ~/pyconcorde
pip install -e .

最後に、目的のプログラムの実行をしました
cd ~/pyconcorde/examples
python us_state_capitals.py

[fiveHundred]

「venv使用」となっていますがvenvのコマンドがありません。
これだとvenvではなく、素でインストールされているpythonが使われていると思いますが、そのあたりはどうですか？

また、TakaiYさんが言っている「pip list」「python -m pip list」「python3 -m pip list」の結果はどうなっていますか？

あと、この問題と関係ないと思いますが、

> This will download and build Concorde (and its dependency QSOpt) and then build PyConcorde. While this may take a few minutes, downloading Concorde only happens the first time the install script is run (unless you remove the data directory).
> If you already have Concorde and/or QSOpt installed (or an equivalent linear solver), you can use those instead. Simply set the environment variable CONCORDE_DIR (or QSOPT_DIR) to point to the folder where you installed Concorde (or QSOpt).

上記の通り、concordeはCONCORDE_DIRで指定する必要がありますし、ない場合は自動でインストールされるので、concordeのビルドは意味を為してないと思います。

[warabinu]

venvのコードが抜けておりました。一番最初に
source ~/venv/bin/activate
によって仮想環境をアクティベートしています。

「pip list」「python -m pip list」「python3 -m pip list」について以下に記載いたします。

pip list
(venv) warabinu@DESKTOP-CD434N2:~$ pip list
Package Version Location
------------------------ ----------- -------------------------
click 8.1.8
concorde 0.1.2
cython 3.1.2
Deprecated 1.2.18
filelock 3.16.1
fsspec 2025.3.0
importlib-metadata 8.5.0
jinja2 3.1.6
Markdown 3.7
MarkupSafe 2.1.5
mpmath 1.3.0
networkx 2.8.8
numpy 1.24.4
nvidia-cublas-cu12 12.1.3.1
nvidia-cuda-cupti-cu12 12.1.105
nvidia-cuda-nvrtc-cu12 12.1.105
nvidia-cuda-runtime-cu12 12.1.105
nvidia-cudnn-cu12 9.1.0.70
nvidia-cufft-cu12 11.0.2.54
nvidia-curand-cu12 10.3.2.106
nvidia-cusolver-cu12 11.4.5.107
nvidia-cusparse-cu12 12.1.0.106
nvidia-nccl-cu12 2.20.5
nvidia-nvjitlink-cu12 12.9.86
nvidia-nvtx-cu12 12.1.105
pandas 2.0.3
pillow 10.4.0
pip 20.0.2
pkg-resources 0.0.0
pyconcorde 0.1.0 /home/warabinu/pyconcorde
PyRSS2Gen 1.1
python-dateutil 2.9.0.post0
pytz 2025.2
setuptools 44.0.0
six 1.17.0
sympy 1.13.3
tabulate 0.8.10
torch 2.4.1
torchaudio 2.4.1
torchvision 0.19.1
tqdm 4.67.1
triton 3.0.0
tsplib95 0.7.1
typing-extensions 4.13.2
tzdata 2025.2
wheel 0.45.1
wrapt 1.17.2
zipp 3.20.2

「python -m pip list」

(venv) warabinu@DESKTOP-CD434N2:~$ python -m pip list
Package Version Location
------------------------ ----------- -------------------------
click 8.1.8
concorde 0.1.2
cython 3.1.2
Deprecated 1.2.18
filelock 3.16.1
fsspec 2025.3.0
importlib-metadata 8.5.0
jinja2 3.1.6
Markdown 3.7
MarkupSafe 2.1.5
mpmath 1.3.0
networkx 2.8.8
numpy 1.24.4
nvidia-cublas-cu12 12.1.3.1
nvidia-cuda-cupti-cu12 12.1.105
nvidia-cuda-nvrtc-cu12 12.1.105
nvidia-cuda-runtime-cu12 12.1.105
nvidia-cudnn-cu12 9.1.0.70
nvidia-cufft-cu12 11.0.2.54
nvidia-curand-cu12 10.3.2.106
nvidia-cusolver-cu12 11.4.5.107
nvidia-cusparse-cu12 12.1.0.106
nvidia-nccl-cu12 2.20.5
nvidia-nvjitlink-cu12 12.9.86
nvidia-nvtx-cu12 12.1.105
pandas 2.0.3
pillow 10.4.0
pip 20.0.2
pkg-resources 0.0.0
pyconcorde 0.1.0 /home/warabinu/pyconcorde
PyRSS2Gen 1.1
python-dateutil 2.9.0.post0
pytz 2025.2
setuptools 44.0.0
six 1.17.0
sympy 1.13.3
tabulate 0.8.10
torch 2.4.1
torchaudio 2.4.1
torchvision 0.19.1
tqdm 4.67.1
triton 3.0.0
tsplib95 0.7.1
typing-extensions 4.13.2
tzdata 2025.2
wheel 0.45.1
wrapt 1.17.2
zipp 3.20.2

「python3 -m pip list」
(venv) warabinu@DESKTOP-CD434N2:~$ python3 -m pip list
Package Version Location
------------------------ ----------- -------------------------
click 8.1.8
concorde 0.1.2
cython 3.1.2
Deprecated 1.2.18
filelock 3.16.1
fsspec 2025.3.0
importlib-metadata 8.5.0
jinja2 3.1.6
Markdown 3.7
MarkupSafe 2.1.5
mpmath 1.3.0
networkx 2.8.8
numpy 1.24.4
nvidia-cublas-cu12 12.1.3.1
nvidia-cuda-cupti-cu12 12.1.105
nvidia-cuda-nvrtc-cu12 12.1.105
nvidia-cuda-runtime-cu12 12.1.105
nvidia-cudnn-cu12 9.1.0.70
nvidia-cufft-cu12 11.0.2.54
nvidia-curand-cu12 10.3.2.106
nvidia-cusolver-cu12 11.4.5.107
nvidia-cusparse-cu12 12.1.0.106
nvidia-nccl-cu12 2.20.5
nvidia-nvjitlink-cu12 12.9.86
nvidia-nvtx-cu12 12.1.105
pandas 2.0.3
pillow 10.4.0
pip 20.0.2
pkg-resources 0.0.0
pyconcorde 0.1.0 /home/warabinu/pyconcorde
PyRSS2Gen 1.1
python-dateutil 2.9.0.post0
pytz 2025.2
setuptools 44.0.0
six 1.17.0
sympy 1.13.3
tabulate 0.8.10
torch 2.4.1
torchaudio 2.4.1
torchvision 0.19.1
tqdm 4.67.1
triton 3.0.0
tsplib95 0.7.1
typing-extensions 4.13.2
tzdata 2025.2
wheel 0.45.1
wrapt 1.17.2
zipp 3.20.2

[fiveHundred]

colabのため、差異があるかもしれませんが、それで試して見た限りで言いますと、

まず、あなたが言っているのに加えて、
pip install concorde
をやっていると思いますが、このconcordeとpyconcordeは共存できないため、
pip uninstall concorde
で削除してください。
（venvを使っているのであれば、新たに環境を作り直すほうが手っ取り早いかもしれません）

また、最新バージョンではなく
git checkout f75601d
で少し前のバージョンを使うと動作するかもしれません。

[warabinu]

venvのフォルダを削除し、環境を作り直したところ、別のエラーが出てしまいました。

エラーメッセージは次の通りです。

Traceback (most recent call last):
File "us_state_capitals.py", line 7, in <module>
from concorde.tsp import TSPSolver
File "/home/warabinu/pyconcorde/concorde/tsp.py", line 10, in <module>
from concorde._concorde import _CCutil_gettsplib, _CCtsp_solve_dat
ImportError: /home/warabinu/pyconcorde/concorde/_concorde.cpython-38-x86_64-linux-gnu.so: undefined symbol: CCutil_dheap_freeFF

実行したコマンドは次の通りです。
python3 -m venv venv
source venv/bin/activate
git clone https://github.com/jvkersch/pyconcorde.git
git checkout f75601d

ここで、
pyconcorde/data/concorde.h
について
#ifdef CC_PROTO_GETHOSTNAME
extern int
gethostname (char *, int);
#endif
をコメントアウト

pip install -e .
pip install numpy pandas torch tqdm
cd ~/pyconcorde/examples
python us_state_capitals.py

[fiveHundred]

なぜヘッダの一部をコメントアウトしたのでしょう？
それで関数の一部が使えなくなったのが原因だと思いますが。

デフォルトで動作しないのであれば、とりあえずbuildしたconcordeがあるので、そちらをCONCORDE_DIRで指定するのはどうでしょう。

[warabinu]

コメントアウトしたのはこの部分でエラーがでてしまい、重複して定義してしまったのかと考えたからです。コメントアウトすることで pip install -e .にエラーがでなくなりましたが、それが原因でエラーがでている以上やめたほうが良いと理解しました。

「CONCORDE_DIRで指定する」とはどういうことでしょうか？concordeは仮想環境を作り直したときにアンインストールしてしまいました。

[fiveHundred]

あなたがやった

cd ~
wget http://www.math.uwaterloo.ca/tsp/concorde/downloads/codes/src/co031219.tgz
tar -xvzf co031219.tgz
cd concorde

./configure
make

で生成したconcordeのことです。
pipのconcordeのほうではありません。

そのconcordeをCONCORDE_DIRで指定すれば、そちらが使用されるという意味です。

[warabinu]

そちらのConcordeも関係がないと思ってフォルダごと消してしまいました。
入れなおしたほうがよいでしょうか？

つまり、
export CONCORDE_DIR=/home/warabinu/concorde
で指定するということでしょうか？

[fiveHundred]

はい、それで試してみてください。

[warabinu]

export CONCORDE_DIR=/home/warabinu/concorde
pip install -e .
を実行したところ、次のようなエラーが発生しました。

ERROR: Command errored out with exit status 1:
command: /home/warabinu/venv/bin/python3 -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'/home/warabinu/pyconcorde/setup.py'"'"'; __file__='"'"'/home/warabinu/pyconcorde/setup.py'"'"';f=getattr(tokenize, '"'"'open'"'"', open)(__file__);code=f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' develop --no-deps
cwd: /home/warabinu/pyconcorde/
Complete output (63 lines):
running develop
running egg_info
writing pyconcorde.egg-info/PKG-INFO
writing dependency_links to pyconcorde.egg-info/dependency_links.txt
writing requirements to pyconcorde.egg-info/requires.txt
writing top-level names to pyconcorde.egg-info/top_level.txt
dependency /home/warabinu/concorde/concorde.h won't be automatically included in the manifest: the path must be relative
dependency /tmp/pip-build-env-6g5ik2od/overlay/lib/python3.8/site-packages/numpy/core/include/numpy/arrayobject.h won't be automatically included in the manifest: the path must be relative
dependency /tmp/pip-build-env-6g5ik2od/overlay/lib/python3.8/site-packages/numpy/core/include/numpy/arrayscalars.h won't be automatically included in the manifest: the path must be relative
dependency /tmp/pip-build-env-6g5ik2od/overlay/lib/python3.8/site-packages/numpy/core/include/numpy/ndarrayobject.h won't be automatically included in the manifest: the path must be relative
dependency /tmp/pip-build-env-6g5ik2od/overlay/lib/python3.8/site-packages/numpy/core/include/numpy/ndarraytypes.h won't be automatically included in the manifest: the path must be relative
dependency /tmp/pip-build-env-6g5ik2od/overlay/lib/python3.8/site-packages/numpy/core/include/numpy/ufuncobject.h won't be automatically included in the manifest: the path must be relative
reading manifest file 'pyconcorde.egg-info/SOURCES.txt'
reading manifest template 'MANIFEST.in'
/tmp/pip-build-env-6g5ik2od/overlay/lib/python3.8/site-packages/setuptools/command/develop.py:41: EasyInstallDeprecationWarning: easy_install command is deprecated.
!!

********************************************************************************
Please avoid running ``setup.py`` and ``easy_install``.
Instead, use pypa/build, pypa/installer or other
standards-based tools.

See https://github.com/pypa/setuptools/issues/917 for details.
********************************************************************************

!!
easy_install.initialize_options(self)
/tmp/pip-build-env-6g5ik2od/overlay/lib/python3.8/site-packages/setuptools/_distutils/cmd.py:66: SetuptoolsDeprecationWarning: setup.py install is deprecated.
!!

********************************************************************************
Please avoid running ``setup.py`` directly.
Instead, use pypa/build, pypa/installer or other
standards-based tools.

See https://blog.ganssle.io/articles/2021/10/setup-py-deprecated.html for details.
********************************************************************************

!!
self.initialize_options()
warning: no files found matching 'requirements.txt'
adding license file 'COPYING'
writing manifest file 'pyconcorde.egg-info/SOURCES.txt'
running build_ext
building 'concorde._concorde' extension
x86_64-linux-gnu-gcc -pthread -Wno-unused-result -Wsign-compare -DNDEBUG -g -fwrapv -O2 -Wall -g -fstack-protector-strong -Wformat -Werror=format-security -g -fwrapv -O2 -fPIC -I/tmp/pip-build-env-6g5ik2od/overlay/lib/python3.8/site-packages/numpy/core/include -I/home/warabinu/concorde -I/home/warabinu/concorde -I/home/warabinu/venv/include -I/usr/include/python3.8 -c concorde/_concorde.c -o build/temp.linux-x86_64-cpython-38/concorde/_concorde.o
In file included from /tmp/pip-build-env-6g5ik2od/overlay/lib/python3.8/site-packages/numpy/core/include/numpy/ndarraytypes.h:1940,
from /tmp/pip-build-env-6g5ik2od/overlay/lib/python3.8/site-packages/numpy/core/include/numpy/ndarrayobject.h:12,
from /tmp/pip-build-env-6g5ik2od/overlay/lib/python3.8/site-packages/numpy/core/include/numpy/arrayobject.h:5,
from concorde/_concorde.c:1154:
/tmp/pip-build-env-6g5ik2od/overlay/lib/python3.8/site-packages/numpy/core/include/numpy/npy_1_7_deprecated_api.h:17:2: warning: #warning "Using deprecated NumPy API, disable it with " "#define NPY_NO_DEPRECATED_API NPY_1_7_API_VERSION" [-Wcpp]
17 | #warning "Using deprecated NumPy API, disable it with " \
| ^~~~~~~
In file included from concorde/_concorde.c:1159:
/home/warabinu/concorde/concorde.h:173: warning: "NDEBUG" redefined
173 | #define NDEBUG
|
<command-line>: note: this is the location of the previous definition
x86_64-linux-gnu-gcc -pthread -shared -Wl,-O1 -Wl,-Bsymbolic-functions -Wl,-Bsymbolic-functions -Wl,-z,relro -g -fwrapv -O2 build/temp.linux-x86_64-cpython-38/concorde/_concorde.o data/qsopt.a /home/warabinu/concorde/concorde.a data/qsopt.a /home/warabinu/concorde/concorde.a -L/usr/lib -o build/lib.linux-x86_64-cpython-38/concorde/_concorde.cpython-38-x86_64-linux-gnu.so
/usr/bin/ld: /home/warabinu/concorde/concorde.a(fmatch.o): relocation R_X86_64_PC32 against symbol `stderr@@GLIBC_2.2.5' can not be used when making a shared object; recompile with -fPIC
/usr/bin/ld: final link failed: bad value
collect2: error: ld returned 1 exit status
error: command '/usr/bin/x86_64-linux-gnu-gcc' failed with exit code 1
----------------------------------------
Rolling back uninstall of pyconcorde
Moving to /home/warabinu/venv/lib/python3.8/site-packages/pyconcorde.egg-link
from /tmp/pip-uninstall-iahp6j8f/pyconcorde.egg-link
ERROR: Command errored out with exit status 1: /home/warabinu/venv/bin/python3 -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'/home/warabinu/pyconcorde/setup.py'"'"'; __file__='"'"'/home/warabinu/pyconcorde/setup.py'"'"';f=getattr(tokenize, '"'"'open'"'"', open)(__file__);code=f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' develop --no-deps Check the logs for full command output.

[fiveHundred]

難雑そうだったので、こちらもwslで環境構築して色々試してみました。
以下の通り行えば、pyconcordeの導入が出来ると思います。

# qsoptのダウンロード
mkdir qsopt
cd qsopt
wget https://www.math.uwaterloo.ca/~bico/qsopt/downloads/codes/ubuntu/qsopt
chmod 755 qsopt
wget https://www.math.uwaterloo.ca/~bico/qsopt/downloads/codes/ubuntu/qsopt.a
chmod 755 qsopt.a
wget https://www.math.uwaterloo.ca/~bico/qsopt/downloads/codes/ubuntu/qsopt.h
cd ..

# concordeのビルド
wget http://www.math.uwaterloo.ca/tsp/concorde/downloads/codes/src/co031219.tgz
tar -xvzf co031219.tgz
cd concorde
export CFLAGS=-fPIC
./configure --with-qsopt=/home/xxx/qsopt
make
cd ..

# pyconcordeのインストール
source venv/bin/activate
git clone https://github.com/jvkersch/pyconcorde.git
cd pyconcorde
export CONCORDE_DIR=/home/xxx/concorde
pip install -e .

ただ上記を行った場合でも、cartopyのインストールが出来なかったため、サンプルの動作は最後まで出来ませんでした。
そもそもcolabで行った際も404エラーで断念したので、この点は仕方ないと思います。

[warabinu]

ご教示いただいた通りに進めたところ、pyconcordeの導入ができました。
別のプログラムで動くことも確認しました。
時間をかけて丁寧にご対応いただきありがとうございました。
ベストアンサーに選ばせていただきたいのですが、同じ内容を回答欄に投稿いただくことは可能でしょうか。

Answer 1

pip list の結果に concorde というパッケージが見えます

https://pypi.org/project/concorde/
で

Simple static site generator built from Markdown and Jinja

というTSPと関係ないパッケージですね。
こちらがimportされているだけだと思います。

pip install concorde

したのではないでしょうか? そしてそれを忘れているか隠しているかだと思います。

単に

pip uninstall concorde

でいいと思いますよ。

Answer 2

以下の通り行えば、pyconcordeの導入が出来ると思います。

# qsoptのダウンロード
mkdir qsopt
cd qsopt
wget https://www.math.uwaterloo.ca/~bico/qsopt/downloads/codes/ubuntu/qsopt
chmod 755 qsopt
wget https://www.math.uwaterloo.ca/~bico/qsopt/downloads/codes/ubuntu/qsopt.a
chmod 755 qsopt.a
wget https://www.math.uwaterloo.ca/~bico/qsopt/downloads/codes/ubuntu/qsopt.h
cd ..

# concordeのビルド
wget http://www.math.uwaterloo.ca/tsp/concorde/downloads/codes/src/co031219.tgz
tar -xvzf co031219.tgz
cd concorde
export CFLAGS=-fPIC
./configure --with-qsopt=/home/xxx/qsopt
make
cd ..

# pyconcordeのインストール
source venv/bin/activate
git clone https://github.com/jvkersch/pyconcorde.git
cd pyconcorde
export CONCORDE_DIR=/home/xxx/concorde
pip install -e .

ただ上記を行った場合でも、cartopyのインストールが出来なかったため、サンプルの動作は最後まで出来ませんでした。
そもそもcolabで行った際も404エラーで断念したので、この点は仕方ないと思います。