2026年11月10日火曜日

c++　テンプレートとconst_expr

実装ステージに入っています。雑多なコードをテンプレート化により整理します。実装では、何が良い実装か未だ確定しないので、パラメータは、テンプレート化して、後で変えるだけで、実装の中身も変えます。テンプレートが決まると固定した定数が出てくるので、さらにconst_exprにより静的にコンパイルするようにします。if文であっても、静的に評価されるので、実行時は、if文にはなりません。

一にアルゴリズム、二にデータ構造、三に実装テクニックですが、最後の部分でも数％の効果が期待できます。

 

WRITE＿WIDTH＝４，６，８，１２，１６，２０，２４で最適化コードを。

WRITE_WIDTH が 4,6,8,12,16,20,24 の固定値しか来ないなら、memcpy() に任せるより専用化した方が速いです。


ポイントは、


16byteまでは a0 の計算結果だけで完結

20,24byteは次の128bitも加算して一部書く

SSE2のみ使用

ストア数最小



template<int WRITE_WIDTH>

static inline void add_u8_aligned16_X(

    unsigned char* A,

    const unsigned char* B)

{

    __m128i a0 = _mm_load_si128((const __m128i*)(A + 0));

    __m128i b0 = _mm_load_si128((const __m128i*)(B + 0));

 

    a0 = _mm_add_epi8(a0, b0);

 

    if constexpr (WRITE_WIDTH == 4)

    {

        *(uint32_t*)A = (uint32_t)_mm_cvtsi128_si32(a0);

    }

    else if constexpr (WRITE_WIDTH == 6)

    {

        uint32_t lo32 = (uint32_t)_mm_cvtsi128_si32(a0);

        uint16_t hi16 = (uint16_t)(_mm_extract_epi16(a0, 2));

 

        *(uint32_t*)(A + 0) = lo32;

        *(uint16_t*)(A + 4) = hi16;

    }

    else if constexpr (WRITE_WIDTH == 8)

    {

        _mm_storel_epi64((__m128i*)A, a0);

    }

    else if constexpr (WRITE_WIDTH == 12)

    {

        _mm_storel_epi64((__m128i*)A, a0);

 

        uint32_t x =

            (uint32_t)_mm_extract_epi16(a0, 4)

          | ((uint32_t)_mm_extract_epi16(a0, 5) << 16);

 

        *(uint32_t*)(A + 8) = x;

    }

    else if constexpr (WRITE_WIDTH == 16)

    {

        _mm_store_si128((__m128i*)A, a0);

    }

    else if constexpr (WRITE_WIDTH == 20)

    {

        __m128i a1 = _mm_load_si128((const __m128i*)(A + 16));

        __m128i b1 = _mm_load_si128((const __m128i*)(B + 16));

 

        a1 = _mm_add_epi8(a1, b1);

 

        _mm_store_si128((__m128i*)(A + 0), a0);

 

        *(uint32_t*)(A + 16)

            = (uint32_t)_mm_cvtsi128_si32(a1);

    }

    else if constexpr (WRITE_WIDTH == 24)

    {

        __m128i a1 = _mm_load_si128((const __m128i*)(A + 16));

        __m128i b1 = _mm_load_si128((const __m128i*)(B + 16));

 

        a1 = _mm_add_epi8(a1, b1);

 

        _mm_store_si128((__m128i*)(A + 0), a0);

        _mm_storel_epi64((__m128i*)(A + 16), a1);

    }

}

WRITE_WIDTH が 4,6,8,12,16,20,24 の固定値しか来ないなら、memcpy() に任せるより専用化した方が速いです。

ポイントは、

  • 16byteまでは a0 の計算結果だけで完結
  • 20,24byteは次の128bitも加算して一部書く
  • SSE2のみ使用
  • ストア数最小
投稿者 時刻: 0 件のコメント:

2026年11月9日月曜日

MIPソルバの得意領域、不得意領域

Q. MIPソルバの得意領域、不得意領域について、リニアソルバの観点から説明して。


MIP（混合整数計画問題）ソルバは、実数変数だけでなく整数変数（0や1のバイナリ変数を含む）を扱える非常に強力な最適化ツールです。
リニアソルバ（線形計画法/LPソルバ）の観点から見ると、MIPソルバは「LPソルバを高速なエンジン（部品）として内部で何度も呼び出しながら、整数条件という巨大な迷路を探索するシステム」と言えます。この仕組みに基づいた、MIPソルバの得意領域と不得意領域は以下の通りです。
📊 MIPソルバの「得意領域」
MIPソルバは、ベースとなるLPソルバの「連続変数を高速に解く能力」を活かしつつ、「Yes/Noの論理条件」や「不連続な境界線」を数式に落とし込める領域で圧倒的な強みを発揮します。
  • 組み合わせと論理制約のモデリング
    • 0か1かで表される「投資する/しない」「拠点を置く/置かない」といった決定
    • 「Aを選ぶならBは選べない」といった複雑なビジネスルールの組み込み
  • 固定費と変動費の同時最適化
    • 工場を稼働させるだけで発生する「固定コスト（バイナリ変数）」と、生産量に比例する「変動コスト（連続変数）」が混在する問題
  • 大枠の「質的」なスケジュール管理
    • シフト管理、航空機のダイヤ編成、生産ラインの段取り替えなど
    • 「誰が・いつ・どのタスクを行うか」という割り当て問題
  • 厳密な最適性の評価（最適性ギャップの算出）
    • LP緩和（整数条件を無視した線形計画問題）を解くことで、「これ以上絶対に良くならない理論上の限界値（下界・上界）」を計算できる
    • これにより、途中で計算を止めても「現在の解が理論上最大で何%エラーを含んでいるか」がわかる
