内容

備忘のため、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
- 目的関数は設定せず、制約条件を満たす組合せの候補を全て求めるようにしている。

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