3.8.11. 実数緩和について

次の数理計画問題を考えてみましょう．

\[\begin{split}\begin{array}{l} \bf{整数変数} \\ \hline x_{i}, \quad i \in \{1, 2\} \\ \hline \bf{制約} \\ \hline x_i \ge 0.1, \quad \forall i \\ \hline 2\sum_{i} x_i \le 3 \\ \hline \bf{目的関数(最大化)} \\ \hline \sum_{i} x_i \\ \hline \\ \end{array}\end{split}\]

実はこの問題には整数解は存在しませんが，実数変数であれば実行可能解が存在します． 次の例は数理計画問題を一度 整数計画問題として求解し，実行不可能だったら実数変数として解き直しています．:

def showresult(p, x):
    if p.isFeasible():
        print('feasible!')
        print(x.val)
    elif p.isInfeasible():
        print('infeasible!')
    else:
        print('some error!')

def problem(vartype):
    p = Problem(type=max, silent=True)
    i = Element(value=[1, 2])
    x = Variable(index=i, lb=0.1, type=vartype)
    p += 2*Sum(x[i]) <= 3
    p += Sum(x[i])
    p.solve()
    showresult(p, x)
    return p.isInfeasible()

is_infeasible = problem(int)
if is_infeasible:
    print('relax!')
    problem(float)

この出力は次のようになります．:

infeasible!
relax!
feasible!
x[1].val=0.7499999998309204
x[2].val=0.7499999998309204

上記の例ではほぼ同じ問題を再度定義しているため冗長と言えます． 変数の type 属性を後から変更できる性質を利用すると，問題はそのままで実数緩和を行うことができます．:

p = Problem(type=max, silent=True)
i = Element(value=[1, 2])
x = IntegerVariable(index=i, lb=0.1)
p += 2*Sum(x[i]) <= 3
p += Sum(x[i])

p.solve()
showresult(p, x)

if p.isInfeasible():
    print('relax!')
    x.type = float  # 実数変数に変更
    p.solve()
    showresult(p, x)

type 属性の変更には添字をつけることはできません．次の記述は誤りです．:

x[i].type = float