数理最適化ソルバー SCIP を用いてあなたの理想のミリオン10th Act-4 セットリストをつくってみよう

1. はじめに

こんにちは。お久しぶりです。星島航です。 おかげさまでミリオンを追い始めて3年ほど経ちました。変わらずロコを応援しています。ミリアニ、とても良かったですよね。

さて、今回は実に1年9か月ぶり、2本目の記事を書きました。研究者ならクビになっているペースですね。よろしくお願いします。

2. 先に結果の一例だけ

今回のタイトルは、

  • 数理最適化ソルバーSCIPを用いてあなたの理想のミリオン10th Act-4 セットリストをつくってみよう

です。ここで早めに注釈を入れておく必要がありますが、この後に紹介するのは『私の理想』の一例です。 そして、何なら出来上がったセットリストは私の理想にすらまだ少し遠いです。 これからまだまだ改善の余地がありますが、公開することで「理想のセットリストとは？」という議論の下地にしていただければと思います。

前提として、以下の点を念頭においてご覧ください。

  • 全体曲は別枠で考えているので入っていません
  • 全曲フルサイズでの披露を想定し、1日あたり（全体曲を除き）27曲としています
    • 今回の想定と一番形式が似ている（何が披露されるか予想しづらい、全曲フルサイズ）ミリオン7th Reburnの曲数を参考にしました
  • 全曲（ASメンバーを除く）オリジナルメンバーでの披露を想定しています

では、前回記事同様、まずは最終結果を掲載します。

（サイズが小さくなってしまうので元画像リンク）

最適化ソルバーにより作成したAct-4セットリストの一例（キャスト情報なし）

最適化ソルバーにより作成したAct-4セットリストの一例

各列の説明は以下の通りです。

  • 一番左の列の2つ1組の数値
    • 「何日目の何曲目か」を表しています。
  • 左から2列目
    • 楽曲名です。
  • 以降の39列
    • 各キャストさんの楽曲披露タイミングを表しています。
    • セルに記載されている3つの数値は、「その楽曲までを含めたその日の累計披露回数、（その楽曲までを含めた2日間の累計披露回数）；その楽曲の披露メンバー数」を表しています。

いかがでしょうか。 良い悪いは色々なご意見があると思いますが、ここでは「数理最適化によってセットリストを作ると一例としてこんな感じになるよ」ということだけ伝わればよいかなと思います。

では、ここから上記のセットリストはどのような手順で作られたかをご説明していきます。

3. 使用した一次データについて

今回の取り組みにあたり、

  • ミリオンライブ！の楽曲の一覧および過去のライブ披露実績

のデータが必要でした。これらのデータは、music765plus様が運営されている『アイドルマスター楽曲メモ』に掲載されている情報を使用させていただきました。欲しい情報が全て掲載されており、大変助かりました。ありがとうございました。

4. コードおよび二次データの置き場所

こちらのリポジトリ

github.com

に置いておきました。コードは1つのJupyter Notebookファイルのみです。一応前回の反省を活かして少しだけ可読性にも気を使いましたが、まだ読みづらいと思います。使ってみたい人は頑張ってください。

今回もいくつかパラメータがあり、調整すると異なる結果が得られて面白いと思うので、実行環境がある方はcloneしてそれらのパラメータを調整して実行してください。その際は結果をTwit... Xで共有してくれると嬉しいです。

5. 背景： Act-4楽しみ

さて、いよいよミリオン10th Act-4が迫って来ましたね。

idolmaster-official.jp

なんといってもこの公演で特筆すべきは出演キャストです。Day1は32名、Day2はなんとミリオンスターズ39名全員参加！すごい。

このことが発表された時、みなさんは最初に何を考えたでしょうか。私は「Day2にMS全員いるということは、あの曲もこの曲も全部、オリジナルメンバーで聴けるかも！」でした。

常々「全楽曲、一度はオリジナルメンバーで披露して欲しい…」と思っている私にとってはまたとないチャンスです。普段の周年ライブ同様今回もASメンバーは不在なので完全なオリジナルメンバーが揃わない曲もありますが、それでもせめてMSメンバーが揃った状態での披露が観たい。

それに、Day2に目が行きがちですが、近年の周年ライブでは2日間でキャストを半分に分けて1日十数名の参加という形が定番となっていたことを考えるとDay1の32名も相当多いです。

そこで私は考えました。

「2日とも『全曲オリジナルメンバーでの披露』縛りでセットリストを作れるのでは…？」

と。

6. 目的：『理想』のセットリストを考えてみたい

思い立ったら、やってみましょう。

上記の背景も踏まえ、セットリストを作成してみます。

ただし、上記の通り「オリジナルメンバー縛り」だけで楽曲を並べるのはそれほど難しくありません。2日目はMSのキャストが全員いるので物理的にはASを含まない楽曲は全て可能ですし、1日目も32名でできる楽曲は相当数あります。

よって、もう少し考慮する事項を増やし、以下のように目的を定めます。

  • 以下の条件を満たすセットリストを作成する
    1. 全楽曲オリジナルメンバーでの披露縛り
      • 前述の通り、私の希望
    2. 現実的である
      • 各キャストの楽曲披露回数に偏りがない
      • 各キャストの楽曲披露間隔に無理がない
      • 特定の楽曲同士の曲順が不自然でない（MTS Final曲など）
      • など
    3. なるべく、披露が期待されている楽曲を多く含む
      • 盛り上がりを考慮して、ライブ後半に含んでいるとなお良い

あれ、急に難しくなりましたね。

7. 手法：数理最適化

先ほど「それほど難しくない」と書いたばかりですが、条件に「現実的である」を入れると一気に難易度が上がります。なぜなら、ミリオンはユニットが固定されていないからです。

これは私がミリオンの良いところだと思っている点であり、このおかげで色々な組合せでの楽曲が楽しめるのですが、今回挑戦する「全楽曲オリジナルメンバーでの披露縛り」とは非常に相性が悪いです。

なぜなら、ある楽曲をセットリストに加えると複数のキャストの楽曲披露回数が同時に増え、代わりに別の楽曲を取り除くとと別の複数のキャストの披露回数が同時に減り、…となるからです。セットリストに含めたい楽曲を選びつつキャスト全員のトータルの楽曲披露回数を調整するのがとても大変だということがイメージできるかと思います。これを人手で行うのはとても大変で、私にはちょっとできません。

しかし、私も一応エンジニアの端くれ。コンピュータと数学の力を借りてなんとかできないか…

…

あれ、よく見ると、これは組合せ最適化問題じゃないですか。そうです。みんな大好き（？）、数理最適化の出番です。

最適化問題とは、

  • 設定された「制約条件」をすべて満たし、「目的関数」の値が最小（または最大）となる解（「変数」の集合）を求める問題

であり、その最適化問題を解くにあたりよく使われる手法として「メタヒューリスティクス」とともによく挙げられるのが「数理最適化」です。

両者にはそれぞれ特徴がありますが、ここでは割愛します。「数理最適化の方が厳密だが使うのがめんどくさい」くらいに思っておいてください。それぞれ一長一短であり、問題の大きさや複雑さによって使い分けられています。

前回の記事では「斬新なユニット組合せ」をメタヒューリスティクス（の一種であるタブーサーチ（を中途半端に改造した局所探索法））を使用して解きました。

wtr-hshjm.hatenablog.com

