問題及びその定式化

日程表作成問題は、項目vs関係者の相伴表から、各クラスター（日に対応）に属する 項目数をある値（１日の許容会議数）以下にするという制約条件のもとで、項目をあ るクラスター数（会議の総日数）に分割（日割り）するクラスタリング問題とみなせ る。クラスタリングのための評価基準は関係者の延べ出席日数を最小とすることであ る。この問題は以下のように定式化できる。

項目の総数を $M$、関係者の総数を $N$、クラスター数を $K$、各クラスターに属す る項目数の上限を $D$，項目と関係者の相反表を $X = [ x_{ij} ]$, $(1 \le i \le M,1 \le j \le N)$ とする。ただし、 $x_{ij} \in \{0,1\}$ であり、$x_{ij}=1$ は 関係者 $j$ が項目 $i$ に関係していることを意味する。また、各項目に対応する行 ベクトル $\mbox{\boldmath$x$}_1,\ldots,\mbox{\boldmath$x$}_M$ を該当ベクトルと呼ぶことにする。このとき、 問題は、

$$n_k \le D \ \ \ \ (1 \le k \le K)$$ (262)

なる制約条件のもとで、関係者の延べ出席日数

$$f(C_1,\ldots,C_K) = \sum_{k=1}^K w(\bigcup_{i \in C_k} \mbox{\boldmath$x$}_i)$$ (263)

を最小にする日割り $\{C_1,\ldots,C_K\}$ を求めることである。ここで、$n_k$ は 第 $k$ 日に割り当てられた項目の個数を表し、$C_k$ は第 $k$ 日に割り当てられた 項目の集合を表す。また、 $w(\mbox{\boldmath$x$})$ はベクトル $\mbox{\boldmath$x$}$ の要素の $1$ の個数 を評価する関数であり、　 $\bigcup_{i \in C_k} \mbox{\boldmath$x$}_i$ は第 $k$ 日に割り当て られたすべての項目に対して、その該当ベクトルの要素ごとのOR（論理和）を取るこ とを意味する。