2025年10月27日月曜日

シフト最適化アルゴリズム

 下は、2017年にRAMPで使用したスライドです。

早いもので、これから8年が経ちました。シフト最適化に良いアルゴリズムは何か?というのは、私が、10年以上追い求めているテーマで、この講演時から、SATソルバの限界を感じていてMIPソルバの勉強を始めました。終生の目標として、未解決ナーススケジューリング問題を全問解くという、前人未到の目標を掲げて研究に取り組んできました。

このときは、感触でしかなかったのですが、今は、割に確信に近いイメージを持っています。一つの方式で全てのインスタンスを包含する最適アルゴリズムは存在しない、というイメージです。

<メタヒューリスティクスは無くならない>

ナーススケジューリング問題の黎明期は、メタヒューリスティクス開発の全盛期で、その後次々と、ベンチマーク問題がMIPソルバにより解かれ、メタヒューリスティクスは駆逐されたように思われています。確かに、そうした面はあります。

が、実務問題で厳密解が得られているか?という問いに対して、実は、スケジュールナースでも、最近は凝った制約の塊になることが多く、例えば、5年以上使いこなしているお客さまのプロジェクトを見ても、複雑化した制約が追加され、厳密解が得られることは、多くはない、という傾向が強まった、と思っています。

そして、超大規模のインスタンスに対しては、依然として、現実時間内に現実的な解を得るには、メタヒューリスティクスに頼らざるを得ない、ということではないかと思います。

学生さんがよく取り上げるテーマですが、既にベンチマークセットがあるので、それに対してどうだ?という比較で論じて欲しいと思います。単に実務問題で解けた、では価値がないと思います。

<SATソルバが得意なインスタンス傾向>

SATソルバは、数を数えるのが苦手です。線形制約は、全てブール演算から構成する必要があります。逆に言えば、数を数える場面がない、もしくは少ない場面では、無類の強さを発揮します。例えば、数独もその一つです。100x100の数独問題を解けるのは、今も昔も今後もSATソルバだけだと思います。そのような傾向の強いインスタンス、組み合わせ最適化問題には、SATソルバが最適です。

もう一つの傾向として、

■解空間/探索空間の比率が高いとき

に強さを発揮する傾向にあります。平たく言うとソフトエラーの数が少ないインスタンスは、強いということです。池上ベンチは、全ての制約がソフト制約で、その意味では、探索空間の枝刈りを行うことは出来ません。そのため、探索空間は確かに膨大なのですが、解空間も意外に広い、解の範囲が広範囲に分布しその比率は意外に高いのです。

こうしたインスタンスには探索中の学習が効果を発揮し、高速に求解出来ます。

<MIPソルバが得意なインスタンス傾向>

MIPソルバは、基本線形制約(SATソルバでいう基数制約)で記述します。AND/ORという非線形演算子は備えていないので、そういったオペレータが多いインスタンスは苦手です。で、何が得意かというと、

■数を数える

■解空間が狭い問題

が得意です。SATソルバが苦手な分野を補完しえるということです。Simplexや内点法といったLpソルバのリニア解を近傍探索するアプローチを取っています。基本、数を数えることしか出来ないのですが、それでも人間が作るインスタンスは、リニア解が近い傾向があり、解空間が狭い、地球上の一つの砂粒を探しだすような最適化問題には、LPソルバをベースにした方法しか考えられません。人間が扱うような問題は、リニア解近傍に最適解が存在することが多い、ということを前提としています。SATもMIPもランダムな制約には、全く持って歯が立たないのですが、現実の人間の営みのなかにあるエントロピーがそうさせているのでは?と考えています。

<ナーススケジューリング問題についてあてはめると>

スタッフ一人一人をRosterと言います。スケジュールナース用語では行制約ですが、Roster内演算は、多数のAND/OR演算が主で、僅かに公休数とか夜勤数といった数を数える場面があります。

一方、組織の品質を求める縦制約(列制約)については、ほぼ数を数えるだけです。つまりLPソルバにやらせた方が得策、ということになります。

従い、Rosterをサブ問題として、AND/OR演算を隠ぺいし、列制約を主問題としてLPソルバで扱うのが、一般的ナーススケジューリング問題に対する理にかなったアプローチ、ということが言えます。


<今後の潮流>

MIPでもなくSATでもない、否、MIPでもありSATでもある、新しい形態の数理ソルバが今後の厳密解ソルバの主役になっていきます。

現在、超大規模用にRefineする必要があり、一つ一つの求解部品を丹念に設計し直し組み上げていく作業の途中です。

オープン問題を全問解いたあとに論文化を予定しています。10年の研究成果が出るかどうかは未だ分かりません。

厳密解が分かれば、新しいメタ解法の開発に役立つと期待されます。



2025年10月26日日曜日

