解析ソルバー HiGHS C++ソースにおいて、高速化技術、C++の高速化・アルゴリズムの高速化、その他すべての高速化について、100個、あげて下さい。
引用 ChatGPT
以下、HiGHS の C++ ソースを使う前提で、
**「C++実装の高速化」「アルゴリズムの高速化」「モデル側の高速化」「ビルド・実行環境の高速化」**を全部まとめて、100個挙げます。
まず前提だけ短く書くと、HiGHS は LP / MIP / QP 向けの高性能ソルバーで、presolve、simplex、ipm、pdlp、parallel などの主要オプションを持っています。CPU 並列の適用範囲は限定的で、現状は主に dual simplex / interior point / MIP に並列機会があり、さらに PDLP には GPU を使う系統もあります。最近のリリースでは MIP ヒューリスティクスやカット強化も追加・改善されています。
100個
1. ビルド・コンパイル最適化
Release ビルド固定にする。Debug は絶対に比較対象にしない。
/O2 または /Ox を使う。
/GL + LTCG を使ってリンク時最適化する。
/arch:AVX2 など、CPU に合った ISA を有効化する。
/fp:fast を許容できる箇所では使う。
NDEBUG を定義して assert 系を消す。
例外を使わない層は例外依存を減らす。
RTTI を不要なら切る。
PGO（Profile Guided Optimization） を使う。
静的リンク版 / DLL版 を比較し、呼び出し境界コストを確認する。
2. メモリ確保・解放の高速化
ループ中の new/delete を禁止する。
std::vector::reserve() を徹底する。
再利用バッファを持つ。
small object の頻繁生成を避ける。
arena / pool allocator を検討する。
疎行列構築時に nnz を事前見積もりする。
コピーより move を優先する。
一時 std::string を減らす。
オプション設定を毎回文字列解析しない。
solver オブジェクト再生成を避けて再利用する。
3. データレイアウト最適化
連続メモリに寄せる。
AoS より SoA が有利な箇所は SoA 化する。
インデックス型を必要以上に大きくしない。
頻出フラグを bitset 化する。
キャッシュラインをまたぐ小構造体乱立を避ける。
アクセス順を row-wise / col-wise で統一する。
疎行列は HiGHS が得意な形式に素直に渡す。
ソート済み index で投入し、後処理を減らす。
重複係数を事前集約する。
ゼロ係数は作る前に落とす。
4. C++コードの基本高速化
小関数は inline しやすい形に保つ。
仮想関数をホットパスで避ける。
const& / span で不要コピー回避。
emplace_back を使う。
範囲チェック付きアクセスをホットループで避ける。
分岐を減らす。
条件順序を出現頻度順に並べる。
ループ不変値を外に出す。
size() の多重評価を避ける。
ホットループの logging を完全停止する。
5. 疎行列・係数生成の高速化
モデル生成時間を別計測し、solve 時間と分ける。
列ごと / 行ごとにまとめて投入して API 呼び出し回数を減らす。
係数生成時に整数→倍精度変換を減らす。
同一パターン列をキャッシュする。
列生成法では同型列の再生成を避ける。
枝刈りで使わない制約は最初から作らない。
巨大 Big-M を避ける。
係数スケールを揃える。
明らかに冗長な bound を投入前に削る。
プレソルブで消えるだけの構造を元モデル側で消す。
6. HiGHSオプション選択の高速化
presolve=on/choose を試し、固定する。 HiGHS には presolve オプションがあります。
LP は solver=simplex / ipm / pdlp を問題別に比較する。HiGHS はこれらを選べます。
基本解が必要なら simplex 系を優先する。
巨大疎 LP なら PDLP 候補にする。HiGHS 文書では PDLP 系があり、GPU 利用の記述もあります。
IPM 後 crossover が不要なら切ることを検討する。run_crossover オプションがあります。
parallel=on/choose を必ず比較する。オプションとして存在します。
time_limit を適切に設定して暴走ケースを遮断する。
ranging など不要な解析機能は切る。ranging オプションがあります。
ログ出力頻度を減らす。
実験時は乱数種や設定を固定し、公平比較する。
7. LPアルゴリズムの高速化
dual simplex が強い問題を見極める。HiGHS は dual simplex を主要手法として持ちます。
basis warm start を使える場面では活用する。
小変更再最適化では cold start を避ける。
列追加型アルゴリズムでは basis を引き継ぐ。
退化が強いなら pricing や pivot の相性を確認する。
再スケーリングの効果を計測する。
数値的に悪い行列を改善して反復数を減らす。
等式過多モデルは構造変換を検討する。
密な列を減らす。
bound tightening を自前でも入れる。
8. MIPアルゴリズムの高速化
まず LP 緩和を強くする。MIP はそこでほぼ決まる。
変数 bound を締める。
Big-M を最小化する。
対称性を壊す制約を入れる。
支配変数・支配制約を削る。
fixing を事前に入れる。
初期実行可能解を与える。
分枝しやすい定式化に変える。
カットを増やせば良いとは限らないので計測で選ぶ。
最近追加された MIP ヒューリスティクスも、問題によっては速くも遅くもなるので切替比較する。最近のリリースでは RINS / RENS / root reduced cost、さらに ZI rounding / shifting などの記述があります。
9. 定式化そのものの高速化
制約数より非ゼロ数(nnz)を減らす意識を持つ。
同値な定式化を複数作って速い方を使う。
列生成が効くなら全面展開をやめる。
枝価格法系では pricing を最適化の主戦場と考える。
ナップサック pricing は専用 DP / B&B に置き換える。
問題分解できるなら分けて解く。
ラグランジュ緩和で上界下界を早く作る。
ヒューリスティクスで良い初期解を入れる。
変数数削減のための集約モデルを作る。
絶対必要な整数変数だけ整数にする。
10. 並列化・ハードウェア活用
HiGHS の並列適用範囲を理解した上でスレッド数を調整する。CPU 並列の機会は限定的です。
solver を複数条件で並列試行し、最速採用する。
モデル生成と solve をパイプライン化する。
NUMA 環境ではメモリ配置を意識する。
大規模 LP はメモリ帯域律速を疑う。
GPU が有効な超大規模 LP では PDLP 系も候補にする。HiGHS 文書に GPU 利用の記述があります。
SSD スワップ前提の巨大問題は避け、RAM 内完結を目指す。
CPU 固定クロック・電源設定を見直す。
ベンチマーク時に他プロセスを止める。
最後は必ず profiler で確認し、思い込み最適化をやめる。
特に効きやすい「上位10個」
実務的には、まずこの10個からです。
Release + LTCG + PGO
presolve の有無比較
simplex / ipm / pdlp の比較
モデル生成時のゼロ・重複係数削除
Big-M 縮小
bound tightening
初期解・warm start 活用
疎行列投入の一括化
logging 停止
profiler でホットスポット確認
HiGHSで特に重要な見方
LP: 定式化の疎性、スケーリング、warm start
MIP: LP 緩和の強さ、Big-M、対称性除去、初期実行可能解
列生成: pricing の高速化が本丸
C++: メモリ確保回数とデータレイアウトが本丸
必要なら次に、
「この100個を HiGHS + C++ 用に、効果順A/B/Cランク表にして整理」 します。