今回は「セットリスト作成」を（最適化問題の一種である）組合せ最適化問題と解釈し、数理最適化ソルバー SCIP を使用して解いていくことにします。

数理最適化を用いて課題を解決するには、課題を定式化する必要があります。

定式化に必要なのは、

  • 定数
  • 変数
  • 制約条件
  • 目的関数

の設定です。

今回のセットリスト作成問題に当てはめてみると、

  • 定数 → 変数の定義および制約条件の表現に必要な値の集合
    • ライブの日数、1日あたりの披露楽曲数、候補曲数、キャスト視点で必要な楽曲披露間隔などを用意する
  • 変数 → 「あるセットリスト1つ」を表す1組の変数の集合
    • 「具体的な値を持った変数の集合1つ」と「あるセットリスト1つ」が1対1に対応するように定義する
    • 制約を表現しやすい形で定義すると良い
  • 制約条件 → セットリストが満たすべき条件の集合
    • 変数同士もしくは変数と定数の関係式で表現する
  • 目的関数 → 「どのようなセットリストが『理想』のセットリストであるか」を表す関数
    • より『理想』に近いセットリストを表す変数の集合を入力すればするほど出力が大きく（もしくは小さく）なるような関数を、変数および定数を用いて定義する

となります。

文字だけの説明だとイメージしにくいかもしれませんが、定式化、実験の章で図をたくさん使って詳しく説明します。

さて、早速実際にこの課題を定式化していきましょう…と言いたいところですが、ちょっと待ってください。

定式化の経験がある方であれば、もうこの時点で変数の置き方は何パターンかイメージができていると思います。

しかし、現時点では目的関数＝「どのようなセットリストが『理想』のセットリストであるか」自体が定まっていません。

そして、実は変数の定義に必要な「候補曲数」も定まっていません。

次章ではまず、これらを定めるために必要な材料集めをしていきましょう。

8. 定式化の準備

8-1. 各楽曲の「披露期待ポイント」の定義

ところで、「目的」に何気なく書いた「披露が期待されている楽曲」ってどのような楽曲でしょうか。

もちろん人によって違うと思いますが、もし楽曲ごとに「この楽曲が披露されれば○○ポイント」のような数値があれば、目的関数を「セットリスト全体で披露される楽曲のポイントの合計値」のように定義することができます。

まずは各楽曲に対する「Act-4での披露を期待されている度合い」を定量化してみましょう。

（ここからは私の願望が強く反映されているので、心の中で突っ込みでも入れながらお読みください。Notebookでは各種パラメータを調整できるように作ってあるので、異なる考えをお持ちの方はパラメータを変更して遊んでみてください。）

私がAct-4で披露を期待する楽曲については、以下のように整理できます。

  • 楽曲のオリジナルメンバーにおけるMSメンバーの割合が高い楽曲ほど優先してほしい
  • 楽曲の新旧に関わらず、キャストによって披露されていない曲はまず最優先とし、しばらく披露されていない楽曲も優先してほしい
  • 以下の条件に合致する楽曲ほど優先してほしい
    • 周年ライブで披露されていない
    • オリジナルメンバーで披露されていない
    • オリジナルかつフルサイズ（Remixやショートバージョンではない）音源で披露されていない

これらの希望を反映させる形で、全ての楽曲uに対する「披露期待ポイントe_{u}」を以下のように定義します。

\displaystyle e_{u} = r_{u} \times \{ a - \max_{v \in W_{u}}(n_{uv} \times b_{uv} \times o_{uv} \times z_{uv}) \}

ここで、

  • r_{u}: 楽曲 uのオリジナルメンバーにおけるMSメンバーの割合
  • a: 現在の周年数(=10)
  • W_{u}: 楽曲 uの過去に行われた全ての（キャストによる）披露 vに関する情報の集合（MRなどは含まない）
  • n_{uv}: 楽曲 uの披露 vが行われた周年期間を表す数値（例：「8周年ライブ初日～9周年ライブ初日の前日」の間の披露の場合、8）
  • b_{uv}: 楽曲 uの披露 vが周年ライブでの披露だった場合1、そうでなかった場合0.5
  • o_{uv}: 楽曲 uの披露 vが（MSの）オリジナルメンバー全員を含む披露だった場合1、そうでなかった場合0.5
    • ただし、楽曲のオリジナルメンバーが7人以上の場合は（揃うのが難しいので）常に1とする
  • z_{uv}: 楽曲 uの披露 vがオリジナル音源かつフルサイズでの披露だった場合1、そうでなかった場合0.5

とします。

（定式化の方で使いたい文字を避けたため内容と関連のない文字だらけになってしまっています。分かりにくくてすみません。）

また、「オリジナルメンバー」について、基本的には初出のオリジナル音源の歌唱メンバーとしていますが、以下の楽曲については記載の通りとしています。

  • 『アイル』：Harmonized ver.（Machicoさん、阿部里果さん、愛美さん）とする
  • 『リフレインキス』：Brand New Ver.（種田梨沙さん、村川梨衣さん、上田麗奈さん、雨宮天さん）とする
  • LTFチーム曲：Brand New Ver.（南早紀さん、香里有佐さんを含む）とする
  • MTG属性曲：音源歌唱メンバーに加え、各属性のMSのメンバー全員を含む
  • MTS Finalチーム曲：音源歌唱メンバーに加え、各チームのダンスメンバー全員を含む

なお、 W_{u} = \emptyset、つまり楽曲 uが過去に一度もキャストによって披露されていない場合、 e_{u} = r_{u} \times 10とします。

式に文字がたくさん出てややこしそうですが計算自体は簡単です。例えば『dans l'obscurité』の場合、過去6回の披露機会がありますが、maxの中身が最大となる披露機会は8thライブでの披露で、 8 \times 1 \times 0.5 \times 1 = 4（8周年期間、周年ライブ、メンバー揃っていない、オリジナルフル音源）となります。

直近の披露であるMOIW2023は 9 \times 0.5 \times 0.5 \times 1 = 2.25（9周年期間、周年ライブでない、メンバー揃っていない、オリジナルフル音源）となり、8thライブの値よりも小さくなるので、必ずしも直近の披露が計算対象となるわけではないことに注意してください。

Chrono-Lexicaはメンバー5人中5人がMSメンバーであるので、 u=dans l'obscuritéについて、 e_{u} = 5/5 \times (10 - 4) = 6 ポイントとなります。

他にもいくつか例を出すと、10th Act-1で待望の（MS）オリジナルメンバーで披露された『ココロがかえる場所』は e_{u} = 3/4 \times (10 - 10) = 0 ポイント、8周年期間にSEASON-@IR!!!!の配信・一部メンバーで披露された『産声とクラブ』は e_{u} = 3/4 \times (10 - 2) = 6 ポイントとなります。

この「披露期待ポイントe_{u}」を、2024/01/08時点で「ミリオンライブ！の楽曲」に掲載されている楽曲（+MILLION C@STING!!!の結果によって制作および歌唱メンバーが決定している楽曲）全338曲（※）について計算しました。

※以下の楽曲を取り除いた曲数です。

  • バージョン違い（ソロバージョンなど）
    • オリジナル縛りなので。
  • Remix
    • 同上。
  • ZWEIGLANZの楽曲
    • 多分やらないと思うので。
  • 合同曲、スタマス、ポプマス、MOIW・アイラブ歌合戦楽曲
    • 多分やらないと思うので。
    • ただし『VOY@GER』は私が聴きたいのでMS 3人だけのバージョンの音源があるので残しました。