重い制約と軽い制約

 重い制約とは、ソルバ負荷が大きい制約のことを指します。軽い制約とは、ソルバ負荷が軽い制約を指します。ソルバ負荷が大きいとは、それを制約するのにメモリを食う制約を言います。メモリを食うというのは、一般に探索空間が大きい制約になります。探索空間とは、探索する状態の数を指します。つまり、ソルバ負荷が大きい制約は、探索するべき状態の数が大きい制約のことです。

およそ最適化シフト勤務表において、何が重い制約かは、ソルバの種類によらず一定の傾向があります。ここでソルバ種類とは、

■MIPソルバ(数理ソルバ)

■SATソルバ(MaxSATソルバ)

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

を指しますが、こういった種類によらず普遍的に重い制約を指します。重い制約とは、

1)シフト数が25を超える

2)パターン制約においてパターン長が長い

3)最大ー最小制約において最大値が大きい

になります。具体的には、パターン長で1週間を超えるような制約は避けるべきです。最大ー最小については、10個を超えると負担になってくるようなイメージを持っています。

勿論必要な制約であれば、使って構わないのですが、不要な負担は出来るだけ避けて頂くのが求解速度の関係で吉となります。

1)シフト数

シフトの割り当ては、1日に1個です。シフト数が2個なら 2状態しかありませんから全く負担にはなりません。シフトが32個あったとすると、32シフトのなかから1個を選ぶ必要があります。言い換えると1個以上かつ1個以下である必要があります。つまり、1個以上のORと取って、かつ全ての2個の組み合わせを禁止する必要があります。そうなると32C2の組み合わせを禁止する必要があり、32C2=32*31/2個分の組み合わせを禁止しなくてはいけません。2状態に対して指数関数的に状態空間が増えます。Days*Staff分で効いてきます。これが、最適化シフト勤務表においてシフト数は出来るだけ少なくしてください、と言っている理由です。

2)最大-最小制約

例えば、一カ月のうち、1日だけ働くを制約してみましょう。その組み合わせ状態数は、31C1で、31通りです。これに対して、16日働くことにすると31C16で601080390通りの組み合わせが存在します。これは、大変そうだな、というイメージになると思います。でも一カ月のうち30日働くは、31C30=31に過ぎません。なので、必ず大きな数程負担という訳ではないということになります。

特に、SAT系ソルバは、この制約がネックになることが多いです。

3)パターン長

何故長いパターンは負担なのでしょうか?シフトが2状態しかないABというパターンは、2状態のTreeで表現出来ます。



これが、4パターン長(16組み合わせ)では、


5パターン長(32組み合わせ)と増えていくと以下のようなイメージとなります。


7パターンは、以下です。



これが、1週間のパターン長での話です。指数関数的に組み合わせ状態数が増えて大変そうだな、ということを分かって頂けると思います。たった2シフトでのグラフですが、最初の1)シフト数が大きいと、さらに複雑なグラフとなります。シフト数が2)線形制約、3)パターン長、全てに効いてきます。


例えば、スケジューリングベンチマークinstance15では、

とありますが、これらは2パターンに過ぎず、ソルバの負担は軽いです。

しかし、以下のNo1.時間制約と、E6のシフトパターン制約は、重い制約の部類となります。



この中で最も軽い制約は、E7/E8 次いで、E5<E4<E3の順となります。



2025年10月25日土曜日

法政大学 野々部先生の講演

いつの間にか、久保先生とMOAIという会社を立ち上げられたようで、拝聴しました。

組合せ最適化問題に対する実用的アプローチ(第5回 MOAI研究部会 8月5日) - YouTube

面白く聴かせて頂きました。メタヒューリスティクスの実装の中身をここまで詳しく解説されているのは、見たことがありません。メタヒューリスティクスは、古くて新しい潮流があると思います。新しい潮流部分、戦略的摂動等について述べられているのが興味深いと思いました。「feasibilityの境界付近に最適解は存在する」は、確かに私も似たような経験をしたことがあったと思います。

野々部先生は、ナーススケジューリングコンペティションⅠで入賞されています。野々部先生のアルゴリズムは、Nuoptにも搭載され我が国におけるメタヒューリスティクスの第一人者です。

muc15_CR6_2.pdf



2025年10月24日金曜日

Highs Hypo

 A factorisation-based regularised interior point method using the augmented system

Highsの新しいIPMソルバの実装論文が出ました。

インスタンスによっては、10倍程度の向上もあったようですが、平均的には、期待したほどではありません。Leading SolverのCOPTとかの比較が論ぜられていないので、性能の相対位置が分からないのですが、トップとは未だ相当の性能差があると思います。監修者のJacek Gondzio氏は、IPM業界の重鎮でありIPMに関する論文を数多く出していて、期待していたのですが残念な結果となりました。

IPMは、旧新両方残るようです。旧IPMは、CROSSOVERなしにBasicSolutionを得ることが出来ます。(通常のIPMがCROSSVOERで時間を食ってしまうことを回避できるメリットがあります。)

