重み付き制約充足問題
変数 $x_j (j=1,2,\ldots,n)$ に対して有限集合から成る領域 (domain) $D_j$ を定義する.
制約 $C_i (i=1,2,\ldots,m)$ は変数の $n$ 組の部分集合として定義される. 制約充足問題(constraint satisfaction problem)は,制約を満たすように, 変数に領域の中の1つの値を割り当てることを目的とした問題である.
これの判定問題版(解があるか否かを判定する問題)が,最初の$NP$-完全問題として知られる制約充足問題 (satisfiability problem; SAT) である.
この問題は実行可能性判定問題の範疇に含まれるが,これに制約からの逸脱ペナルティを付加することによって,以下の組合せ最適化問題になる.
解ベクトル $x$ が制約 $C_i$ から逸脱している量を表すペナルティ関数を $g_i (x)$ とする. 各制約 $C_i$ の重みを $w_i$ としたとき,重み付き制約充足問題(weighted constraint satisfaction problem)は以下のように書ける.
$$ \begin{array}{lll} minimize & \sum_{i=1}^m w_i g_i(x) & \\ s.t. & x_j \in D_j & j=1,2,\ldots,n \end{array} $$この問題に対しては,メタヒューリスティクスに基づく制約最適化ソルバーSCOP (Solver for COnstraint Programing)が開発されている. SCOPについての詳細は,付録1を参照されたい.
SCOPは実務的な問題を解くために開発されたものであるが,様々な基本的な組合せ最適化問題も簡単に解くことができる. 例として,グラフ彩色問題のところで,SCOPを用いた数行の最適化コードを示している.
実務的な問題の例としては,シフトスケジューリングのことろで,看護婦スケジューリング問題のモデル化を示している. 以下では,もう1つの実務的な例として,時間割作成問題への適用を考える.
時間割作成問題
通常の時間割作成の他に,大学では試験の時間割などにもニーズがある.
次の集合が与えられている.
- 授業(クラス)集合: 大学への応用の場合には,授業には担当教師が紐付けられている.
- 教室集合
- 学生集合
- 期集合:通常は1週間(5日もしくは6日)の各時限を考える.
以下の条件を満たす時間割を求める.
- すべての授業をいずれか期へ割当
- すべての授業をいずれか教室へ割当
- 各期、1つの教室では1つ以下の授業
- 同じ教員の受持ち講義は異なる期へ
- 割当教室は受講学生数以上の容量をもつ
- 同じ学生が受ける可能性がある授業の集合(カリキュラム)は,異なる期へ割り当てなければならない
考慮すべき付加条件には,以下のものがある.
- 1日の最後の期に割り当てられると履修学生数分のペナルティ
- 1人の学生が履修する授業が3連続するとペナルティ
- 1人の学生の授業数が、1日に1つならばペナルティ($0$ か $2$ 以上が望ましい)
これは制約最適化問題として以下のように定式化できる.
授業 $i$ の割り当て期を表す変数 $X_i$ (領域はすべての期の集合)と割り当て教室を表す変数 $Y_i$ (領域はすべての教室の集合)を用いる.
定式化では,これらの変数は値変数として表記する. それぞれ, 授業 $i$ を期 $t$ に割り当てるとき $1$ の $0$-$1$ 変数 $x_{it}$, 授業 $i$ を教室 $k$ に割り当てるとき $1$ の $0$-$1$ 変数 $y_{ik}$ となる.
SCOPにおいては,以下の2つの制約は自動的に守られるので必要ない.
- すべての授業をいずれか期へ割当
- すべての授業をいずれか教室へ割当
他の制約は,以下のように記述できる.
各期 $t$ の各教室 $k$ への割り当て授業は1以下であることを表す制約: $$ \sum_{i} x_{it} y_{ik} \leq 1 \ \ \ \forall t,k $$
同じ教員の受持ち講義は異なる期へ割り当て:
教員 $l$ の担当する授業の集合を $E_l$ とすると,この制約は 「$X_{i} (i \in E_l)$ はすべて異なる値をもつ」と書くことができる. SCOPでは,このようなタイプの制約を相異制約とよび,そのまま記述できる.
- 割当教室は受講学生数以上の容量をもつ.
授業 $i$ ができない(容量を超過する)教室の集合を $K_i$ する.
$$ \sum_{i, k \in K_i} y_{ik} \leq 0 $$- 同じ学生が受ける可能性がある授業の集合(カリキュラム)は,異なる期へ割り当てなければならない.
カリキュラム $j$ に含まれる授業の集合を $C_j$ としたとき,以下の制約として記述できる.
$$ \sum_{i \in C_j} x_{it} \leq 1 \ \ \ \forall j, t $$- 1日の最後の期に割り当てられると履修学生数分のペナルティ
1日の最後の期の集合を $L$, 授業 $i$ の履修学生数を $w_i$ とする. $$ \sum_{i, t \in L} w_i x_{it} \leq 0 $$
- 1人の学生が履修する授業が3連続すると1ペナルティ
$T$ を1日のうちで最後の2時間でない期の集合とする. $$ \sum_{i \in C_j} x_{it} + x_{i,t+1} +x_{i,t+2} \leq 2 \ \ \ \forall j, t \in T $$
- 1人の学生の授業数が、1日に1つならば1ペナルティ(0か2以上が望ましい)
各日 $d$ に含まれる期の集合を $T_d$ とし, 日 $d$ におけるカリキュラム $j$ に含まれる授業数が $0$ か $2$ 以上なのかを表す $0$-$1$ 変数 $z_{jd}$ を用いる.
$$ \sum_{i \in C_j} x_{it} \leq |T_d| z_{jd} \ \ \ \forall d, j $$$$ \sum_{i \in C_j} x_{it} \geq 2 z_{jd} \ \ \ \forall d, j $$上の定式化をSCOPで解くことによって,付加的な制約を「できるだけ」満たす時間割を作成することができる.
時間割作成の国際コンペティション (ITC2007) では, SCOPは3つの異なるトラックですべてメダル(3位, 2位, 3位)を獲得している.
OR-tools
Googleが開発しているOR-toolsでも同様のことができる.cp_modelは,SCOPとは異なる求解手法である制約伝播を用いているため,パズルのような問題を解くことが得意である. OR-toolsについての詳細は,以下を参照されたい.
https://developers.google.com/optimization
以下に,簡単な最適化の例を示す.
from ortools.sat.python import cp_model
model = cp_model.CpModel()
var_upper_bound = max(50, 45, 37)
x = model.NewIntVar(0, var_upper_bound, "x")
y = model.NewIntVar(0, var_upper_bound, "y")
z = model.NewIntVar(0, var_upper_bound, "z")
model.Add(2 * x + 7 * y + 3 * z <= 50)
model.Add(3 * x - 5 * y + 7 * z <= 45)
model.Add(5 * x + 2 * y - 6 * z <= 37)
model.Maximize(2 * x + 2 * y + 3 * z)
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
print("Maximum of objective function: %i" % solver.ObjectiveValue())
print()
print("x value: ", solver.Value(x))
print("y value: ", solver.Value(y))
print("z value: ", solver.Value(z))
class VarArraySolutionPrinter(cp_model.CpSolverSolutionCallback):
"""Print intermediate solutions."""
def __init__(self, variables):
cp_model.CpSolverSolutionCallback.__init__(self)
self.__variables = variables
self.__solution_count = 0
def on_solution_callback(self):
self.__solution_count += 1
for v in self.__variables:
print("%s=%i" % (v, self.Value(v)), end=" ")
print()
def solution_count(self):
return self.__solution_count
# Creates the model.
model = cp_model.CpModel()
# Creates the variables.
num_vals = 3
x = model.NewIntVar(0, num_vals - 1, "x")
y = model.NewIntVar(0, num_vals - 1, "y")
z = model.NewIntVar(0, num_vals - 1, "z")
# Create the constraints.
model.Add(x != y)
# Create a solver and solve.
solver = cp_model.CpSolver()
solution_printer = VarArraySolutionPrinter([x, y, z])
status = solver.SearchForAllSolutions(model, solution_printer)
print("Status = %s" % solver.StatusName(status))
print("Number of solutions found: %i" % solution_printer.solution_count())