計算式については異論もあるかと思いますが、これでひとまず全楽曲について「どの程度披露が期待されているか」を定量化することができました。

8-2. 最適化対象の最終候補曲の絞り込み

次に、前述の338曲の中からさらに以下の楽曲を除外します。

  • 全体曲15曲
    • 具体的には、周年曲11曲、『DIAMOND DAYS』、『EVERYDAY STARS!!』、『Rat A Tat!!!』、『セブンカウント』
    • 理由は少し長くなるので後述。
  • ラジオ曲4曲、カバー曲1曲（『IGNITE』）
    • やらないと思うので。先ほど取り除かなかった理由は、途中で気が変わったからです。
  • （MSソロ曲以外で、）ASメンバーを除くとオリジナルメンバーが1人以下となる楽曲
    • 具体的には、LTD曲のうちASとMSのペアである楽曲、ASのMTG曲、ASのソロ曲、『World Changer』
    • 理由は、今回のコンセプトである「オリジナルメンバー縛り」を適用すると不可能もしくはソロ披露となってしまうためです。
  • 互いにメンバーが完全一致する楽曲のうち、披露期待ポイントが一番高い楽曲以外の楽曲
    • 具体的には、ソロ曲やMTG, MTWの曲は同じメンバーで複数曲が存在するので、それぞれ1曲に絞ります。
      • 例①：（キャストで書いて、）メンバーが「中村温姫さん」である楽曲は4曲ありますが、そのうち披露期待ポイントが最も高いのは4点の『STEREOPHONIC ISOTONIC』であるので、それ以外の3曲を除外します。
      • 例②：メンバーが「中村温姫さん、戸田めぐみさん、斉藤佑圭さん、渡部恵子さん」である楽曲は『月曜日のクリームソーダ』、『I did+I will』の2曲ありますが、（どちらも披露期待ポイントが4点なので五十音順で早い）『I did+I will』を残し、『月曜日のクリームソーダ』を除外します。最適化の都合上片方のみを残しましたが、今回は楽曲の長さは考慮していないので、得点が同じ場合は最適化結果を見るときに入れ替えても大丈夫です（？）。
    • 理由は単純に、2曲あるユニットの楽曲をAct-4だけで2曲やることはないと思うからです。ソロも同様です。もしあったらすみません。

全体曲について書いておきます。

冒頭の結果でも言及した通り、全体曲はセットリスト作成の対象から除外します。

理由は、今回の取り組みではキャストごとの披露曲数や披露間隔を考慮します（後述）が、全体曲は「全キャストが同じ披露タイミングで披露する」ということを考えると、

  • 披露によって曲数は全員一律に増える
  • 間隔は誰かが2曲連続（全体曲→個別曲、もしくはその逆）となってしまうことが避けられない

ので、最適化対象に含めて披露曲順を考慮することにあまり意味というか関心がないからです（MCのタイミングまで考慮すると意味が出てきますが、Act-4はMCほとんど無いだろうと想定しています）。そもそも曲順は大体1曲目、アンコール前ラスト、アンコール数曲、と決まっていますし。

「どの全体曲が披露されるか」は気になるところですが、披露期待ポイントをもとに考えると『Welcome!!』が最有力候補です まあそれは置いておきましょう。

決して今回のAct-4で全体曲が披露されないと予想しているわけではなく（そんなことあり得ないですね）、あくまで最適化の対象からは外すということでご了承ください。

以上の処理により、最適化対象である最終候補曲が決定しました。残った楽曲数は176曲です。

これら176曲を「五十音順」および「披露期待ポイント（同率の場合は五十音）順」に並べた結果をこちらに出力しているので、ご興味のある方はご覧ください。

これで、定式化の準備が完了しました。

9. （制約条件以外の）定式化

では、早速定式化をしていきましょう。

おさらいですが、定式化には

  • 定数
  • 変数
  • 制約条件
  • 目的関数

が必要です。

なお、「制約条件」については「実験」の章で1つずつ説明しながら加えていくことにします。その方がいろいろなセットリストをお見せできて面白いので。

それでは、文字がたくさん出てきますが頑張りましょう（？）。

9-1. 定数

まずは「どのようなセットリストを作るのか」を決定する定数を決めていきます。

定数は文字通り、一度定めたら最適化実行中は値が変わりません。今回は、（自明であるものも含め）以下のように定めました。

  • キャスト数： c = 39
    • 嬉しいですね。
    • キャスト識別子の集合を、 C = \lbrace 1, ..., c \rbrace とします。
  • ライブ日数： d = 2
    • これは決定事項です。
    • ライブ日数識別子の集合を、 D = \lbrace 1, ..., d \rbrace とします。
      • 自明ですが、識別子がそのまま何日目かを表しています。
  • 1日あたりの（全体曲を除いた）披露楽曲数： p = 27
    • プラス全体曲3曲で1日30曲を想定しています。
    • 各日の披露曲順識別子の集合を、 P = \lbrace 1, ..., p \rbrace とします。
      • 自明ですが、識別子がそのまま曲順を表しています。
  • 候補楽曲数： s = 176
    • 「8. 定式化の準備」で決定した値です。
    • 候補楽曲識別子の集合を、 S = \lbrace 1, ..., s \rbrace とします。
      • 具体的には、候補曲を期待ポイント順に並べたこちらをそのまま使用しており、識別子1は『Clover Days』、2は『Dual Style Idol』、…を表しています。
    • キャスト識別子 mがメンバーに含まれている楽曲識別子の集合を、 S_mとします。
      • S_m \subseteq S, \forall m \in C
      • 例えば、中村温姫さん（キャスト識別子12）に着目すると、 S_{12} = \lbrace 7, 21, 40, ..., 168, 176 \rbrace となります。
  • キャスト識別子 mの（全体曲以外の）合計楽曲披露数の下限 a_{m_{\min}}、上限 a_{m_{\max}}
    • 両日参加のキャスト： a_{m_{\min}} = 5, a_{m_{\max}} = 5
      • 1日あたりの披露数は a'_{m_{\min}} = 2, a'_{m_{\max}} = 3、つまり1日2～3曲、2日合計で5曲と設定します。
    • Day2のみ参加のキャスト： a_{m_{\min}} = 3, a_{m_{\max}} = 3
      • 1日あたりの披露数は（当然） a'_{m_{\min}} = 3, a'_{m_{\max}} = 3、つまりDay2で3曲です。
      • ただし、戸田めぐみさん（キャスト識別子21）は公式から「一部の楽曲のみ参加」とアナウンスがあるので、 a_{21_{\max}} = 1, a_{21_{\min}} = 1とします。当然 a'_{21_{\max}} = 1, a'_{21_{\min}} = 1です。
        • 出てくれるだけで嬉しいです。実際は全体曲のみの参加となるかもしれませんが、期待を込めて1としています。
  • 各キャストに必要な、楽曲披露の間隔： g = 3
    • 1曲披露したら、次の担当楽曲の披露まで最低3曲は間を空けなければいけない、という設定とします。

9-2. 変数

変数には、人間から見た分類として

  • 決定変数
    • 具体的にその値が解を決定する変数
  • 補助変数
    • 決定変数に複雑な制約条件を設定するために用意される変数

