GurobiのFeasRelax機能は、「モデルの実行可能性を回復するためにどのような修正が必要か？」という課題に対処します。この記事では、このFeasRelax機能の使用方法を紹介します。 なお、How do I determine why my model is infeasible? は、実行不能性分析ツールのトピックをさらに詳しく説明しています。
Gurobiは、実行不能なモデルの実行可能性緩和を作成する model.feasRelaxS()とmodel.feasRelax() の2つの方法を提供しています（Python用および他のAPI用に対応するメソッドがあります）。feasRelaxSはfeasRelaxの簡易版です。この記事ではfeasRelaxSについて紹介しますが、feasRelaxもほぼ同様に利用できます。
Exampleの workforce3.py に示されているように、feasRelaxSを使用して、実行不能なモデルを実行可能にするために変更が必要な変数および/または制約の境界値を確認できます。以下のPythonスクリプトは緩和が必要な境界値を計算します。扱っている問題設定によっては、変数の境界値の変更、または制約の境界値の変更のみの変更に意味があるかもしれないことに注意してください。これはfeasRelaxSの第3および第4引数を介して設定できます。
import gurobipy as gp
from gurobipy import GRB
import sys
# "infeasible_model.mps.bz2" は適当な実行不能モデル
m = gp.read("infeasible_model.mps.bz2")
m.optimize()
status = m.Status
if status == GRB.UNBOUNDED:
print('モデルは非有界のため求解できません')
sys.exit(0)
if status == GRB.OPTIMAL:
print('最適な目的関数値は %g です' % m.ObjVal)
sys.exit(0)
if status != GRB.INF_OR_UNBD and status != GRB.INFEASIBLE:
print('最適化はステータス %d で停止しました' % status)
sys.exit(0)
# 境界を緩和してモデルを実行可能に修正
print('モデルは実行不能です。 境界値を緩和しています')
orignumvars = m.NumVars
# 変数の境界のみを緩和
m.feasRelaxS(0, False, True, False)
# 変数の境界と制約の両方を緩和する場合
# m.feasRelaxS(0, False, True, True)
m.optimize()
status = m.Status
if status in (GRB.INF_OR_UNBD, GRB.INFEASIBLE, GRB.UNBOUNDED):
print('緩和されたモデルは求解できません \
非有界または実行不能です')
sys.exit(1)
if status != GRB.OPTIMAL:
print('最適化はステータス %d で停止しました' % status)
sys.exit(1)
# 緩和の人工変数の値を表示
print('\nスラック変数の値:')
slacks = m.getVars()[orignumvars:]
for sv in slacks:
if sv.X > 1e-9:
print('%s = %g' % (sv.VarName, sv.X))
このスクリプトのスラック値の出力は例えば次のようになります:
スラック値::
ArtU_varname1 = 1
ArtL_varname2 = 2.79911e-06
ArtP_constrname1 = 1.57294e-04
ArtN_constrname2 = 2
変数の境界値について、スラック変数は「ArtU_」または「ArtL_」で始まり、その後に元の変数の名前が続きます。「ArtU_」で始まる場合は、元の変数の上限を増加させる必要があることを意味し、「ArtL_」で始まる場合は、元の変数の下限を減少させる必要があることを意味します。上記の出力では、varname1の上限を1増加させ、varname2の下限を2.79911e-06減少させる必要があります。
制約の境界について、スラック変数は「ArtP_」または「ArtN_」で始まり、その後に元の制約の名前が続きます。「ArtP_」で始まる場合は、制約のRHS（右辺）を減少させる必要があることを意味し、「ArtN_」で始まる場合は、RHSを増加させる必要があることを意味します。上記の出力では、constrname1のRHSを1.57294e-04減少させ、constrname2のRHSを2増加させる必要があります。
与えられたスラック値に従って元のモデルファイルを変更することで、実行可能なモデルが生成できるはずです。
また、1e-07やそれ以下の小さなスラック値も、デフォルトのFeasibilityTolを下回っていたとしても重要である可能性があることに注意してください。これは特に数値的に難しい問題(数値的に不安定な問題)に当てはまります。
もしrelaxobjtype=2（model.feasRelaxS()およびmodel.feasRelax()の最初の引数）が指定されている場合、実行可能性緩和の目的関数は、境界および制約違反の総数を最小化することです。この場合、バイナリ変数も実行可能性緩和に関与します。これらのバイナリ変数の名前は「ArtUB_」、「ArtLB_」、「ArtPB_」または「ArtNB_」で始まり、それぞれ変数と制約の名前が続きます。バイナリ変数は、どの変数および/または制約を緩和する必要があるかを示します。
実現可能性緩和モデルをさらにカスタマイズするには、 Model.feasRelax()メソッドを使用して：
- どの特定の変数または制約が緩和の対象とされるかを制御できます。
- 各変数の境界および制約に対するペナルティをカスタマイズできます。