一方、CuoptのBarrierは、GPUによる実装です。以下に記述があるのですが、GH200は、F1仕様のGPUで

NVIDIA GH200搭載のサーバのお値段 - Vengineerの妄想

であり、市井のGPUでどうなるか良くわかりません。

Solve Linear Programs Using the GPU-Accelerated Barrier Method in NVIDIA cuOpt | NVIDIA Technical Blog


いずれにしても、Cuoptは、高速化したPDLPX、IPMにしてもGPUによるDirect factoring が魅力であり、WSL2で試してみる必要があると考えます。(欲しいのは業界最高性能のLpソルバです。)

課題がまた増えてしまいました。

■整数化課題

■開発ソースをGCC化

■VisualStudio2022 WSL2で、Cuoptを評価、実装

これでは、年内かかってしまうと思います。しかし、業界最速のLpソルバであることは、間違いないと思います。これで時間さえかければ、最後に残った超大規模のオープンナーススケジューリング問題(探索空間10の82911乗,宇宙の素粒子の数は10の100乗程度)を解ける筈です。なんとか年内に解決したいと思います。こんなにも早く実装して頂いたNVIDIAのChristopher Maesさんに感謝したいと思います。


2025年10月23日木曜日

新しい整数化方法

 Feasibility Pumpは、Feasibleな解を見つけ出すには有用ですが、ここでの主題

1)規模が大きすぎてコンパイルできない

2)できるだけ浅いブランチで、最適化解を得る

という目的には合致していません。

そこで、新しい整数化方法が望まれます。

前に論じたように、Lp値は、時々間違った値が含まれることが、根本的な問題です。一方LP値自体は、真値最適化値に近いベクトルであることは間違いないので、これを利用しない手はありません。よって、主題は、

1)規模が大きすぎてコンパイルできない

2)できるだけ浅いブランチで、最適化解を得る

3)間違った固定化を行わない

ということになろうかと思います。上記に基づいて、現在設計中なのですが、どうなるかは未だ分かりません。少なくとも1)3)については、達成可能と見ていますが、肝心の2)については、やってみないと分かりません。これまで、多くの研究課題に取り組んできましたが、100の方法を試してモノになるのは、数個以下という実績です。

とにかく、やってみようと思います。

2025年10月22日水曜日

Feasibility とは?

 Feasibility PumpのFeasibilityとは何でしょうか? 実現可能性と訳されますが、OR用語でなじみがないと思います。これは、スケジュールナース用語にすると、「解がある」ということです。

「解が存在する」とは、ハード制約の全てを満足しているという状態を指します。スケジュールナースでは、よく「解がない」状態が出現します。ハード制約が一つでも満たせなければ、解は存在しません。この逆で、ハード制約の全てを満足しているという状態が、feasibleです。feasibleの反対が「解がない」です。

特に開発時には、見たくはないのですが、出てくる経験をした方も多いのではないでしょうか?まとめると、

「解がない」 ⇔ 「解が存在する」=Feasible

ということになります。シフト最適化を行う場合に、数理ソルバは一般に、

⇒Feasible ⇒最適化(コストの最小化)

という2段構えのプロセスとなります。最初に、ハード制約を全て満足する解を見つけて、其の後にコスト最小化となります。

数理ソルバの場合は、Feasibleと言い、SAT業界の場合は、

「解がない」=UNSAT ⇔ 「解が存在する」=Feasible =SAT

と言う対応になります。同じことを違う言葉で言っています。

ところで、スケジュールナースの場合、Feasibleは、どの時点で分かるのでしょうか?

実は、赤字がなくて o xxxが出たならば、既にfeasibleです。




上の例で、最初のo は、0.396secで出ています。この時点で、feasible、つまり全てのハード制約を満たしていて、以降は、ソフト制約の割り当て最適化を行っています。スケジュールナースの場合、このfeasibleに要する時間は、大抵の場合数秒以下です。もし10秒を超える規模のプロジェクトでしたら、それはかなりの大規模プロジェクト、ということが出来ます。時間のかかるのは、コスト最小化プロセスです。こういう風に解改善の様子が目で見て分かるシフト最適化ソルバは、スケジュールナース以外多分ないと思います。


2025年10月21日火曜日

instance23/24の整数化課題

現状、 二つの課題があります。

1)AL1でコンパイル出来ない問題

2)整数化方法の高精度化

AL3は、下記Branch and Priceです。コパイに整数化方法について聞いてみました。



LP(線形計画)ソルバから整数化する方法には、以下のような代表的なアプローチがあります。これは、連続変数を含むLP問題を整数制約付きの問題(整数計画問題)に変換する際に用いられます。


🔧 LPソルバから整数化する主な方法

1. 分枝限定法(Branch and Bound)

  • LP緩和問題を解いて得られた非整数解をもとに、変数に整数制約を加えた部分問題を分割。
  • 各部分問題を再帰的に探索し、最適な整数解を見つける。
  • 商用ソルバ(Gurobi、CPLEX)や無料ソルバ(SCIP、CBC)で広く使われている。