がありますが、今回の問題は単純なので（正確には、補助変数を使わなければ表現できないような複雑な制約条件を考えてないようにしているので）、決定変数のみが必要となります。

今回の決定変数は、「あるセットリスト1つ」を表す1組の変数の集合です。セットリストを表すには、どのように定義すればよいでしょうか。

ちょっと天下り式ですが、今回は d \times p \times s個のバイナリ変数（0か1のいずれかの値を取る変数） x_{ijk}の集合 \boldsymbol{x}を用いることにします。 数式で書くと、

\displaystyle x_{ijk} \in \lbrace 0, 1 \rbrace \\ \forall i \in D, \forall j \in P, \forall k \in S

です。つまり、 2 \times 27 \times 176 = 9504個のバイナリ変数の集合で1つのセットリストを表すことになります。

「手法：数理最適化」で記載した

  • 「具体的な値を持った変数の集合1つ」と「あるセットリスト1つ」が1対1に対応するように定義する

についてですが、今回は

  • x_{ijk} = 1の場合、 i日目の j曲目に楽曲 kが披露される
  • （つまり x_{ijk} = 0の場合、 i日目の j曲目に楽曲 kが披露されない）
  • （＋前提として後述の制約01が成り立つ）

というように変数をみることで、1組の \boldsymbol{x}が1つのセットリストを表すようにします。

視覚化すると以下の通りとなります。

決定変数のイメージ

1つのマスが1つの x_{ijk}を表しており、図全体が1つのセットリスト \boldsymbol{x}を表しています。

上記の図1枚で、1日目の1曲目に楽曲識別子 s-2の楽曲を、2曲目に識別子 2の楽曲を、…2日目の p曲目（27曲目）に識別子 1の楽曲を披露するような1つのセットリストを表しています。

もしかすると、鋭い方は「バイナリ変数ではなく整数変数（仮に x'_{ik}とします）の集合を使って、『 x'_{ik} = jの場合、 i日目の j曲目に楽曲 kが披露される』とすれば、変数も少なくなるし良いのでは？」と考えたかもしれません。

もちろんそのように考えることも正しいです。1つのセットリストを表すような変数の定義の仕方は1通りではありません。

さらにいうと、確かに一部の制約条件（後述の制約06とか）の設定ではその方が都合が良いこともあります。

しかし、セットリストに加えたい（と多くの人が思うであろう）制約条件は、そのほとんどがバイナリ変数を使用した方が簡単に表現することができます。

後ほど説明する制約条件の定式化で、バイナリ変数の表現力の高さを楽しんでください。

9-3. 目的関数

さて、目的関数ですが、これがどんな関数とすべきかを改めて確認すると、

  • 「どのようなセットリストが『理想』のセットリストであるか」を表す関数
    • より『理想』に近いセットリストを表す変数の集合を入力すればするほど出力が大きく（もしくは小さく）なるような関数を、変数および定数を用いて定義する

です。

ここで、「各楽曲の「披露期待ポイント」の定義」で定義した「披露期待ポイントe_{k}」（ kは候補曲識別子）を使いましょう。

前提として、披露期待ポイントはその楽曲の披露期待度が高いほど大きい値となるように設計しています。このことを考慮すると、一番最初に思いつくのは「セットリスト \boldsymbol{x}に含まれた楽曲の披露期待ポイントの合計」を目的関数とし、その値が大きいほど『良い』セットリストとみなす、という問題設定です。

これを式で表すと、

\displaystyle \sum\limits_{i \in D} \sum\limits_{j \in P} \sum\limits_{k \in S} e_{k} x_{ijk}

となります。 x_{ijk}は i日目の j曲目に楽曲 kが披露される時に1となるので、セットリストのどこかで楽曲 kが披露されていれば、 e_{k}ポイントが加算されるようになっています。

しかし、単純にこれで良いでしょうか。もう少しだけ『理想』について考えてみましょう。

例えば、今まで完全未披露ながらDay2にメンバーが揃っており、今回多くの方が披露を期待しているであろう楽曲『Clover Days』。この曲が、もしDay2の（全体曲を除いて）1曲目や2曲目に披露されたらどう思うでしょうか。まあやってくれるだけ嬉しいですけどちょっと拍子抜けというか、できればトリに近いところで聴きたくないでしょうか。主観と言われればそれまでですが、私はそう思います。

これを一般化して、

  • 披露期待ポイントが高い楽曲ほど、なるべく終盤に披露されてほしい

という要求を、目的関数に反映させていきましょう。

上記の要求を反映させるには、披露期待ポイントが高い楽曲がセットリストの各日の後半に配置されているセットリストほど値が大きくなるように目的関数を設計すれば良さそうです。

そこで、新たな定数 h（1以上）を用意します。そして、目的関数の計算の際に、その楽曲が披露されているか否かだけでなく、その披露曲が何曲目に配置されているかによって楽曲の披露期待ポイントに 1～ hを掛けて和を取るようにしてみましょう。

式で表すと、

\displaystyle \sum\limits_{i \in D} \sum\limits_{j \in P} \sum\limits_{k \in S} ((1 + (h-1)j / p) \times e_{k} x_{ijk})

となります。

これは、例えば h=2とすると、Day1, 2それぞれで、1曲目に披露される楽曲の披露期待ポイントを1.037倍、2曲目は1.074倍、…、27曲目は2.0倍にして足し合わせたものがそのセットリストの目的関数の値となります。

このように設定することで、「できるだけ披露期待ポイントが高い楽曲を後半に配置しているセットリスト」＝「目的関数の値が大きいセットリスト」＝「『良い』セットリスト」と判断されます。

まあ「披露期待ポイントが高い楽曲が後半にあるほど良いセットリストである」とは一概には言えないと思いますが、今回はこのような設定としたいと思います。

さあ、ようやく（制約条件以外の）準備が整いました。次章からいよいよセットリストを作っていきます。

10. 制約条件の定式化、実験

さて、「目的」に記載した、セットリストを作成するにあたっての条件をおさらいしましょう。

  • 再掲：以下の条件を満たすセットリストを作成する
    1. 全楽曲オリジナルメンバーでの披露縛り
      • 前述の通り、私の希望
    2. 現実的である
      • 各キャストの楽曲披露回数に偏りがない
      • 各キャストの楽曲披露間隔に無理がない
      • 特定の楽曲同士の曲順が不自然でない（MTS Final曲など）
      • など
    3. なるべく、披露が期待されている楽曲を多く含む
      • 盛り上がりを考慮して、ライブ後半に含んでいるとなお良い

まず1.についてですが、こちらは、常に満たされています。

今回の問題設定は「どの楽曲をいつ披露するか」です。「ある楽曲 kが披露される場合、その披露は必ず（MSの）オリジナルメンバーによる披露」を前提としており、「どの楽曲を誰が歌うか」は最適化の対象ではありません。よって、この条件は問題設定の段階でクリアしています。

次に2.の前に3.について先に書くと、前節の「目的関数」の項で設定した目的関数によって実現されます。

本章の本題である2.については、各節で追加する制約条件で実現していきます。

さて、ここでさらっと大事なことを書くのですが、今回使用する数理最適化ソルバー SCIP は混合整数最適化問題に特化したソルバーです（説明には「非線形もいける」みたいなことも書いていますがおそらく求解性能は落ちると思います）。

