3.8.9. LP の値を丸めて MILP の近似解を得るテクニック¶
混合整数線形計画問題(MILP)は線形計画問題(LP)に比べ難しく，実行可能解や最適解が求まらないこともあります． 一方で MILP の整数変数を連続変数に緩和した問題(連続緩和問題)は線形計画問題のため，ずっと簡単になります． 本項では連続緩和問題の丸め値を元問題の近似値として与えることで近似解を求める手法を紹介します．:
def problem(type):
x = Variable(type=type, lb=0, ub=5)
y = Variable(lb=0, ub=5)
p = Problem()
p += 180*x + 160*y
p += 6*x + y >= 12
p += 4*x + 6*y >= 24
return p
rp = problem(type=float) # 連続緩和問題(rp は relaxed problem の頭文字)
rp.solve() # 連続緩和問題を解く(LP なので簡単)
rx = rp.variables['x']
rx[rx.index] = round(rx.val) # 整数値に丸めた値を設定
rx.fix() # x の値を固定
rp.solve()
print(rx.val, rp.objective.val)
problem は type=int とすれば元問題の MILP を，type=float とすればその連続緩和問題を返す関数です． fix メソッドは変数の上下限を現在の値に固定します．すなわち今回の場合は「rp += rx == rx.val」という制約と 同じ意味ですが，fix は制約ではなく上下限扱いとなります． また，後述の unfix で固定状態を細かく制御できる点でも異なります．
連続緩和問題で得られた x の値(実数値)を整数に丸めて固定し，再求解することで MILP を解くことなく 整数性を満たした求解を行っています． ただし，この解はあくまで近似解であり，実行可能解である保証もありませんが，元問題が難しい場合は 検討の余地があるでしょう． また，丸め値を設定する箇所は「rx = ...」と記述できないことに注意しましょう． このように記述してしまうと rx の参照先が上書きされてしまいます． なお，「rx[rx.index] = ...」という記述は添字の有無に拘わらず利用できます．
上記では元問題の整数変数が x ひとつでしたが，以下のように汎用的に記述することで， モデルに含まれるすべての整数変数に丸め値を固定することができます．:
p = problem(type=int) # 元問題(MILP)
rp = problem(type=float) # 連続緩和問題(LP)
rp.solve()
for rvar, var in zip(rp.variables.values(), p.variables.values()):
if var.type is not float: # 元問題で整数変数の変数のみ
rvar[rvar.index] = round(rvar[rvar.index].val)
rvar.fix()
rp.solve()
print(rp.objective.val)
以下に今回用いた問題の最適解をまとめておきます．(IP は参考)
class |
x.type |
y.type |
x.val |
y.val |
目的関数値 |
|---|---|---|---|---|---|
LP |
float |
float |
1.5 |
3.0 |
750.0 |
MILP |
int |
float |
2.0 |
2.7 |
786.7 |
IP |
int |
int |
2.0 |
3.0 |
840.0 |
連続緩和問題で得られた x の値 1.5 を整数に丸めた値 2.0 は元問題における最適解と一致していますが， 偶然であることに注意しましょう． 実際，x の値を 1.0 に丸めた場合は実行不可能となります． 実行不可能な場合に一部の整数変数の固定を解除するといった対応を考えてみましょう．
次の例は，一度 fix メソッドで固定した変数の値の一部を unfix メソッドを用いて解除しています． このような部分的な解除は制約式では行うことができません．:
i = Element(value=[1, 2, 3])
z = IntegerVariable(index=i, lb=10, init=20)
p = Problem()
p += Sum(z[i])
z.fix() # p += z[i] == z[i].val, 'cons' と意味は同じ
p.solve()
print(z.val) # {1: 20, 2: 20, 3: 20}
z[2].unfix() # del p['cons'][2] はできない
p.solve()
print(z.val) # {1: 20, 2: 10, 3: 20}