2. 分枝価格法(Branch and Price)

  • 分枝限定法に列生成(Column Generation)を組み合わせた手法。
  • 特に大規模な整数計画問題(例:車両経路問題)に有効。

3. 分枝制約法(Branch and Cut)

  • 分枝限定法にカット制約(Cutting Planes)を加えて、探索空間を効率的に削減。
  • LP緩和解が整数解でない場合、制約を追加して非整数解を排除。

4. 切断平面法(Cutting Plane Method)

  • LP緩和問題を解いた後、非整数解を排除するための不等式(カット)を追加。
  • Gomoryカットなどが代表例。

5. ラグランジュ緩和法

  • 一部の制約を目的関数にペナルティ項として組み込み、緩和問題を解く。
  • 組合せ最適化問題に対して近似解を得る手法としても使われる。

6. ヒューリスティック・メタヒューリスティック

  • 厳密解ではなく、実用的な近似解を得るための手法。
  • 例:局所探索、遺伝的アルゴリズム、焼きなまし法など。

🧠 実装面でのポイント

  • Pythonでは PySCIPOptPython-MIPPuLP などのライブラリを使って整数化が可能です。
  • モデル定義時に x = model.add_var(var_type=INTEGER) のように変数タイプを指定することで整数制約を加えられます。



コパイにFeasiblity Pumpについて聞いてみました。



Feasibility Pump(実現可能性ポンプ)は、混合整数計画問題(MIP)において**実行可能な整数解を素早く見つけるための発見的手法(ヒューリスティック)**です。特に初期解の探索や整数化の補助として使われます。


🔍 Feasibility Pumpの概要

  • 目的:LP緩和で得られる非整数解をもとに、実行可能な整数解を見つける。

  • 手法の流れ

    1. LP緩和問題を解いて連続解 ( x^* ) を得る。
    2. ( x^* ) の整数部分を丸めて整数ベクトル ( z ) を作成。
    3. ( z ) が制約を満たすかチェック。満たせば終了。
    4. 満たさない場合、目的関数を「( x ) と ( z ) の距離を最小化」に変更して再度LPを解く。
    5. 新しい ( x ) を得て再び丸める。
    6. このプロセスを繰り返すことで、実行可能な整数解に近づける。
  • 特徴

    • 厳密解ではなく、実行可能な解を早期に得ることが目的。
    • 分枝限定法の初期解として使うと探索効率が向上する。
    • SCIPやCPLEXなどのソルバではオプションとして有効化可能。

⚙️ 実装・設定例(SCIPやNUOPT)

  • feasibility pump はソルバのオプションで設定可能:

    • Branch.FeasPump.ON:有効化
    • Branch.FeasPump.OFF:無効化
    • Branch.FeasPump.AUTO:自動判定
  • Pythonライブラリ(例:PySCIPOpt)でも setHeuristicParam などで制御可能。


🧠 応用と研究動向

  • 強化学習と組み合わせた「スマートFeasibility Pump」も研究されており、より効率的な初期解探索が可能になると期待されています。

必要であれば、Pythonでの実装例や他の発見的手法(RINS、Divingなど)との比較もできますよ。どんな場面で使いたいか教えていただければ、より実践的なアドバイスをお届けします。



コパイに聞いてみました。



Rounding heuristics(丸めヒューリスティクス)は、線形緩和(LP relaxation)で得られた非整数解を整数解に変換するための近似手法です。整数計画問題(特に0-1整数計画)において、厳密解の探索が困難な場合に、実行可能かつ「そこそこ良い」解を得るために使われます。


🔧 主なRounding Heuristicsの種類

1. 単純丸め(Simple Rounding)

  • 各変数を0.5以上なら1、未満なら0に丸める。
  • 制約違反が起こりやすく、実行可能性は保証されない。

2. 乱択丸め法(Randomized Rounding)

  • 線形緩和で得た値を確率とみなし、コイン投げで0または1に決定。
    • 例:( x_i = 0.8 ) → 80%の確率で1、20%で0
  • 実装がシンプルで、理論的にも良好な近似性能を持つ。
  • 集合被覆問題やスケジューリング問題などでよく使われる。

3. 独立丸め法(Independent Rounding)

  • 各変数を独立に乱択丸めする。
  • 制約を満たす保証はないが、期待値ベースで性能分析が可能。

4. 制約付き丸め(Constraint-aware Rounding)

  • 制約を満たすように丸め方を調整。
  • 例:丸め後に制約違反があれば、修正ステップを挿入。

5. ラグランジュ丸め(Lagrangian Rounding)

  • ラグランジュ緩和で得た双対情報を使って丸める。
  • より構造的な問題に適用される。

