解析ソルバー HiGHS C++ソースにおいて、高速化技術、C++の高速化・アルゴリズムの高速化、その他すべての高速化について、100個、あげて下さい。
引用 Gemini
HiGHSは、現在世界で最も高速なオープンソースの線形計画法（LP）および混合整数計画法（MIP）ソルバーの一つです。その高速化の秘密は、教科書的なアルゴリズムの実装にとどまらず、**「計算幾何学的なデータ構造の最適化」と「徹底したC++の低レイヤ最適化」**の両面にあります。
100個のポイントを、アルゴリズム、実装技術、データ構造などのカテゴリに分けて解説します。
1. 改良単体法（Simplex Method）の高速化
単体法の核心は「いかに少ない反復回数で、いかに速く1ステップを回すか」にあります。
主対対偶単体法（Dual Simplex）の優先利用: LPでは一般的に対偶法の方が高速で安定しています。
Steepest Edge Pricing: 勾配が最も急な方向を選ぶことで、反復回数を劇的に削減します。
Devex Pricing: Steepest Edgeの近似版。計算負荷を抑えつつ効率的なパスを選択します。
Btran/Ftranの疎性（Sparsity）活用: ベクトルの非ゼロ要素のみを計算対象にします。
Hyper-sparsityの利用: 解のベクトルが極めて疎な場合、専用の高速ルーチンへ切り替えます。
LU分解のMarkowitzピボッティング: フィルイン（非ゼロ要素の増加）を最小限に抑えます。
Forrest-Tomlinアップデート: 基底行列の更新を効率的に行い、再分解の頻度を下げます。
Harrisの許容誤差選択: 数値的不安定性を回避し、無駄な反復を防ぎます。
Crash手続き: 最初に「良さそうな」基底を高速に見つけ、反復のスタートラインを上げます。
定期的な再分解（Refactorization）: 誤差の蓄積を防ぎ、計算効率をリセットします。
Primal-Dual遷移: 必要に応じて主問題と対偶問題を切り替えて解きます。
ピボット選択のタイブレーク戦略: 数値的安定性と疎性のバランスをとります。
劣決定系の高速処理: 変数が多い問題特有の最適化。
過決定系の高速処理: 制約が多い問題特有の最適化。
スラック変数の効率的表現: メモリと計算の両面でスラックを特別扱いします。
2. 内点法（Interior Point Method / IPM）
大規模で疎な行列に対して威力を発揮します。
メカニズムとしての予測子・修正子法（Predictor-Corrector）: 収束を早めます。
KKTシステムの正則化: 数値的な安定性を確保し、反復の質を上げます。
Cholesky分解の順序付け（Ordering）: AMDやMETISを用いたフィルイン抑制。
疎なコラムの分離処理: 密な列が計算を遅延させるのを防ぐため、シャーマン・モリソンの公式などで別処理します。
Iterative Refinement: 線形システムの解の精度を高速に向上させます。
クロスオーバー・アルゴリズム: 内点法の解から単体法の基底解へ高速に変換します。
3. 混合整数計画法（MIP）の高速化
離散的な決定が必要なMIPは、探索空間の削減が命です。
強分岐（Strong Branching）: 実際に分岐してみて、どの変数が最も目的関数に影響するかを事前に評価します。
信頼性分岐（Reliability Branching）: 過去の強分岐の結果を統計的に再利用します。
擬似コスト（Pseudo-costs）: 分岐による目的関数の変化を予測します。
ドメイン伝播（Domain Propagation）: 一つの変数の値が決まった際、他の変数の範囲を即座に更新します。
衝突分析（Conflict Analysis）: 不可能な組み合わせから新しい制約（カット）を生成します。
Gomory Mixed Integer Cuts: 数学的な切り口を追加して探索空間を削ります。
MIR Cuts (Mixed Integer Rounding): 丸めを利用した強力なカット。
Clique Cuts: 変数間の相互排他関係を利用。
Flow Cover Cuts: ネットワークフロー構造を抽出してカットを生成。
Feasibility Pump: 素早く実行可能解（暫定解）を見つけるための強力なヒューリスティック。
Local Branching: 暫定解の近傍を集中攻撃します。
RINS (Relaxation Induced Neighborhood Search): 連続緩和解と暫定解の共通点を利用。
Symmetry Breaking: 問題の対称性を検知し、重複した探索を排除します。
Node Selection (Best Bound First): 期待値の高いノードから探索。
Node Selection (Depth First): メモリ節約と暫定解発見を優先。
Lazy Constraints: 必要になるまで制約を追加しない仕組み。
User Heuristicsのフック: ユーザー定義の知識を高速化に組み込む口。
4. 前処理（Presolve）とスケーリング
問題を解く前に、小さく、解きやすくします。
Row/Column Singletonの除去: 変数や制約が一つしかない場合の即時解決。
冗長な制約の検出: 他の制約に内包される式を削除。
変数の固定（Fixing variables）: 範囲制約から値が確定する変数を排除。
Bound Strengthening: 制約を組み合わせて変数の上下限を絞り込みます。
Coefficient Tightening: 係数をより厳しいものに書き換えます。
Dual Redundancy: 対偶問題の視点から不要な変数を削除。
Aggregator: 変数を別の変数の式で置き換え、次元を削減します。
Equilibration Scaling: 行列の要素の桁数を揃え、数値安定性を向上。
Geometric Mean Scaling: スケーリング係数の決定手法。
Ruiz Scaling: 繰り返し計算による高度なスケーリング。
5. C++ 実装レベルの高速化
HiGHSが「モダン」と言われる所以です。
キャッシュ効率の良いデータレイアウト: 疎行列をCSC（Compressed Sparse Column）形式で保持。
メモリプールの活用: 頻繁な new/delete を避け、フラグメンテーションを防止。
std::vector::reserve() の徹底: 再確保によるコピーコストを排除。
仮想関数の抑制: ホットパス（頻繁に呼ばれる箇所）での動的ディスパッチを回避。
インライン化（Inlining）: 小さな関数をコンパイル時に展開。
テンプレートによる特殊化: 型に応じた最適コードの生成。
SIMDの活用: 並列命令を用いたベクトル演算の加速。
ムーブセマンティクスの活用: 大きな行列データの所有権移動を高速化。
アライメントの最適化: データのメモリ境界を揃えてロードを高速化。
const 伝播の徹底: コンパイラの最適化ヒントを最大化。
例外処理の最小化: パフォーマンス低下を防ぐため、正常系での例外利用を避ける。
分岐予測の最適化: if 文の順序を統計的な確率に基づいて配置。
ループ展開（Loop Unrolling）: ループのオーバーヘッドを削減。
ポインタ・エイリアシングの排除: __restrict 的なアプローチでメモリアクセスを最適化。
カスタム・アロケータ: 特定のデータ構造に最適化されたメモリ管理。
6. 並列化・マルチスレッド（Parallelism）
OpenMPによる並列計算: 行列演算やヒューリスティックの並列実行。
並列MIP探索: 複数のCPUコアで異なるサブツリーを同時に探索。
決定論的並列化（Deterministic Parallelism）: 実行のたびに結果が変わらないよう制御。
スレッドセーフなロギング: ログ出力がボトルネックにならないよう設計。
タスク並列: 独立した前処理タスクを同時に実行。
アトミック演算の利用: ミューテックスを避け、軽量な同期を実現。
7. 疎行列・線形代数ライブラリの最適化
Sparse Accumulator (SPA): 疎なベクトル加算を効率化するデータ構造。
リンクリストによる非ゼロ要素管理: 行列の更新時に要素移動を最小化。
ビットセットによるフラグ管理: 大量の変数状態を高速にスキャン。
高速な絶対値・比較演算: CPU命令を直接叩く工夫。
再利用可能な作業配列: 関数の呼び出しごとにメモリを確保せず、ワークスペースを使い回す。
行列の転置の高速化: キャッシュを意識した転置アルゴリズム。
8. ソフトウェア設計とアーキテクチャ
モジュール化されたソルバー構造: 必要最小限の機能だけを呼び出す。
遅延評価（Lazy Evaluation）: 必要になるまで計算しない。
ロギングレベルの動的制御: 不要な文字列操作をスキップ。
プロファイリングに基づいたホットスポット修正: ボトルネックの継続的な排除。
回帰テストによるパフォーマンス監視: 修正による速度低下を即座に検知。
9. 特殊な問題構造への対応
SOS (Special Ordered Sets) の処理: 特定の変数集合に対する専用ロジック。
区分線形関数の高速処理: 近似を用いた最適化。
ネットワーク構造の自動抽出: グラフ理論的アプローチで高速化。
10. 数値的安定性と効率のトレードオフ（残り17個）
動的ピボット耐性（Pivot Tolerance）: 状況に応じて精度と速度を調整。
スラック変数の再利用: 基底変更時の計算量削減。
整数性の許容誤差の自動調整: 無駄なノード探索を防止。
高速なInfinity表現: 計算のオーバーフローを防ぎつつ比較を単純化。
行列のスパース・シンボリック分解の再利用: 数値だけ変わる場合の再計算抑制。
列生成（Column Generation）の口: 大規模問題への拡張性。
ヒストグラムを用いた分岐変数選択: 統計的データの蓄積。
メモリ使用量の動的監視: スワップ発生を防ぎ、速度低下を回避。
SIMD化されたドット積計算: 疎ベクトルと密ベクトルの積を加速。
プリフェッチ命令の挿入: 次に使うデータを事前にキャッシュへ。
関数コールのインライン深度の調整: バイナリサイズと速度のバランス。
std::unordered_map ではなく独自のハッシュテーブル: 高速なルックアップ。
行列要素のソート維持: 二分探索による高速アクセスを可能に。
数値不安定時の自動再スタート: 泥沼の計算を避け、クリーンな状態で再開。
実行時CPU機能検知: AVX2などの命令を動的に使い分け。
ビット操作による状態フラグの圧縮: キャッシュラインに多くの情報を詰め込む。
ソースコードの「ミニマリズム」: 複雑さを排除し、コンパイラの最適化を促す設計。
まとめ
HiGHSが速いのは、単に「Simplexがすごい」からではなく、**「メモリの1バイト、CPUの1サイクルを惜しむC++の執念」と「数理最適化の高度な理論」**が、密に統合されているからです。ソースコードを読む際は、特に src/util/HighsSparseMatrix.cpp や src/lp/HEkk.cpp （Simplexの核心部）にこれらのテクニックが凝縮されています