候補を評価して結果を判断する#
ソルバーやサンプラーの出力、あるいは人が用意した計画など、すでに候補が手元にある場合にもOMMXを使えます。共通の問題表現に照らして、どの条件を満たすか、目的値はいくつか、ほかの指標はどうなるかを評価できます。OMMX Adapterで求解することは前提ではありません。
結果を比較する前に、どの問題に対する評価かを揃えます。 ソルバーに渡した問題では許される候補でも、準備の途中で外した条件には違反することがあります。変数の値を復元すること、実行可能性を確認すること、最適性を示すことは、それぞれ別の問いです。
解く問題と、検査する条件を分ける#
ある生産ラインは通常運転では毎時100個まで、低速運転では毎時60個まで生産できます。担当者が毎時65個の計画を提案したとします。通常運転ならこの生産上限を満たし、低速運転なら上限を5個超えます。探索時にソルバーが低速運転の上限を無視できたとしても、元の要件での判定は同じです。候補を判断するには生産量と運転モードの両方が必要です。
ソルバーの出力にも担当者が作った計画にも、同じ検査を使えます。この上限を満たしたら、ほかの制約と変数の定義域も確認します。すべてを満たす実行可能な計画でも、別の計画のほうがよい目的値を達成する可能性があります。
OMMXは、ソルバーに課す条件から外した制約も保持できます。現在課している制約を active、外したあとも保持する制約を removed と呼びます。そのため、activeな条件を満たすかと、保持した条件をすべて満たすかを区別して評価できます。整数性やboundといった変数の定義域は、どちらの判定でも考慮します。
特殊制約を同じ条件を表す通常制約へ置き換えた場合や、制約を目的関数のpenalty項へ変えた場合にも、元の制約をremovedとして保持します。removedは変更の記録であり、それがあることだけでは元の問題を保存する変換かどうかは分かりません。特に有限のpenalty weightでは、元の条件に違反する候補が選ばれる可能性があります。
返された値と保持された条件を解釈するには、その求解で使った問題を表す変換済みInstanceを使います。ただし、その評価を元の問題についての判定とみなす前に、変換の保証を確認してください。情報が保持されていること自体は、すべての変更が元の実行可能領域や最適解を保存した証明にはなりません。
実行可能性の判定と違反の調べ方はSolutionのReference、保持するデータとactiveな制約との関係はremoved constraintsのReferenceにまとめています。
復元した値と、補った値を区別する#
準備の途中で変数を固定したり、別の変数の式で表したりすると、ソルバーが選ぶ値を減らせます。OMMXは記録された固定値や式を使って、省略された値を復元します。例えば変換によって \(y=2z\) が記録されていれば、返された \(z=1\) から \(y=2\) を得られます。ただし、この計算ができることだけでは、元の条件をすべて満たすことや、元の候補をすべて表現できることは分かりません。
現在の問題に無関係な変数は、これとは異なります。値を省略した場合、OMMXは既定値で補うことができます。その値はソルバーが選んだ値でも、元の候補から復元した値でもありません。保持した制約や報告用指標には影響する場合があるため、特定の候補について判断したいときは、その候補の値を渡します。
現在の問題に必要な値が欠けている場合に、任意の既定値で埋めることはありません。役割の分類、既定値の規則、整合性の検査、実行できる例は値の復元・補完のReferenceにあります。
報告目的値とソルバーの状態を、その文脈で読む#
ソルバー向けの目的関数と、利用者へ報告する目的関数は異なることがあります。\(3x\) の最大化は \(-3x\) の最小化で表せるため、同じ \(x=1\) に対してソルバー向けの値は \(-3\)、元の値は \(3\) です。出力用の目的関数を保持している場合、OMMXは結果にその目的値を返します。正確な動作は出力目的関数のReferenceを参照してください。
Penalty化した問題でも、報告目的値にはソルバーが使うpenaltyが含まれない場合があります。報告目的値がよいことだけでは、実行可能性は分かりません。条件を満たすかは別に確認します。
例えば、Binary変数 \(x\) を最小化する問題の制約 \(x=1\) を、penalty項 \(0.5(x-1)^2\) に置き換えます。\(x=0\) ではソルバー向けの目的値が \(0.5\)、元の目的値が \(0\) になり、\(x=1\) ではどちらも \(1\) です。Penalty化した問題は、元の制約に違反する候補を選びます。報告目的値だけの比較や、それをソルバーのpenalty込みの値とみなす読み方では、この違いを捉えられません。
候補の評価だけでは最適性も分かりません。時間制限で終了したソルバーが実行可能な候補を返すことも、多数のサンプルから選んだ候補が観測した範囲で最良でも大域的には最適でないこともあります。ソルバーの最適性の主張は実際に解いた問題に対するものであり、別の表現へ引き継ぐには変換の保証が必要です。最適性の引継ぎのReferenceで扱います。
Backendの診断情報は、なぜ終了したか、探索がどこまで進んだかを読むためのものです。boundはソルバーが解いた問題の最適値の範囲を限定し、gapはbackendの定義に従った隔たりを示します。符号・スケール・penaltyが変わる場合、どちらも報告目的値と同じ尺度とは限りません。
例えば最小化問題で、見つかった最良の実行可能な候補の目的値が120、証明された下界が100なら、最適値は100から120の間にあります。前者がprimal bound、後者がdual boundで、最大化では上下の役割が逆になります。進捗グラフでは、探索によってこの範囲がどう狭まるかを読みます。両者が一致する前に探索が終了することも、候補が見つかるまで有限なboundが得られないこともあります。報告される相対gapはbackendの定義に従うため、単なる区間の幅とは異なります。
収集方法、各fieldの意味、実行例はSCIPとHiGHSの診断情報のReferenceにあります。SCIPのReferenceには、実際の求解で上下界が近づき、gapが縮まる様子を示す図があります。途中の記録は観測値なので、最終的な結果は終了報告で確認します。
同じ基準で候補を比較する#
共通の評価によって異なる解法の結果を比較しやすくなりますが、比較する基準を揃える必要があります。
問題の版と数値条件、および候補の値と変数の対応。
実行可能性を判定する制約・変数の定義域・数値的な許容誤差。
順位付けに使う目的関数、最大化・最小化の向き、penaltyの扱い。
SampleSetは、与えた候補の評価と選択を支援します。その最良候補は、選んだ基準でその候補集合の中で最良という意味です。解法自体を比較する場合は、時間制限などの実行条件も別に考慮します。Adapter比較のReferenceには、同じモデルをHiGHSとSCIPで解き、結果を比較して変数値を図示する完全な使用例があります。
業務上の判断には、目的値以外のコストや距離などが必要なこともあります。名前付き関数なら、最適化する対象を変えずに指標を評価できます。名前による結果抽出では、業務上のラベルを使って値を取り出せます。結果をアプリケーションへ戻すための機能であり、実行可能性や最適性の保証を追加するものではありません。