Printemps メタヒューリスティクスソルバ

 メタヒューリスティクスに基づく汎用線形整数計画ソルバーの開発 - Speaker Deck

ベースになっているのは、法政大学の野々部先生のWCSPです。WCSPは、汎用国産ソルバNuorium Optimizer にも組み込まれています。

藤井　浩一｜株式会社NTTデータ数理システム

野々部先生のWCSPは、第一回のナーススケジューリング国際競技会で、3位に入賞されています。野々部先生とは、以前RAMP講演でお会いしました。

その系統であるPrintempsもシフトスケジューリング問題に期待が持てるかもしれません。オープンソースでMPSファイルも読み取れます。オプションで連続変数を整数として読むことも出来ます。

Optimization Night#9に参加できなさそうなので発表されるPRINTEMPSで一人遊んでみた #最適化 - Qiita

こうしたソルバは、分枝限定法ソルバの初期段階でのUBを得るのに有効な場合があります。以前は、Feasibility Pump しかありませんでしたが、最近では、

GitHub - GioniMexi/FeasPumpCollection: Using multiple reference vectors in the Feasibility Pump.

CAI教授のローカルソルバシリーズ、

GitHub - shaowei-cai-group/Local-MIP: A standalone local search solver for general mixed integer programming

GitHub - shaowei-cai-group/NuPBO: A local search solver for PBO

GitHub - shaowei-cai-group/ParaILP: A Parallel Local Search Framework for Integer Linear Programming with Cooperative Evolution Mechanism

GitHub - shaowei-cai-group/PRS-sc24: Submission of PRS and PRS-distributed to International SAT Competition 2024

等あります。