⚠️ MIPソルバの「不得意領域」
リニアソルバの観点から見たMIP最大の弱点は、「整数条件が一つ加わるだけで、問題の難易度が爆発的（NP困難）に跳ね上がる」という点にあります。
  • 変数の数が膨大な「巨大すぎる」問題
    • LPであれば数百万変数でも数分で解けますが、MIPでは数百の整数変数があるだけで、探索すべき組み合わせが天文学的数字（\(2^{100}\)など）になり、時間切れになることがあります。
  • 非線形（カーブや乗算）が絡む問題
    • ベースが「リニア（線形）」ソルバであるため、変数同士の掛け算（\(x \times y\)）や、曲線（二次関数や対数など）を直接扱うのが苦手です。
    • ※区分線形近似などで直線に分解すれば解けますが、数式が複雑化し計算速度が落ちます。
  • 秒単位・リアルタイムの応答が求められる制御
    • LPソルバのように「毎回決まった時間（多項式時間）で確実に解ける」という保証がありません。
    • データの条件が少し変わっただけで、一瞬で解けていた問題が突然数時間経っても終わらなくなる（挙動の不安定さ）性質があるため、リアルタイム制御には不向きです。
  • 順序や経路の「微細な」最適化
    • 巡回セールスマン問題（TSP）のような、純粋な並び替えやルート探索。
    • 解けないわけではありませんが、MIPとして定式化すると制約条件が膨大になりやすいため、メタヒューリスティクス（遺伝的アルゴリズムや局所探索法など）専用のアルゴリズムのほうが遥かに高速に解けるケースが多いです。
💡 まとめ（リニアソルバとの比較）
特徴LPソルバ（リニア）MIPソルバ
変数の種類実数（連続的な値）のみ実数 ＋ 整数・バイナリ
計算時間の予測予測しやすい（規模に比例）予測しにくい（爆発する可能性あり）
アプローチ傾きを滑らかに下る階段を一段ずつ、分岐しながら探す
主な用途配合比率、予算配分、最大流シフト、拠点配置、生産計画
現在、具体的な業務の最適化（シフト、物流、生産計画など）を検討されていますか？
もし差し支えなければ、どのような問題（解きたい課題）を想定しているか教えていただければ、MIPソルバが適しているか、それとも他の手法（ヒューリスティクスなど）が良いかアドバイスできます。




Q.整数条件が一つ加わって、難易度が上がる、具体例を簡単に示して。
最もわかりやすい例として、「100万円の予算で、利益を最大化する」という投資（あるいは仕入れ）のシミュレーションで考えてみましょう。
1. 整数条件がない場合（LP：リニア）
  • 設定： 1口50万円で、利益が60万円になる投資案件（案件A）があるとします。この案件は「0.1口」といった中途半端な量でも購入できるとします。
  • 解き方： リニアソルバは「一番効率が良いものを、買えるだけ買う」という判断をします。
  • 結果： 100万円 ÷ 50万円 ＝ ぴったり「2口」購入して、利益は120万円。
これは、坂道を一番高いところに向かってまっすぐ上るだけなので、一瞬で答えが出ます。
2. 【ここが問題】整数条件が「1つ」加わった場合（MIP）
  • 設定： 先ほどの条件に、「案件B：1口70万円で、利益が90万円（案件Aより効率が良い）」という選択肢が1つだけ加わったとします。
  • 条件： ただし、案件Bは不動産のようなもので、「1口丸ごと（整数）」でしか買えない（0.5口などは不可）という条件（整数条件）がつきます。案件Aはこれまで通り、いくらでも細かく分割して買えるとします。
一見、効率の良い案件Bを混ぜるだけなので簡単そうに見えますが、ソルバの頭の中は一気に複雑になります。
ソルバが考えなければならない分岐（迷路）：
  1. 案件Bを「0口」にする場合：
    • 残り予算100万円をすべて案件Aに使い、2口購入 ＝ 利益120万円
  2. 案件Bを「1口（70万円）」にする場合：
    • 残り予算は30万円。これを案件Aに使う（30万÷50万＝0.6口）
    • 利益は、案件B（90万）＋ 案件Aの0.6口分（36万）＝ 利益126万円
  3. 案件Bを「2口（140万円）」にする場合：
    • 予算オーバーなので却下。
🧠 なぜ難易度が上がるのか？
整数条件がない（LP）ときは、「傾き（効率）が一番良いものを限界まで突っ込む」という1つのルールだけで計算できました。
しかし、整数条件が「1つ」入っただけで、ソルバは「それを0個にするか、1個にするか、2個にするか…」というパターンをすべて独立した世界としてシミュレーション（分岐）し、それぞれで残りの予算配分を計算し直して、最後に結果を比較するという作業が必要になります。
今回は選択肢が「0, 1, 2」の3通りだけなので人間でもすぐ解けますが、これが「整数条件の変数が100個」になると、探索するルートが「2の100乗（天文学的な数）」に膨れ上がってしまうため、難易度が爆発するのです。
投稿者 時刻: 0 件のコメント:
登録: 投稿 (Atom)