【pythonで最適化】いろんな方法でTSPを解いてみた！
NP困難な最適化問題として知られる巡回セールスマン問題を、複数の近似解法と厳密解法を使って解いてみました。使用した解法は以下の４個です。整数計画問題(MTZ制約を使用、厳密解法)遺伝的アルゴリズム(近似解法)焼きなまし法(近似解法)2-opt(山登り法として実装、近似解法)実装はp
pulp
3pulpで整数計画問題を解く〜実装編〜
プロ野球のスケジュール作成を題材に、定式化からpulpを使った実装まで。定式化はこちら↓https://yamakuramun.info/?p=187筆者の環境：macOS Catalina version10.15.6python3.8.3pulpのインストー
pulpで整数計画問題を解く〜定式化編〜
プロ野球のスケジュール作成を題材に、定式化からpulpを使った実装まで。実装編はこちら↓https://yamakuramun.info/?p=227定式化の流れ目的を明確にする→解きたい問題が持つ制約条件を全列挙→数式に変換→適切な手法を用いて解く目的