内容
-
備忘のため、Googleの数理最適化ツールOR-Toolsの、cp_modelモジュールのCpModelクラスのAddBoolOrメソッドの使い方をまとめてみました。
-
「基本編 その1」では、AddBoolOrメソッドの動作を理解するためのサンプルコード(ハード制約)とその実行結果を紹介しています。
-
OR-Toolsのエキスパートの方には、少々退屈な内容かもしれません。初心者の方であれば、参考になるかもしれません。
注意
- 当方、OR-Toolsの初心者です。おおむね理解したつもりで書いていますが、もしかしたら間違っているところがあるかもしれません。ご容赦下さい。
AddBoolOrメソッド
- 数理最適化のモデルに、制約条件を加えるメソッドのひとつ。OR-ToolsのRef.では、以下のように記載されている。
def AddBoolOr(self, literals)
Adds Or(literals) == true.
(OR-ToolsのRef.より引用)
- literalsに、ブール変数のリストを指定すると、全てのブール変数がFalseとなる組合せを禁止し、その他の組合せを許容する制約条件が加えられる。
AddBoolOrの使い方の例(ハード制約条件の実装)
- cp_modelモジュールをインポートする。
from ortools.sat.python import cp_model
- CpModelクラスのオブジェクトを作る。
model = cp_model.CpModel()
- 最適化したい変数(ブール変数)のリストを定義する。
num_vars = 3
vars = [model.NewBoolVar("vars[%i]" % i) for i in range(num_vars)]
- 禁止したい変数の組合せを反転したリストを作る。ここでは、例として、以下の組合せを禁止することを想定している。
- vars[0]==True(=1), vars[1]==False(=0), vars[2]==False(=0)
negated_forbidden_lits = [vars[0].Not(), vars[1], vars[2]]
- 制約条件を加える。
model.AddBoolOr(negated_forbidden_lits)
- CpSolverクラスのオブジェクトを作る。
solver = cp_model.CpSolver()
- 制約条件を満たす組合せの候補を求める。その結果を表示する(解の候補を全て表示するため、VarArraySolutionPrinterクラスを使っている。)。
solution_printer = cp_model.VarArraySolutionPrinter(vars)
status = solver.SearchForAllSolutions(model, solution_printer)
サンプルコード
- 3つのブール変数vars[0], vars[1], vars[2]の組合せの候補を求めるプログラムの例。
- AddBoolOrを使って、以下の組合せを禁止する制約条件を加えている。
- vars[0]==1, vars[1]==0, vars[2]==0
- 目的関数は設定せず、制約条件を満たす組合せの候補を全て求めるようにしている。
- AddBoolOrを使って、以下の組合せを禁止する制約条件を加えている。
from ortools.sat.python import cp_model
def main():
# Creates model.
model = cp_model.CpModel()
# Defines variables, which will be optimized.
num_vars = 3
vars = [model.NewBoolVar("vars[%i]" % i) for i in range(num_vars)]
# Defines negated forbidden combination of variables.
# (Forbids the combination "vars[0]=1, vars[1]=0, vars[2]=0".)
negated_forbidden_lits = \
[vars[0].Not(), vars[1], vars[2]]
# Adds constraints.
model.AddBoolOr(negated_forbidden_lits)
# Solves the problem.
solver = cp_model.CpSolver()
solution_printer = cp_model.VarArraySolutionPrinter(vars)
# Writes all solutions and its statistics.
print("< Solutions >")
status = solver.SearchForAllSolutions(model, solution_printer)
print()
print("< Statistics >")
print("Status : %s" % solver.StatusName(status))
print("Number of solutions : %i" % solution_printer.solution_count())
print()
if __name__ == "__main__":
main()
サンプルコードの実行結果
- 以下の組合せを禁止する制約条件を加えているので、該当の組合せを除く7個(=2^3-1)の組合せが表示される。
- vars[0]==1, vars[1]==0, vars[2]==0
< Solutions >
Solution 0, time = 0.00 s
vars[0] = 0 vars[1] = 0 vars[2] = 0
Solution 1, time = 0.00 s
vars[0] = 0 vars[1] = 1 vars[2] = 0
Solution 2, time = 0.00 s
vars[0] = 0 vars[1] = 1 vars[2] = 1
Solution 3, time = 0.00 s
vars[0] = 0 vars[1] = 0 vars[2] = 1
Solution 4, time = 0.00 s
vars[0] = 1 vars[1] = 0 vars[2] = 1
Solution 5, time = 0.00 s
vars[0] = 1 vars[1] = 1 vars[2] = 1
Solution 6, time = 0.00 s
vars[0] = 1 vars[1] = 1 vars[2] = 0
< Statistics >
Status : OPTIMAL
Number of solutions : 7
制約条件をなくした場合の実行結果
- AddBoolOrをコメントアウトして、制約条件をなくすと、vars[0], vars[1], vars[2]の全ての組合せが表示されるようになる。
- Solution 5に、禁止されていた、以下の組合せが追加されている。
- vars[0]==1, vars[1]==0, vars[2]==0
< Solutions >
Solution 0, time = 0.00 s
vars[0] = 0 vars[1] = 0 vars[2] = 0
Solution 1, time = 0.01 s
vars[0] = 0 vars[1] = 1 vars[2] = 0
Solution 2, time = 0.01 s
vars[0] = 0 vars[1] = 1 vars[2] = 1
Solution 3, time = 0.01 s
vars[0] = 0 vars[1] = 0 vars[2] = 1
Solution 4, time = 0.01 s
vars[0] = 1 vars[1] = 0 vars[2] = 1
Solution 5, time = 0.01 s
vars[0] = 1 vars[1] = 0 vars[2] = 0
Solution 6, time = 0.01 s
vars[0] = 1 vars[1] = 1 vars[2] = 0
Solution 7, time = 0.01 s
vars[0] = 1 vars[1] = 1 vars[2] = 1
< Statistics >
Status : OPTIMAL
Number of solutions : 8