「混合整数最適化問題」の定義を順を追って説明すると、

となっています。つまり、混合整数最適化問題は線形最適化問題の一部なので、SCIPを使用するためには

  • 目的関数を線形関数で表さないといけない
  • 全ての制約条件を線形の等式または不等式で表さないといけない

ということを守る必要があります。

ここでいう「線形」とは、変数とそれにかかる係数が1次の多項式で表現されること、つまり変数同士の掛け算や累乗などが含まれていない状態を指します。

後追いでの確認になってしまいますが、先ほど設定した目的関数

\displaystyle \sum\limits_{i \in D} \sum\limits_{j \in P} \sum\limits_{k \in S} ((1 + (h-1)j / p) \times e_{k} x_{ijk})

は、この条件を満たしているので大丈夫ですね（大丈夫なように設定したのですが）。

以降で設定していく制約条件についても、線形性を意識していきましょう。

10-1. 「制約01：ある日のある曲順では1曲のみが披露される」

「何を言っているんだ、当たり前じゃないか」と思われるかもしれませんが、今のところ決定変数 \boldsymbol{x}の各要素 x_{ijk}は

  • x_{ijk} = 1の場合、 i日目の j曲目に楽曲 kが披露される
  • （つまり x_{ijk} = 0の場合、 i日目の j曲目に楽曲 kが披露されない）

という前提しか置かれていません。つまり、変数に何の制約も掛けなければ、例えば

  • x_{1,1,1} = 1かつ x_{1,1,2} = 1というセットリスト \boldsymbol{x}
    • つまり「1日目の1曲目に楽曲識別子1の楽曲が披露される」かつ「1日目の1曲目に楽曲識別子2の楽曲が披露される」というセットリスト

が許されてしまいます。1つの披露枠で2曲やるなんて、そんなことは普通のライブではあり得ません。 例えば、「2日目の5曲目は『フェスタ・イルミネーション × 鳥籠スクリプチュア BATTLE MIX』です」と言われるようなものです。え、他ブランドではあった…？知りませんね…

今回はこのような披露形式は考えないこととします。

もちろん、逆に「1日目の10曲目はどの楽曲も披露されない」というような事態も発生しないようにしたいです。

上記をまとめると、「ある日のある曲順では必ず1曲のみが披露される」という制約を設定する必要があります。

これを式で表すと、以下の通りとなります。

\displaystyle \sum_{k \in S} x_{ijk} = 1 \\ \forall i \in D, \forall j \in P

例として、 i=1, j=1、つまり1日目の1曲目の披露曲を1曲とする制約を可視化すると以下の通りとなります。

制約01：ある日のある曲順では1曲のみが披露される

赤枠で囲まれた s個の決定変数 x_{ijk}の合計が必ず1でなければいけない、という制約条件です。 x_{ijk}は0か1しかとらないので、この合計が1ということは赤枠のうち1つの x_{ijk}のみが1となっていることと同じことを意味します。線形性も問題ないですね。これを、全ての (i, j)の組合せに対して課すのが制約01です。

では、一旦この制約01のみを課して、目的関数の値を最大化させるセットリストを作ってみましょう。どうなるか予想してみてください。

ちなみに、以降は断りがなければ解の最大探索時間を10分とします。つまり、10分探した中で、制約条件を全て満たし目的関数の値が最大となるセットリストが出力されるようします。

…

結果は以下の通りとなります。

（元画像リンク）

制約01を課したセットリスト作成結果（キャスト情報なし）

制約01を課したセットリスト作成結果

本記事冒頭でも見方を記載しましたが、改めて説明すると、

  • 一番左の列の2つ1組の数値
    • 「何日目の何曲目か」を表しています。
  • 左から2列目
    • 楽曲名です。
  • 以降の39列
    • 各キャストさんの楽曲披露タイミングを表しています。
    • セルに記載されている3つの数値は、「その楽曲までを含めたその日の累計披露回数、（その楽曲までを含めた2日間の累計披露回数）；その楽曲の披露メンバー数」を表しています。

となります。

はい、『Clover Days』を2日間で54回披露するセットリストが出来上がりました。1秒で出来上がりました。目的関数の値は、820ポイントです！（ポイントはこちらのCSVの最終行で確認できます。）

…すみません、茶番でした（想定外の桁数で文字がセルを突き破ってますし…）。問題だらけのセットリストです。というかこれをセットリストというのも憚られます。

どうしてこうなってしまったのでしょうか。SCIPくんは強火のBlooming Cloverファンなのでしょうか。もちろんそうではありません。SCIPは言われた通りに制約条件を守り、言われた通りに目的関数の値が最大となるようにセットリストを組んだだけです。

そうです、明らかに制約条件が足りないからですね。

ここから、制約条件を少しずつ加えて記事冒頭に掲載した（まだ良さそうな）セットリストに近づけていきましょう。

10-2. 「制約02：すべての候補楽曲はAct-4を通じて1回以下だけ披露される」

（他にもあるかもしれませんが、）先ほどのセットリストを見て真っ先に思い浮かぶ問題点は、「同じ曲を何回も披露している」でしょう。これを防ぐように、「すべての候補楽曲はAct-4を通じて1回以下だけ披露される」という制約条件を設定しましょう。

これを式で表すと、以下の通りとなります。

\displaystyle \sum_{i \in D} \sum_{j \in P} x_{ijk} \le 1 \\ \forall k \in S

例として、 k=1、つまり楽曲識別子1の披露回数を1回以下とする制約を可視化すると以下の通りとなります。

制約02：1楽曲1披露以下

赤枠で囲まれた d \times p個の決定変数の合計が必ず1以下でなければいけない、という制約条件です。1以下であるということは、1回披露されるか0回披露される（つまり披露されない）かに限定されるということです。線形性も問題ないですね。これを、全ての楽曲 kに対して課すのが制約02です。

では、制約01～02を課して、目的関数の値を最大化させるセットリストを作ってみましょう。今回もどうなるか予想してみてください。

…

結果は以下の通りとなります。

（元画像リンク）

制約01～02を課したセットリスト作成結果（キャスト情報なし）

制約01～02を課したセットリスト作成結果

今回も1秒で出来上がりました。まあ1曲1回までの縛りが増えただけで、披露期待ポイントが高い順にセットリストの下から並べていくだけですからね。目的関数の値は626ポイントです。当然ですが、制約が増えているので前回と比べて下がりました。確認はこちらから。

さて、『Clover Days』54連続よりははるかにまともなセットリストができましたが、まだまだ突っ込みたいところは満載です。次は何を考えましょうか。

まずは物理的に可能なセットリストにしたいですよね。今回のセットリストでは、Day2のみ出演のキャストさんがメンバーに含まれている楽曲がDay1に入ってきてしまっています。本記事ではオリジナルメンバーでの披露縛りを前提としているので、このセットリストは受け入れられません。次の制約を考えましょう。

10-3. 「制約03：すべてのキャストは各日に設定された回数上下限を守って楽曲を披露する」

次の制約として、キャストさん視点での各日の披露曲数の上下限を設定しましょう。

ただ、決定変数 x_{ijk}にはキャスト識別子は直接表れません。どうすればよいでしょうか。こちらは先に制約式と可視化の図を見て頂いた方がわかりやすいかもしれません。

\displaystyle a_{m_{\min}} \le \sum_{i \in D} \sum_{j \in P} \sum_{k \in S_{m}} x_{ijk} \le a_{m_{\max}} \\ \forall m \in C