🧠 応用と実装例

  • Pythonでの実装は numpy.random.rand() を使って乱択丸めが可能。
  • 実務では「最適解は不要、実行可能な近似解で十分」という場面で活躍。
  • 例えばシフトスケジューリングや施設配置問題などで、短時間で良好な解を得る手段として有効です。

📚 参考資料




RINSについても聞きました。



RINS(Relaxation Induced Neighborhood Search)は、混合整数計画問題(MIP)に対する**発見的探索手法(ヒューリスティック)**の一つで、既存の解とLP緩和解の情報を活用して、局所探索を行うアルゴリズムです。特に、分枝限定法の探索を補助する目的で使われます。


🔍 RINSの基本アイデア

  • 目的:既存の実行可能な整数解を改善するために、探索空間の一部(近傍)を限定して再探索する。
  • 手法の流れ
    1. 分枝限定法の途中で得られたLP緩和解現在の最良整数解を比較。
    2. 両者で一致している変数を固定し、一致していない変数のみを探索対象とする。
    3. この限定された近傍で新たなMIPを解くことで、より良い解を得る可能性がある。

⚙️ 特徴と利点

  • 探索空間の縮小:一致している変数を固定することで、探索空間が大幅に減少。
  • 高速化:限定された近傍での探索なので、計算時間が短くなる。
  • 改善効果:初期解の改善や探索の加速に寄与する。
  • ソルバ対応:Gurobi、CPLEX、SCIPなどの主要ソルバでRINSが組み込まれている。

🧠 応用例

  • 大規模なスケジューリング問題や配置問題で、分枝限定法単体では収束が遅い場合に有効。
  • 他のヒューリスティック(Feasibility Pump、Divingなど)と組み合わせて使われることも多い。

📌 参考情報

  • NUOPTやSCIPのマニュアルでは、RINSを有効化するオプションが用意されています。
  • 例えば SCIP では heuristics/rins/freqheuristics/rins/maxnodes などのパラメータで制御可能です。

RINSは「LP緩和解と整数解の差分に注目する」という点で、他のヒューリスティックとは一線を画しています。もし、具体的な問題に対してRINSを使いたい場合は、ソルバの設定やパラメータ調整のアドバイスもできますよ。

Sources: NTTデータ数理システム NUOPTマニュアル

Divingについても聞きました。

Diving(ダイビング)は、混合整数計画問題(MIP)におけるヒューリスティック手法の一種で、LP緩和解を出発点として、探索空間を深く潜っていくように局所探索を行うアルゴリズムです。特に、実行可能な整数解を素早く見つけるために使われます。


🧭 Divingの基本的な流れ

  1. LP緩和問題を解く
    線形計画の連続解(非整数解)を取得。

  2. 丸めや固定を行う
    LP解の中で「確信度の高い」変数を整数に固定。たとえば、0.99なら1に、0.01なら0に。

  3. 部分問題を解く
    固定された変数をもとに、残りの変数でLPを再解き、さらに丸める。

  4. 探索を継続
    実行可能な整数解が得られるまで、または制限時間・ノード数に達するまで繰り返す。


🔍 Divingのバリエーション

  • Fractional Diving:LP解で最も非整数度が高い変数から順に固定。
  • Objective Diving:目的関数の改善に寄与する変数を優先して固定。
  • Pseudo-cost Diving:過去の探索履歴から、分枝効果が高い変数を選ぶ。
  • Strong Diving:複数の候補を試して最も良い分枝を選ぶ(計算コスト高)。

⚙️ Divingの特徴と利点

  • 高速性:厳密な探索よりも高速に実行可能解を得られる。
  • 初期解生成:分枝限定法の初期解として有効。
  • ソルバ対応:SCIPやCPLEXなどでDivingヒューリスティックが組み込まれている。

📌 実装例(SCIP)

SCIPでは以下のようなパラメータで制御可能です:

  • heuristics/diving/freq:Divingの頻度
  • heuristics/diving/maxdepth:探索の最大深さ
  • heuristics/diving/strategy:使用するDiving戦略(fractional, objectiveなど)

Divingは「深く潜っていく」イメージ通り、探索空間の奥にある実行可能解を狙う手法です。Feasibility PumpやRINSと組み合わせることで、より強力な初期解探索が可能になります。

Sources: 東京大学 最適化アルゴリズムの基礎東北大学 情報システム評価学講義資料Wikipedia 整数計画問題





現状AL3で使用してヒューリスティクスは、AL1(MaxSAT)とRounding Heuristicsを組み合わせたものです。この方法は、特にRosterにソフト制約がないことが特徴のベンチマーク(ScheudlingBenchmarks)で、極めて有効であることが分かっています。

New Scehduling Benchmarks

しかし、課題もあります。Rounding Heuristicsでは、1.0を確率1、つまり正しい値として固定化(ハード制約化)してしまいます。実は、この変換がいつも正しい、という訳ではありません。実際Instance13/20で、ROOTにおけるLP値は、次のような分布になっていました。


