既存の問題と候補解を評価する

既存の問題と候補解を評価する#

手元の候補が問題の条件を満たすか、目的値はいくつかを、OMMXで確認します。Instance.evaluate()は与えた候補を検査する操作であり、より良い候補を探す操作ではありません。

このページでは、二次計画問題の公開ライブラリQPLIBの問題0018と、同じページの公開候補を読みます。問題を自分で構築する必要はありません。Pythonと通常の変数・目的関数・制約の知識があれば、ほかのTutorialを実行せずに進められます。

1. 問題と候補のファイルを用意する#

インストール手順に従ってPython SDKを用意してください。Notebookではその環境を実行カーネルに選びます。Adapterやソルバーは追加しません。

問題の.qplibファイルと候補の.solファイルを公式サイトから取得します。初回はインターネット接続が必要です。以下は作業ディレクトリのqplib-exampleフォルダーへ保存し、同名のファイルがある場合は再ダウンロードしません。

from pathlib import Path
from urllib.request import urlretrieve

data_dir = Path("qplib-example")
data_dir.mkdir(exist_ok=True)
for folder, extension in [("qplib", "qplib"), ("sol", "sol")]:
    filename = f"QPLIB_0018.{extension}"
    path = data_dir / filename
    if not path.exists():
        _ = urlretrieve(f"https://qplib.zib.de/{folder}/{filename}", path)

この問題はAndrea Scozzari氏からQPLIBへ提供されたもので、QPLIBはCC BY 4.0で公開されています。取得済みの二つのファイルをqplib-exampleへ置いた場合も、パスを定義するためにこのセルを実行してください。存在するファイルはダウンロードしないため、その場合はネットワーク接続は不要です。

2. 読み込んだ候補を評価する#

Instanceは変数・目的関数・制約をまとめた問題、Stateは変数IDから値への割り当てです。読み込んだだけでは、その候補が実行可能かは分かりません。evaluate()に両者を渡すことで、目的値と実行可能性を持つSolutionを得ます。

from ommx import Instance, State

instance = Instance.load_qplib(str(data_dir / "QPLIB_0018.qplib"))
state = State.load_qplib_solution(
    str(data_dir / "QPLIB_0018.sol"),
    num_variables=len(instance.decision_variables),
)
solution = instance.evaluate(state, atol=1e-8)

print(f"{solution.objective=}")
print(f"{solution.feasible=}")

solution.objective=-6.386014981598351
solution.feasible=True

objectiveはOMMXが問題の目的関数へ候補を代入して計算した値です。候補ファイルに書かれた目的値をそのまま採用するのではありません。この問題は最小化なので、実行可能な候補同士なら小さい目的値の方が良い候補です。feasible=Trueは、指定した許容誤差で変数の範囲・種類と制約を満たしたことを示します。ここでのatol=1e-8は、浮動小数点計算による微小なずれを許容する設定です。

num_variablesには、元のQPLIB問題の変数数を渡します。この.solでは値が0の変数が省略されていますが、この指定で50変数の割り当てを読み込めます。問題と候補は、必ず同じ問題に対応するファイルを使ってください。

3. 変数と制約の評価を読む#

この問題の変数は、0以上の連続値を取ります。次の表では値が0でない変数だけを表示します。idはOMMX内の変数ID、Continuousは連続変数、lowerとupperは下限・上限、valueは候補の値です。infは有限の上限を設けていないことを示します。

variables = solution.decision_variables_df()
variables.loc[variables["value"] != 0, ["kind", "lower", "upper", "value"]]
kind lower upper value
id
13 Continuous 0.0 inf 0.209637
16 Continuous 0.0 inf 0.275231
38 Continuous 0.0 inf 0.226998
40 Continuous 0.0 inf 0.288135

続いて、制約ごとの評価を見ます。この問題は変数の和を1とする制約を持ち、読み込み後は「和が1以下」「和が1以上」という2本の不等式で表されます。

columns = ["name", "equality", "value", "violation", "feasible"]
solution.constraints_df()[columns]
name equality value violation feasible
regular_constraint_id
0 Qplib_constr_0 [c_u] <=0 -5.551115e-17 0.000000e+00 True
1 Qplib_constr_0 [c_l] <=0 5.551115e-17 5.551115e-17 True

左端のregular_constraint_idは読み込み後の制約IDです。nameのc_uは上限側、c_lは下限側の条件を表します。

  • equalityが<=0の行では、制約の式を評価したvalueが0以下であることを要求します。

  • violationは違反の大きさです。負のvalueはこの不等式を満たすため、違反ではありません。

  • feasibleは許容誤差を含めた判定です。violationが約5.55e-17のように小さい正の値でも、今回の許容範囲ならTrueになります。

制約の表だけでは、変数の範囲や種類まで満たすかは分かりません。候補全体の判定にはsolution.feasibleを使います。

4. 条件を満たさない候補も調べる#

同じ問題に、全変数を0とした別の候補を与えてみます。IDは読み込んだInstanceから取り、各変数の値を明示します。

zero_state = State(
    {variable.id: 0.0 for variable in instance.decision_variables}
)
zero_solution = instance.evaluate(zero_state, atol=1e-8)
print(f"{zero_solution.objective=}")
print(f"{zero_solution.feasible=}")

constraints = zero_solution.constraints_df()
constraints.loc[~constraints["feasible"], columns]

zero_solution.objective=0.0
zero_solution.feasible=False
name equality value violation feasible
regular_constraint_id
1 Qplib_constr_0 [c_l] <=0 1.0 1.0 False

目的値0は計算できましたが、変数の和が1以上という下限側の条件に違反しています。feasible=Falseの行で、どの条件が満たされなかったかを調べられます。違反行の抽出には、微小な正のviolationではなく、この判定結果を使ってください。

ここまでで、既存の問題と候補を読み込み、目的値・実行可能性・制約の評価を確認できました。この処理は候補を探索していないため、公開候補が問題全体の最適解であることの証明にはなりません。

関連する説明#

目次