制約03：1キャストの披露曲数上下限

「定数」の節で定義した通り、 S_{m}はキャスト識別子 mがオリジナルメンバーに含まれている楽曲の集合（ Sの部分集合）であり、これは既知の情報です。

よって、「キャスト識別子 mが含まれている楽曲のうちセットリストに含まれている楽曲数」＝「キャスト識別子 mの披露曲数」（全楽曲オリジナルメンバー披露縛りという前提があるのでイコールとなります）を表す上記の制約式の真ん中の値（図の赤枠の合計）は問題なく計算することができます。

そして、各キャストに対してはライブ全体での披露曲数の上下限を定数で設定しているので、赤枠の合計値がその上下限に収まっているという制約条件を設定することで、キャストの披露曲数に対する制約を掛けることができます。

（なお、これは制約01, 02が成立しているという前提を置く必要がありますが、数理最適化では「設定された制約が全て満たされるような解」のみを解とするので、このように他の制約条件の成立を前提として別の制約条件を設定できます。）

上記の図では一例として、楽曲識別子 1, 4, 5, ..., s-1のオリジナルメンバーであるキャストに対してライブ全体の披露曲数の制約を掛ける際の合計値計算範囲を赤枠で示しています。

同じ原理で、赤枠の範囲を1日目もしくは2日目のみに限定して、その日・そのキャスト用の上下限設定値を使うことで、1日あたりの披露曲数の制約も掛けることができます。これにより、例えば「田所あずささんがメンバーに含まれている楽曲は1日目で合計0曲の披露とする」＝「田所あずささんが1日目不在である」という制約も表現できます。

なお、様々な思惑（？）により、「オリジナルメンバーが7人以上の楽曲」についてはMSメンバーが全員揃わなくてもDay1に披露可能としました。

では、制約01～03を課して、目的関数の値を最大化させるセットリストを作ってみましょう。ちなみに、この制約の追加によって、到達できる目的関数の最大値が自明ではなくなるため、10分では最適解が見つからなくなります。もともと選択肢自体は 2^{9504}と膨大ですからね。このあたりから人間視点での予想も難しくなってきます。

結果は以下の通りとなります。

（元画像リンク）

制約01～03を課したセットリスト作成結果（キャスト情報なし）

制約01～03を課したセットリスト作成結果

ひとまず、物理的に実行可能となりました。Day2のみ参加のキャストさんがオリジナルメンバーに含まれている楽曲は、Day1では披露されないセットリストになっています。また、各キャストさんの楽曲披露回数も、全キャストさんについて設定を守ることができています。かつ、披露期待ポイントが高い楽曲がたくさん含まれたセットリストにもなっています。目的関数の値は573ポイント（確認はこちら）。だいぶ良くなってきましたね。でももう少しキャストさんに配慮してみましょう。

10-4. 「制約04：すべてのキャストは設定された曲数以上に楽曲披露間隔が空いている」

「物理的に実行可能」とは言ったものの、全節の結果を見ると、キャストさんによっては楽曲披露間隔が狭い箇所があるのが気になります。

例えば、種田梨沙さんはDay2の20, 21, 23曲目に出番となっています。これは厳しい。キャストさんに良いパフォーマンスをしてもらうためにも、ある程度の披露曲同士の間隔は欲しいところです。

今回は、「1曲披露したら最低3曲は休める」という設定をしてみましょう（なぜ3曲かというと、3曲までなら後述の制約と共存しやすいからです）。

この制約条件はどのように式で表せばよいでしょうか。少しだけ考えてみてください。

…

答えは、以下の通りです。

\displaystyle \sum_{l = 0}^{g} \sum_{k \in S_{m}} x_{i(j+l)k} \le 1 \\ \forall i \in D, \forall m \in C, \forall j \in P'

ただし、空けたい間隔 g = 3とし、 P' = \lbrace 1, ..., p - g \rbraceとします。

可視化の図は以下の通りです。

制約04：キャスト視点での楽曲披露間隔

各キャストについて「そのキャストがオリジナルメンバーに含まれている楽曲」を対象に合計を取る、という点は制約03と似ていますが、 j方向については全ての和ではなく、「開けたい間隔+1」の範囲の和となっています。具体的には、今回は3曲以上空けたいので、1～4曲目の和、ということになります（作図の都合上、図は「2曲以上空けたい」の場合となっていますがご了承ください）。

一見よくわからないかもしれませんが、少し考えてみましょう。自身が担当する楽曲について、1～4曲目の合計が1以下という制約を掛けることは、1～4曲目での出番を1回以下に抑えるということです。この「合計1回以下」という制約を、2～5曲目、3～6曲目、…24～27曲目の全てで設定すれば、1日を通して、どの出演箇所に着目しても出番と出番の間隔が3曲以上空くことが保証されます。

この制約を、全ての日付、全てのキャストさんについて設定すれば、全員の負担が抑えられたセットリストになります。

では、制約01～04を課して、目的関数の値を最大化させるセットリストを作ってみましょう。

結果は以下の通りとなります。

（元画像リンク）

制約01～04を課したセットリスト作成結果（キャスト情報なし）

制約01～04を課したセットリスト作成結果

期待通り、全キャストさんについて、日ごとに見ると出番と出番の間隔が3曲以上空いています。キャストさんの負担という観点では、結構良いセットリストになっているのではないでしょうか。ちなみに、目的関数の値は539ポイントです（確認はこちら）。

10-5. 「制約05：指定した2曲について披露される日付を一致させる」

さて、前節の結果を見ると、MTS Final楽曲4曲全てが1日目のセットリストに入ってきていますね。セットリストに入ってくること自体は、披露期待ポイントの観点からみると妥当です。ただ、条件によっては、4曲のうち1曲だけが披露がなかったり、1曲だけ2日目に披露されるようなセットリストが出力される可能性はあります。たまたま前節はそうなっていませんが、MTS Finalの楽曲はひとまとまりという印象が強い（主観です）ので、明示的に「披露されるのであれば同じ日に披露される」という制約を掛けておきたいところです。

「特定の楽曲2曲 k_{1}, k_{2}が披露されるか否かを各日付で一致させる」という制約条件は、以下のように表せます。

\displaystyle \sum_{j \in P} x_{ijk_{1}} = \sum_{j \in P} x_{ijk_{2}} \\ \forall i \in D

今までの制約条件と比べると簡単ですね。一応可視化の図も載せておきましょう。

制約05：同日披露

図は、楽曲識別子 1と s-1について、1日目で披露されるか否かを一致させる（両方披露するか、両方披露しないか）制約条件を設定するために使用する変数の範囲を示しています。

3曲以上の複数曲について一致させたい場合は、1曲目と2曲目、2曲目と3曲目、…の全ての組合せに対して制約を掛ければ期待する結果が得られます。

では、制約01～05を課して、目的関数の値を最大化させるセットリストを作ってみましょう。制約05の対象は、

  • MTSチーム曲4曲
    • 『ダイヤモンド・クラリティ』、『Shamrock Vivace』、『空色♡ Birthday Card』、『ESPADA』
  • MTS Final曲4曲
    • 『サウンド・オブ・ビギニング』、『Supersonic Booster!』、『オレンジ・エピソード』、『Like twinkling STARS』