これは、UBが得られたときのシフトを1として、それに対するROOTノードにおけるLP値を正規化したHistogramです。例えば、instance20における1の値が最もあり得ることを示していて、50%近くが正しい変換であることを示しています。0の割合が4%位で、完全に間違っている割合を示しています。これに対してinstance13の正解率は、3割程度で、間違っているのも15%位あることが分かります。このことから、instance13の方が深くDepthを稼がないと正解に近い値に辿り着けない、難易度が高い問題、と言うことが言えます。

この値は、ROOTでの値なので、Branchingを行っていけば、急速に正解率を上げることが出来ます。LPソルバが高速ならば、下手にヒューリスティクスを駆使するよりもDepthを深くした方が、早く真値UBを得ることが出来ます。

問題は、instance23/24のような大規模問題では、LPソルバが、とんでもなく遅いので、ヒューリスティクスに工夫を加えて、浅いDepthでも早期にUBを得る必要がある、ということです。つまり、

■単純なRounding Heuristicsよりも信頼度の高い方法で、

■大規模問題もコンパイルできる=(1)課題

方法を編み出すことが課題となります。この要件から、Rins,Diving,Feasiblity Pumpといった既存方法ではなく、新しい方法が必要とされています。

Lpソルバの方は、ほぼ最高性能のソルバを使うことが出来ます。RosteringGraphも予備データの収集が完了し目途がたちました。できる努力は、上記のみということになります。

2025年10月20日月曜日

Q.日付が小さ過ぎるのですがどうやったら大きくなりますでしょうか?

 Q.予定の日付が小さいです。(解日付は問題ないです。)






Ans. 

一度、任意のセルをダブルクリックして(セルサイズ縮小)




再度ダブルクリック(セルサイズ拡大)すると良いようです。



従い、

「予定セルをダブルクリックしてみる」

ことで対処をお願いできれば、と思います。現象からみて、「初期Viewでは、セルサイズ拡大時でもセルサイズ縮小時のフォントを用いている」 という設計になっていることが原因のように思います。
なお、次回リリース時に改善を検討したいと思います。

ご指摘ありがとうございました。

2025年10月19日日曜日

Cuopt mittlemann benchmarks

 25.10で1位となったようです。

plato.asu.edu/ftp/lpfeas.html

勿論、精度を無視した結果です。面白いのは、Defaultで、

PDLP,Dual Simplex,Barrierが並列に走ることです。GPUが動いている間は、CPUが遊んでいるので、それもアリだと思いますが、問題規模で最適ソルバは大体決まってしまうので実用的な意味はあまりないと思います。

ともあれ、最高性能のLPソルバは、これまで商用ソルバに頼るしかなかったのが、これからは、Cuopt/Highsが使えるようになります。



2025年10月18日土曜日

Q.11月のシフト作成にあたり、ソフトに希望を入力して求解を行ったところ、エラーが発生いたしました。

 Q.具体的には、夜勤希望を2名入力したにもかかわらず、求解の結果では3名が割り当てられていたり、夜勤属性が4回可能なスタッフに夜勤1回しか割り当てられていなかったりといった状況です。




Ans.

赤だらけの状態の解は、「解がない」状態での解です。「解がない」状態での解は、意味がありませんので見ないでください。見るべきは、エラーメッセージです。赤字で何か言っているはずです。エラーメッセージをよくご覧になってください。


赤丸部をダブルクリックすると当該エラー部に飛びます。ソフト制約レベル6のエラーです。


許容エラー数を超えているっぽいので、列制約レベル6の許容エラー数を3
→4にしてみます。


赤字エラーは消失し解は存在します。

これで、原因は、休みが6+3+1=10個入っていることが分かります。11月1日の予定を見てみると、確かに10個の休み(産休・研修も休みとカウントしています)となっています。変更前は、許容エラー3なので、6+3=9までが、許容範囲で、9<10なのでハードエラー(解がない)となります。


実際、解を見ても10個の休みとしてカウントされています。


以上です。

2025年10月17日金曜日

放射線技師勤務表2

 Githubにユーザサンプルプロジェクトを追加しました。

マニュアルは、

https://www.nurse-scheduling-software.com/japanese/publications/Automation_of_Radiological_Technologist_Rostering_with_Constraints2.pdf

直ぐ上にある放射線技師勤務表プロジェクトは、2の前身になります。ほぼこの状態で5年間お使い頂いた後に、今年6月に、呼び出し勤務(オンコール)を追加したい、とのことで、オンコール勤務をタスクとした、タスク型勤務表を設計しました。つまり、上記の主な差は、
シフト勤務表とタスク型勤務表にあります。同時に、日々の必要用人数をDailyで定義したいとのことでしたので、それについても追加しています。

二つのプロジェクトを見比べると、多くの制約が追加されていることが分かると思います。これらは、皆必要な制約です。

その対極にあるのが、
違いは、ユーザさまご自身が、解を見たときに、即座に良くない点を指摘できる かどうか?ということです。

