5. モデルの定式化

組合せ最適化問題は、決定変数と目的関数、制約条件からなります。 「2. 決定変数の作り方」、「3. 多項式と目的関数」、「4. 制約条件」では、 決定変数は VariableGenerator を用いて作成することができ、 目的関数と制約条件は PolyConstraint によって表現することができることを解説しました。

このページでは、これらを組み合わせて、組合せ最適化問題をプログラムコード上で表現する方法について解説します。

参考

Poly クラスのほかに係数行列形式 Matrix クラスのインスタンスも目的関数として使用することができます。 目的関数が Matrix として表現されている場合も、このページで解説する内容と全く同様に使用することができます。

係数行列形式についての詳細は「係数行列による目的関数の作成」を参照してください。

5.1. モデルの構築

Amplify SDK において、組合せ最適化問題は Model クラスのインスタンスとして表現されます。

目的関数と制約条件が両方ある組合せ最適化問題を表現するには、目的関数を表す Poly と制約条件を表す Constraint または ConstraintList を加算するのが簡単な方法です。

from amplify import VariableGenerator, Model, equal_to, one_hot

gen = VariableGenerator()
q = gen.array("Binary", shape=(2, 3))

objective = q[0, 0] * q[0, 1] - q[0, 2]
constraint1 = equal_to(q[0, 0] + q[0, 1] - q[0, 2], 0)
constraint2 = one_hot(q[1, :])
constraint_list = constraint1 + constraint2
  • 目的関数と制約条件を足してモデルを構築する:

    >>> model = objective + constraint1
    >>> print(model)
    minimize:
      q_{0,0} q_{0,1} - q_{0,2}
    subject to:
      q_{0,0} + q_{0,1} - q_{0,2} == 0 (weight: 1)
    
  • 目的関数と制約条件リストを足してモデルを構築する:

    >>> model = objective + constraint_list
    >>> print(model)
    minimize:
      q_{0,0} q_{0,1} - q_{0,2}
    subject to:
      q_{0,0} + q_{0,1} - q_{0,2} == 0 (weight: 1),
      q_{1,0} + q_{1,1} + q_{1,2} == 1 (weight: 1)
    

目的関数のみまたは制約条件のみからなる組合せ最適化問題を表現するには、 Model クラスのコンストラクタに、目的関数を表す Poly (または Matrix) のインスタンス、あるいは制約条件を表す Constraint または ConstraintList のインスタンスを渡します。

  • 目的関数 (Poly) からモデルを構築する:

    >>> model = Model(objective)
    >>> print(model)
    minimize:
      q_{0,0} q_{0,1} - q_{0,2}
    
  • 単一の制約条件オブジェクト (Constraint) からモデルを構築する:

    >>> model = Model(constraint1)
    >>> print(model)
    minimize:
      0
    subject to:
      q_{0,0} + q_{0,1} - q_{0,2} == 0 (weight: 1)
    
  • 複数の制約条件オブジェクト (ConstraintList) からモデルを構築する:

    >>> model = Model(constraint_list)
    >>> print(model)
    minimize:
      0
    subject to:
      q_{0,0} + q_{0,1} - q_{0,2} == 0 (weight: 1),
      q_{1,0} + q_{1,1} + q_{1,2} == 1 (weight: 1)
    

モデルを構築したあとで、制約条件 (Constraint または ConstraintList) を追加することもできます。

>>> model = Model(objective)
>>> print(model)
minimize:
  q_{0,0} q_{0,1} - q_{0,2}
>>> model += constraint1
>>> print(model)
minimize:
  q_{0,0} q_{0,1} - q_{0,2}
subject to:
  q_{0,0} + q_{0,1} - q_{0,2} == 0 (weight: 1)

モデルが目的関数を多項式 Poly クラスのインスタンスで持つ場合には、目的関数の加算と減算も可能です。

>>> model += q[0, 0] * q[0, 1]
>>> print(model)
minimize:
  2 q_{0,0} q_{0,1} - q_{0,2}
subject to:
  q_{0,0} + q_{0,1} - q_{0,2} == 0 (weight: 1)
>>> model -= q[0, 0]
>>> print(model)
minimize:
  2 q_{0,0} q_{0,1} - q_{0,0} - q_{0,2}
subject to:
  q_{0,0} + q_{0,1} - q_{0,2} == 0 (weight: 1)

5.2. モデルのアトリビュート

objective プロパティにより、Model クラスが持っている目的関数を取得することができます。

from amplify import VariableGenerator, equal_to

gen = VariableGenerator()
q = gen.array("Binary", 2, 3)

objective = q[0,0] * q[0,1] - q[0,2]
constraint = equal_to(q[0,0] + q[0,1] - q[0,2], 0)
model = objective + constraint
>>> print(model.objective)
q_{0,0} q_{0,1} - q_{0,2}

constraints プロパティにより、Model クラスが保持している制約条件を取得することができます。このプロパティは ConstraintList クラスのインスタンスを返します。

>>> print(model.constraints)
[q_{0,0} + q_{0,1} - q_{0,2} == 0 (weight: 1)]

注釈

モデルは目的関数と制約条件をコピーせずに格納します。そのため、モデルに含まれる目的関数や制約条件を変更すると、構築前の変数も変更されることに注意してください。

model = Model(objective)
model += q[0, 0]
assert model.objective == objective

5.3. モデルに含まれる制約条件の重みを変更する

モデルの構築後に、モデルが含んでいる制約条件の重みを変更したい場合があります。

注釈

制約条件の重みの調整に関しては「ペナルティ関数の重み」を参照してください。

以下の例では、特定の制約条件の重みを 2 倍にします。

>>> print(model)
minimize:
  q_{0,0} q_{0,1} - q_{0,2}
subject to:
  q_{0,0} + q_{0,1} - q_{0,2} == 0 (weight: 1)
>>> model.constraints[0] *= 2
>>> print(model)
minimize:
  q_{0,0} q_{0,1} - q_{0,2}
subject to:
  q_{0,0} + q_{0,1} - q_{0,2} == 0 (weight: 2)