の2グループで、それぞれのグループに対して「同じ日に全曲披露する、もしくは1曲も披露しない」という制約を掛けます。

結果は以下の通りとなります。

（元画像リンク）

制約01～05を課したセットリスト作成結果（キャスト情報なし）

制約01～05を課したセットリスト作成結果

前節の時点でも偶然満たされてはいましたが、今回も期待通りに満たされていますね。目的関数の値は564ポイントです（確認はこちら）。

10-6. 「制約06：指定した2曲について披露順を指定する」

前節まででまあまあ良いセットリストになってきた気がしますが、まだ少し気になる点もあります。それは、特定の楽曲同士の披露順の前後関係です。

前節では偶然大丈夫でしたが、前々節の結果を見ると、Day2の24曲目がミリアニTeam6thの『Unknown Boxの開き方』、26曲目がTeam3rdの『オレンジノキオク』となっています。ちょっと気にならないでしょうか。

Act-3では、間に他の楽曲を挟みつつ、1日の中で楽曲披露順が1th→2nd→4th→5th→7th→8thのように、Teamの順番が守られていました。まあAct-3はアニメがテーマの公演であり、Act-4はそうではないのでそこまで気にしなくても良いかもしれませんが、今回もこれを踏襲するため、「特定の楽曲2曲 k_{1}, k_{2}について、どちらも同日に披露される場合は披露順の前後関係を指定する」という制約を設定してみましょう。

さて、この制約は今までと比べると少しだけ難しくなります。なぜなら、今までの制約で考えてきたような「決定変数そのものの足し算」だけでは「曲順」が表現できないからです。どうすればよいでしょうか。

結論としては、以下のような制約式となります。

\displaystyle \sum_{j \in P} jx_{ijk_{1}} \le \sum_{j \in P} jx_{ijk_{2}} + p(1 - \sum_{j \in P} x_{ijk_{2}}) \\ \forall i \in D

可視化の図は以下の通りとなります。

制約01：特定の2曲の披露順指定

ちょっと難しいですね。ある日付に対して楽曲 k_{1}, k_{2}が披露されるか否かで場合分けして説明します。

  • 楽曲 k_{1}, k_{2}がともに披露されない場合

制約式の左辺は0、右辺第1項も0、右辺第2項は pとなります。 pは「1日あたりの披露曲数」なので正の整数です。よって、この制約式は常に成立します。

  • 楽曲 k_{1}のみが披露される場合

制約式の左辺は x_{ijk_{1}}=1となる時の j、つまり k_{1}の披露曲順なので1以上 p以下の値となります。そして、右辺第1項は0、右辺第2項は pとなります。よって、この制約式は常に成立します。

  • 楽曲 k_{2}のみが披露される場合

制約式の左辺は0、右辺第1項は x_{ijk_{2}}=1となる時の j、つまり k_{2}の披露曲順なので1以上 p以下の値となります。そして、右辺第2項は0となります。よって、この制約式は常に成立します。

  • 楽曲 k_{1}, k_{2}がともに披露される場合

制約式の左辺は k_{1}の披露曲順、右辺第1項は k_{2}の披露曲順、右辺第2項は0となります。よって、この制約式を成立させるためには、 k_{1}の披露曲順を k_{2}の披露曲順より小さく（＝早く）する必要があります。

以上により、上記の制約式が今回の「指定した2曲について披露順を指定したい」という希望を叶えるために適切な制約条件であることが確認できました。

3曲以上の複数曲、例えば7曲について披露順を指定させたい場合は、楽曲1→楽曲2、楽曲1→楽曲3、…、楽曲1→楽曲7、楽曲2→楽曲3、…、楽曲6→楽曲7、というように、 {}_{7} \mathrm{C}_{2}=21通りの組合せに対して制約を掛ければ期待する結果が得られます。

ちょっと独り言ですが、この制約式はなかなかテクニカルで面白いですよね。

まず、ある日・ある楽曲の決定変数 x_{ijk}全てに対して jとの積の和を取ることで（ x_{ijk}が1となるような jはそのうち1つだけなので）その楽曲の披露曲順を取り出すことができる、というのは勉強になりました（『整数計画法による定式化入門』という資料を参考にしました）。

また、特定の条件、今回は「 k_{1}, k_{2}がともに披露される場合」にのみ制約を掛けたい場合に、大きな整数値（今回は p）を制約式に利用する方法も、「Big-M法」と呼ばれるテクニックの一つです（『定式化技法集』というサイトの該当ページを参考にしました）。私も教科書では読んだことがあったのですが、実問題の定式化で使用したのは初めてです。こちらも勉強になりました。

式の見た目は複雑ですが、 jも pも定数なので、制約式の線形性も保たれています。

では、制約01～06を課して、目的関数の値を最大化させるセットリストを作ってみましょう。制約06の対象は、

  • MTSチーム曲4曲
    • 『ダイヤモンド・クラリティ』、『Shamrock Vivace』、『空色♡ Birthday Card』、『ESPADA』
  • MTS Final曲4曲
    • 『サウンド・オブ・ビギニング』、『Supersonic Booster!』、『オレンジ・エピソード』、『Like twinkling STARS』
  • ミリアニチーム曲7曲
    • 『Star Impression』、『海風とカスタネット』、『オレンジノキオク』、『catch my feeling』、『バトンタッチ』、『Unknown Boxの開き方』、『トワラー』、『REFRAIN REL@TION』

の3グループで、それぞれのグループ内に対して「同じ日に披露する場合は並びの通りに披露順を守る」という制約を掛けます。

結果は以下の通りとなります。

（元画像リンク）

制約01～06を課したセットリスト作成結果（キャスト情報なし）

制約01～06を課したセットリスト作成結果

前節の時点でも偶然満たされてはいましたが、今回も期待通りに満たされていますね。目的関数の値は560ポイントです（確認はこちら）。

10-7. 「制約07：指定した2曲について披露順を連続とする」

さて、出来上がるセットリストも（個人的には）かなり良くなってきたように思いますが、前節の結果で気になることはあるでしょうか。

ミリアニ曲は、2日目で14曲目『オレンジノキオク』(3rd)→15曲目『catch my feeling』(4th)→17曲目『バトンタッチ』(5th)→24曲目『Unknown Boxの開き方』(6th)となっており、いい感じだと思います。

ただ、1日目でMTS Final曲4曲は、1日目で12曲目『サウンド・オブ・ビギニング』、14曲目『Supersonic Booster!』、17曲目『オレンジ・エピソード』、22曲目『Like twinkling STARS』となっているのですが、順序は守られつつも披露順が離れているのはなんか変な感じがします。制約06で順序のみを指定したばかりで身もふたもないですが、MTS Final曲についてはさらに踏み込み、連続での披露となるようにしましょう。

この希望の実現のためには、「特定の楽曲2曲 k_{1}, k_{2}について、 k_{1}が披露される場合は必ず次に k_{2}が披露される」という制約を設定すればよいですね。

今回の制約式は簡単です。以下の通りとなります。

\displaystyle x_{ijk_{1}} = x_{i(j+1)k_{2}} \\ \forall i \in D, \forall j \in P''

ただし、 P'' = \lbrace 1, ..., p - 1 \rbraceとします。

可視化の図は以下の通りとなります。

制約07：指定の2曲を連続披露