今回、設計は私が行いましたが、改善設計については、ZOOM中、ご指摘に基づいてユーザさまと共に行いました。その共同での変更作業を通じて、プロジェクトの変更の仕方を学んで頂けたと思います。それにより、将来のメンテナンスに対しても、ユーザさまご自身で柔軟性を持って対処可能になると思います。

一つのカスタムプロジェクトの例ですが、

■職場の数だけ仕様が存在する
■職場の数だけプロジェクトが存在する
■自身のプロジェクトは、自身でメンテナンスする

というカスタムプロジェクトでありながら、ユーザ自身でメンテナンス出来る理想に近づいたと思います。業者にシステム化を頼んではみたものの、その後の対応やコストと言った面で満足されているでしょうか?それに対するスケジュールナース解にもなっていると思います。

2025年10月15日水曜日

Q.連休中に業務が重ならないように設定してもらっているのですが、日勤-夜勤入り,日勤ー日勤が割り当てられる場合がある

 Ans.

仕様は、連休中に呼び出しを配置しないものでした。






今回のご要求について、


を仕様追加しました。下記Pythonコード(Oct.01.2025)を修正・追加しました。



明け、ICCRCも不可につき、下記OCT042025も追加


以上です。

2025年10月14日火曜日

Q. Excel 管理シートではなく、スケジュールナース上で必要人数を変更したい

 Q.各部署の必要人数について任意の日程について、必要人数を設定するには、管理シートで変更可能なのですが予定入力を設定した後に、必要人数の変更しようとすると、再度、管理シートを変更しスケジュールナースに取り込まなければなりません。Excel 管理シートではなく、スケジュールナース上で必要人数を変更したい



Ans.

スケジュールナース上では、タスク予定の下の方に、日々の必要人数が、Excel管理シートからインポートされています。



この値を変更することで、必要人数を変更することが出来ます。上段が最大値、下段が最小値です。


値を変更したら、リフレッシュさせて、変更を確認してください。


2025年10月13日月曜日

Smoothie 各種MIPソルバをパラレルに走らせオープン問題に挑む試み

 Smoothie: Solver Mixing Object OrienTed Hybrid Integrated Executable

Mittleman Benchmarksサイトを眺めていると

plato.asu.edu/ftp/milp.html

上記に気づきました。COPTを1としたとき、Highsは、6.61になっていますが、これが、SCIPと組み合わせると、 4.14、まで向上する、ということのようです。ここまでくると商用ソルバに肉薄・匹敵すると言ってもよいと思います。

Highsは、さらにパラレルTreeサーチや、Lpソルバに新バリア法も準備中なので、今年中に、さらに飛躍することになると思います。

2025年10月12日日曜日

Cuoptでバリア法によるLPソルバがPR

 予想通り、Cuopt25.10で、PR(Pull Request)されたようです。