図では、「楽曲 s-2が1曲目に披露される場合必ず楽曲 2が2曲目に披露される、かつ楽曲 s-2が1曲目に披露されない場合必ず楽曲 2も2曲目に披露されない」という制約を表しています。これを、2, 3曲目、3, 4曲目…、26, 27曲目すべてに設定することで、「2つの楽曲は必ず連続でしか披露されない」を実現することができます。

3曲以上の複数曲を連続させたい場合は、1曲目と2曲目、2曲目と3曲目、…の全ての組合せに対して制約を掛ければ期待する結果が得られます。

では、制約01～07を課して、目的関数の値を最大化させるセットリストを作ってみましょう。制約07の対象は、

  • MTSチーム曲4曲
    • 『ダイヤモンド・クラリティ』、『Shamrock Vivace』、『空色♡ Birthday Card』、『ESPADA』
  • MTS Final曲4曲
    • 『サウンド・オブ・ビギニング』、『Supersonic Booster!』、『オレンジ・エピソード』、『Like twinkling STARS』

の2グループで、それぞれのグループに対して「4曲は連続で披露する、もしくは1曲も披露しない」という制約を掛けます。

結果は以下の通りとなります。

（元画像リンク）

制約01～07を課したセットリスト作成結果（キャスト情報なし）

制約01～07を課したセットリスト作成結果

期待通り、1日目で15曲目『サウンド・オブ・ビギニング』、16曲目『Supersonic Booster!』、17曲目『オレンジ・エピソード』、18曲目『Like twinkling STARS』と、4曲連続の披露となっていますね。

目的関数の値は558ポイントです（確認はこちら）。

以上で、本記事で用意した制約は全てとなります。お疲れさまでした。（ここまで読んでくれる方がいるのか不安ですが…）

11. 最終結果とまとめ

さて、前節では実験のため、1回のセットリスト作成の制限時間を10分に制限していました。しかし、当然10分では選択肢 2^{9504}個のセットリスト全ての目的関数を評価することはできません。というか何年かかるんでしょうね。おそらくSCIPは求解にランダム要素は入っておらず、理論上無限の時間があれば最適解を見つけるようにできているはずですが、実用上は時間を制限してその時間内に見つかった最も目的関数の値が良い解を出力させるように使うこととなります。

つまり、同じ定数・変数設定、制約条件、目的関数であれば、実行時間が長ければ長いほど目的関数の値が大きい＝『良い』セットリストが得られるはずです。

というわけで、前節の最後の設定、つまり制約01～07を課して、10分ではなく90分で実行してみましょう。

結果は以下の通りとなります。

（元画像リンク）

制約01～07を課したセットリスト作成結果（90分）（キャスト情報なし）

制約01～07を課したセットリスト作成結果（90分）

変わらずすべての制約が守られていますが、セットリストが変わりましたね。こちらのセットリストの目的関数の値は568ポイントです（確認はこちら）。やはり時間をかければかけるほど『良い』セットリストが得られるようです。

本記事では、一旦このセットリストを『理想』のセットリストとして終えようと思います。

…

さて、この最終的に得られたセットリスト、いかがでしょうか。まあ私が設定した制約は全て守られていて、かつ私が設定した目的関数の値が大きい解が出力されているのだから、少なくとも私にとっては『理想』のセットリストとなっているはず…なのですが、やはりまだ気になる部分はあります。いくつか思いつくままに列挙すると、

  • ソロ曲やるキャストさんとやらないキャストさんがいるけど、いいの？
    • Act-3でもそうだったから…
  • Act-2でもやったけど、Act-4でもJus-2-MintとD/Zealやるの？
    • な、なくはないかな…
  • MTV曲多過ぎない？
    • 未披露曲の披露期待ポイントを高くしてるから…
  • （全体曲を除く）ラストがソロ曲で良いのか？
    • なくはないかな…
  • 『Sweet Sweet Soul』、つい最近東京ドームで観た。
    • 披露期待ポイントの計算対象が直近の披露じゃない場合があるから…
  • そもそもこんなに一生懸命未披露曲を消化する必要ある？
    • 披露期待ポイントと目的関数の設計には改善の余地があると思います…
  • ライブの後半に披露期待ポイントが高い曲が集中するのって本当にうれしい？
    • うーん…
  • キャストさん視点で最低3曲空けるのはよいけど、例えばDay2の愛美さんは6曲目で出番が終わってたり、種田さんの最初の出番が18曲目だったり、もうちょっとバランス考えられない？
    • それはそう…
  • なんか、大人数曲を入れて各キャストさんの披露曲数を底上げした上で、披露期待ポイントが高い曲を詰め込んで、曲数足りない人にソロを割り振って調整してるように見えない？それが『理想』でいいの？
    • 見える。多分よくない（直球）。

という感じで、まだまだ『理想』とは程遠いです。

ただ、これは世の中の実課題を最適化問題として解こうとしたときにはよくあることで、上記の「気になる点」の中には「気になる点があるセットリスト」を見せられて初めて気づく点も多々ありました。これは、「実装→結果の確認→制約条件や目的関数が本当に適切なのかのフィードバック」のサイクルをたくさん回すしか解決方法はないし、それが最適化の面白いところでもあります。

この記事も、ある程度まで出来上がったセットリストを公開することで、「こういう条件はあった方が良いんじゃないか」「この制約はいらない」「メドレーありにして入れて曲数増やせ」「そもそもオリジナルメンバーで縛るな」などの議論が生まれることを期待して作成したものです。

なので、公開するNotebookで各種パラメータを変えて好きに使ってみてほしいですし、少しプログラミングができる方ならもっと根本から披露期待ポイントや目的関数の計算ルールを変更することもできると思います。あなたの『理想』のセットリストもぜひ見せてください。

12. おまけ

最後に私欲盛り盛りの、具体的には私が聴きたい曲を披露必須指定にしたセットリストを掲載しておきます。

曲名の最後に<req.>が付いている15曲が必須指定となっています。制約式の説明は割愛しますが、指定の曲について制約02の不等号を等号に変えればよいだけです。Notebookでは制約99として実装しています。使ってみてください。

これが本当の私の『理想』のセットリストです。180分も時間をかけました。なお目的関数の値は511。さすがに前節の最終結果の方が多くの人に支持を得られるセットリストでしょう。でも良いんです。これは『私の理想』ですから。

（元画像リンク）

私の『理想』のセットリスト（キャスト情報なし）

私の『理想』のセットリスト

最後までお読みいただきありがとうございました。

謝辞

本文中でも言及しましたが、music765plus様が運営されている『アイドルマスター楽曲メモ』は、データの使用だけでなくちょっとした調べ物の際もとてもお世話になりました。ありがとうございました。

また、今回も公開前に記事を読んでコメントをくれた友人に感謝します。

2024/02/05追記：

この記事を呟いたツイー…ポストを、数理最適化の梅谷先生にリポストしていただいたようです。ありがとうございます。おそらくX上で「数理最適化」などのワードを自動で拾うようにされているだけなのだとは思いますが、この記事が読まれている可能性もわずかにあるので動揺しました。私は梅谷先生が書かれた『しっかり学ぶ数理最適化』という本で数理最適化を勉強しており、この記事も最適化についての説明や文字の置き方など多大な影響を受けています。

www.kspub.co.jp

ミリオンが好きなみなさんも、この本で数理最適化を勉強して私と一緒にミリオン×数理最適化を流行らせていきましょう（？？？）。