Barrier method for LPs with cuDSS sparse Cholesky / LDLT on the GPU (… · NVIDIA/cuopt@9f241a1

残念ながらWindowsのサポートはなく、WSL2でのみのようです。

Mittleman Benchmarkは、未だ掲載がありませんが、相当に期待されます。PDLPXも搭載されていて、その開発スピードは、素晴らしいです。いつの間にかDualSimplex(こちらはCPUのみ)も書かれています。crossoverも出来るようです。

バリア法は、CPUとのハイブリッドソルバ、PDLPXは、ほぼGPUソルバ,DualSimplexは、CPU onlyのソルバとなります。揃っているので、LP規模と用途において柔軟に選べると思います。これまでは、バリア法は、CPU onlyと思われていましたが、cuDSSや、cuSparseの利用によりハイブリッドアーキテクチャとしたところが新しい試みとなります。

Windowsで利用するには、WSL2ですので、スケジュールナース開発バージョンVisual Studio 2022をGCCに対応させる必要があります。それは、相当な労力を要するので、10月中は、HIGHS版が出るのを待ちたいと思います。それでもリリースされそうにないのならGCC化を検討したいと思います。



2025年10月11日土曜日

排他集合の確認

 下記で、「後休みの呼び出し回数」と「前休の呼び出し回数」は、互いに排他的な曜日集合である必要があります。


ここで、「前休」とは、「休みの前」を指します。休みの前のオンコール呼び出しの回数を指します。この曜日集合は、

一方、「後休」とは、休みの後、正確には、「前休」以外の全ての日になります。


「後休」と「前休」は、互いに交わることがなく、かつ、「後休」と「前休」を足すと全集合になります。このような集合を排他集合と言います。曜日集合では、しばしば、この排他集合が必要になります。

休み前の呼び出しカウントと、休み後の呼び出しカウントは、ダブってはいけないし、同時に、カウント取りこぼし日もあってはならない、こうした要求には、排他集合が必要になります。

それでは、どのようにして排他的であることを確認すればよいでしょうか?

排他的であることを確認するには、「かつ」オペレーションで、空集合、「または」オペレーションで、全集合(今月)を確認すれば、よいです。




2025年10月9日木曜日

列制約の目的は、「看護品質の向上」ではない

 列制約とは、縦の列のことです。


トップの日の看護品質、あるいは平均的な看護品質をさらに向上させることではありません。最も低い日の看護品質を引き上げて、一定以上の看護品質を保つことが目的です。全ての日が、一定水準以上になるように平準化することが目的になります。平たく言うと、全日に渡って医療事故を防止する、そのような看護師配置とすることが目的になります。

一般に、列制約については、かなり厳密に運用されていると思います。人力解でも上のような制約エラーが多発する勤務表を見ることは少ないです。これは、管理項目として、実際に日々縦のラインをチェックしている結果であると思います。これに対して、行制約の方は、一般に緩く、頂いた仕様に対して結構なエラーが生じる傾向にあります。恐らくは、列制約を満足させることを優先させ、看護師QOLについては、そこまで気を廻せない、ということではないか?と想像します。



<上記赤ラインを必要以上に高くとったときの問題>

下記は、人力では到底出来ないような複雑な列制約の結果です。多くの制約を満たしていません。

これに対して、予定を元に戻して


求解させれば、スケジュールナース解が出ます。


ほぼ、列制約エラーは、消えました。(初日に出ているのは、先月の人力解の影響です)

人力解とスケジュールナース解とでの比較でみると、

人力解の目的関数値は、UB=877


スケジュールナース解の目的関数値は、UB=141


となっていて、5倍以上の差が生じています。特に、重篤なエラーが少なくなっています。

それなら問題ないじゃないか?と思われるかもしれませんが、実は問題があります。

二つの問題が生じます。

(1)解空間が必要以上に狭まる

(2)メンテナンスが困難になる

メンテナンスのない勤務表は存在しません。組織変更、人事異動、退職、妊娠・出産等により、月々に変更することが付きまといます。制約が複雑であればあるほど程、融通が利かないので、誰かが制約を変更しなければならない確率が高まります。



<シンプルisベストがお勧め>

結論としては、現時点で運用中のルールをそのまま仕様化することをお勧めします。往々にして願望を仕様化すると、複雑で高すぎる制約となります。

スケジュールナースを使いこなす上でも、バランス感覚は必要です。Githubにも色々な実践的プロジェクトファイル例を挙げています。どれも、上のような複雑な列制約はありませんので参考にしてください。シフト最適化の第一歩は、仕様化です。職場の数だけ仕様があります。多くのシフト最適化勤務表をスケジュールナースのプロジェクトに落としてきた経験から言うと、この仕様化さえできれば、ほぼ間違いなく成功します。

仕様化は、職場のルールを言葉にすることです。頭の中にあるルールを書き出す、簡単なようでこれが最も難しいのです。そのためのコンシェルジェ、伴走サービスが、勤務表作成サービスです。看護師や介護士の最適化シフト勤務表作成の仕方については、以下の詳細なレクチャ資料があり、ある程度パターン化しているので、自力でプロジェクト作成する道もあります。


また、ペア禁止は、汎用的な手段で、経験的にかなり多くを記述しても問題が生じる可能性は低いです。参考にしてください。




2025年10月8日水曜日

仕様書は、願望ではなく、現在運用しているルールを書く

お客さまからシフト勤務の仕様書を頂いて、制約に落としプロジェクトファイルを作成しました。この仕様書は、看護師勤務表ですが、今までにない複雑で精緻な仕様でした。特に列制約記述が複雑でした。

 



下は、お客さまの勤務表解(人力解)をスケジュールナースの予定として入力し求解した結果です。Excelデータを整列させ、コピペし、予定入力としています。この際、EXCELデータシート上の勤務表名をスケジュールナースのシフトラベルとしています。これを求解させると、人力解に対して仕様違反の箇所をマークさせることが出来ます。

Excelデータ


Excel上で、2段を1段に整列。空白部を日勤ラベル.に置換


スケジュールナース予定にコピペ


求解



上記の通り、大量のエラーが表示されています。項目ごとに様相は、異なります、全くエラーがない項目もあります。大量のエラーが表示されている項目は、恐らく管理していないと思われます。

看護師長は、縦の列、日々の看護師組み合わせをチェックしている筈です。頭の中にある、ある基準ライン以下であれば、その候補解を却下することによって、一定以上の看護品質を確保してと思います。大量にエラーが出ている項目については、その作業を行っていない、つまり品質確保項目ではない、ということではないでしょうか? (逆に言えば、それがなくても品質は保てる)

できるだけ看護品質を高めたい、スケジュールナースなら何とかしてくれる?という気持ちの表れだと思いますが、仕様書は、願望を書くところではありません。

最適化シフト勤務表仕様書は、現実の今運用している、あるがままのルールを書く ようにしてください。

願望仕様による弊害は、後述します。